95-10
Parallel Machine Deadline Batch Scheduling
by Brucker, P.; Kovalyov, M.Y.; Shafransky, Y.M.; Werner, F.
Preprint series: 95-10, Preprints
The paper is published: Annals of Operations Research 83, 1998, 23 - 40.
Abstract: The problem of scheduling G groups of jobs on m parallel machines isconsidered. Each group consists of several identical jobs. We have to findsplittings of groups into batches (i.e. sets of jobs to be processed jointly) andto schedule the batches on the machines. It is possible for different batches ofthe same group to be processed concurrently on different machines. However,at any time, a batch can be processed on at most one machine. A sequenceindependent machine set-up time is required immediately before a batch of agroup is processed. A deadline is associated with each group. The objectiveis to find a schedule which is feasible with respect to deadlines. The problemis shown to be NP -hard even for the case of two identical machines, unitprocessing times, unit set-up times and a common deadline. It is stronglyNP -hard if machines are uniform, the number of jobs in each group is equaland processing times, set-up times and deadlines are unit. Special cases whichare polynomially solvable are discussed. For the general problem, a familyfDP \'\' g of approximation algorithms is constructed. A new dynamic roundingtechnique is used to develop DP \'\' . For any \'\' ? 0, DP \'\' delivers a schedule inwhich the completion time of each group is at most (1 + \'\') times the valueof its deadline if there exists a schedule which is feasible with respect to thedeadlines. The time complexity of DP \'\' is O(G 2m+1 =\'\' 2m ).
Keywords: parallel machine scheduling, batching, fully polynomial approximation scheme, computational complexity
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.