基于截断学习效应的流水作业排序问题研究  

Flow Shop Scheduling Problem with Truncated Learning Effects

作　　者：王雪茹 白雪莲 王吉波 殷娜 WANG Xueru BAI Xuelian WANG Jibo YIN Na(School of Science, Shenyang Aerospace University, Shenyang 110136, China)

机构地区：[1]沈阳航空航天大学理学院,沈阳110136

出　　处：《重庆师范大学学报（自然科学版）》2017年第5期12-17,共6页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金(No.71471120);沈阳航空航天大学基金项目(No.201608Y)

摘　　要：【目的】给出具有截断学习效应的加权总完工时间流水作业排序问题的最优解。【方法】建立具有截断学习效应的加权总完工时间流水作业排序问题的数学模型,给出优势性质、下界和上界,并采用分支定界算法求解该问题的最优解。【结果】数值模拟结果表明:启发式算法得到的解比较准确,最大误差为0.411 7,分支定界算法的效率比较高,处理100个工件所用的最大时间不超过460s。【结论】计算结果表明分支定界算法能够很快地给出该问题的最优排序。[Purposes]In order to give the optimal solution of the total weighted completion time flow shop scheduling problem with truncated learning effects.[Methods]A mathematical model of the total weighted completion time flow shop scheduling problem with truncated learning effects is established,the dominance property,lower bounds and a heuristic algorithm are proposed,thus the branch and bound algorithm can be used to obtain the optimal solution of the problem.[Findings]Numerical simulations show that the solutions of the heuristic algorithm are quite accurate and very fast;the efficiency of the branch and bound algorithm is very efficient,100 jobs of the max CPU time of the branch and bound algorithm is 460 s.[Conclusions]Computational experiments show that the optimal schedule can be obtained quickly by the branch and bound algorithm.

关 键 词：截断学习效应 流水作业 排序 分支定界算法 加权总完工时间 

分 类 号：O223[理学—运筹学与控制论] C934[理学—数学]