Premium
A flow‐shop problem with sequence‐dependent additive setup times
Author(s) -
Szwarc Wlodzimierz,
Gupta Jatinder N. D.
Publication year - 1987
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/1520-6750(198710)34:5<619::aid-nav3220340503>3.0.co;2-b
Subject(s) - job shop scheduling , sequence (biology) , flow shop scheduling , mathematical optimization , bounded function , permutation (music) , scheduling (production processes) , schedule , computer science , mathematics , flow (mathematics) , algorithm , mathematical analysis , genetics , geometry , acoustics , biology , operating system , physics
The flow‐shop scheduling problem with sequence‐dependent additive setup times is considered as a special case of the general problem, and a polynomially bounded approximate method is developed to find a minimum makespan permutation schedule. The approximate algorithm is shown to yield optimal results for the two‐machine case. A version of Sule's model is defined that produces the first approximation of the optimal solution for this problem. Computational experience along with numerical examples are provided to test the effectiveness of the method.