Solving the permutation flow shop problem with blocking and setup time constraints

Abstract: In this paper, the flow shop with blocking and sequence and machine dependent setup time problem aiming to minimize the makespan is studied. Two mixed-integer programming models are proposed (TNZBS1 and TNZBS2) and two other mixed-integer programming models, originally proposed for the no setup problem, are adapted to the problem. Furthermore, an Iterated Greedy algorithm is proposed for the problem. The permutation flow shop with blocking and sequence and machine dependent setup time is an underexplored problem and the authors did not find the use of mixed-integer programming models for the problem in any other work. To compare the models, a database of 80 problems was generated, which vary in number of machines and jobs. For the small sized problems, the adapted MILP model obtained the best results. However, for bigger problems, both proposed MILP models obtained significantly better results compared to the adapted models, proving the efficiency of the new models. When comparing the Iterated Greedy algorithm with the MILP models, the former outperformed the latter.

How to cite this paper

 Takano, M & Nagano, M. (2020). Solving the permutation flow shop problem with blocking and setup time constraints.International Journal of Industrial Engineering Computations , 11(3), 469-480.

Refrences

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.
Maleki-Darounkolaei, A., Modiri, M., Tavakkoli-Moghaddam, R., & Seyyedi, I. (2012). A three-stage assembly flow shop scheduling problem with blocking and sequence-dependent set up times. Journal of Industrial Engineering International, 8-26.
Miyata, H. H., & Nagano, M. S. (2019). The blocking flow shop scheduling problem: A comprehensive and conceptual review. Expert Systems with Applications, 137, 130-156.
Norman, B. A. (1999). Scheduling flowshops with finite buffers and sequence-dependent setup times. Computer & Industrial Engineering, 16(1), 163-177.
Pan, C. H. (1997). A study of integer programming formulations for scheduling problems. International Journal of Systems Science, 28, 33-41.
Pan, Q.-K., & Ruiz, R. (2014). An effective iterated greedy algorithm for the mixed no-idle permutationflowshop scheduling problem. Omega, 44, 41-50.
Papadimitriou, C., & Kanellakis, P. (1980). Flow-shop scheduling with limited temporary storage. Journal of the Association for Computing Machinery, 27(3), 533-549.
Rad, S. F., Ruiz, R., & Boroojerdiana, N. (2009). New high performing heuristics for minimizing makespan in permutation flowshops. Omega, 37(2), 331-345.
Ronconi, D. P., & Birgin, E. G. (2012). Mixed-integer programming models for flowshop scheduling problems minimizing the total earliness and tardiness. Just-in-Time Systems, 61, 91-105.
Sanches, F. B., Takano, M. I., & Nagano, M. S. (2016). Evaluation of heuristics for a branch and bound algorithm to minimize the makespan in a flowshop with blocking. Acta Scientiarum, 38(3), pp. 321-326.
Stafford, E. F. (1988). On the Development of a Mixed-Integer Linear Programming Model for the Flowshop Sequencing Problem. Journal of the Operational Research Society, 39, 1163-1174.
Stafford, E. F., Tseng, F. T., & Gupta, J. N. (2005). Comparative evaluation of MILP flowshop models. Journal of the Operational Research Society, 56, 88-101.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
Takano, M. I., & Nagano, M. S. (2019). Evaluating the performance of constructive heuristics for the blocking flow shop scheduling. International Journal of Industrial Engineering Computations, 10, pp. 37-50.
Zhu, Z., & Heady, R. B. (2000). Minimizing the sum of earliness/tardiness in multimachine scheduling: a mixed integer programming approach. Computers & Industrial Engineering, 38, 297-305.