考虑多约束的MOJ调度问题

摘要/Abstract

摘要： 统筹考虑晶圆加工过程中的多品种、p-s-d（past-sequence-dependent）换模时间以及衰退效应等约束的特征，建立了单机MOJ(multiple orders per job)调度模型，并对调度模型采用改进型遗传蚁群算法进行求解。首先，对问题域进行描述，以系统总加权提前/拖期惩罚成本最小为优化目标，建立了数学规划模型。在此基础上，对决策变量进行分离，提出具有双层嵌套编码机制的改进型遗传蚁群调度算法。该算法将遗传算法融合到动态自适应蚁群算法的每一次迭代过程中，并为有效提高算法的收敛性能，引入ATCS(Apparent Tardiness Cost With Setups）修正准则。最后，设计仿真实验，结果表明，该算法是有效、可行的。

关键词: 多品种, p-s-d换模时间, 衰退效应, 调度, 改进型遗传蚁群算法

Abstract: With a comprehensive consideration of the characteristics of multiple product types, the past-sequence-dependent (p-s-d) setup times and the deterioration effects constraints in processes of wafer fabrication, a scheduling model of multiple orders per job(MOJ) in a single machine is developed and a modified genetic algorithm-ant colony optimization(MGA-ACO) algorithm is applied to solve the scheduling problem. Firstly, a scheduling problem domain is described. Mathematical programming models are also set up with an objective function of minimizing total weighted earliness-tardiness penalties of the system. On the basis of the descriptions, the decision-making variables are separated and a MGA-ACO algorithm adopting two-level encoding mechanism is put forward. Genetic algorithm is introduced into the process of dynamic and adaptive ant colony iterations. To guarantee the algorithm convergence performance, the modified rules of apparent tardiness cost with setups(ATCS) is developed. Finally, the simulation experiments are designed, and the results indicate that the developed algorithm is valid and feasible.

Key words: multiple product types, p-s-d setup times, deterioration effects, scheduling, MGA-ACO algorithm

王腾周炳海. 考虑多约束的MOJ调度问题[J]. .

参考文献

[1].Qu P,Mason S J． Using tabu search on the single machine multi-orders per job scheduling problem [C]//IIE Annual Conference and Exhibition 2004． Houston: Institute of Industrial Engineers,2004: 1831-1835．
[2].Sobeyko O,Monch L． Genetic algorithms to solve a single machine multiple orders per job scheduling problem [C]//2010 Winter Simulation Conference． Piscataway: IEEE,2010: 2493 – 2503．
[3].Jampani J,Mason S J． Column generation heuristics for multiple machine,multiple orders per job scheduling problems[J]． Annals of Operations Research,2008,159(1): 261-273．
[4]Mason S J, Chen J S.Scheduling multiple orders per job in a single machine to minimize total completion time[J].European Journal of Operational Research, 2010, 207(1):70-77
[5]Erramilli V, Mason S J.Multiple orders per job compatible batch scheduling[J].IEEE Transactions on Electronics Packaging Manufacturing, 2006, 29(4):285-296
[6]Erramilli V, Mason S J． Multiple orders per job batch scheduling with incompatible jobs[J]． Annals of Operations Research, 2008, 159(1): 245–260.
[7].Chen J S．Optimization models for the flow-shop scheduling problem with multiple orders per job[C]//2010 40th International Conference on Computers and Industrial Engineering．Piscataway: IEEE,2010: 1-6．
[8]Zhou B H, Zhai Z Q.Lifetime distribution model of port facilities with pitting corrosion of stochastic processes[C]//2010 International Conference on Frontiers of Manufacturing and Design Science. Chongqing: Applied Mechanics and Materials,2011:46-50.
[9]Shen L X, Wu Y B.Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects[J].Applied Mathematical Modelling, 2013, 37(7):5444-5451
[10]徐久强，邢佩龙，孔秋实，等.基于改进蚁群算法的双向物流路径优化[J].东北大学学报：自然科学版, 2012, 33(9):1240-1243
(Xu Jiu-qiang, Xing Pei-long, Kong Qiu-shi, et al.Logistics routing optimization based on improved ant colony algorithm[J].Journal of Northeastern University:Natural Science Practice, 2012, 33(9):1240-1243)
[11]Qu P, Mason S J.Metaheuristic scheduling of 300 mm jobs containing multiple orders[J].IEEE Transactions on Semiconductor Manufacturing, 2005, 18(4):633-643
[12]Pfund M, Fowler J W, Gadkari A et al.Scheduling jobs on parallel machines with setup times and ready times[J].Computers & Industrial Engineering, 2008, 54(4):764-782
[13]翟子青，周炳海.基于随机过程的镍基合金点蚀建模方法[J].金属学报, 2011, 47(9):1159-1166
(Zhai Zi-qing, Zhou Bing-hai.Stochastic process-based modeling method for pitting corrsion of Ni-based alloy[J].Acta Metallurgica Sinica, 2011, 47(9):1159-1166)

[1]	丁山，臧仕义，曹殿明，佘黎煌. 基于动态ID跳变的CAN总线安全调度算法[J]. 东北大学学报（自然科学版）, 2022, 43(3): 350-358.
[2]	杜子超，卢福强，王素欣，王雷震. 众包物流配送车辆调度模型及优化[J]. 东北大学学报（自然科学版）, 2021, 42(8): 1210-1216.
[3]	姜旭艳，严锦立，全巍，孙志刚. SSA:一种面向CQF模型的TSN资源调度算法[J]. 东北大学学报:自然科学版, 2020, 41(6): 784-791.
[4]	王生生，张伟，董如意，李文辉. 改进蚱蜢算法在电动汽车充换电站调度中的应用[J]. 东北大学学报:自然科学版, 2020, 41(2): 170-175.
[5]	李稷，徐安军. 炼钢车间多天车动态调度仿真方案[J]. 东北大学学报:自然科学版, 2020, 41(12): 1699-1707.
[6]	韩美灵，邓庆绪，张天宇，林宇晗. 基于G-EDF的DAG并行任务多核响应时间分析[J]. 东北大学学报:自然科学版, 2019, 40(3): 315-320.
[7]	周炳海，顾佳颖. 考虑多资源约束的非等效并行机节能调度算法[J]. 东北大学学报:自然科学版, 2019, 40(3): 403-408.
[8]	王生生，杜鹏，董如意，李永贺. 改进的花朵授粉算法在微网优化调度中的应用[J]. 东北大学学报:自然科学版, 2018, 39(3): 334-338.
[9]	周炳海，谭芬. 基于循环配送策略的汽车装配线物料配送调度方法[J]. 东北大学学报:自然科学版, 2018, 39(3): 389-393.
[10]	曾程宽，刘士新. 缓冲区间有限条件下的作业车间调度方法[J]. 东北大学学报:自然科学版, 2018, 39(12): 1679-1684.
[11]	王旭，刘士新，王佳. 求解具有时空约束的板坯库天车调度问题Memetic算法[J]. 东北大学学报:自然科学版, 2017, 38(7): 913-917.
[12]	陈迪，孙福权，刘士新. MRO服务中心多技能员工优化调度模型[J]. 东北大学学报:自然科学版, 2016, 37(7): 927-930.
[13]	周炳海，周淑美，赵猛. 基于析取图考虑物料搬运的Job Shop调度算法[J]. 东北大学学报:自然科学版, 2016, 37(1): 138-142.
[14]	刘晓斌，周炳海. OHT搬运系统防阻塞调度策略[J]. 东北大学学报:自然科学版, 2015, 36(2): 176-181.
[15]	冯凯，贺东风，徐安军，汪红兵. 钢包调度评价方法研究[J]. 东北大学学报:自然科学版, 2015, 36(12): 1728-1732.