A genetic algorithm-estimation of distribution algorithm for a kind of heterogeneous parallel machine scheduling problem with multiple operations in chemical production

doi:10.3969/j.issn.0438-1157.2014.03.031

Abstract

Abstract: A genetic algorithm-estimation of distribution algorithm (GA-EDA) was proposed to optimize the makespan criterion for a kind of heterogeneous parallel machine scheduling problem, i.e., the heterogeneous parallel machine scheduling problem with multiple operations and sequence-dependent setup times (HPMSP_MOSST), which widely existed in chemical production. Firstly, a probability model training mechanism based on GA was presented and used to increase the information accumulation of the probability model at the initial stage of the evolution, and then the efficiency of search was improved. Secondly, an effective hybrid strategy of GA and EDA was designed to help the algorithm achieve a reasonable balance between global exploration and local exploitation abilities. Computer simulation showed the effectiveness and robustness of the proposed GA-EDA.

Key words: heterogeneous parallel machine, multiple operations, genetic algorithm, estimation of distribution algorithm, optimization, probability model, computer simulation

摘要： 针对化工生产中广泛存在的一类带多工序的异构并行机调度问题，即部分产品需多工序加工，同时不同产品间带序相关设置时间的异构并行机调度问题（heterogeneous parallel machine scheduling problem with multiple operations and sequence-dependent setup times， HPMSP_MOSST），提出了一种遗传-分布估计算法（genetic algorithm-estimation of distribution algorithm， GA-EDA），用于优化最早完工时间（makespan）。首先，提出了一种基于GA的概率模型训练机制，用来提高概率模型在算法进化初期的信息积累量，进而提高搜索的效率；其次，设计了一种有效的GA与EDA混合策略，使得算法的全局探索和局部开发能力得到合理平衡。计算机模拟验证了GA-EDA的有效性和鲁棒性。

关键词: 异构并行机, 多工序, 遗传算法, 分布估计算法, 优化, 概率模型, 计算机模拟

CLC Number:

TQ021.8

LI Zuocheng, QIAN Bin, HU Rong, LUO Rongjuan, ZHANG Guilian. A genetic algorithm-estimation of distribution algorithm for a kind of heterogeneous parallel machine scheduling problem with multiple operations in chemical production[J]. CIESC Journal, 2014, 65(3): 981-992.

李作成, 钱斌, 胡蓉, 罗蓉娟, 张桂莲. 遗传-分布估计算法求解化工生产中一类带多工序的异构并行机调度问题[J]. 化工学报, 2014, 65(3): 981-992.

References 45

[1]	Lei Deming(雷德明). Intelligent Scheduling Technology and Application of Modern Manufacturing System (现代制造系统智能调度技术及其应用)[M]. Beijing: China Electric Power Press, 2011: 233-239
[2]	Shi Ye(史烨), Li Kai(李凯). Research on simulated annealing scheduling algorithm for parallel machine problem[J]. Operations Research and Management Science (运筹与管理), 2011, 20(4): 104-112
[3]	Hao Jinghua(郝井华), Liu Min(刘民), Wu Cheng(吴澄), Zhang Rui(张瑞). Job-clustering-based scheduling algorithm for parallel machine and its application[J]. Computer Integrated Manufacturing Systems(计算机集成制造系统), 2006, 12(12): 2062-2073
[4]	Ying K C, Cheng H M. Dynamic parallel machine scheduling with sequence-dependent setup times using an iterated greedy heuristic[J]. Expert Systems with Applications, 2010, 37: 2848-2852
[5]	Beraldi P, Ghiani G, Grieco A, Guerriero E. Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs[J]. Computers & Operations Research, 2008, 35: 3644-3656
[6]	Jin Feng(金锋), Song Shiji(宋士吉), Yang Jianhua(杨建华), Wu Cheng(吴澄). Dyeing machine scheduling problem in dyeing & finishing workshop[J]. Computer Integrated Manufacturing Systems (计算机集成制造系统), 2008, 14(3): 543-547
[7]	Meyr H. Simultaneous lotsizing and scheduling on parallel machines[J]. European Journal of Operational Research, 2002, 139: 277-292
[8]	Li K, Yang S L. Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms[J]. Applied Mathematical Modelling, 2009, 33: 2145-2158
[9]	Liu Chaoying(刘朝英). Light Industry and Pharmaceutical Production Automation(轻工与制药生产自动化)[M]. Beijing: China Machine Press, 2006: 78-88
[10]	Huang Dexian(黄德先), Ye Xinyu(叶心宇), Zhu Jianmin (竺建敏), Li Xiugai(李秀改). Advanced Process Control of Chemical Process(化工过程先进控制)[M]. Beijing: Chemical Industry Press, 2006: 9-10
[11]	Wu Qidi(吴启迪), Kang Qi(康琦), Wang Lei(汪镭), Lu Jinshan(陆金山). An Introduction to Nature-inspired Computation(自然计算导论)[M]. Shanghai: Shanghai Scientific and Technical Publishers, 2011: 58-61
[12]	Zhang Jun(张军), Zhan Zhihui(詹志辉). Computation Intelligence(计算智能)[M]. Beijing: Tsinghua University Press, 2009: 54-58
[13]	Wang Weiling(王伟玲), Li Junfang(李俊芳), Wang Jing(王晶). Double-population genetic algorithm for multi-objective job shop scheduling problem[J]. Computer Integrated Manufacturing Systems(计算机集成制造系统), 2011, 17(4): 808-815
[14]	Li Jingyao(李兢尧), Sun Shudong(孙树栋), Huang Yuan(黄媛), Niu Ganggang(牛刚刚). Double-objective inherited genetic algorithm for dual resource constrained job shop[J]. Control and Decision (控制与决策), 2011, 26(12):1761-1776
[15]	Pezzella F, Morganti G, Ciaschetti G. A genetic algorithm for the flexible job-shop scheduling problem[J]. Computers & Operations Research, 2008, 35: 3202-3212
[16]	Chen J S, Pan J C H, Lin C M. A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem[J]. Expert Systems with Applications, 2008, 34: 570-577
[17]	Ventura J A, Yoon S H. A new genetic algorithm for lot-streaming flow shop scheduling with limitedcapacity buffers[J]. J. Intell. Manuf., 2012, DOI 10.1007/s10845-012-0650-9
[18]	Qingdaoerji R, Wang Y P. A new hybrid genetic algorithm for job shop scheduling problem[J]. Computers & Operations Research, 2012, 39: 2291-2299
[19]	Wu Lianying, Hu Yangdong, Xu Dongmei, Hua Ben. A genetic algorithm-based approach to scheduling of batch production with maximum profit[J]. Chinese J. Chem. Eng., 2005, 13(1): 68-73
[20]	Zhang Wei(张伟), Zhao Jinhui(赵进慧), Wang Ning(王宁). Integer-coded genetic algorithm with novel repairing mechanism for large scale unit-commitment problem[J]. CIESC Journal (化工学报), 2012, 63(9): 2972-2979
[21]	Zhou Shude(周树德), Sun Zengqi(孙增圻). A survey on estimation of distribution algorithms[J]. Acta Automatica Sinica (自动化学报), 2007, 33(2): 113-124
[22]	Wang Shengyao(王圣尧), Wang Ling(王凌), Fang Chen(方晨), Xu Ye(许烨). Advances in estimation of distribution algorithm[J]. Control and Decision (控制与决策), 2012, 27(7): 961-974
[23]	Wang Lifang(王丽芳). Copula Estimation of Distribution Algorithm(Copula分布估计算法)[M]. Beijing: China Machine Press, 2012: 21-131
[24]	Baluja S, Caruana R. Removing the genetics from the standard genetic algorithm//Proceeding of the International Conference on Machine Learning[C]. Lake Tahoe, CA, 1995:38-46
[25]	Baluja S. Population-based incremental learning: a method for integrating genetic search based function optimization and competitive learning: Technical Report CMU-CS-94-193[R]. Pittsburgh, PA: Carnegie Mellon University, 1994
[26]	Jin Bingyao(金炳尧), Wei Chengjian(蔚承建), He Zhenya(何振亚). PBIL algorithm and its application[J]. Journal of Zhejiang Normal University: Nat. Sci. (浙江师范大学学报:自然科学版), 1999, 22(4): 44-49
[27]	Jarboui B, Eddaly M, Siarry P. An estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems[J]. Computers & Operations Research, 2009, 36: 2638-2646
[28]	Zhang Y, Li X P. Estimation of distribution algorithm for permutation flow shops with total flowtime minimization[J]. Computers & Industrial Engineering, 2011, 61: 706-718
[29]	Pan Q K, Ruiz R. An estimation of distribution algorithm for lot-streaming flow shop problems with setup times[J]. Omega, 2012, 40: 166-180
[30]	Wang L, Wang S Y, Xu Y, Zhou G, Liu M. A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem[J]. Computers & Industrial Engineering, 2012, 62: 917-926
[31]	Wang Shengyao(王圣尧), Wang Ling(王凌), Xu Ye(许烨), Zhou Gang(周刚). An estimation of distribution algorithm for solving hybrid flow-shop scheduling problem[J]. Acta Automatica Sinica (自动化学报), 2012, 38(3): 437-443
[32]	He Y H, Hui C W. Automatic rule combination approach for single-stage process scheduling problems[J]. American Institute of Chemical Engineers, 2007, 53: 2026-2047
[33]	He Y H, Hui C W. A rule-based genetic algorithm for the scheduling of single-stage multi-product batch plants with parallel units[J]. Computers and Chemical Engineering, 2008, 32: 3067-3083
[34]	Niu Q, Zhou T J, Wang L. A hybrid particle swarm optimization for parallel machine total tardiness scheduling[J]. Int. J. Adv. Manuf. Technol., 2010, 49: 723-739
[35]	Liu B, Wang L, Liu Y, Qian B, Jin Y H. An effective hybrid particle swarm optimization for batch scheduling of polypropylene processes[J]. Computers and Chemical Engineering, 2010, 34: 518-528
[36]	Vallada E, Ruiz R. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times[J]. European Journal of Operational Research, 2011, 211: 612-622
[37]	Tahar D N, Yalaoui F, Chu C B, Amodeo L. A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times[J]. Int. J. Production Economics, 2006, 99: 63-73
[38]	Chen S H, Chang P C, Cheng T C E, Zhang Q F. A self-guided genetic algorithm for permutation flow-shop scheduling problems[J]. Computers & Operations Research, 2012, 39: 1450-1457
[39]	Zhang Q, Sun J, Tsang E. An evolutionary algorithm with guided mutation for the maximum clique problem[J]. IEEE Transactions on Evolutionary Computation 2005, 9: 192-200
[40]	Chang P C, Chen S H, Fan C Y. Mining gene structures to inject artificial chromosomes for genetic algorithm in single machine scheduling problems[J]. Applied Soft Computing Journal, 2008, 8: 767-777
[41]	Wang Ling(王凌). Shop Scheduling with Genetic Algorithms(车间调度及其遗传算法)[M]. Beijing: Tsinghua University Press, 2003: 22-235
[42]	Liu Min(刘民), Wu Cheng(吴澄). Intelligent Optimization Scheduling Algorithms for Manufacturing Process and Their Application (制造过程智能优化调度算法及其应用)[M]. Beijing: National Defense Industry Press, 2008: 49-53
[43]	Wang Ling(王凌), Wang Shengyao(王圣尧), Fang Chen(方晨). A hybrid distribution estimation algorithm for solving multidimensional knapsack problem[J]. Control and Decision (控制与决策), 2011, 26(8): 1121-1125
[44]	Wang S Y, Wang L, Zhou G, Xu Y. An estimation of distribution algorithm for the flexible job-shop scheduling problem[J]. LNAI, 2012, 6839: 9-16
[45]	Wang Ling(王凌), Qian Bin(钱斌). Hybrid Differential Evolution and Scheduling Algorithm(混合差分进化与调度算法)[M].Beijing: Tsinghua University Press, 2012: 126-133