Chinese Journal of Mechanical Engineering >

2022 , Vol. 35 >Issue 1: 12 - 12

DOI: https://doi.org/10.1186/s10033-022-00683-7

Intelligent Manufacturing Technology

Integrated Production and Transportation Scheduling Method in Hybrid Flow Shop

  • Wangming Li ,
  • Dong Han ,
  • Liang Gao ,
  • Xinyu Li ,
  • Yang Li
展开
  • The State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan, 430074, China

收稿日期: 2021-02-21

  修回日期: 2021-12-15

  网络出版日期: 2022-06-30

基金资助

Supported by National Key R & D Program of China (Grant No. 2019YFB1704603) and National Natural Science Foundation of China (Grant Nos. U21B2029 and 51825502)

收起

Integrated Production and Transportation Scheduling Method in Hybrid Flow Shop

  • Wangming Li ,
  • Dong Han ,
  • Liang Gao ,
  • Xinyu Li ,
  • Yang Li
Expand
  • The State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong University of Science and Technology, Wuhan, 430074, China

Received date: 2021-02-21

  Revised date: 2021-12-15

  Online published: 2022-06-30

Supported by

Supported by National Key R & D Program of China (Grant No. 2019YFB1704603) and National Natural Science Foundation of China (Grant Nos. U21B2029 and 51825502)

Fold

摘要

The connection between production scheduling and transportation scheduling is getting closer in smart manufacturing system, and both of those problems are summarized as NP-hard problems. However, only a few studies have considered them simultaneously. This paper solves the integrated production and transportation scheduling problem (IPTSP) in hybrid flow shops, which is an extension of the hybrid flow shop scheduling problem (HFSP). In addition to the production scheduling on machines, the transportation scheduling process on automated guided vehicles (AGVs) is considered as another optimization process. In this problem, the transfer tasks of jobs are performed by a certain number of AGVs. To solve it, we make some preparation (including the establishment of task pool, the new solution representation and the new solution evaluation), which can ensure that satisfactory solutions can be found efficiently while appropriately reducing the scale of search space. Then, an effective genetic tabu search algorithm is used to minimize the makespan. Finally, two groups of instances are designed and three types of experiments are conducted to evaluate the performance of the proposed method. The results show that the proposed method is effective to solve the integrated production and transportation scheduling problem.

关键词： Hybrid flow shop; Integrated scheduling; Task pool; Hybrid algorithm

本文引用格式

Wangming Li , Dong Han , Liang Gao , Xinyu Li , Yang Li . Integrated Production and Transportation Scheduling Method in Hybrid Flow Shop[J]. Chinese Journal of Mechanical Engineering, 2022 , 35(1) : 12 -12 . DOI: 10.1186/s10033-022-00683-7

Abstract

The connection between production scheduling and transportation scheduling is getting closer in smart manufacturing system, and both of those problems are summarized as NP-hard problems. However, only a few studies have considered them simultaneously. This paper solves the integrated production and transportation scheduling problem (IPTSP) in hybrid flow shops, which is an extension of the hybrid flow shop scheduling problem (HFSP). In addition to the production scheduling on machines, the transportation scheduling process on automated guided vehicles (AGVs) is considered as another optimization process. In this problem, the transfer tasks of jobs are performed by a certain number of AGVs. To solve it, we make some preparation (including the establishment of task pool, the new solution representation and the new solution evaluation), which can ensure that satisfactory solutions can be found efficiently while appropriately reducing the scale of search space. Then, an effective genetic tabu search algorithm is used to minimize the makespan. Finally, two groups of instances are designed and three types of experiments are conducted to evaluate the performance of the proposed method. The results show that the proposed method is effective to solve the integrated production and transportation scheduling problem.

Key words： Hybrid flow shop; Integrated scheduling; Task pool; Hybrid algorithm

参考文献

[1] Wei Qin, Zilong Zhuang, Yang Liu, et al. A two-stage ant colony algorithm for hybrid flow shop scheduling with lot sizing and calendar constraints in printed circuit board assembly. Computers & Industrial Engineering, 2019:138.
[2] Leilei Meng, Chaoyong Zhang, Xinyu Shao, et al. More MILP models for hybrid flow shop scheduling problem and its extended problems. International Journal of Production Research, 2020, 58(13):3905-3930.
[3] Quan-ke Pan, Ling Wang, Kun Mao, et al. An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process. IEEE Transactions on Automation Science and Engineering, 2013, 10(2):307-322.
[4] Biao Zhang, Quan-ke Pan, Liang Gao, et al. A three-stage multiobjective approach based on decomposition for an energy-efficient hybrid flow shop scheduling problem. IEEE Transactions on Systems, Man, and Cybernetics:Systems, 2020, 50(12):4984-4999.
[5] Xingyu Li, Baicun Wang, Chao Liu, et al. Intelligent manufacturing systems in covid-19 pandemic and beyond:Framework and impact assessment. Chinese Journal of Mechanical Engineering, 2020, 33:58.
[6] Ning Zhao, Song Ye, Kaidian Li, et al. Effective iterated greedy algorithm for flow-shop scheduling problems with time lags. Chinese Journal of Mechanical Engineering, 2017, 30(3):652-662.
[7] Lin Gui, Liang Gao, Xinyu Li. Anomalies in special permutation flow shop scheduling problems. Chinese Journal of Mechanical Engineering, 2020, 33:46.
[8] Ning Zhao, Siyu Chen, Yanhua Du. Emergency local searching approach for job shop scheduling. Chinese Journal of Mechanical Engineering, 2013, 26(5):918-927.
[9] Guomin Li, Xinyu Li, Liang Gao, et al. Tasks assigning and sequencing of multiple AGVs based on an improved harmony search algorithm. Journal of Ambient Intelligence and Humanized Computing, 2019, 10(11):4533-4546.
[10] T Miyamoto, K Inoue. Local and random searches for dispatch and conflict-free routing problem of capacitated AGV systems. Computers & Industrial Engineering, 2016, 91:1-9.
[11] Dunbing Tang, Min Dai. Energy-efficient approach to minimizing the energy consumption in an extended job-shop scheduling problem. Chinese Journal of Mechanical Engineering, 2015, 28(5):1048-1055.
[12] MK Marichelvam, T Prabaharan, Yang XS. Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan. Applied Soft Computing, 2014, 19:93-101.
[13] Ghiath Al Aqel, Xinyu Li, Liang Gao. A modified iterated greedy algorithm for flexible job shop scheduling problem. Chinese Journal of Mechanical Engineering, 2019, 32:21.
[14] G Ulusoy, Ü BILGE. Simultaneous scheduling of machines and automated guided vehicles. International Journal of Production Research, 1993, 31(12):2857-2873.
[15] A Ahmadi-Javid, P Hooshangi-Tabrizi. A mathematical formulation and anarchic society optimisation algorithms for integrated scheduling of processing and transportation operations in a flow-shop environment. International Journal of Production Research, 2015, 53(19):5988-6006.
[16] T Nishi, Y Hiranaka, I E Grossmann. A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles. Computers & Operations Research, 2011, 38(5):876-888.
[17] A Elmi, S Topaloglu. A scheduling problem in blocking hybrid flow shop robotic cells with multiple robots. Computers & Operations Research, 2013, 40(10):2543-2555.
[18] S Zabihzadeh, J Rezaeian. Two meta-heuristic algorithms for flexible flow shop scheduling problem with robotic transportation and release time. Applied Soft Computing, 2016, 40:319-330.
[19] Y Ho, H Liu. The performance of load-selection rules and pickup-dispatching rules for multiple-load AGVs. Journal of Manufacturing Systems, 2009, 28(1):1-10.
[20] S A Brah, L L Luan. Heuristics for scheduling in a flow shop with multiple processors. European Journal of Operational Research, 1999, 113(1):113-122.
[21] P Lacomme, M Larabi, N Tchernev. A disjunctive graph for the job-shop with several robots. MISTA conference, 2007:285-92.
[22] F Glover. Future paths for integer programming and links to artificial intelligence. Computers and Operations Research, 1986, 13:533-549.
[23] Victor Fernandez-Viagas, Josem Framinan. Design of a testbed for hybrid flow shop scheduling with identical machines. Computers & Industrial Engineering, 2020:141.
[24] G Ulusoy, F Sivrikaya-şerifoǧlu, Ü Bilge. A genetic algorithm approach to the simultaneous scheduling of machines and automated guided vehicles. Computers & Operations Research, 1997, 24(4):335-351.
[25] Yingli Li, Xinyu Li, Liang Gao, et al. An improved artificial bee colony algorithm for distributed heterogeneous hybrid flowshop scheduling problem with sequence-dependent setup times. Computers & Industrial Engineering, 2020:147.
[26] S Mirjalili, S M Mirjalili, A Lewis. Grey wolf optimizer. Advances in Engineering Software, 2014, 69:46-61.
[27] E Duman, M Uysal, A F Alkaya. Migrating Birds Optimization:A new metaheuristic approach and its performance on quadratic assignment problem. Information Sciences, 2012, 217:65-77.
[28] F S Şerifoğlu, G Ulusoy. Multiprocessor task scheduling in multistage hybrid flowshops:a genetic algorithm approach. Journal of the Operational Research Society, 2004, 55(5):504-512.
[29] Jamest Lin, Chun-chih Chiu, Yu-hsiang Chang. Simulation-based optimization approach for simultaneous scheduling of vehicles and machines with processing time uncertainty in FMS. Flexible Services and Manufacturing Journal, 2019, 31(1):104-141.
[30] Two groups of instances for IPTSP. https://github.com/WaminLee/Instances-For-Integrated-Scheduling-Problem. Accessed 20 February 2021.
Options
文章导航

/

〈 〉

版权所有 © 《Chinese Journal of Mechanical Engineering》编辑部

技术支持：北京玛格泰克科技发展有限公司