## THE COMPLEXITY OF ONE-MACHINE BATCHING PROBLEMS

DC FieldValueLanguage
dc.contributor.authorALBERS, S
dc.contributor.authorBRUCKER, P
dc.date.accessioned2021-12-23T16:04:11Z-
dc.date.available2021-12-23T16:04:11Z-
dc.date.issued1993
dc.identifier.issn0166218X
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/6302-
dc.descriptionNATO 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
dc.description.abstractBatching 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.
dc.language.isoen
dc.publisherELSEVIER SCIENCE BV
dc.relation.ispartofDISCRETE APPLIED MATHEMATICS
dc.subjectBATCHING
dc.subjectMathematics
dc.subjectMathematics, Applied
dc.subjectNP-HARD
dc.subjectPOLYNOMIAL ALGORITHM
dc.subjectSHORTEST PATH PROBLEM
dc.subjectSINGLE
dc.titleTHE COMPLEXITY OF ONE-MACHINE BATCHING PROBLEMS
dc.typeconference paper
dc.identifier.doi10.1016/0166-218X(93)90085-3
dc.identifier.isiISI:A1993MQ83100002
dc.description.volume47
dc.description.issue2
dc.description.startpage87
dc.description.endpage107
dc.publisher.placePO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS
dcterms.isPartOf.abbreviationDiscret Appl. Math.
dcterms.oaStatusBronze

#### Page view(s)

1
Last Week
0
Last month
0
checked on Apr 19, 2024