Modeling and optimization of the hybrid flow shop scheduling problem with sequence-dependent setup times

Abstract: The hybrid flow shop scheduling problem (HFSP) is an extension of the classic flow shop scheduling problem and widely exists in real industrial production systems. In real production, sequence-dependent setup times (SDST) are very important and cannot be neglected. Therefore, this study focuses HFSP with SDST (HFSP-SDST) to minimize the makespan. To solve this problem, a mixed-integer linear programming (MILP) model to obtain the optimal solutions for small-scale instances is proposed. Given the NP-hard characteristics of HFSP-SDST, an improved artificial bee colony (IABC) algorithm is developed to efficiently solve large-sized instances. In IABC, permutation encoding is used and a hybrid representation that combines forward decoding and backward decoding methods is designed. To search for the solution space that is not included in the encoding and decoding, a problem-specific local search strategy is developed to enlarge the solution space. Experiments are conducted to evaluate the effectiveness of the MILP model and IABC. The results indicate that the proposed MILP model can find the optimal solutions for small-scale instances. The proposed IABC performs much better than the existing algorithms and improves 61 current best solutions of benchmark instances.

How to cite this paper

 Xue, H., Meng, L., Duan, P., Zhang, B., Zou, W & Sang, H. (2024). Modeling and optimization of the hybrid flow shop scheduling problem with sequence-dependent setup times.International Journal of Industrial Engineering Computations , 15(2), 473-490.

Refrences

Allahverdi, A. (2015). The third comprehensive survey on scheduling problems with setup times/costs. European journal of operational research, 246(2), 345-378.
Behnamian, J., & Ghomi, S. F. (2011). Hybrid flowshop scheduling with machine and resource-dependent processing times. Applied Mathematical Modelling, 35(3), 1107-1123.
Dai, L.-L., Pan, Q.-K., Miao, Z.-H., Suganthan, P. N., & Gao, K.-Z. (2023). Multi-Objective Multi-Picking-Robot Task Allocation: Mathematical Model and Discrete Artificial Bee Colony Algorithm. IEEE Transactions on Intelligent Transportation Systems.
Engin, O., & Döyen, A. (2004). A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future generation computer systems, 20(6), 1083-1095.
Fan, J., Li, Y., Xie, J., Zhang, C., Shen, W., & Gao, L. (2021). A hybrid evolutionary algorithm using two solution representations for hybrid flow-shop scheduling problem. IEEE Transactions on Cybernetics.
Fattahi, P., Hosseini, S. M. H., Jolai, F., & Tavakkoli-Moghaddam, R. (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations. Applied Mathematical Modelling, 38(1), 119-134.
Garey, M. R., & Johnson, D. S. (1978). ``strong''np-completeness results: Motivation, examples, and implications. Journal of the ACM (JACM), 25(3), 499-508.
Gómez-Gasquet, P., Andrés, C., & Lario, F.-C. (2012). An agent-based genetic algorithm for hybrid flowshops with sequence dependent setup times to minimise makespan. Expert Systems with Applications, 39(9), 8095-8107.
Gupta, J. N. (1986). Flowshop schedules with sequence dependent setup times. Journal of the Operations Research Society of Japan, 29(3), 206-219.
He, X., Pan, Q.-K., Gao, L., Neufeld, J. S., & Gupta, J. N. (2024). Historical information based iterated greedy algorithm for distributed flowshop group scheduling problem with sequence-dependent setup times. Omega, 123, 102997.
Jemmali, M., & Hidri, L. (2023). Hybrid Flow Shop with Setup Times Scheduling Problem. Comput. Syst. Sci. Eng, 44, 563-577.
Johnson, S. M. (1954). Optimal two‐and three‐stage production schedules with setup times included. Naval research logistics quarterly, 1(1), 61-68.
Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., & Werner, F. (2005). An evaluation of sequencing heuristics for flexible flowshop scheduling problems with unrelated parallel machines and dual criteria. Otto-von-Guericke-Universitat Magdeburg, 28(05), 1-23.
Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., & Werner, F. (2008). Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. The International Journal of Advanced Manufacturing Technology, 37, 354-370.
Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization. Retrieved from
Karaboga, D., & Basturk, B. (2008). On the performance of artificial bee colony (ABC) algorithm. Applied Soft Computing, 8(1), 687-697.
Khare, A., & Agrawal, S. (2019). Scheduling hybrid flowshop with sequence-dependent setup times and due windows to minimize total weighted earliness and tardiness. Computers & Industrial Engineering, 135, 780-792.
Kurz, M. E., & Askin, R. G. (2003). Comparing scheduling rules for flexible flow lines. International Journal of Production Economics, 85(3), 371-388.
Lee, G.-C., Hong, J. M., & Choi, S.-H. (2015). Efficient heuristic algorithm for scheduling two-stage hybrid flowshop with sequence-dependent setup times. Mathematical Problems in Engineering, 2015.
Liao, C.-J., Tjandradjaja, E., & Chung, T.-P. (2012). An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem. Applied Soft Computing, 12(6), 1755-1764.
Liao, Y., Zhantao, L., Li, X., & Chenfeng, P. (2022). Heuristics for the Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup times. Mathematical Problems in Engineering, 2022.
Meng, L., Duan, P., Gao, K., Zhang, B., Zou, W., Han, Y., & Zhang, C. (2024). MIP modeling of energy-conscious FJSP and its extended problems: From simplicity to complexity. Expert Systems with Applications, 241, 122594.
Meng, L., Gao, K., Ren, Y., Zhang, B., Sang, H., & Chaoyong, Z. (2022). Novel MILP and CP models for distributed hybrid flowshop scheduling problem with sequence-dependent setup times. Swarm and Evolutionary Computation, 71, 101058.
Meng, L., Zhang, C., Ren, Y., Zhang, B., & Lv, C. (2020). Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem. Computers & Industrial Engineering, 142, 106347.
Meng, L., Zhang, C., Zhang, B., Gao, K., Ren, Y., & Sang, H. (2023). MILP modeling and optimization of multi-objective flexible job shop scheduling problem with controllable processing times. Swarm and Evolutionary Computation, 82, 101374.
Naderi, B., Zandieh, M., Balagh, A. K. G., & Roshanaei, V. (2009). An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert Systems with Applications, 36(6), 9625-9633.
Nishi, T., Hiranaka, Y., & Inuiguchi, M. (2010). Lagrangian relaxation with cut generation for hybrid flowshop scheduling problems to minimize the total weighted tardiness. Computers & Operations Research, 37(1), 189-198.
Ozsoydan, F. B., & Sağir, M. (2021). Iterated greedy algorithms enhanced by hyper-heuristic based learning for hybrid flexible flowshop scheduling problem with sequence dependent setup times: a case study at a manufacturing plant. Computers & Operations Research, 125, 105044.
Pan, Q.-K., & Dong, Y. (2014). An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimisation. Information Sciences, 277, 643-655.
Pan, Q.-K., Gao, L., Li, X.-Y., & Gao, K.-Z. (2017). Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times. Applied Mathematics and Computation, 303, 89-112.
Pan, Q.-K., Wang, L., Li, J.-Q., & Duan, J.-H. (2014). A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation. Omega, 45, 42-56.
Pan, Q.-K., Wang, L., Mao, K., Zhao, J.-H., & Zhang, M. (2012). An effective artificial bee colony algorithm for a real-world hybrid flowshop problem in steelmaking process. IEEE Transactions on Automation Science and Engineering, 10(2), 307-322.
Rashidi, E., Jahandar, M., & Zandieh, M. (2010). An improved hybrid multi-objective parallel genetic algorithm for hybrid flow shop scheduling with unrelated parallel machines. The International Journal of Advanced Manufacturing Technology, 49, 1129-1139.
Ruiz, R., & Maroto, C. (2006). A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. European journal of operational research, 169(3), 781-800.
Salvador, M. (1973). Asolution to a special class of flow shop scheduling problems. Lecture Notes in Economics and Mathematical Systems, 86, 83-91.
Tian, H., Li, K., & Liu, W. (2016). A pareto-based adaptive variable neighborhood search for biobjective hybrid flow shop scheduling problem with sequence-dependent setup time. Mathematical Problems in Engineering, 2016.
Xu, Y., & Wang, L. (2011). Differential evolution algorithm for hybrid flow-shop scheduling problems. Journal of Systems Engineering and Electronics, 22(5), 794-798.
Zandieh, M., Ghomi, S. F., & Husseini, S. M. (2006). An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times. Applied Mathematics and Computation, 180(1), 111-127.