School of Computer Science, Liaocheng University, Liaocheng 252059, China
Macau Institute of Systems Engineering, Macau University of Science and Technology, Macau 999078, China
Show Author Information
Hide Author Information
Abstract
The hybrid flow shop group scheduling problem (HFGSP) with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production mode. However, there are several unresolved challenges in problem modeling and algorithmic design tailored for HFGSP. In our study, we place emphasis on the constraint of timeliness. Therefore, this paper first constructs a mixed integer linear programming model of HFGSP with sequence-dependent setup time and delivery time windows to minimize the total weighted earliness and tardiness (TWET). Then a penalty groups-assisted iterated greedy integrating idle time insertion () is proposed to solve the above problem. In the , a double decoding strategy is proposed based on the earliest available machine rule and the idle time insertion rule to calculate the TWET value. Subsequently, to reduce the amount of computation, a skip-based destruction and reconstruction strategy is designed, and a penalty groups-assisted local search is proposed to further improve the quality of the solution by disturbing the penalized groups, i.e., early and tardy groups. Finally, through comprehensive statistical experiments on 270 test instances, the results prove that the proposed algorithm is effective compared to four state-of-the-art algorithms.
No abstract is available for this article. Click the button above to view the PDF directly.
References
[1]
F. Zhao, B. Zhu, and L. Wang, An estimation of distribution algorithm-based hyper-heuristic for the distributed assembly mixed No-idle permutation flowshop scheduling problem, IEEE Trans. Syst. Man Cybern. Syst., vol. 53, no. 9, pp. 5626–5637, 2023.
L. Wang, Z. Pan, and J. Wang, A review of reinforcement learning based intelligent optimization for manufacturing scheduling, Complex System Modeling and Simulation, vol. 1, no. 4, pp. 257–270, 2021.
Y. Fu, Y. Hou, Z. Wang, X. Wu, K. Gao, and L. Wang, Distributed scheduling problems in intelligent manufacturing systems, Tsinghua Science and Technology, vol. 26, no. 5, pp. 625–645, 2021.
D. Laha and U. K. Chakraborty, Minimising total flow time in permutation flow shop scheduling using a simulated annealing-based approach, Int. J. Autom. Contr., vol. 4, no. 4, p. 359, 2010.
Y. Wang, Y. Wang, Y. Han, J. Li, K. Gao, and Y. Nojima, Intelligent optimization under multiple factories: Hybrid flow shop scheduling problem with blocking constraints using an advanced iterated greedy algorithm, Complex System Modeling and Simulation, vol. 3, no. 4, pp. 282–306, 2023.
E. Jiang, L. Wang, and J. Wang, Decomposition-based multi-objective optimization for energy-aware distributed hybrid flow shop scheduling with multiprocessor tasks, Tsinghua Science and Technology, vol. 26, no. 5, pp. 646–663, 2021.
X. Zhang, B. Zhang, L. Meng, Y. Ren, R. Meng, and J. Li, An evolutionary algorithm for a hybrid flowshop scheduling problem with consistent sublots, Int. J. Autom. Contr., vol. 16, no. 1, pp. 19–44, 2022.
X. He, S. Dong, and N. Zhao, Research on rush order insertion rescheduling problem under hybrid flow shop based on NSGA-III, Int. J. Prod. Res., vol. 58, no. 4, pp. 1161–1177, 2020.
A. Mendoza-Mendoza, W. Ospino-Castro, and D. Romero-Martínez, Production scheduling in a flexible hybrid flow shop in the food industry based on the theory of constraints, Int. J. Eng. Res. Afr., vol. 52, pp. 124–136, 2021.
R. Pugazhenthi, M. A. Xavior, and R. Saravanan, A case study on effect of grouping technique in a multi-stage hybrid flow shop, Int. J. Comput. Sci. Math., vol. 7, no. 1, pp. 42–53, 2016.
S. L. Jiang, C. Xu, L. Zhang, and Y. Ma, A decomposition-based two-stage online scheduling approach and its integrated system in the hybrid flow shop of steel industry, Expert Syst. Appl., vol. 213, p. 119200, 2023.
M. Baxendale, J. M. McGree, A. Bellette, and P. Corry, Machine-based production scheduling for rotomoulded plastics manufacturing, Int. J. Prod. Res., vol. 59, no. 5, pp. 1301–1318, 2021.
N. Salmasi, R. Logendran, and M. R. Skandari, Total flow time minimization in a flowshop sequence-dependent group scheduling problem, Comput. Oper. Res., vol. 37, no. 1, pp. 199–212, 2010.
A. D. Wilson, R. E. King, and T. J. Hodgson, Scheduling non-similar groups on a flow line: Multiple group setups, Robot. Comput. Integr. Manuf., vol. 20, no. 6, pp. 505–515, 2004.
Y. Wang, Y. Han, Q. K. Pan, H. Li, and Y. Wang, Redefining hybrid flow shop group scheduling: Unveiling a novel hybrid modeling paradigm and assessing 48 MILP and CP models, Swarm Evol. Comput., vol. 83, p. 101416, 2023.
Y. Wang, Y. Han, Y. Wang, Q. K. Pan, and L. Wang, Sustainable scheduling of distributed flow shop group: A collaborative multi-objective evolutionary algorithm driven by indicators, IEEE Trans. Evol. Comput.
[17]
F. Zhao, G. Zhou, and L. Wang, A cooperative scatter search with reinforcement learning mechanism for the distributed permutation flowshop scheduling problem with sequence-dependent setup times, IEEE Trans. Syst. Man Cybern. Syst., vol. 53, no. 8, pp. 4899–4911, 2023.
H. Qin, Y. Han, Y. Wang, Y. Liu, J. Li, and Q. Pan, Intelligent optimization under blocking constraints: A novel iterated greedy algorithm for the hybrid flow shop group scheduling problem, Knowl. Based Syst., vol. 258, p. 109962, 2022.
A. Missaoui and Y. Boujelbene, An effective iterated greedy algorithm for blocking hybrid flow shop problem with due date window, RAIRO-Oper. Res., vol. 55, no. 3, pp. 1603–1616, 2021.
F. Zhao, H. Zhang, and L. Wang, A pareto-based discrete jaya algorithm for multiobjective carbon-efficient distributed blocking flow shop scheduling problem, IEEE Trans. Ind. Inform., vol. 19, no. 8, pp. 8588–8599, 2023.
B. Zhang, L. L. Meng, C. Lu, Y. Y. Han, and H. Y. Sang, Automatic design of constructive heuristics for a reconfigurable distributed flowshop group scheduling problem, Comput. Oper. Res., vol. 161, p. 106432, 2024.
Z. Y. Wang, Q. K. Pan, L. Gao, and Y. L. Wang, An effective two-stage iterated greedy algorithm to minimize total tardiness for the distributed flowshop group scheduling problem, Swarm Evol. Comput., vol. 74, p. 101143, 2022.
R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, vol. 5, pp. 287–326, 1979.
W. K. Yeung, C. Oğuz, and T. C. Edwin Cheng, Two-stage flowshop earliness and tardiness machine scheduling involving a common due window, Int. J. Prod. Econ., vol. 90, no. 3, pp. 421–434, 2004.
B. de Athayde Prata and H. Y. Fuchigami, A genetic iterated greedy algorithm for the blocking flowshop to minimize total earliness and tardiness, J. Intell. Manuf.
[26]
X. L. Jing, Q. K. Pan, L. Gao, and L. Wang, An effective iterated greedy algorithm for a robust distributed permutation flowshop problem with carryover sequence-dependent setup time, IEEE Trans. Syst. Man Cybern. Syst., vol. 52, no. 9, pp. 5783–5794, 2022.
Y. Hou, Y. Fu, K. Gao, H. Zhang, and A. Sadollah, Modelling and optimization of integrated distributed flow shop scheduling and distribution problems with time windows, Expert Syst. Appl., vol. 187, p. 115827, 2022.
Q. K. Pan, R. Ruiz, and P. Alfaro-Fernández, Iterated search methods for earliness and tardiness minimization in hybrid flowshops with due windows, Comput. Oper. Res., vol. 80, pp. 50–60, 2017.
A. Khare and S. Agrawal, Scheduling hybrid flowshop with sequence-dependent setup times and due windows to minimize total weighted earliness and tardiness, Comput. Ind. Eng., vol. 135, pp. 780–792, 2019.
A. Missaoui and R. Ruiz, A parameter-Less iterated greedy method for the hybrid flowshop scheduling problem with setup times and due date windows, Eur. J. Oper. Res., vol. 303, no. 1, pp. 99–113, 2022.
J. Behnamian, M. Zandieh, and S. M. T. Fatemi Ghomi, Due windows group scheduling using an effective hybrid optimization approach, Int. J. Adv. Manuf. Technol., vol. 46, pp. 721–735, 2010, .
M. Zandieh, B. Dorri, and A. R. Khamseh, Robust metaheuristics for group scheduling with sequence-dependent setup times in hybrid flexible flow shops, Int. J. Adv. Manuf. Technol., vol. 43, nos. 7&8, pp. 767–778, 2009.
O. Shahvari, N. Salmasi, R. Logendran, and B. Abbasi, An efficient tabu search algorithm for flexible flow shop sequence-dependent group scheduling problems, Int. J. Prod. Res., vol. 50, no. 15, pp. 4237–4254, 2012.
S. Yuan, T. Li, and B. Wang, A co-evolutionary genetic algorithm for the two-machine flow shop group scheduling problem with job-related blocking and transportation times, Expert Syst. Appl., vol. 152, p. 113360, 2020.
T. Keshavarz, N. Salmasi, and M. Varmazyar, Minimizing total completion time in the flexible flowshop sequence-dependent group scheduling problem, Ann. Oper. Res., vol. 226, no. 1, pp. 351–377, 2015.
H. X. Qin, Y. Y. Han, B. Zhang, L. L. Meng, Y. P. Liu, Q. K. Pan, and D. W. Gong, An improved iterated greedy algorithm for the energy-efficient blocking hybrid flow shop scheduling problem, Swarm Evol. Comput., vol. 69, p. 100992, 2022.
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.
X. Han, Y. Han, Q. Chen, J. Li, H. Sang, Y. Liu, Q. Pan, and Y. Nojima, Distributed flow shop scheduling with sequence-dependent setup times using an improved iterated greedy algorithm, Complex System Modeling and Simulation, vol. 1, no. 3, pp. 198–217, 2021.
C. Lu, Q. Liu, B. Zhang, and L. Yin, A Pareto-based hybrid iterated greedy algorithm for energy-efficient scheduling of distributed hybrid flowshop, Expert Syst. Appl., vol. 204, p. 117555, 2022.
F. Zhao, C. Zhuang, L. Wang, and C. Dong, An iterative greedy algorithm with Q-learning mechanism for the multiobjective distributed No-idle permutation flowshop scheduling, IEEE Trans. Syst. Man Cybern. Syst., vol. 54, no. 5, pp. 3207–3219, 2024.
H. X. Qin, Y. Y. Han, Y. P. Liu, J. Q. Li, Q. K. Pan, and X. Han, A collaborative iterative greedy algorithm for the scheduling of distributed heterogeneous hybrid flow shop with blocking constraints, Expert Syst. Appl., vol. 201, p. 117256, 2022.
Y. Wang, Y. Han, Y. Wang, J. Li, K. Gao, and Y. Liu, An effective two-stage iterated greedy algorithm for distributed flowshop group scheduling problem with setup time, Expert Syst. Appl., vol. 233, p. 120909, 2023.
Y. Wang, Y. Han, Y. Wang, M. F. Tasgetiren, J. Li, and K. Gao, Intelligent optimization under the makespan constraint: Rapid evaluation mechanisms based on the critical machine for the distributed flowshop group scheduling problem, Eur. J. Oper. Res., vol. 311, no. 3, pp. 816–832, 2023.
F. Yu, C. Lu, J. Zhou, and L. Yin, Mathematical model and knowledge-based iterated greedy algorithm for distributed assembly hybrid flow shop scheduling problem with dual-resource constraints, Expert Syst. Appl., vol. 239, p. 122434, 2024.
S. Aqil and K. Allali, Local search metaheuristic for solving hybrid flow shop problem in slabs and beams manufacturing, Expert Syst. Appl., vol. 162, p. 113716, 2020.
H. Qin, Y. Han, Q. Chen, J. Li, and H. Sang, A double level mutation iterated greedy algorithm for blocking hybrid flow shop scheduling, Control Decis., vol. 37, no. 9, pp. 2323–2332, 2022.
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.
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.
M. Nawaz, E. E. Enscore Jr, and I. Ham, A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, vol. 11, no. 1, pp. 91–95, 1983.
V. N. Nair, B. Abraham, J. MacKay, G. Box, R. N. Kacker, T. J. Lorenzen, J. M. Lucas, R. H. Myers, G. G. Vining, J. A. Nelder, et al., Taguchi’s parameter design: A panel discussion, Technometrics, vol. 34, no. 2, pp. 127–161, 1992.
Ji Q, Han Y, Wang Y, et al. A Penalty Groups-Assisted Iterated Greedy Integrating Idle Time Insertion: Solving the Hybrid Flow Shop Group Scheduling with Delivery Time Windows. Complex System Modeling and Simulation, 2024, 4(2): 137-165. https://doi.org/10.23919/CSMS.2024.0005
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/).
