单机单转包商调度与外包联合优化问题的改进启发式算法

发布时间：2019-02-27 20:41

【摘要】：针对以总完工时间与总外包费用加权和为优化目标、总外包费用不超过给定上限的单机单转包商调度与外包联合优化问题,设计出一种改进的剔除型启发式算法。该算法通过运用动态规划技术求解新的辅助问题来获取初始外包工件集,并引入判定条件提前从初始外包工件集中剔除特定工件。为满足对总外包费用的上限约束,还利用新型的启发式筛选次序族逐一确定从当前外包工件集中剔除的工件。在仿真实验中,通过生成大量的测试算例,对比分析了改进算法与另2种已报道算法在求解质量、计算时间上的表现情况。实验结果表明所提出的改进算法在解的整体质量上具备显著的比较优势,并且能在5.6秒内完成对工件总数为1500的测试算例的求解。
[Abstract]:Based on the weighted sum of total completion time and total outsourcing cost, an improved elimination heuristic algorithm is designed to solve the joint optimization problem of single machine and single subcontractor scheduling and outsourcing with the total outsourcing cost less than the given upper limit. The algorithm uses dynamic programming technology to solve new auxiliary problems to obtain the initial outsourced workpiece set, and introduces the decision condition to remove the specific workpiece from the initial outsourced workpiece set in advance. In order to meet the upper bound of the total outsourced cost, a new heuristic screening suborder family is used to determine the jobs that are removed from the current outsourced job set one by one. In the simulation experiment, by generating a large number of test examples, the performance of the improved algorithm and the other two reported algorithms in solution quality and calculation time are compared and analyzed. The experimental results show that the proposed improved algorithm has significant comparative advantages in the overall quality of the solution and can be used to solve the test example with the total number of workpiece 1500 in 5.6 seconds.
【作者单位】： 济南大学商学院;
【基金】：国家自然科学基金青年项目(71501083) 教育部人文社科研究青年基金资助项目(14YJCZH098) 山东省优秀中青年科学家科研奖励基金资助项目(BS2015ZZ002) 济南大学科研基金资助项目(XKY1322)
【分类号】：TP301.6

【相似文献】

相关期刊论文 前10条

1 毛道晓;徐克林;张志英;侯丽清;;越库中心选址模型与启发式算法[J];中南大学学报(自然科学版);2013年02期

2 李克文,吴孟达,张雄明;约简的一种启发式算法[J];计算机工程与科学;2004年01期

3 宋万忠;;一种改进的多机场地面等待启发式算法[J];计算机应用;2007年S1期

4 周旭东;王丽爱;陈];;启发式算法求解最大团问题研究[J];计算机工程与设计;2007年18期

5 李亚志;朱夏;;基于插入-分段的无等待流水作业调度复合启发式算法[J];东南大学学报(自然科学版);2013年03期

6 唐立新;祁慧;杨自厚;王梦光;;基于P-中位模型的聚类分析的拉格朗日启发式算法[J];模式识别与人工智能;1997年01期

7 张潜,高立群,刘雪梅,胡祥培;定位-运输路线安排问题的两阶段启发式算法[J];控制与决策;2004年07期

8 黄志,黄文奇;作业车间调度问题的一种启发式算法[J];计算机工程与应用;2004年26期

9 袁俊斌;苏庆忠;;基于启发式算法的物流配送中心选址研究[J];价值工程;2009年11期

10 戴香粮;王映龙;;混合启发式算法在汽车调度中的应用[J];电子技术应用;2009年07期

相关会议论文 前5条

1 刘嘉敏;马广煜;黄有群;;基于组合的三维集装箱装入启发式算法的研究[A];全国第13届计算机辅助设计与图形学（CAD/CG）学术会议论文集[C];2004年

2 刘金朋;魏长江;;启发式算法求最短路径的一种高效率实现方法[A];2007北京地区高校研究生学术交流会通信与信息技术会议论文集（上册）[C];2008年

3 范敏;邹平;朱兴东;;一种启发式离散化算法及其Delphi实现[A];第二届中国智能计算大会论文集[C];2008年

4 冯德鸿;唐加福;郭琦;李辉;;订货批量问题改进的相关策略启发式算法与仿真分析[A];2007系统仿真技术及其应用学术会议论文集[C];2007年

5 李兵;吴孟达;;信息系统中一种基于属性相对重要度的启发式约简算法[A];中国系统工程学会模糊数学与模糊系统委员会第十一届年会论文选集[C];2002年

相关重要报纸文章 前1条

1 本报记者 刘华;金融危机为成都接包商带来重大机遇[N];成都日报;2008年

相关博士学位论文 前5条

1 赖向京;原子团簇结构预测的现实途径—高性能启发式算法[D];华中科技大学;2012年

2 黎展滔;具有成组约束的柔性流水车间作业计划制定的启发式算法[D];广东工业大学;2012年

3 董兴业;启发式算法及其在同顺序流水作业问题中的应用[D];北京交通大学;2008年

4 古继兴;KOD多播技术与Steiner树启发式算法[D];上海交通大学;2007年

5 任志磊;组合优化问题的特化与泛化算法设计[D];大连理工大学;2013年

相关硕士学位论文 前10条

1 周书橙;护士排班的启发式算法研究与排班管理系统的设计实现[D];北京交通大学;2016年

2 刘赛赛;基于增强学习的启发式和元启发式搜索的参数调优策略[D];电子科技大学;2016年

3 刘志宏;合同组批系统中优化算法的研究[D];东北大学;2013年

4 陈涛;基于大数据和混合启发式算法的公交调度方法[D];杭州电子科技大学;2016年

5 刘永凯;课表安排问题的启发式算法研究[D];厦门大学;2009年

6 陈雪瑛;基于启发式算法的库存路径优化问题研究[D];北京交通大学;2008年

7 陈敏;基于启发式算法的合同组批系统研究与设计[D];东北大学;2012年

8 于U，

本文编号：2431561