Journal Home > Volume 1 , Issue 3
Complex System Modeling and Simulation 2021, 1(3): 198-217 https://doi.org/10.23919/CSMS.2021.0018
Open Access | Issue | Published: 29 October 2021

Distributed Flow Shop Scheduling with Sequence-Dependent Setup Times Using an Improved Iterated Greedy Algorithm

Show Author's Information Xue Han1,  Yuyan Han1( ),  Qingda Chen2,  Junqing Li3,  Hongyan Sang1,  Yiping Liu4,  Quanke Pan5,  Yusuke Nojima6
School of Computer Science, Liaocheng University, Liaocheng 252000, China
State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang 110819, China
School of Information Science and Engineering, Shandong Normal University, Jinan 252000, China
College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China
School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072, China
Department of Computer Science and Intelligent Systems, Osaka Prefecture University, Osaka 599-8531, Japan
Keywords:
distributed permutation flow shop, iterated greedy, local search, swapping strategy
Cite this article:
Han X, Han Y, Chen Q, et al. Distributed Flow Shop Scheduling with Sequence-Dependent Setup Times Using an Improved Iterated Greedy Algorithm. Complex System Modeling and Simulation, 2021, 1(3): 198-217. https://doi.org/10.23919/CSMS.2021.0018
Download citation
EndNote(RIS)
BibTeX

1077

Views

102

Downloads

Citations

87

Crossref

N/A

WoS

84

Scopus

N/A

CSCD

Abstract Full text About this article

To meet the multi-cooperation production demand of enterprises, the distributed permutation flow shop scheduling problem (DPFSP) has become the frontier research in the field of manufacturing systems. In this paper, we investigate the DPFSP by minimizing a makespan criterion under the constraint of sequence-dependent setup times. To solve DPFSPs, significant developments of some metaheuristic algorithms are necessary. In this context, a simple and effective improved iterated greedy (NIG) algorithm is proposed to minimize makespan in DPFSPs. According to the features of DPFSPs, a two-stage local search based on single job swapping and job block swapping within the key factory is designed in the proposed algorithm. We compare the proposed algorithm with state-of-the-art algorithms, including the iterative greedy algorithm (2019), iterative greedy proposed by Ruiz and Pan (2019), discrete differential evolution algorithm (2018), discrete artificial bee colony (2018), and artificial chemical reaction optimization (2017). Simulation results show that NIG outperforms the compared algorithms.


menu
Abstract
Full text
Outline
About this article

Distributed Flow Shop Scheduling with Sequence-Dependent Setup Times Using an Improved Iterated Greedy Algorithm

Show Author's information Xue Han1, Yuyan Han1( ), Qingda Chen2, Junqing Li3, Hongyan Sang1, Yiping Liu4, Quanke Pan5, Yusuke Nojima6
School of Computer Science, Liaocheng University, Liaocheng 252000, China
State Key Laboratory of Synthetical Automation for Process Industries, Northeastern University, Shenyang 110819, China
School of Information Science and Engineering, Shandong Normal University, Jinan 252000, China
College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China
School of Mechatronic Engineering and Automation, Shanghai University, Shanghai 200072, China
Department of Computer Science and Intelligent Systems, Osaka Prefecture University, Osaka 599-8531, Japan

Abstract

To meet the multi-cooperation production demand of enterprises, the distributed permutation flow shop scheduling problem (DPFSP) has become the frontier research in the field of manufacturing systems. In this paper, we investigate the DPFSP by minimizing a makespan criterion under the constraint of sequence-dependent setup times. To solve DPFSPs, significant developments of some metaheuristic algorithms are necessary. In this context, a simple and effective improved iterated greedy (NIG) algorithm is proposed to minimize makespan in DPFSPs. According to the features of DPFSPs, a two-stage local search based on single job swapping and job block swapping within the key factory is designed in the proposed algorithm. We compare the proposed algorithm with state-of-the-art algorithms, including the iterative greedy algorithm (2019), iterative greedy proposed by Ruiz and Pan (2019), discrete differential evolution algorithm (2018), discrete artificial bee colony (2018), and artificial chemical reaction optimization (2017). Simulation results show that NIG outperforms the compared algorithms.

Keywords: distributed permutation flow shop, iterated greedy, local search, swapping strategy

References(47)

[1]

B. Naderi and R. Ruiz, The distributed permutation flowshop scheduling problem, Comput. Oper. Res., vol. 37, no. 4, pp. 754–768, 2010.
DOI Google Scholar
[2]

Y. P. Fu, Y. S. Hou, Z. F. Wang, X. W. Wu, K. Z. Gao, and L. Wang, Distributed scheduling problems in intelligent manufacturing systems, Tsinghua Sci. Technol., vol. 26, no. 5, pp. 625–645, 2021.
DOI Google Scholar
[3]

S. Parthasarathy and C. Rajendran, An experimental evaluation of heuristics for scheduling in a real-life flowshop with sequence-dependent setup times of jobs, Int. J. Prod. Econom., vol. 49, no. 3, pp. 255–263, 1997.
DOI Google Scholar
[4]

S. Y. Wang, L. Wang, M. Liu, and Y. Xu, An effective estimation of distribution algorithm for solving the distributed permutation flow-shop scheduling problem, Int. J. Prod. Econ., vol. 145, no. 1, pp. 387–396, 2013.
DOI Google Scholar
[5]

H. Bargaoui, O. B. Driss, and K. Ghédira, A novel chemical reaction optimization for the distributed permutation flowshop scheduling problem with makespan criterion, Comput. Ind. Eng., vol. 111, pp. 239–250, 2017.
DOI Google Scholar
[6]

J. P. Huang, Q. K. Pan, Z. H. Miao, and L. Gao, Effective constructive heuristics and discrete bee colony optimization for distributed flowshop with setup times, Eng. Appl. Artif. Intell., vol. 97, p. 104016, 2021.
DOI Google Scholar
[7]

R. Ruiz, Q. K. Pan, and B. Naderi, Iterated Greedy methods for the distributed permutation flowshop scheduling problem, Omega, vol. 83, pp. 213–222, 2019.
DOI Google Scholar
[8]

J. P. Huang, Q. K. Pan, and L. Gao, An effective iterated greedy method for the distributed permutation flowshop scheduling problem with sequence-dependent setup times, Swarm Evol. Comput., vol. 59, p. 100742, 2020.
DOI Google Scholar
[9]
H. X. Qin, Y. Y. Han, Q. D. Chen, J. Q. Li, and H. Y. Sang, A double level mutation iterated greedy algorithm for blocking hybrid flow shop scheduling, (in Chinese), Control Decision, doi: 10.13195/j.kzyjc.2021.0607.
[10]

K. Sörensen, Metaheuristics—The metaphor exposed, Int. Trans. Oper. Res., vol. 22, no. 1, pp. 3–18, 2015.
DOI Google Scholar
[11]

B. Naderi and R. Ruiz, A scatter search algorithm for the distributed permutation flowshop scheduling problem, Eur. J. Oper. Res., vol. 239, no. 2, pp. 323–334, 2014.
DOI Google Scholar
[12]

F. Q. Zhao, L. X. Zhao, L. Wang, and H. B. Song, An ensemble discrete differential evolution for the distributed blocking flowshop scheduling with minimizing Makespan Criterion, Expert Syst. Appl., vol. 160, p. 113678, 2020.
DOI Google Scholar
[13]

T. Meng, Q. K. Pan, and L. Wang, A distributed permutation flowshop scheduling problem with the customer order constraint, Knowledge-Based Syst., vol. 184, p. 104894, 2019.
DOI Google Scholar
[14]

Y. L. Li, F. Li, Q. K. Pan, L. Gao, and M. F. Tasgetiren, An artificial bee colony algorithm for the distributed hybrid flowshop scheduling problem, Procedia Manuf., vol. 39, pp. 1158–1166, 2019.
DOI Google Scholar
[15]

V. Fernandez-Viagas, P. Perez-Gonzalez, and J. M. Framinan, The distributed permutation flow shop to minimise the total flowtime, Comput. Ind. Eng., vol. 118, pp. 464–477, 2018.
DOI Google Scholar
[16]

Q. K. Pan, L. Gao, L. Wang, J. Liang, and X. Y. Li, Effective heuristics and metaheuristics to minimize total flowtime for the distributed permutation flowshop problem, Expert Syst. Appl., vol. 124, pp. 309–324, 2019.
DOI Google Scholar
[17]

Z. Q. Zhang, B. Qian, R. Hu, H. P. Jin, and L. Wang, A matrix-cube-based estimation of distribution algorithm for the distributed assembly permutation flow-shop scheduling problem, Swarm Evol. Comput., vol. 60, p. 100785, 2021.
DOI Google Scholar
[18]

H. B. Song and J. Lin, A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times, Swarm Evol. Comput., vol. 60, p. 100807, 2021.
DOI Google Scholar
[19]

J. Deng and L. Wang, A competitive memetic algorithm for multi-objective distributed permutation flow shop scheduling problem, Swarm Evol. Comput., vol. 32, pp. 121–131, 2017.
DOI Google Scholar
[20]

G. C. Wang, X. Y. Li, L. Gao, and P. G. Li, A multi-objective whale swarm algorithm for energy-efficient distributed permutation flow shop scheduling problem with sequence dependent setup times, IFAC-PapersOnLine, vol. 52, no. 13, pp. 235–240, 2019.
DOI Google Scholar
[21]

G. C. Wang, L. Gao, X. Y. Li, P. G. Li, and M. F. Tasgetiren, Energy-efficient distributed permutation flow shop scheduling problem using a multi-objective whale swarm algorithm, Swarm Evol. Comput., vol. 57, p. 100716, 2020.
DOI Google Scholar
[22]

J. F. Chen, L. Wang, and Z. P. Peng, A collaborative optimization algorithm for energy-efficient multi-objective distributed no-idle flow-shop scheduling, Swarm Evol. Comput., vol. 50, p. 100557, 2019.
DOI Google Scholar
[23]

M. Mirabi, Ant colony optimization technique for the sequence-dependent flowshop scheduling problem, Int. J. Adv. Manuf. Technol., vol. 55, nos. 1–4, pp. 317–326, 2011.
DOI Google Scholar
[24]

R. Vanchipura, R. Sridharan, and A. S. Babu, Improvement of constructive heuristics using variable neighbourhood descent for scheduling a flow shop with sequence dependent setup time, J. Manuf. Syst., vol. 33, no. 1, pp. 65–75, 2014.
DOI Google Scholar
[25]

A. Sioud and C. Gagné, Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times, Eur. J. Oper. Res., vol. 264, no. 1, pp. 66–73, 2018.
DOI Google Scholar
[26]

M. S. Nagano, H. H. Miyata, and D. C. Araújo, A constructive heuristic for total flowtime minimization in a no-wait flowshop with sequence-dependent setup times, J. Manuf. Syst., vol. 36, pp. 224–230, 2015.
DOI Google Scholar
[27]

F. Q. Zhao, L. X. Zhang, Y. Zhang, W. M. Ma, C. Zhang, and H. B. Song, A hybrid discrete water wave optimization algorithm for the no-idle flowshop scheduling problem with total tardiness criterion, Expert Syst. Appl., vol. 146, p. 113166, 2020.
DOI Google Scholar
[28]

H. R. Li, X. Y. Li, and L. Gao, A discrete artificial bee colony algorithm for the distributed heterogeneous no-wait flowshop scheduling problem, Appl. Soft Comput., vol. 100, p. 106946, 2021.
DOI Google Scholar
[29]

Y. L. Li, X. Y. Li, L. Gao, and L. L. Meng, An improved artificial bee colony algorithm for distributed heterogeneous hybrid flowshop scheduling problem with sequence-dependent setup times, Comput. Ind. Eng., vol. 147, p. 106638, 2020.
DOI Google Scholar
[30]

F. Q. Zhao, L. X. Zhang, J. Cao, and J. X. Tang, A cooperative water wave optimization algorithm with reinforcement learning for the distributed assembly no-idle flowshop scheduling problem, Comput. Ind. Eng., vol. 153, p. 107082, 2021.
DOI Google Scholar
[31]

Z. S. Shao, W. S. Shao, and D. C. Pi, Effective constructive heuristic and metaheuristic for the distributed assembly blocking flow-shop scheduling problem, Appl. Intell., vol. 50, no. 12, pp. 4647–4669, 2020.
DOI Google Scholar
[32]

R. Ruiz and T. Stützle, A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, Eur. J. Oper. Res., vol. 177, no. 3, pp. 2033–2049, 2007.
DOI Google Scholar
[33]

V. Fernandez-Viagas, R. Ruiz, and J. M. Framinan, A new vision of approximate methods for the permutation flowshop to minimise makespan: State-of-the-art and computational evaluation, Eur. J. Oper. Res., vol. 257, no. 3, pp. 707–721, 2017.
DOI Google Scholar
[34]

S. W. Lin, K. C. Ying, and C. Y. Huang, Minimising makespan in distributed permutation flowshops using a modified iterated greedy algorithm, Int. J. Prod. Res., vol. 51, no. 16, pp. 5029–5038, 2013.
DOI Google Scholar
[35]

V. Fernandez-Viagas and J. M. Framinan, A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem, Int. J. Prod. Res., vol. 53, no. 4, pp. 1111–1123, 2015.
DOI Google Scholar
[36]

Q. K. Pan and R. Ruiz, An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem, Omega, vol. 44, pp. 41–50, 2014.
DOI Google Scholar
[37]

J. Y. Ding, S. J. Song, J. N. D. Gupta, R. Zhang, R. Chiong, and C. Wu, An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem, Appl. Soft Comput., vol. 30, pp. 604–613, 2015.
DOI Google Scholar
[38]

V. Fernandez-Viagas and J. M. Framinan, A best-of-breed iterated greedy for the permutation flowshop scheduling problem with makespan objective, Comput. Oper. Res., vol. 112, p. 104767, 2019.
DOI Google Scholar
[39]
J. Y. Mao, X. L. Hu, Q. K. Pan, Z. H. Miao, C. X. He, and M. F. Tasgetiren, An iterated greedy algorithm for the distributed permutation flowshop scheduling problem with preventive maintenance to minimize total flowtime, in 2020 39th Chinese Control Conf., (CCC), Shenyang, China, 2020, pp. 1507−1512.
[40]

K. C. Ying, S. W. Lin, and C. Y. Huang, Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic, Expert Syst. Appl., vol. 36, no. 3, pp. 7087–7092, 2009.
DOI Google Scholar
[41]

X. L. Jing, Q. K. Pan, L. Gao, and Y. L. Wang, An effective Iterated Greedy algorithm for the distributed permutation flowshop scheduling with due windows, Appl. Soft Comput., vol. 96, p. 106629, 2020.
DOI Google Scholar
[42]

W. S. Shao, D. C. Pi, and Z. S. Shao, Local search methods for a distributed assembly no-idle flow shop scheduling problem, IEEE Syst. J., vol. 13, no. 2, pp. 1945–1956, 2019.
DOI Google Scholar
[43]

D. P. Ronconi, A note on constructive heuristics for the flowshop problem with blocking, Int. J. Prod. Econ., vol. 87, no. 1, pp. 39–48, 2004.
DOI Google Scholar
[44]
Z. K. Zhang and Q. H. Tang, Integrating preventive maintenance to two-stage assembly flow shop scheduling: MILP model, constructive heuristics and meta-heuristics, Flex. Serv. Manuf. J., doi: 10.1007/s10696-021-09403-0.
[45]

S. Hatami, R. Ruiz, and C. Andrés-Romano, Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times, Int. J. Prod. Econ., vol. 169, pp. 76–88, 2015.
DOI Google Scholar
[46]
J. Q. Pan, W. Q. Zou, and J. H. Duan, A discrete artificial bee colony for distributed permutation flowshop scheduling problem with total flow time minimization, in 2018 37th Chinese Control Conf. (CCC), Wuhan, China, 2018, pp. 8379−8383.
[47]

G. H. Zhang, K. Y. Xing, and F. Cao, Discrete differential evolution algorithm for distributed blocking flowshop scheduling with makespan criterion, Eng. Appl. Artif. Intell., vol. 76, pp. 96–107, 2018.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 31 May 2021
Revised: 13 July 2021
Accepted: 15 August 2021
Published: 29 October 2021
Issue date: September 2021

Copyright

© The author(s) 2021

Acknowledgements

Acknowledgements

This work was jointly supported by the National Natural Science Foundation of China (Nos. 61803192, 61973203, 61966012, 61773192, 61603169, 61773246, and 71533001). Thanks for the support of Shandong province colleges and universities youth innovationtalent introduction and education program.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return