Chemical reaction optimization algorithm for the distributed permutation flowshop scheduling problem

SHEN Jingnan; WANG Ling; WANG Shengyao

doi:10.16511/j.cnki.qhdxxb.2015.21.009

PDF(1442 KB)

Journal of Tsinghua University(Science and Technology) ›› 2015, Vol. 55 ›› Issue (11) : 1184-1189,1196. DOI: 10.16511/j.cnki.qhdxxb.2015.21.009

AUTO MATION

Chemical reaction optimization algorithm for the distributed permutation flowshop scheduling problem

{{article.zuoZhe_EN}}

Author information +

History +

Abstract

An effective chemical reaction optimization(CRO) algorithm was developed to solve the distributed permutation flowshop scheduling problem(DPFSP). Four basic CRO algorithm operators were used in the solution to enrich the search behavior and ensure the population diversity. An effective local search procedure was developed based on the DPFSP characteristics to enhance the local exploitation ability of the algorithm. Finally, the effects of the parameter settings on the algorithm were investigated using the design-of-experiment method with the numerical results showing that this algorithm is effective.

Key words

distributed scheduling / permutation flowshop scheduling problem / chemical reaction optimization / local search

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

SHEN Jingnan, WANG Ling, WANG Shengyao. Chemical reaction optimization algorithm for the distributed permutation flowshop scheduling problem[J]. Journal of Tsinghua University(Science and Technology). 2015, 55(11): 1184-1189,1196 https://doi.org/10.16511/j.cnki.qhdxxb.2015.21.009

References

[1] Chan H K, Chung S H. Optimisation approaches for distributed scheduling problems[J]. International J of Production Research, 2013, 51(9):2571-2577.
[2] 王凌. 车间调度及其遗传算法[M].北京:清华大学出版社, 2003.WANG Ling. Shop Scheduling with Genetic Algorithms[M]. Beijing:Tsinghua University Press, 2003.(in Chinese)
[3] Naderi B, Ruiz R. The distributed permutation flowshop scheduling problem[J]. Computers & Operations Research, 2010, 37(4):754-768.
[4] Jia H Z, Nee A Y C, Fuh J Y H, et al. A modified genetic algorithm for distributed scheduling problems[J]. J of Intelligent Manufacturing, 2003, 14(3-4):351-62.
[5] Chan F T S, Chung S H, Chan P L Y. An adaptive genetic algorithm with dominated genes for distributed scheduling problems[J]. Expert Systems With Applications, 2005, 29(2):364-371.
[6] Chan F T S, Chung S H, Chan L Y, et al. Solving distributed FMS scheduling problems subject to maintenance:genetic algorithms approach[J]. Robotics and Computer-Integrated Manufacturing, 2006, 22(5):493-504.
[7] Jia H Z, Fuh J Y H, Nee A Y C, et al. Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems[J]. Computers & Industrial Engineering, 2007, 53(2):313-20.
[8] Chung S H, Chan F T S, Chan H K. A modified genetic algorithm approach for scheduling of perfect maintenance in distributed production scheduling[J]. Engineering Applications of Artificial Intelligence, 2009, 22(7):1005-1014.
[9] De Giovanni L, Pezzella F. An improved genetic algorithm for the distributed and flexible job-shop scheduling problem[J]. European J of Operational Research, 2010, 200(2):395-408.
[10] Gao J, Chen R. A hybrid genetic algorithm for the distributed permutation flowshop scheduling problem[J]. International J of Computational Intelligence Systems, 2011, 4(4):497-508.
[11] Gao J, Chen R, Deng W. An efficient tabu search algorithm for the distributed permutation flowshop scheduling problem[J]. International J of Production Research, 2013, 51(3):641-651.
[12] Lam A Y S, Li V O K. Chemical-reaction-inspired metaheuristic for optimization[J]. IEEE Trans on Evolutionary Computation, 2010, 14(3):381-399.
[13] Xu J, Lam A Y S, Li V O K. Chemical reaction optimization for task scheduling in grid computing[J]. IEEE Trans on Parallel and Distributed Systems, 2011, 22(10):1624-1631.
[14] Li J Q, Pan Q K. Chemical-reaction optimization for flexible job-shop scheduling problems with maintenance activity[J]. Applied Soft Computing, 2012, 12(9):2896-2912.
[15] Xu J, Lam A Y S, Li V O K. Parallel chemical reaction optimization for the quadratic assignment problem[C]//Proc of the Int Conf on Genetic and Evolutionary Methods. Las Vegas, NV, USA, 2010:125-131.
[16] 郑环宇, 王凌, 方晨. 求解 RCPSP 的一种改进化学反应算法[J/OL].[2012-10-22] http://www.paper.edu.cn/html/releasepaper/2012/10/209/. ZHENG Huanyu, WANG Ling, FANG Chen. An improved chemical reaction optimization algorithm for solving RCPSP[J/OL].[2012-10-22] http://www.paper.edu.cn/html/releasepaper/2012/10/209/.(in Chinese)
[17] Iwata K, Murotsu Y, Oba F, et al. Solution of large-scale scheduling problems for job-shop type machining systems with alternative machine tools[J]. CIRP Annals- Manufacturing Technology, 1980, 29(1):335-338.
[18] Merz P, Freisleben B. A genetic local search approach to the quadratic assignment problem[C]//Proc of the 7th Int Conf on Genetic Algorithms. San Francisco, CA, USA:Morgan Kaufmann, 1997:465-472.
[19] Montgomery D C. Design and Analysis of Experiments[M]. Hoboken:John Wiley and Sons, 2005.