An improved iterated greedy algorithm for distributed robotic flowshop scheduling with order constraints. (February 2022) - Li, Wenhan; Chen, Xiaolong; Li, Junqing; Sang, Hongyan; Han, Yuyan; Du, Shubo
Highlights: The DPFSP with order and robot constraints is investigated. An improved iterated greedy (IIG) algorithm is proposed to minimize makespan. Several order assignment strategies and neighborhood structures are developed. The simulated annealing (SA) algorithm is embedded to enhance the search ability. Abstract: Research in robotic scheduling has gained significant focus, especially for multi-factory manufacturing systems. In addition, production orders should be considered during the scheduling procedure. Therefore, this study considers an extension of the distributed permutation flow shop problem (DPFSP) with order constraints, in which the jobs of the same production order must be assigned to the same factory. Each factory has a single robot responsible for transporting jobs, and the deterioration time constraint is also considered. The objective is to minimize the maximum completion time of all factories. To this end, an improved iterated greedy (IIG) algorithm is investigated to solve the DPFSP with both robotic transportation and order constraints. In the proposed algorithm, each solution is represented by a two-dimensional vector to report the order assignment and the factory assignment. Next, an efficient decoding heuristic is developed to consider the robot routing during the transportation process. Then, an improved destruction and construction approach is embedded in the proposed algorithm to improve the computational complexity. Four problem-specific neighbourhood search operators are designed to enhance the local search abilities. Finally, the simulated annealing (SA) algorithm is embedded as the acceptance criterion to improve the exploration search abilities. The IIG algorithm is compared with several efficient algorithms in the literature, and the experimental results show the competitive performance of the proposed algorithm.