成果/Result
- 三机流水作业问题若干特殊情形的NP困难性(英文)被引量：3收藏
- 作者：刘朝晖 俞文魮
- 机构：华东理工大学数学系与应用数学研究所
- 来源：《运筹学学报》 2000
- 关键词：时间表 加工时间 NP困难性 三机流水作业问题
- 摘要：本文研究以加工总长为目标函数的三台机器流水作业问题的特殊情形的计算复杂性，证明了下列情形为ＮＰ困难的：所有工件在第二台机器上有相同的加工时间；所有工件在第一和第三台机器上有相同的加工时间；每个工件至少有一个零工序；每个工...
- 下载全文在线阅读
- 链式先后关系下的单机分批排序问题被引量：3收藏
- 作者：刘朝晖 俞文
- 机构：华东理工大学数学系
- 来源：《运筹学学报》 1999
- 关键词：排序 链式先后关系 完工时间和 单机分批排序
- 摘要：在本文，我们证明链式先后关系下的单机分批排序问题是强NP困难的，解决了Albers和Brucker（1993）提出的待解决问题．关于此问题，Albers和Brucker（1993）也曾试图给出NP困难性证明，我们阐明了其...
- 下载全文在线阅读
- 树上的最小-最大k旅行商问题若干变种的精确算法被引量：3收藏
- 作者：高哲成 余炜 刘朝晖
- 机构：华东理工大学数学学院
- 来源：《华东理工大学学报（自然科学版）》 2021
- 关键词：拟多项式 最小-最大 旅行商问题 路覆盖 中国邮递员问题
- 摘要：树上的最小-最大k旅行商问题是多旅行商问题在树形结构中的推广问题。研究了树上的最小-最大k旅行商问题、树上的多仓库最小-最大k旅行商问题以及树上的最小-最大k路覆盖问题,提出了基于自下而上的动态规划的拟多项式时间精确算法...
- 下载全文在线阅读
- 带批运输的两台同型机排序问题的改进算法被引量：2收藏
- 作者：汪磊扬 刘朝晖
- 机构：华东理工大学数学系
- 来源：《运筹学学报》 2013
- 关键词：排序 批运输 近似算法
- 摘要：研究带批运输的两台同型机排序问题.在该问题中,工件在两台同型机上加工,完工的工件由一辆容量为z的车运输到客户.这里假设工件有不同的物理大小,目标是求一个时间表使得所有工件送达客户且车回到机器所在位置的时间最小,给出了一个...
- 下载全文在线阅读
- 成组加工的单机延误工件个数问题被引量：2收藏
- 作者：刘朝晖 俞文
- 机构：华东理工大学应用数学研究所
- 来源：《华东理工大学学报（自然科学版）》 1998
- 关键词：单机时间表 成组技术 延误工件个数 NP困难性
- 摘要：证明了成组加工的单机延误工件个数问题是强ＮＰ困难的，即使限定所有工件有单位加工时间且所有组间调整时间为零也是如此。对同组工件有相同工期的限制情形给出了一个多项式算法。关于同组工件既有相同工期，又有相同加工时间的进一步限制...
- 下载全文在线阅读
- 关于工件组的两机自由作业时间表问题被引量：2收藏
- 作者：刘朝晖 俞文鮆
- 机构：华东理工大学数学系
- 来源：《华东理工大学学报（自然科学版）》 2000
- 关键词：时间表 工件组 自由作业 加工全长 算法 NP困难
- 摘要：讨论关于工件组的两机自由作业时间表的加工全长问题。无论是对于成组加工情形还是分组情形 ,该问题都可以被证明是 NP困难的。对于成组加工的情形 ,设计了一个性能比为 5/4的近似算法 ,该算法生成的时间表作为分组情形的解 ...
- 下载全文在线阅读
- 基于Delaunay三角剖分处理二维欧式空间MTSP的近似算法被引量：2收藏
- 作者：寿涛 刘朝晖
- 机构：华东理工大学数学系
- 来源：《华东理工大学学报（自然科学版）》 2017
- 关键词：MTSP Delaunay三角剖分 近似算法
- 摘要：考虑了在二维欧式平面内的多旅行商问题,通过Delaunay三角剖分的方法,将问题转化为求解多个旅行商问题。树分解算法的核心是Delaunay边的空圆性质并且可以证明该算法的近似比为2。最后,通过数值模拟验证了算法的有效性...
- 下载全文在线阅读
- 安装、加工和拆卸时间分离的两台机器混合作业问题(英文)被引量：2收藏
- 作者：刘朝晖 李毅
- 机构：华东理工大学数学系
- 来源：《运筹学学报》 2009
- 关键词：运筹学 排序 混合作业 算法
- 摘要：混合作业是经典的自由作业和异序作业的一种综合,其中一些工件可以按任意的机器顺序进行处理,而另一些工件必须遵守预先指定的机器顺序.本文研究安装、加工和拆卸时间分离的两台机器混合作业排序问题,该问题已经被知道是强NP困难的,...
- 下载全文在线阅读
- 线形网络上单台车辆分群调度问题被引量：2收藏
- 作者：包晓光 刘朝晖 余炜
- 机构：上海海洋大学信息学院;华东理工大学理学院
- 来源：《运筹与管理》 2017
- 关键词：运筹学 近似算法 线形网络 车辆路线 车辆调度
- 摘要：本文研究线形网络上单台车辆分群调度问题:若干客户分布在一条直线上,它们被划分成若干个连续子集,其中每个子集称为一个群;每个客户有一个释放时间和一个服务时间;一台机器服务所有客户,且要求每个群内的客户连续服务;目标为极小化...
- 下载全文在线阅读
- 极小化延误工件个数的单机分组排序问题被引量：1收藏
- 作者：刘朝晖
- 机构：华东理工大学应用数学研究所
- 来源：《华东理工大学学报（自然科学版）》 1997
- 关键词：分组排序 单台机器 延误工件个数 复杂性 排序
- 摘要：研究了以极小化延误工件个数为目标的单机分组排序问题，证明了该问题是强ＮＰ困难的，甚至限定所有工件有单位加工时间和一致的组间调整时间也是如此。
- 下载全文在线阅读
- 无容量限制的批处理机时间表问题被引量：1收藏
- 作者：刘朝晖 俞文■
- 机构：华东理工大学数学系
- 来源：《华东理工大学学报（自然科学版）》 2001
- 关键词：排序 批处理机 多项式时间算法 NP困难性 到达时间 工期 加工时间 时间表问题
- 摘要：研究无容量限制的批处理机时间表问题 ,在工件有到达时间和工期约束下 ,证明了当工件的到达时间和工期 ,或到达时间和加工时间一致单调时 ,该问题是多项式时间可解的 ;当加工时间和工期一致单调时 ,该问题是
- 下载全文在线阅读
- 总延误问题顺时安排法的性能比被引量：0收藏
- 作者：俞文煎 刘朝晖
- 机构：华东理工大学应用数学研究所
- 来源：《运筹学学报》 1997
- 关键词：时间表 总延误问题 近似算法 顺时安排法
- 摘要：给定一组工件的加工时间与工期，要求确定这些工件在一台机器上的加工排列，使相应的总延误达到最小，这就是总延误问题，该问题在近年已被证明是ＮＰ困难的。由Ｗｉｌｋｅｒｓｏｎ和Ｉｒｗｉｎ（１９７１），林诒勋（１９８３）等所研究的...
- 下载全文在线阅读
- 总延误问题顺时安排法的性能比被引量：0收藏
- 作者：刘朝晖
- 机构：华东理工大学应用数学研究所
- 来源：《运筹学学报》 1997
- 关键词：时间表 总延误问题 近似算法 顺时安排法
- 摘要：给定一组工件的加工时间与工期，要求确定这些工件在一台机器上的加工排列，使相应的总延误达到最小，这就是总延误问题，该问题在近年已被证明是ＮＰ困难的。由Ｗｉｌｋｅｒｓｏｎ和Ｉｒｗｉｎ（１９７１），林诒勋（１９８３）等所研究的...
- 下载全文在线阅读
- 两台机器若干作业问题的双向排序法被引量：0收藏
- 作者：俞文鮆 刘朝晖
- 机构：华东理工大学数学系
- 来源：《华东理工大学学报（自然科学版）》 1999
- 关键词：自由作业 单件作业 混合作业 双向排序法 排序
- 摘要：研究两台机器若干作业的加工全长问题，首次引入双向排序法，对自由作业、单件作业、混合作业，以及三阶段工件的两机自由作业问题分别给出了新的算法，明显地简化了现有的处理方式。
- 下载全文在线阅读
- 有服务等级约束的同类机在线排序问题的可分算法被引量：0收藏
- 作者：周鹏程 刘朝晖
- 机构：华东理工大学理学院
- 来源：《华东理工大学学报（自然科学版）》 2018
- 关键词：排序 同类机 服务等级 竞争比
- 摘要：研究了一类有四个服务等级的可分排序问题,在一定条件下改进了下界,并且提出了一种最优算法。在该问题中,工件和机器都带有各自的服务等级约束,当且仅当工件的服务等级比机器的服务等级高或者相同时,该机器才被允许对该工件进行加工,...
- 下载全文在线阅读
- 代价依赖于加工位置的单机排序情形被引量：0收藏
- 作者：刘珊珊 刘朝晖
- 机构：华东理工大学理学院
- 来源：《华东理工大学学报（自然科学版）》 2015
- 关键词：排序情形 指派博弈 学习效应 支付方案
- 摘要：对于客户代价依赖于加工位置而非整个工序的单机排序情形,每个客户在不同位置上的代价可以由一个代价矩阵来描述。给定一个排序情形,一个可行解包括最终采用的工序和相应的客户代价支付方案。本文研究最优工序下的客户代价支付方案,给出...
- 下载全文在线阅读
- 关于单台批处理机在线排序的一些研究被引量：0收藏
- 作者：刘朝晖 王桢
- 机构：华东理工大学数学系
- 来源：《运筹与管理》 2009
- 关键词：运筹学 排序 批处理机 在线算法
- 摘要：一台批处理机一次可以同时加工多个工件（称为一批），每批工件有相同的开工和完工时间，加工时间等于其中最长工件的加工时间。本文研究单台批处理机上的在线排序，其中每个工件有事先未知的到达时间，加工时间在其到达时才知道，目标是极...
- 下载全文在线阅读
