具有DeJong学习效应的两台机器流水作业排序问题  

Two Machine Flowshop Scheduling with DeJong’s Learning Effect

作　　者：柏孟卓[1] 温学兵[2] BAI Mengzhuo;WEN Xuebing(School of Mathematics and Systems Science,Shenyang Normal University;Department of Editorial Journal,Shenyang Normal University,Shenyang 110035,China)

机构地区：[1]沈阳师范大学数学与系统科学学院 [2]沈阳师范大学学报编辑部,沈阳110035

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

基　　金：国家自然科学基金(No.11572146);辽宁省教育厅科学研究项目(No.LJC202002)。

摘　　要：【目的】讨论具有DeJong学习效应的两台机器流水作业排序问题。【方法】目标函数是极小化总完工时间。【结果】首先对一般情况,证明了SPT算法的界为2。然后考虑了两种特殊情况:(1)两个工序的加工时间和与第2台机器工序实际加工时间同序;(2)第2台机器工序的加工时间相同。对于第1种特殊情况,给出了SPT算法一个改进的界。对于第2种特殊情况,给出了最优算法。【结论】推广了已有文献的结果。[Purposes]A two-machine flowshop scheduling with DeJong’s learning effect is considered.[Methods]The objective is to find a sequence that minimizes the total completion time.[Findings]For general model,it is proved that the worst-case bound of SPT algorithm is 2.Furthermore,two special cases are analyzed,one is that the total processing time of two operations and the real processing time of the operations on second machine are agreeable,the other is that the processing times on the second machine are equal.An improved worst-case bound for SPT algorithm is presented for the first special case and a polynomial algorithm for the second special case,respectively.[Conclusions]The results of the existing literature are generalized.

关 键 词：排序 DeJong学习效应 流水作业 SPT规则 

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