Premium
An exact algorithm for the batch sequencing problem in a two‐machine flow shop with limited buffer
Author(s) -
Agnetis A.,
Rossi F.,
Gristina G.
Publication year - 1998
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199803)45:2<141::aid-nav2>3.0.co;2-8
Subject(s) - computer science , exploit , job shop scheduling , mathematical optimization , minification , context (archaeology) , flow shop scheduling , heuristic , algorithm , upper and lower bounds , flow (mathematics) , mathematics , artificial intelligence , routing (electronic design automation) , computer network , paleontology , mathematical analysis , computer security , geometry , biology
This paper deals with the problem of makespan minimization in a flow shop with two machines when the input buffer of the second machine can only host a limited number of parts. Here we analyze the problem in the context of batch processing, i.e., when identical parts must be processed consecutively. We propose an exact branch‐and‐bound algorithm, in which the bounds exploit the batching nature of the problem. Extensive computational results show the effectiveness of the approach, and allow us to compare it with a previous heuristic approach. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 141–164, 1998