全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
化工学报  2014 

遗传-分布估计算法求解化工生产中一类带多工序的异构并行机调度问题

DOI: 10.3969/j.issn.0438-1157.2014.03.031, PP. 981-992

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

Full-Text   Cite this paper   Add to My Lib

Abstract:

针对化工生产中广泛存在的一类带多工序的异构并行机调度问题,即部分产品需多工序加工,同时不同产品间带序相关设置时间的异构并行机调度问题(heterogeneousparallelmachineschedulingproblemwithmultipleoperationsandsequence-dependentsetuptimes,HPMSP_MOSST),提出了一种遗传-分布估计算法(geneticalgorithm-estimationofdistributionalgorithm,GA-EDA),用于优化最早完工时间(makespan)。首先,提出了一种基于GA的概率模型训练机制,用来提高概率模型在算法进化初期的信息积累量,进而提高搜索的效率;其次,设计了一种有效的GA与EDA混合策略,使得算法的全局探索和局部开发能力得到合理平衡。计算机模拟验证了GA-EDA的有效性和鲁棒性。

References

[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 Computers target="_blank">
[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 Computers target="_blank">
[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]  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
[24]  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 Computers target="_blank">
[25]  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
[26]  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
[27]  Wang Ling(王凌), Qian Bin(钱斌). Hybrid Differential Evolution and Scheduling Algorithm(混合差分进化与调度算法)[M].Beijing: Tsinghua University Press, 2012: 126-133
[28]  Wang Lifang(王丽芳). Copula Estimation of Distribution Algorithm(Copula分布估计算法)[M]. Beijing: China Machine Press, 2012: 21-131
[29]  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
[30]  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
[31]  Jin Bingyao(金炳尧), Wei Chengjian(蔚承建), He Zhenya(何振亚). PBIL algorithm and its application[J]. Journal of Zhejiang Normal University: Nat. Sci. (浙江师范大学学报:自然科学版), 1999, 22(4): 44-49
[32]  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 Computers target="_blank">
[33]  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 Computers target="_blank">
[34]  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
[35]  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
[36]  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
[37]  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
[38]  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
[39]  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
[40]  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
[41]  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
[42]  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
[43]  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
[44]  Wang Ling(王凌). Shop Scheduling with Genetic Algorithms(车间调度及其遗传算法)[M]. Beijing: Tsinghua University Press, 2003: 22-235
[45]  Liu Min(刘民), Wu Cheng(吴澄). Intelligent Optimization Scheduling Algorithms for Manufacturing Process and Their Application (制造过程智能优化调度算法及其应用)[M]. Beijing: National Defense Industry Press, 2008: 49-53

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133