An Improved Genetic Algorithm for Flexible Job Shop Scheduling Problem with Multiple Time Constraints

doi:10.3969/j.issn.1007-7375.2020.02.003

Abstract

Abstract: The processing time, set-up time and transport time are considered as independent time factors in the flexible job shop scheduling model. A flexible job shop scheduling model considering multiple time constraints is established with the goal of minimum makespan, minimum total set-up time and minimum total transport time. An improved genetic algorithm is proposed to solve the model. By testing the standard data set and comparing with other literature algorithms, the feasibility and effectiveness of the improved genetic algorithm are verified.

Key words: flexible job shop scheduling, genetic algorithm, set-up time, transport time, makespan

CLC Number:

TP301

ZHANG Guohui, HU Yifan, SUN Jinghe. An Improved Genetic Algorithm for Flexible Job Shop Scheduling Problem with Multiple Time Constraints[J]. Industrial Engineering Journal, 2020, 23(2): 19-25,48.

References

[1] SHEN L, DAUZÈRE-PÉRÈS S, NEUFELD J S. Solving the flexible job shop scheduling problem with sequence-dependent setup times[J]. European Journal of Operational Research, 2017, 265(2): 503-516
[2] ROSSI A, DINI G. Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method[J]. Robotics and Computer-Integrated Manufacturing, 2007, 23(5): 503-516
[3] 杨立熙, 余慧慧. 考虑运输时间的柔性作业车间调度问题研究[J]. 武汉理工大学学报(信息与管理工程版), 2017, 39(1): 608-613
YANG Lixi, YU Huihui. Research on flexible job-shop scheduling problem with transport time consideration[J]. Journal of Wuhan University of Technology (Information & Management Engineering), 2017, 39(1): 608-613
[4] 赵宁, 李开典, 田青, 等. 考虑运输时间柔性作业车间调度问题的快速寻优方法[J]. 计算机集成制造系统, 2015, 21(3): 724-732
ZHAO Ning, LI Kaidian, TIAN Qing, et al. Fast optimization approach of flexible job shop scheduling with transport time consideration[J]. Computer Integrated Manufacturing Systems, 2015, 21(3): 724-732
[5] 朱伟. 基于规则导向的柔性作业车间多目标动态调度算法[J]. 系统工程理论与实践, 2017, 37(10): 2690-2699
ZHU Wei. Multi-objective dynamic scheduling algorithm for flexible job-shop problem based on rule orientation[J]. Systems Engineering—Theory & Practice, 2017, 37(10): 2690-2699
[6] NOURI H E, DRISS O B, GHÉDIRA K. Solving the flexible job shop problem by hybrid metaheuristics-based multiagent model[J]. Journal of Industrial Engineering International, 2018, 14(1): 1-14
[7] ZHANG G H, SHAO X Y, LI P G, et al. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem[J]. Computers & Industrial Engineering, 2009, 56(4): 1309-1318
[8] 余璇, 梁工谦, 董仲慧. 基于混合遗传禁忌搜索算法的多目标柔性作业车间调度[J]. 机械制造, 2016, 54(8): 90-93
[9] 余建军, 孙树栋, 郝京辉. 免疫算法求解多目标柔性作业车间调度研究[J]. 计算机集成制造系统, 2006, 12(10): 1643-1650
YU Jianjun, SUN Shudong, HAO Jinghui. Multi-objective flexible job-shop scheduling based on immune algorithm[J]. Computer Integrated Manufacturing Systems, 2006, 12(10): 1643-1650
[10] 李明, 雷德明. 基于新型帝国竞争算法的高维多目标柔性作业车间调度[J]. 控制理论与应用, 2019, 36(6): 893-901
LI Ming, LEI Deming. Novel imperialist competitive algorithm for many-objective flexible job shop scheduling[J]. Control Theory & Applications, 2019, 36(6): 893-901
[11] 林震, 帅剑平, 袁煜. 多目标柔性作业车间调度的多交叉策略元胞进化算法[J]. 科学技术与工程, 2017, 17(7): 74-81
LIN Zhen, SHUAI Jianping, YUAN Yu. Multi-crossover strategy of multi-objective cellular genetic algorithm research on flexible job-shop scheduling problem[J]. Science Technology and Engineering, 2017, 17(7): 74-81
[12] 张国辉, 张海军, 张理涛, 等. 改进遗传算法求解低碳约束的柔性车间调度问题[J]. 组合机床与自动化加工技术, 2018(6): 180-184
ZHANG Guohui, ZHANG Haijun, ZHANG Litao, et al. Solving the flexible job shop scheduling problem under the restriction of low carbon based on improved genetic algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2018(6): 180-184
[13] BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research, 1993, 41(3): 157-183

[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]	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.
[11]	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.
[12]	WANG Ze, YANG Xinfeng, LIU Lanfen. A Research on Vehicle Scheduling Optimization Considering Power Consumption [J]. Industrial Engineering Journal, 2020, 23(4): 140-147.
[13]	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.
[14]	ZHANG Wei, LI Pengxiang, TONG Ziqiang, YUE Yimeng. Research on Shared Bicycle Recycling Based on Distribution Prediction of Broken Vehicles and Profit and Loss Threshold Analysis [J]. Industrial Engineering Journal, 2020, 23(3): 132-137.
[15]	LI Teng, FENG Shan. A Research on A Random Scheduling Strategy of “Rack to Picker” Picking System [J]. Industrial Engineering Journal, 2020, 23(2): 59-66.