A Hybrid Genetic Algorithm for Flexible Job-Shop Scheduling Problem

Abstract

Abstract: The flexible job-shop scheduling problem (FJSP) is addressed and a hybrid genetic algorithm (GA) is proposed to solve this problem. A heuristic is used to create a set of relatively good schedules for the problem, from which the initial population is created by selecting the relatively good ones. Furthermore, priority rules are integrated into crossover, mutation, exchange, and selection to avoid that it converges to a local optimum. In this way, a better solution can be obtained. Benchmark FJSPs are used to test the proposed method and comparison with some existing approaches is done. Results show that it is effective and efficient for solving FJSPs.

Key words: flexible job-shop scheduling problem, heuristic, genetic algorithm

Shuai Qi1,2, Yao Xi-fan2. A Hybrid Genetic Algorithm for Flexible Job-Shop Scheduling Problem[J]. Industrial Engineering Journal , 2013, 16(1): 31-37.

References

［1］Zhang G H, Xin Y S. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem［J］. Computers & Industrial Engineering, 2009,56(4): 1309-1318. ［2］Zhao H J, Hua P C, Jun T. An improved particle swarm optimization for multi-objective flexible job-shop scheduling problem［C］. Proceedings of 2007 IEEE International Conference on Grey Systems and Intelligent Services.Nanjing:IEEE,2007:1587-1592.  ［3］吴秀丽, 李苏剑. 柔性作业车间多品种小批量调度算法研究［J］. 中国机械工程，2010，21（4）:425-429. Wu Xiu-li, Li Su-jian. Research on batch scheduling problem in a flexible job shop［J］. China Mechanical Engineering，2010，21(4）:425-429. ［4］刘琼, 张超勇. 改进遗传算法解决柔性作业车间调度问题［J］. 工业工程与管理, 2009, 14( 2) : 59-66. Liu Qiong, Zhang Chao-yong. Flexible job-shop scheduling problem with improved genetic algorithm［J］. Industrial Engineering and Management, 2009, 14( 2) : 59-66. ［5］苏春, 王大侠. 基于改进遗传算法的偏柔性作业车间调度［J］. 工业工程, 2010,10(6): 61-65. Su Chun, Wang Da-xia. An improved genetic algorithm for partial flexible job-shop scheduling［J］. Industrial Engineering Journal, 2010,10(6): 61-65. ［6］Ju Q Y, Zhu J Y. Multi-objective flexible Job Shop scheduling of batch production［J］. Chinese Journal of Mechanical Engineering, 2007, 43 ( 8 ):148-154. ［7］晏鹏宇 ,车阿大,李鹏. 具有柔性加工时间的机器人制造单元调度问题改进遗传算法［J］. 计算机集成制造系统, 2010,16(2):404-410. Yan Peng-yu, Che A-da, Li Peng. Improved genetic algorithm for robotic cell scheduling problem with flexible processing times［J］. Computer Integrated Manufacturing Systems, 2010,16(2):404-410. ［8］Xia, W J, Wu Z M. An effective hybrid optimization approach for Multi-objective flexible job-shop scheduling problems［J］. Computers and Industrial Engineering, 2005, 48 (2): 409-425. ［9］白俊杰,龚毅光,王宁生. 多目标柔性作业车间分批优化调度［J］. 计算机集成制造系统, 2010，16（2）:397-403. Bai Jun-jie, Gong Yi-guang, Wang Ning-sheng. Multi-objective flexible Job Shop scheduling with lot-splitting［J］. Computer Integrated Manufacturing Systems, 2010，16（2）:397-403.〖ZK)〗 ［10］牛群, 顾幸生. 基于启发式规则的新型进化算法在流水车间调度中的应用［J］.华东理工大学学报,2006,32(12):1472-1477. Niu Qun, Gu Xing-sheng. An improved evolutionary algorithm based on heuristic rules for flow shop scheduling［J］. Journal of East China University of Science and Technology, 2006,32(12):1472-1477. ［11］肖志娇,常会友,衣杨.启发式规则与GA结合的优化方法求解工作流动态调度优化问题［J］.计算机科学，2007，34（2）：157-161。 Xiao Zhi-jiao, Chang Hui-you Yi Yang. An optimization method of workflow dynamic scheduling based on heuristic GA［J］. Computer Science, 2007，34（2）：157-161。 ［12］Kacem I, Hammadi S, Borne P. Approach by localization and multi-objective evolutionary optimization for flexible job-shop scheduling problems［J］. IEEE transactions on systems, man, and cybernetics, Part C, 2002, 32(1): 1-13. ［13］Horn J, Nafpliotis N. A niched Pareto genetic algorithm for multi-objective optimization ［J］. Evolutionary Computation,1994,27(1):82-87. ［14］Murata T, Ishibuchi H, Tanaka H. Genetic algorithms for flow shop scheduling problem［J］. Computers & Industrial Engineering,1996,30(4):1061-1071. ［15］Kacem I，Hammadi S，Borne P. Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic［J］.Mathematics and Computers in Simulation,2002,60(3):245-276.

[1]	ZHANG Zhengmin, GUAN Zailin, YUE Lei. Performance Analysis of Hybrid GA Based on Lévy Flight in Flexible Job-shop Scheduling Problem [J]. Industrial Engineering Journal, 2021, 24(4): 83-92.
[2]	WANG Xiaojun, WANG Bo, JIN Minjie, YANG Chunxia, BAI Xinli. Multi AGV Scheduling Optimization of AutoStore System Based on Improved Multi Population Genetic Algorithm [J]. Industrial Engineering Journal, 2021, 24(4): 112-118,167.
[3]	WANG Yingying, WU Liyun. A Research on Multi-project Multi-skill Human Resource Scheduling Based on Improved NSGA-II [J]. Industrial Engineering Journal, 2021, 24(3): 130-138.
[4]	ZENG Chuangfeng, LIU Jianjun, CHEN Qingxin, MAO Ning. A Genetic Algorithm-Iterative Greedy Algorithm for a Kind of Unrelated Parallel Machine Scheduling Problem [J]. Industrial Engineering Journal, 2021, 24(2): 110-118.
[5]	HUANG Lu, JI Yanguang. A Bi-level Optimization Model for Logistics Distribution Center Location Problem under Customer Delay Cost [J]. Industrial Engineering Journal, 2021, 24(2): 141-147.
[6]	WANG Bingyi, ZHANG Jin. A Multi-level Express Outlets Layout under Network Sharing and Change [J]. Industrial Engineering Journal, 2021, 24(2): 155-165.
[7]	MA Yueru, WEN Zheng, YI Dan. Multi-objective Home-health-care Staff for the Elderly Routing Optimization Considering Elderly Satisfaction [J]. Industrial Engineering Journal, 2021, 24(1): 74-81,103.
[8]	WANG Jiuhe, GAO Hui, LIU Huan. A Research on Shared Motorcycle Scheduling Problem Based on Genetic Algorithms [J]. Industrial Engineering Journal, 2021, 24(1): 90-96.
[9]	WANG Zhen, GUO Jianquan. Research on Remanufacturing Closed-loop Supply Chain Considering Supply Disruption in Uncertain Environment [J]. Industrial Engineering Journal, 2021, 24(1): 140-146.
[10]	CAO Zhenyu, JIANG Yangsheng, LUO Xiaoling, YANG Jie, ZHANG Yao. A Direct Optimization in Urban Transit Network for Small and Medium-sized Cities [J]. Industrial Engineering Journal, 2020, 23(6): 117-123.
[11]	WU Bin, SONG Yan, CHENG Jing, DONG Min. A Research on Vehicle Routing Problems with Time Windows Based on Density Peak Clustering [J]. Industrial Engineering Journal, 2020, 23(5): 58-66,74.
[12]	WANG Sulin, QIU Feier, CHEN Fan, LIU Chuankun, LU Teng, WANG Zhiyun. A Research on Underground Logistics Node Selection Planning Based on Greedy Genetic Algorithm [J]. Industrial Engineering Journal, 2020, 23(5): 88-95.
[13]	WANG Ze, YANG Xinfeng, LIU Lanfen. A Research on Vehicle Scheduling Optimization Considering Power Consumption [J]. Industrial Engineering Journal, 2020, 23(4): 140-147.
[14]	ZENG Chuifei, LIU Jianjun, CHEN Qingxin, MAO Ning. A Comparative Study of the Algorithm of Assembly Job Shop Lot Streaming Scheduling [J]. Industrial Engineering Journal, 2020, 23(4): 174-182.
[15]	ZHU Xiang, XIANG Yanping. An Optimization of Multi-Freights Loading into Multi-Cars with Balancing Constraints [J]. Industrial Engineering Journal, 2020, 23(3): 123-131.