Integrated Scheduling Algorithm With Batch Processing Machines With the Lot-size Being Two
-
摘要: 提出求解存在加工批量为2的批处理设备的复杂单产品综合调度算法.该算法根据复杂产品具有的树状工艺结构的特点,先采用已有的优先级、短用时和长路径策略调度工序;当工序属于批处理设备时,再采用长路径、临界时间等待和先行工序短用时策略.理论分析和实例表明,提出的算法不仅能够解决存在加工批量为2的批处理设备的复杂单产品综合调度优化问题,而且复杂度不超过二次多项式.Abstract: A new algorithm is proposed to solve the integrated scheduling problem of single complex product with batch processing machines.The maximum lot-size that the batch processing machines can process is two.According to the feature of the structure of the processing tree that is provided with complex products,the algorithm first adopts the priority strategy,short-time strategy and long-path strategy to schedule operations.When the operations belong to the batching machine,the algorithm then adopts the long-path strategy,critical-time waiting strategy,and short-time of previous operation strategy to schedule operations.Theoretical analysis and examples show that the algorithm can solve the integrated scheduling problem of single complex products with batch processing machines on which the lot-size of operations being processed is two.In addition,the complexity is not more than quadratic polynomial.
-
-
[1] LEE C Y,UZSOY R,MARTIN Vega L A.Efficient algorithms for scheduling semiconductor burn-in operations[J].Operations Research,1992,40(4):764-775.
[2] BRUCKER P,GLADKY A,HOOGEVEEN H,et al.Scheduling a batching machine[J].Journal of Scheduling,1998,1(1):31-54.
[3] HOCHBAUM D S,LANDY D.Scheduling semiconductor burn-in operation to minimize total flowtime[J].OperationsResearch,1997,45(6):874-885.
[4] 牛海军,孙树栋.JIT方式下的单机分批调度问题研究[J].西安电子科技大学学报,2002,29(4):444-460.NIU Hai-jun,SUN Shu-dong.Research on the batch scheduling on the single machine using the JIT technique[J].Journal ofXidian University,2002,29(4):444-460.(in Chinese) [5] UNAL A T,KIRAN A S.Batch Scheduling.IIE Transaction,1992,20(4):73-83.
[6] 谢志强.工件间有约束的复杂产品工序调度研究[D].哈尔滨:哈尔滨理工大学机械工程学院,2009.XIE Zhi-Qiang.Study on operation scheduling of complex product with constraint among jobs[D].Harbin:School ofMechanical Engineering,Harbin University of Science and Technology,2009.(in Chinese) [7] XIE Zhi-qiang,YE Guang-jie,ZHANG Da-li,et al.New nonstandard job shop scheduling algorithm[J].Chinese Journal ofMechanical Engineering,2008,21(4):97-100.
[8] 谢志强,莫涛,谭光宇.非紧密衔接工序动态车间调度算法[J].机械工程学院,2008,44(1):155-160.XIE Zhi-qiang,MO Tao,TAN Guang-yu.Dynamic job-shop scheduling algorithm of non-closejoining operations[J].ChineseJournal of Mechanical Engineering,2008,44(1):155-160.(in Chinese) [9] 谢志强,李志敏,郝淑珍,等.工序间存在零等待约束的复杂产品调度研究[J].自动化学报,2009,35(7):983-989.XIE Zhi-qiang,LI Zhi-min,HAO Shu-zhen,et al.Study on complex product scheduling problem with no-wait constraintbetween operations[J].Acta Automatica Sinica,2009,35(7):983-989.(in Chinese) [10] XIE Zhi-qiang,HAO Shu-zhen,YE Guang-jie,et al.A new algorithm for complex product flexible scheduling with constraintbetween jobs[J].Computers&Industrial Engineering,2009,57(3):766-772.
[11] XIE Zhi-qiang,LIU Yong,HAO Shu-zhen,et al.Study on confirming increasable bottleneck device in complex productdynamic scheduling[J].ICCMS,2009:213-217.
[12] 谢志强,郑翘,刘胜辉.关键设备工序紧凑的动态调度算法[J].哈尔滨理工大学学报,2003,8(2):50-53.XIE Zhi-qiang,ZHENG Qiao,LIU Sheng-hui.A dynamic scheduling algorithm based on key equipment’s compactprocedures[J].Journal of Harbin University of Science and Technology,2003,8(2):50-53.(in Chinese) [13] 谢志强,杨静,杨光,等.可动态生成具有优先级工序集的动态Job-Shop调度算法[J].计算机学报,2008,3(31):502-508.XIE Zhi-qiang,YANG Jing,YANG Guang,et al.Dynamic job-shop scheduling algorithm with dynamic set of operationhaving priority[J].Journal of Computers,2008,3(31):502-508.(in Chinese) [14] 师瑞峰,周泓,上官春霞.一种求解job shop问题的混合多目标遗传算法[J].计算机工程与应用,2005(30):1-5.SHI Rui-feng,ZHOU Hong,SHANG-GUAN Chun-xia.A hybrid multi-objective genetic algorithm and its applications to jobshop problems[J].Computer Engineering and Applications,2005(30):1-5.(in Chinese) [15] 曾立平,黄文奇.求解Job-Shop调度问题的一种新的邻域搜索算法[J].计算机研究与发展,2005(4):48-53.ZENG Li-ping,HUANG Wen-qi.A new local search algorithm for the job shop scheduling problem[J].Journal of ComputerResearch and Development,2005(4):48-53.(in Chinese) [16] DROBOUCHEVITCH I G,STRUSEVICH V A.Heuristics for short route job shop scheduling problems[J].MathematicalMethods of Operations Research(ZOR),1998(12):359-375.
计量
- 文章访问数: 14
- HTML全文浏览量: 0
- PDF下载量: 7
下载:
