AN UPPER BOUND FOR THE BRANCH-AND-BOUND ALGORITHM FOR THE BLOCKING PERMUTATION FLOW SHOP WITH TOTAL TARDINESS CRITERION

Thiago Keizo KATO, Mauricio Iwama TAKANO, Marcelo Seido NAGANO

Abstract


The use of an upper bound for the branch and bound algorithm proposed by [1] is proposed in this paper. The problem explored is a blocking-in-process permutation flow shop problem with total tardiness criterion, which is known to be NP-Hard for m≥2. The literature for this theme is scarce, therefore this article aims to fill this gap. To improve the algorithm, it is proposed the use of an initial solution that will be used as an upper bound for the problem. A database that contains 27 different classes of problems was used for the computational experiments. Each class of problems varies in number of jobs (n) and in number of machines (m). To generate the initial solution, different constructive heuristics will be analyzed and compared to each other.

Full Text:

PDF

References


Nagano, M. S., Takano, M. I., & Robazzi, J. V. S. A branch-and-bound for the blocking permutation flowshop with total tardiness criterion, International Journal of Industrial Engineering Computations, 2022.

Garey, M. R., Johnson, D. S., & Sethi, R. The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1976.

Mccormick, S., Pinedo, M., J. Shenker, S., & Wolf, B. Sequencing in an assembly line with blocking to minimize cycle time, Operations Research 37(6), 925-935 ,1989.

Nawaz, M., Enscore, E. E., Ham, I. Heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 1983.

Ronconi, D. P. A note on constructive heuristics for the flowshop problem with blocking, International Journal of Production Economics, 2004.

Quan-Ke Pan,Ling Wang. Effective heuristics for the blocking flowshop scheduling problem with makespan minimization, Omega, 2012.

Ronconi, D. P. e Henriques, L. R. S. Some heuristic algorithms for total tardiness minimization in a flowshop with blocking, Omega, 2009.

Ronconi, D. P. e Armentano, V. A. Lower bounding schemes for flowshops with blocking in-process, The Journal of the Operational Research Society, 2001.

Said, T. et al. Branch and bound algorithm for solv-ing blocking flowshop scheduling problem with total tardiness and total weighted tardiness criteria, International Journal of Operational Research, 2017.

Kim,Y.D. Minimizing mean tardiness inpermutation flowshops, European Journal of Operational Research, v. 85, n. 3, p. 541-555, 1995.

Ronconi, D. P. A branch-and-bound algorithm to minimize the makespan in a flowshop with blocking, Annals of Operations Research, 2005.

Taillard, E. Benchmarks for Basic Scheduling Problems, European Journal of Operational Research, 1993.


Refbacks

  • There are currently no refbacks.


JOURNAL INDEXED IN :