A branch and bound method in a permutation flow shop with blocking and setup times

Abstract: In this paper it is presented an improvement of the branch and bound algorithm for the permutation flow shop problem with blocking-in-process and setup times with the objective of minimizing the total flow time and tardiness, which is known to be NP-Hard when there are two or more machines involved. With that objective in mind, a new machine-based lower bound that exploits some structural properties of the problem. A database with 27 classes of problems, varying in number of jobs (n) and number of machines (m) was used to perform the computational experiments. Results show that the algorithm can deal with most of the problems with less than 20 jobs in less than one hour. Thus, the method proposed in this work can solve the scheduling of many applications in manufacturing environments with limited buffers and separated setup times.

How to cite this paper

 Nagano, M., Takano, M & Robazzi, J. (2022). A branch and bound method in a permutation flow shop with blocking and setup times.International Journal of Industrial Engineering Computations , 13(2), 255-266.

Refrences

Ahmadi, R. H., & Bagchi, U. (1990). Improved lower bounds for minimizing the sum of completion times of n jobs over m machines in a flow shop. European Journal of Operational Research, 44(3), 331-336.
Bansal, S. P. (1977). Minimizing the sum of completion times of n jobs over m machines in a flowshop: A branch and bound approach. A I I E Transactions, 9(3), 306-311.
Chung, C. S., Flynn, J., & Kirca, O. (2002). A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems. International Journal of Production Economics, 79(3), 185-196.
Chung, C. S., Flynn, J., & Kirca, O. (2006). A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems. European Journal of Operational Research, 174(1), 1-10.
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117-129.
Gilmore, P. C., & Gomory, R. E. (1964). Sequencing a one state-variable machine: A solvable case of the traveling salesman problem. Operations Research, 12(5), 655-679.
Ignall, E., & Schrage, L. (1965). Application of the branch and bound technique to some flow-shop scheduling problems. Operations Research, 13(3), 400-412.
Mccormick, S., Pinedo, M., J. Shenker, S., & Wolf, B. (1989). Sequencing in an assembly line with blocking to minimize cycle time. Operations Research, 37(6), 925-935.
Miyata, H. H., & Nagano, M. S. (2019). The blocking flow shop scheduling problem: A comprehensive and conceptual review. Expert Systems with Applications, 137(1), 130–156.
Moslehi, G., & Khorasanian, D. (2013). Optimizing blocking flow shop scheduling problem with total completion time criterion. Computers & Operations Research, 40(7), 1874 -1883.
Nagano, M. S., Robazzi, J. V. S., & Tomazella, C. P. (2020). An improved lower bound for the blocking permutation flow shop with total completion time criterion. Computers & Industrial Engineering, 146(1), 106511.
Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.
Pan, Q. K., & Wang, L. (2012). Effective heuristics for the blocking flowshop scheduling problem with makespan minimization. Omega, 40(2), 218-229.
Pan, Q.-K., & Ruiz, R. (2014). An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem. Omega, 44(1), 41-50.
Pinedo, M. L. (2008). Scheduling: Theory, Algorithms, and Systems. 3rd edn. Springer Publishing Company, New York.
Reddi, S., & Ramamoorthy, C. (1972). On the flow-shop sequencing problem with no wait in process. Journal of the Operational Research Society, 23(3), 323-331.
Rios-Mercado, R. Z., & Bard, J. F. (1999). A Branch-and-Bound Algorithm for Flowshop Scheduling with Setup Times. IIE Transactions on Scheduling & Logistics, 31(8), 721-731.
Robazzi, J. V. S., Nagano, M. S., & Takano, M. I. (2021). A Branch-and-Bound Method to Minimize the Total Flow Time in a Permutation Flow Shop with Blocking and Setup Times. In: Rossit D.A., Tohmé F., Mejía Delgadillo G. (eds) Production Research. ICPR-Americas 2020. Communications in Computer and Information Science, vol 1407. Springer, Cham.
Ronconi, D. P. (2004). A note on constructive heuristics for the flowshop problem with blocking. International Journal of Production Economics, 87(1), 39-48.
Ronconi, D. P. (2005). A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking. Annals of Operations Research, 138(1), 53-65.
Ronconi, D. P., & Armentano, V. A. (2001). Lower bounding schemes for flowshops with blocking in-process. Journal of the Operational Research Society, 52(11), 1289-1297.
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(1), 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-Technology, 38(3), 321-326.
Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2), 278-285.
Takano, M. I., & Nagano, M. S. (2017). A branch-and-bound method to minimize the makespan in a permutation flow shop with blocking and setup times. Cogent Engineering, 4(1), 1389638.
Takano, M. I., & Nagano, M. S. (2019). Evaluating the performance of constructive heuristics for the blocking flow shop scheduling problem with setup times. International Journal of Industrial Engineering Computations, 10(1), 37–50.
Takano, M. I., & Nagano, M. S. (2020). Solving the permutation flow shop problem with blocking and setup time constraints. International Journal of Industrial Engineering Computations, 11(3), 469–480.