An Open Shop Scheduling Problem Based on Memetic Algorithm

doi:10.3969/j.issn.1007-7375.2018.06.003

Abstract

Abstract: Aiming at the Open Shop Scheduling Problem (OSSP), a Memetic Algorithm (MA) is proposed to solve the problem. In the framework of the cultural Genetic Algorithm (GA), both global search and local search for the problem's own characteristics are provided. It provides a new algorithm for solving the open job shop scheduling problem. According to the thought and cultural characteristics of genetic algorithm, the method of climbing as a local search strategy into the genetic algorithm global search strategy is used, and a research of neighborhood structure is conducted on open shop scheduling problem, adding hill-climbing search method to solve the optimal. Based on the comparison of 40 standard examples, it is proved that the proposed algorithm has better performance in solving the scheduling problem with larger search space by comparing with lower bound values.

Key words: memetic algorithm, open shop scheduling, genetic algorithm, hill climbing search

CLC Number:

TH186

CHEN Xiang, ZHU Chuanjun, ZHANG Chaoyong. An Open Shop Scheduling Problem Based on Memetic Algorithm[J]. Industrial Engineering Journal , 2018, 21(6): 16-22.

References

[1] LOW C F, YEH Y. Genetic algorithm-based heuristics for an open shop scheduling problem with setup processing and removal times separated[J]. Robotics and Computer-Integrated Manufacturing, 2009, 25(2):314-322
[2] BRUCKER P, HURINK J, JURISCH B, et al. A branch & bound algorithm for the open-shop problem[J]. Discrete Applied Mathematics, 1997, 76(1-3):43-59
[3] TAILLARD E D. Benchmark for basic scheduling problems[J]. European Journal of Operational Research, 1993, 64(2):278-285
[4] ROCK H, SCHMIDT G. Machine aggregation heuristics in shop-scheduling[J]. Methods of Operations Research, 1983, 45:303-314
[5] AHMADIZAR F, FARAHANI M H. A novel hybrid genetic algorithm for the open shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2012, 62(5-8):775-787
[6] DOULABI S, AVAZBEIUI M, ARAB S, et al. An effective hybrid simulated annealing and two mixed integer linear formulations for just-in-time open shop scheduling problem[J]. The International Journal of Advanced Manufacturing Technology, 2012, 59(9-12):1143-1155
[7] GUERET C, PRINS C. Classical and new heuristics for the open-shop problem:a computational evaluation[J]. European Journal of Operational Research, 1998, 107(2):306-314
[8] 王军强, 郭银洲, 崔福东, 等. 基于多样性增强的自适应遗传算法的开放式车间调度优化[J]. 计算机集成制造系统, 2014, 20(10):2479-2493 WANG Junqiang, GUO Yinzhou, CUI Fudong, et al. Diversity enhancement based adaptive genetic algorithm for open-shop scheduling problem[J]. Computer Integrated Manufacturing Systems, 2014, 20(10):2479-2493
[9] 展勇, 邱长华, 祝海涛. 基于网络流的多并行机可中断开放车间调度算法[J]. 计算机集成制造系统, 2011, 17(5):990-996 ZHAN Yong, QIU Changhua, ZHU Haitao. Algorithm of preemptive open-shop scheduling with parallel machines based on network flow[J]. Computer Integrated Manufacturing Systems, 2011, 17(5):990-996
[10] ROY B, SUSSMAN B. Les problèmes d'ordonnancement avec contraintes disjonctives[C/OL].(2017-08-01).http://www.scirp.org/(S(i43dyn45teexjx455qlt3d2q))/reference/ReferencesPapers.aspx?ReferenceID=1201138.
[11] PINEDO M. 调度:原理、算法和系统[M]. 张智海, 译. 北京:清华大学出版社, 2007.
[12] BELLMAN R E. On a routing problem[J]. Quarterly Applied Mathematics, 1958, 16:87-90
[13] 刘漫丹. 文化基因算法(Memetic Algorithm)研究进展[J]. 自动化技术与应用, 2007, 26(11):1-4, 18 LIU Mandan. The development of the memetic algorithm[J]. Techniques of Automation & Application, 2007, 26(11):1-4, 18
[14] 玄光男, 程润伟. 遗传算法与工程优化[M]. 北京:清华大学出版社, 2004.
[15] MATTFELD D C. Evolutionary Search and The Job Shop[M]. Berlin:Springer, 1995.