Abstract：This paper proposes an estimation of distribution algorithm based on Copula for solving parallel machine scheduling problem with constrained waiting time.By considering the ratios of each class of orders to total lots as variables,a Copula function is constructed for each machine,and then the probability model of the dominant population is established.This algorithm generates individual coding vector group by sampling based on the probability model,and preserves the relative location information of the parent population.The time complexity of the proposed algorithm is analyzed,which increases logarithmically as the number of lots raises.Simulation results based on some instances and comparisons with some existing algorithms demonstrate the effectiveness and robustness of the proposed algorithm.
曹政才, 林诚然, 黄冉. 带等待时间约束并行机调度问题的Copula分布估计算法[J]. 电子学报, 2017, 45(12): 2949-2956.
CAO Zheng-cai, LIN Cheng-ran, HUANG Ran. An Estimation of Distribution Algorithm Based on Copula for Parallel Machine Scheduling with Constrained Waiting Time. Acta Electronica Sinica, 2017, 45(12): 2949-2956.
[1] An Y J,Kim Y D,Choi S W.Minimizing makespan in a two-machine flowshop with a limited waiting time constraint and sequence-dependent setup times[J].Computers & Operations Research,2016,71:127-136.
[2] 曹政才,彭亚珍,李博,等.半导体生产线基于DBR和ANFIS相融合的动态调度方法研究[J].电子学报,2015,43(10):2082-2087. CAO Zhengcai,PENG Yazhen,LI Bo,et.A DBR and ANFIS integrated dynamic scheduling algorithm for semiconductor wafer fabrication[J].Acta Electronica Sinica,2015,43(10):2082-2087.(in Chinese)
[3] 曹政才,赵会丹,王永吉.基于模糊Petri网推理的半导体生产线投料控制策略[J].电子学报,2011,29(7):1545-1550. CAO Zhengcai,Zhao Huidan,Wang Yongji.Releasing control policy for semiconductor wafer fabrication based on fuzzy Petri nets-reasoning[J].Acta Electronica Sinica,2011,29(7):1545-1550.(in Chinese)
[4] 刘民,吴澄.并行多机调度问题的一种基于组合规则的遗传算法[J].电子学报,2000,28(5):52-54. Liu M,Cheng W U,Yang Y J.Genetic algorithm method based on combinatorial rules in identaical parallel machine scheduling problem[J].Acta Electronica Sinica,2000,28(5):52-54.(in Chinese)
[5] 尹文君,刘民,吴澄.带工艺约束并行机调度问题的一种新的遗传算法[J].电子学报,2001,29(11):1482-1485. YIN Wen jun,LIU Min,WU Cheng.Parallel machine production scheduling problem with special procedure constraint by a new genetic.[J] Acta Electronica Sinica.2001,29(11):1482-1485.(in Chinese)
[6] CAO Zhengcai,ZHAO Huidan.ANFIS and SA based approach to prediction,scheduling,and performance evaluation for semiconductor wafer fabrication[J].Chinese Journal of Electronics,2013,22(1):25-30.
[7] 张先超,周泓.变参数量子进化算法及其在求解置换流水车间调度问题中的应用[J]计算机集成制造系统,2016,22(3):774-781. ZHANG XianChao,ZHOU Hong.Variable parameters quantum-inspired evolutionary algorithm and its application in permutation flow-shop scheduling problem[J].Computer Integrated Manufacuring Systems,2016,22(3):774-781.(in Chinese)
[8] CHEN,Xiao,Jing.Parallel test task scheduling with constraints based on hybrid particle swarm optimization and taboo search[J].Chinese Journal of Electronics,2012,21(4):615-618.
[9] Wang K,Choi S H,Lu H.A hybrid estimation of distribution algorithm for simulation-based scheduling in a stochastic permutation flowshop[J].Computers & Industrial Engineering,2015,90(C):186-196.
[10] 李作成,钱斌,胡蓉,等.求解一类异构并行机调度问题的分布估计算法[J].计算机集成制造系统,2013,19(9):2202-2212. LI Zuocheng,QIAN Bing,Hu Rong,et al.Estimation of distribution algorithm for a kind of heterogeneous parallel machine scheduling problem[J].Computer Integrated Manufacturing Systems,2013,19(9):2202-2212.(in Chinese)
[11] 周树德,孙增圻.分布估计算法综述[J].自动化学报,2007,33(2):113-124. Zhou Shude,Sun Zengqi.A survey on estimation of distribution algorithms[J].Acta Automatica Sinica,2007,33(2):113-124.(in Chinese)
[12] 王圣尧,王凌,许烨,等.求解混合流水车间调度问题的分布估计算法[J].自动化学报,2012,38(3):437-443. WANG ShengYao,WANG Ling,XU Ye.An estimation of distribution algorithm for solving hybrid flow-shop scheduling problem[J].Acta Automatica Sinica.2012,38(3):438-443.(in Chinese)
[13] Wang Hungkai,Chien Chenfu.An Algorithm of multi-Subpopulation parameters with hybrid estimation of distribution for semiconductor scheduling with constrained waiting time[J].IEEE Transactions on semiconductor manufacturing.2015,28(3):353-366.
[14] 王丽芳.Copula分布估计算法[M].北京:机械工业出版社,2012.21-131. WANG Lifang.Copula Estimation Of Distribution Algorithem[M].Beijing:China Machine Press 2012.21-131.(in Chinese).
[15] Mönch L,Fowler J W,Dauzère-Pérès S,et al.A survey of problems,solution techniques,and future challenges in scheduling semiconductor manufacturing operations.Journal of Scheduling,[J].Journal of Scheduling,2011,14(6):583-599.
[16] 刘志雄,杨光祥.基于轮盘赌概率分配编码方法的并行机调度优化[A].第二十九届中国控制会议论文集[C].北京:中国自动化学会,2010.
[17] Strelen J C,Nassaj F.Analysis and generation of random vectors with Copulas[A].Proceedings of the 2007 Winter Simulation Conference[C].Washington DC:IEEE,2007.488-496.
[18] Grefenstette J J.Optimization of control parameters for genetic algorithms[J].IEEE Transactions on Systems,Man and Cybernetics,1986,16(1):122-128.
2017, Vol. 45 
