带换模约束的非等效并行机作业族调度方法

doi:10.13196/j.cims.2013.12.zhanggangzhi.3162.8.20131229

摘要/Abstract

摘要： 在半导体制造过程中,调整设备相关参数以提高晶圆质量的同时又会造成换模时间的增加,从而导致产品生产周期的延长。为了有效地解决此类问题,对带换模约束的非等效并行机多作业族调度方法进行了研究。在描述问题域的基础上,试图在设备参数调整次数与换模次数之间寻求一个均衡点,以实现系统最小Makespan为调度目标,建立数学规模模型,构建了求解此类并行机调度问题的改进型多态蚁群算法,并对提出的调度算法进行了仿真实验分析。结果表明所构建的算法是有效、可行的。

关键词: 调度, 非等效并行机, 参数调整, 蚁群算法

Abstract: In semiconductor manufacturing processes,the relevant parameters of equipment was adjusted to improve the high wafer quality and increase the setup time,which leaded to delay on production cycle time.To solve these problems,a multi-job families scheduling method of non-identical parallel machines was explored with setup time constraints.On the basis of describing a scheduling problem domain,a balance point between the number of setups and the number of parameter adjustments was explored to achieve the objective of minimum system Makespan.The corresponding mathematical programming model was built.A modified polymorphic ant colony algorithm was structured to solve the scheduling problem.Simulation experiments results showed that the developed algorithm was valid and feasible.

Key words: scheduling, non-parallel machines, parameter adjustments

中图分类号:

C934

张刚志,周炳海+. 带换模约束的非等效并行机作业族调度方法[J]. , DOI: 10.13196/j.cims.2013.12.zhanggangzhi.3162.8.20131229.

ZHANG Gang-zhi,ZHOU Bing-hai. Job families scheduling for non-identical parallel machines with setup time constraints[J]. , DOI: 10.13196/j.cims.2013.12.zhanggangzhi.3162.8.20131229.

参考文献

［1］MCNAUGHTON R.Scheduling with deadlines and loss functions［J］.Management Science,1959,6(1):1-12.
[2]GLASS A C,POTT N C,SHADE P.Unrelated parallel machine scheduling using local search［J］.Mathematical and Computer Modeling,1994,20(2):41-52.
[3]PIERSMA N,DIJK W.A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search［J］.Mathematical and Computer Modeling,1996,24(9):11-19.
[4]GHIRARDI M,POTTS N C.Makespan minimization for sch- eduling unrelated parallel machines:a recovering beam search approach［J］.European Journal of Operational Research,2005,165(2):457-467.
[5]FANJUL-PEYRO L,RUIZ R. Iterated greedy local search methods for unrelated parallel machine scheduling［J］.European Journal of Operational Research,2010,207(1):55-69.
[6]FANJUL-PEYRO L,RUIZ R.Size-reduction heuristics for the unrelated parallel machines scheduling problem［J］.Computers & Operations Research,2011,38(1):301-309.
[7]ARNAOUT J,RABADI G,MUSA R.A two-stage ant colony optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times［J］.Journal of Intelligent Manufacturing,2010,21(6):693-701.
[8]FLESZAR K,CHARALAMBOUS C.A variable neighborhood descent heuristic for the problem of makespan minimization on unrelated parallel machines with setup times［J］.Journal of Intelligent Manufacturing,2012,23(5):1949-1958.
[9]WENG M X,LU J,REN H.Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective［J］.International Journal of Production Economics,2001,70(3):215-226.
[10]CAI Y W,KUTANOGLU E,HASENBEIN J, et al.Single-machine scheduling with advanced process control constraints［J］.Journal of Scheduling,2012,15(2):165-179.
[11]OBEID A,DAUZERE-PERES S,YUGMA C.Scheduling job families on non-identical parallel machines with time constraints［C］//Proceeding of the 2011 Winter Simulation Conference.Philadelphia,Pa.,USA:Annals of Operation Research,2012:1994-2005.
[12]DUAN Haibin.The principle and application of ant colony algorithm［M］.Beijing:Science Press,2005:201-204(in Chinese).［段海滨.蚁群算法原理及应用［M］.北京:科学出版社,2005:201-204.］
[13]DUAN Haibin.The principle and application of ant colony algorithm［M］.Beijing:Science Press,2005:24-43(in Chinese).［段海滨.蚁群算法原理及应用［M］.北京:科学出版社,2005:24-43.］

[1]	陈志远,伍章俊,童珊珊,刘晓. 基于改进双归档进化算法的多目标动态软件项目调度[J]. 计算机集成制造系统, 2021, 27(9): 2565-2574.
[2]	周博文,黄海军,徐怡,李学俊,高寒,陈天翔,刘晓,徐佳. 无人机配送系统中端边协同的并行任务调度算法[J]. 计算机集成制造系统, 2021, 27(9): 2575-2582.
[3]	文一凭,王志斌,刘建勋,许小龙,康国胜. 云际协作环境下能耗与成本感知的工作流调度方法[J]. 计算机集成制造系统, 2021, 27(9): 2583-2591.
[4]	秦旋,房子涵,张赵鑫. 考虑资源约束的预制构件多目标生产调度优化[J]. 计算机集成制造系统, 2021, 27(8): 2248-2259.
[5]	满君丰,赵龙乾,彭成,李倩倩. 云边协同计算架构下大规模工厂接入的任务调度[J]. 计算机集成制造系统, 2021, 27(8): 2282-2294.
[6]	顾九春,姜天华,朱惠琦. 多目标离散灰狼优化算法求解作业车间节能调度问题[J]. 计算机集成制造系统, 2021, 27(8): 2295-2306.
[7]	黎英杰,刘建军,陈庆新,毛宁. 多层级装配作业车间等量分批策略与调度算法[J]. 计算机集成制造系统, 2021, 27(8): 2307-2320.
[8]	黄晓冬,端木帅飞,毕敬,苑海涛. 服务延迟保障的混合绿色云数据中心成本最小化方法[J]. 计算机集成制造系统, 2021, 27(8): 2416-2425.
[9]	赵芮,顾幸生. 基于引力搜索算法的混合零空闲置换流水车间调度[J]. 计算机集成制造系统, 2021, 27(7): 1909-1917.
[10]	李林林,刘东梅,王显鹏. 基于改进MOEA/D的多目标置换流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(7): 1929-1940.
[11]	陆志强,任逸飞,许则鑫. 基于深度学习的资源投入问题算法[J]. 计算机集成制造系统, 2021, 27(6): 1558-1568.
[12]	杨艳华,姚立纲. 基于时间递推建模及交叉熵算法求解柔性作业车间调度问题[J]. 计算机集成制造系统, 2021, 27(6): 1703-1713.
[13]	段建国,李豪晨,张青雷. 面向绿色制造的半组合式船用曲轴结构件生产车间多目标调度优化[J]. 计算机集成制造系统, 2021, 27(6): 1714-1727.
[14]	马丽萌,乔非,马玉敏,刘鹃. 基于SO-GP的智能车间组合调度规则挖掘[J]. 计算机集成制造系统, 2021, 27(5): 1351-1360.
[15]	胡金昌,刘紫薇,马文凯,吴耀华. 考虑学习效应的单人作业车间多目标调度算法[J]. 计算机集成制造系统, 2021, 27(5): 1361-1370.