A novel mathematical model for a hybrid flow shop scheduling problem under buffer and resource limitations-A case study

Document Type: Research Paper

Authors

1 Department of Industrial Engineering, Science and Research Branch, Islamic Azad University Tehran, Iran

2 South Tehran Branch, Islamic Azad University

3 Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran

Abstract

Scheduling problems play a big role in manufacturing and planning the production for increasing the production efficiency and assigning the resources to operations. Furthermore, in many manufacturing systems there is a physical space between stages that called intermediate buffers. In this study, a model is proposed for minimizing the makespan of a hybrid flow shop scheduling problem with intermediate buffers and resource constraints. These constraints exist in almost every realistic manufacturing system and have an imperative impact on improving the production cost, productivity, and sustainability. In this study, a hybrid algorithm based on genetic algorithm and variable neighborhood search was used, which in tuned with Taguchi’s method helped in solving the proposed model for a tire manufacturing company. The results show that the proposed mathematical model has a high ability for scheduling problems with resource and intermediate buffer constraints and is solvable by the hybrid genetic algorithm.

Keywords

Main Subjects


Abdollahpour, S., & Rezaeian, J. (2015). Minimizing makespan for flow shop scheduling problem with intermediate buffers by using hybrid approach of artificial immune system. Applied Soft Computing, 28, 44–56.

Afzalirad, M., & Rezaeian, J. (2016). Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions. Computers & Industrial Engineering, 98, 40–52.

Allaoui, H., & Artiba, A. (2006). Scheduling two-stage hybrid flow shop with availability constraints. Computers & Operations Research, 33, 1399–1419.

Back, T., Fogel, D. B., & Michalewicz, Z. (2000). Evolutionary Computation 1: Basic Algorithms and Operators (Vol. 1). New York, USA: Tylor and Francis Group.

Belaid, R., T’kindt, V., & Esswein, C. (2012). Scheduling batches in flowshop with limited buffers in the shampoo industry. European Journal of Operational Research, 223(2), 560–572.

Blazewicz, J. (1978). Complexity of computer scheduling algorithms under resource constraints. Paper presented at the Proceedings of the First Meeting AFCET-SMF on Applied Mathematics.

Blazewicz, J., Barcelo, J., Kubiak, W., & Röck, H. (1986). Scheduling tasks on two processors with deadlines and additional resources. European Journal of Operational Research, 26(3), 364–370.

Blazewicz, J., & Ecker, K. (1983). A linear time algorithm for restricted bin packing and scheduling problems. Operations Research Letters, 2(2), 80–83.

Blazewicz, J., Ecker, K. H., Pesch, E., & Schmidt, G. (2007). Handbook on Scheduling. New York: Springer-Verlag.

Błażewicz, J., Kubiak, W., Röck, H., & Szwarcfiter, J. (1987). Minimizing mean flow-time with parallel processors and resource constraints. Acta informatica, 24(5), 513-524.

Brucke, P., & Kramer, A. (1996). Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems. European Journal of Operational Research, 90, 214–226.

Daniels, R. L., Hoopes, B. J., & Mazzola, J. B. (1996). Scheduling parallel manufacturing cells with resource flexibility  Management Science, 42(9), 1260–1276.

Edis, E. B., & Oguz, C. (2011). Parallel machine scheduling with additional resources: a Lagrangian-based constraint programming approach. Berlin, Germany: Springer-Verlag.

Edis, E. B., & Oguz, C. (2012). Parallel machine scheduling with flexible resources. Computers and Industrial Engineering, 63, 433–447.

Edis, E. B., & Ozkarahan, I. (2011). proposed a combined integer/constraint-programming approach to a resource-constrained parallel machine scheduling problem with machine eligibility restrictions. Engineering Optimization, 43(2), 135–157.

Fanjul-Peyro, L., Perea, F., & Ruiz, R. (2017). Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources. European Journal of Operational Research.

Fu, Y., Wang, Z., Zhang, J., & Wang, Z. (2017). A blocking flow shop deteriorating scheduling problem via a hybrid chemical reaction optimization. Advances in Mechanical Engineering, 9(6), 1687814017701371. doi:10.1177/1687814017701371

Garey, M. R., Johnson, D.S. (1975). Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal on Computing, 4(4), 397–411.

Gen, M., & Cheng, R. (1997). Genetic Algorithms and Engineering Design (Vol. I). New York, USA: John Wiley & Sons.

Grigoriev, A., Sviridenko, M., & Uetz, M. (2007). Machine scheduling with resource dependent processing times. Mathematical programming, 110(1), 209-228.

Gupta, J. N. D. (1988). Two-Stage, Hybrid Flowshop Scheduling Problem. Journal of the Operational Research Society, 39(4).

Hall, N. G., & Sriskandarajah, C. (1996). A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process. Operations Research, 44(3), 510 - 525.

Kellerer, H., & Strusevisch, V. A. (2008). Scheduling parallel dedicated machines with the speeding-up resource. Naval Research Logistics, 55(5), 377–389.

Kovalyov, M. Y., & Shafransky, Y. M. (1998). Uniform machine scheduling of unit-time jobs subject to resource constraints. Discrete Applied Mathematics, 84, 253–257.

Laribi, I., Yalaoui, F., Belkai, F., & Sari, Z. (2016). heuristics algorithm for solving flow shop scheduling problem under resources constraints. Paper presented at the 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM, Troyes.

Lenstra, J. K., Rinnooy Kan, A. H. G., and Brucker, P.,. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1(1), 343-362.

Li, X., & Gao, L. (2016). An effective hybrid genetic algorithm and tabu search for flexible job shop scheduling problem. Int. J.ProductionEconomics, 174, 93–110.

Liu, S. Q., & Kozan, E. (2009). Scheduling a flow shop with combined buffer conditions. International Journal of Production Economics, 117(2), 371-380. doi:https://doi.org/10.1016/j.ijpe.2008.11.007

Liu, S. Q., & Kozan, E. (2016). Parallel-identical-machine job-shop scheduling with different stage-dependent buffering requirements. Computers & Operations Research, 74, 31–41.

Liu, X., Li, K., & Ren, H. (2015). A Hybrid Algorithm for the Permutation Flowshop Scheduling Problem without Intermediate Buffers. Discrete Dynamics in Nature and Society, 2015.

Lovaa, A., Tormos, P., Cervantes, M., & Barber, F. (2009). An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes. International Journal of Production Economics, 117(2), 302–316.

Mansouri, S. A., & Aktas, E. (2016). Minimizing energy consumption and makespan in a two-machine flowshop scheduling problem. Journal of the Operational Research Society, 67(11), 1382–1394.

Moslehi, G., & Khorasanian, D. (2014). A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion. Computers & Operations Research, 52, 260–268.

Papadimitriou, C., & Kanellakis, P. (1980). Flow shop scheduling with limited temporary storage. Journal of the ACM, 27(3), 533-549.

Pinedo, M. L. (2016). Scheduling: Theory, Algorithms, and Systems: Springer International Publishing.

Ribas, I., Companys, R., & Tort-Martorell, X. (2017). Efficient heuristics for the parallel blocking flow shop scheduling problem. Expert Systems with Applications, 74(Supplement C), 41-54. doi:https://doi.org/10.1016/j.eswa.2017.01.006

Ruiz-Torres, A. J., Lopez, F. J., & Ho, J. C. (2007). Scheduling uniform parallel machines subject to a secondary resource to minimize the number of tardy jobs. European Journal of Operational Research, 179(2), 302–315.

Ventura, J. A., & Kim, D. (2000). Parallel machine scheduling about an unrestricted due date and additional resource constraints. Iie Transactions, 32(2), 147-153.

Waldherr, S., & Knust, S. (2016). Decomposition algorithms for synchronous flow shop problems with additional resources and setup times. European Journal of Operational Research.

Yaurima, V., Burtseva, L., & Tchernykh, A. (2009). Hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints and limited buffers. Computers & Industrial Engineering, 56(4), 1452-1463. doi:https://doi.org/10.1016/j.cie.2008.09.004