THE COMPLEXITY OF ONE-MACHINE BATCHING PROBLEMS

Autor(en): ALBERS, S
BRUCKER, P
Stichwörter: BATCHING; Mathematics; Mathematics, Applied; NP-HARD; POLYNOMIAL ALGORITHM; SHORTEST PATH PROBLEM; SINGLE
Erscheinungsdatum: 1993
Herausgeber: ELSEVIER SCIENCE BV
Journal: DISCRETE APPLIED MATHEMATICS
Volumen: 47
Ausgabe: 2
Startseite: 87
Seitenende: 107
Zusammenfassung: 
Batching problems are combinations of sequencing and partitioning problems. For each job sequence JS there is a partition of JS into batches with optimal value opt(JS) and one has to find a job sequence which minimizes this optimal value. We show that in many situations opt(JS) is the solution of a shortest path problem in some network. An algorithm solving this special shortest path problem in linear time with respect to the number of vertices is presented. Using this algorithm some new batching results are derived. Furthermore. it is shown that most of the batching problems which are known to be polynomially solvable turn into NP-hard problems when modified slightly.
Beschreibung: 
NATO Advanced Study Institute on New Frontiers in the Theory and Practice of Combinatorial Optimization: Applications in Manufacturing and VLSI Design, BILKENT UNIV ANKARA, ANKARA, TURKEY, JUL 16-28, 1990
ISSN: 0166218X
DOI: 10.1016/0166-218X(93)90085-3

Show full item record

Google ScholarTM

Check

Altmetric