基于混合蛙跳和遗传规划的跨单元调度方法

贾凌云; 李冬妮; 田云娜

doi:10.16383/j.aas.2015.c140455

基于混合蛙跳和遗传规划的跨单元调度方法

doi: 10.16383/j.aas.2015.c140455

1.
北京理工大学计算机学院智能信息技术北京市重点实验室北京 100081;
2.
延安大学数学与计算机科学学院延安 716000

基金项目:

国家自然科学基金(71401014),北京市自然科学基金(4122069)资助

详细信息

作者简介:
贾凌云北京理工大学计算机学院硕士研究生. 主要研究方向为演化计算和生产调度. E-mail: lingyun jia@163.com

通讯作者:
李冬妮北京理工大学计算机学院副教授. 主要研究方向为智能优化, 企业计算,物流管理等. E-mail: ldn@bit.edu.cn

计量
- 文章访问数: 1477
- HTML全文浏览量: 45
- PDF下载量: 1465
- 被引次数: 0
出版历程
- 收稿日期: 2014-06-23
- 修回日期: 2014-11-17
- 刊出日期: 2015-05-20

An Intercell Scheduling Approach Using Shuffled Frog Leaping Algorithm and Genetic Programming

1.
Beijing Key Laboratory of Intelligent Information Technology, School of Computer Science, Beijing Institute of Technology, Beijing 100081;
2.
College of Mathematics and Computer Science, Yan'an University, Yan'an 716000

Funds:

Supported by National Natural Science Foundation of China (71401014) and Natural Science Foundation of Beijing (4122 069)

摘要

摘要: 针对运输能力受限条件下的跨单元问题,提出了一种基于混合蛙跳与遗传规划的超启发式算法.将改进的混合蛙跳算法作为超启发式算法的高层框架,为跨单元调度问题搜索启发式规则,同时利用遗传规划产生可以兼顾多因素的优质规则,用于扩充超启发式算法的规则集.实验表明,提出的算法可以有效地搜索出优异的规则组合,并且通过遗传规划产生的规则可以在很大程度上改善候选规则集,提升算法性能.
- 跨单元调度 /
- 跨单元运输 /
- 超启发式算法 /
- 混合蛙跳算法 /
- 遗传规划
Abstract: To deal with the intercell scheduling problem with limited transportation capabilities, a shuffled frog leaping algorithm-based hyperheuristic approach with genetic programming is developed in this paper. The proposed approach develops an improved shuffled frog leaping algorithm to search the combinations of heuristic rules for the addressed problem. Meanwhile, genetic programming is also introduced into the proposed algorithm to generate well-performing heuristic rules as an extension to the predefined candidate heuristic rules. Experimental results show that the improved shuffled frog leaping algorithm is efficient to search the outperforming combinations of the heuristic rules, and that the heuristic rules generated via genetic programming can obviously improve the quality of the candidate rule set, therefore providing better performance.
- Intercell scheduling /
- intercell transportation /
- hyperheuristic /
- shuffled frog leaping algorithm /
- genetic pro-gramming

HTML全文

参考文献(32)

[1]	Rheault M, Drolet J R, Abdulnour G. Dynamic cellular manufacturing system (DCMS). Computers and Industrial Engineering, 1996, 31(1-2): 143-146
[2]	[2] Garza O, Smunt T L. Countering the negative impact of intercell flow in cellular manufacturing. Journal of Operations Management, 1991, 10(1): 92-118
[3]	[3] Khaksar-Haghani F, Kia R, Mahdavi I, Kazemi M. A genetic algorithm for solving a multi-floor layout design model of a cellular manufactur-ing system with alternative process routings and flexible configuration. The International Journal of Advanced Manufacturing Technology, 2013, 66(5-8): 845-865
[4]	[4] Kia R, Baboli A, Javadian N, Tavakkoli-Moghaddam R, Kazemi M, Khorrami J. Solving a group layout design model of a dynamic cellular manufacturing system with alternative process routings, lot splitting and flexible reconfiguration by simulated annealing. Computers and Operations Research, 2012, 39(11): 2642-2658
[5]	[5] Gupta J N D, Schaller J E. Minimizing flow time in a flow-line manufacturing cell with family setup times. Journal of the Operational Research Society, 2006, 57(2): 163-176
[6]	[6] Tsai C H, Li R K. A due-date oriented scheduling heuristic for job shop cellular manufacturing system. International Journal of Industrial Engineering Theory Applications and Practice, 2000, 7(1): 76-88
[7]	[7] Solimanpur M, Elmi A. A tabu search approach for cell scheduling problem with makespan criterion. International Journal of Production Economics, 2013, 141(2): 639-645
[8]	[8] Golmohammadi A, Ghodsi R. Applying an integer Electromagnetism-like algorithm to solve the cellular manufacturing scheduling problem with an integrated approach. In: Proceedings of the 2009 International Conference on Computers and Industrial Engineering. Troyes: IEEE, 2009. 34-39
[9]	[9] Mosbah A B, Dao T M. Optimimization of group scheduling using simulation with the meta-heuristic extended great deluge (EGD) approach. In: Proceedings of the 2010 IEEE International Conference on Industrial Engineering and Engineering Management. Macao: IEEE, 2010. 275-280
[10]	Gholipour K Y, TavakkoliM R, Khorrami A. Solving a multicriteria group scheduling problem for a cellular manufacturing system by scatter search. Journal of the Chinese Institute of Industrial Engineers, 2011, 28(3): 192-205
[11]	Li W L, Murata T. Particle swarm optimization method for rescheduling of job processing against machine breakdowns for nondisruptive cell manufacturing system. In: Proceedings of the 6th International Conference on New Trends in Information Science and Service Science and Data Mining (ISSDM). Taipei, China: IEEE, 2012. 523-528
[12]	Meng X W, Ju Y H, Wang X H, Wang Y, Li D N. An ACO-based approach for intercell scheduling with various types of machines. In: Proceedings of the 25th Chinese Control and Decision Conference (CCDC). Guiyang, China: IEEE, 2013. 1812-1817
[13]	Pajoutan M, Golmohammadi A, Seifbarghy M. CMS scheduling problem considering material handling and routing flexibility. The International Journal of Advanced Manufacturing Technology, 2014, 72(5-8): 881-893
[14]	Li Dong-Ni, Xiao Guang-Xue, Wang Yan, Tang Jia-Fu. An intercell scheduling approach considering flexible processing routes. Acta Automatica Sinica, 2012, 38(6): 969-975(李冬妮, 肖广雪, 王妍, 唐加福. 一种柔性路径下的跨单元调度方法. 自动化学报, 2012, 38(6): 969-975)
[15]	Li D N, Wang Y, Xiao G X, Tang J F. Dynamic parts scheduling in multiple job shop cells considering intercell moves and flexible routes. Computer and Operations Research, 2013, 40(5):1207-1223
[16]	Eusuff M M, Lansey K E. Optimization of water distribution network design using the shuffled frog leaping algorithm. Journal of Water Resources Planning and Management, 2003, 129(3): 210-225
[17]	Xu Y, Wang L, Wang S Y, Liu M. An effective shuffled frog-leaping algorithm for solving the hybrid flow-shop scheduling problem with identical parallel machines. Engineering Optimization, 2013, 45(12): 1409-1430
[18]	Luke S, Panait L, Balan G, Paus S, Skolicki Z, Kicinger R, Popovici E, Sullivan K, Harrison J, Bassett J, Hubley R, Desai A, Chircop A, Compton J, Haddon W, Donnelly S, Jamil B, Zelibor J, Kangas E, Abidi F, Mooers H, O'Beirne J, Talukder K A, McDermott J. ECJ: a java-based evolutionary computation research system. [Online], available: http: //cs.gmu.edu/ eclab/projects/ecj/, June 5, 2014
[19]	Koza J R. Genetic programming as a means for programming computers by natural selection. Statistics and Computing, 1994, 4(2): 87-112
[20]	Robilliard D, Marion-Poty V, Fonlupt C. Genetic programming on graphics processing units. Genetic Programming and Evolvable Machines, 2009, 10(4): 447-471
[21]	Park S C, Raman N, Shaw M J. Adaptive scheduling in dynamic flexible manufacturing systems: a dynamic rule selection approach. IEEE Transactions on Robotics and Automation, 1997, 13(4): 486-502
[22]	Barman S. Simple priority rule combinations: an approach to improve both flow time and tardiness. International Journal of Production Research, 1997, 35(10): 2857-2870
[23]	Laforge R L, Barman S. The performance of simple priority rule combinations in a flow dominant shop. Production and Inventory-Management Journal, 1989, 30(3): 1-4
[24]	Sarper H, Henry M C. Combinatorial evaluation of six dispatchingrules in a dynamic two-machine flow shop. Omega, 1996, 24(1): 73-81
[25]	Li D N, Meng X W, Liang Q Q, Zhao J Q. A heuristic-search genetic algorithm for multi-stage hybrid flow shop scheduling with single processing machines and batch processing machines. Journal of Intelligent Manufacturing, DOI: 10. 1007/s10845-014-0874-y
[26]	Yang T, Kuo Y, Cho C. A genetic algorithms simulation approachfor the multi-attribute combinatorial dispatching decision problem. European Journal of Operational Research, 2007, 176(3): 1859-1873
[27]	Ebrahimi J, Hosseinian S H, Gharehpetian G B. Unit commitment problem solution using shuffled frog leaping algorithm. IEEE Transactions on Power Systems, 2011, 26(2): 573-581
[28]	Rahimi-Vahed A, Mirzaei A H. A hybrid multi-objective shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem. Computers and Industrial Engineering, 2007, 53(4): 642-666
[29]	Eusuff M, Lansey K, Pasha F. Shuffled frog-leaping algorithm: a memetic metaheuristic for discrete optimization. Engineering Optimization, 2006, 38(2): 129-154
[30]	Teekeng W, Thammano A. A combination of shuffled frog leaping and fuzzy logic for flexible job-shop scheduling problems. Procedia Computer Science, 2011, 6: 69-75
[31]	Luo X H, Ye Y, Li X. Solving TSP with shuffled frog-leaping algorithm. In: Proceedings of the 8th International Conference on Intelligent Systems Design and Applications. Washington, D.C., USA: IEEE, 2008. 228-232
[32]	Glover F, Laguna M, Mart R. Fundamentals of scatter search and path relinking. Control and Cybernetics, 2000, 39(3): 653-684