by Brucker, P., Kovalyov, M.Y., Shafransky, Y.M., Werner, F..
Series: 1995-10, Preprints
The problem of scheduling G groups of jobs on m parallel machines is
considered. Each group consists of several identical jobs. We have to find
splittings of groups into batches (i.e. sets of jobs to be processed jointly) and
to schedule the batches on the machines. It is possible for different batches of
the same group to be processed concurrently on different machines. However,
at any time, a batch can be processed on at most one machine. A sequence
independent machine set-up time is required immediately before a batch of a
group is processed. A deadline is associated with each group. The objective
is to find a schedule which is feasible with respect to deadlines. The problem
is shown to be NP -hard even for the case of two identical machines, unit
processing times, unit set-up times and a common deadline. It is strongly
NP -hard if machines are uniform, the number of jobs in each group is equal
and processing times, set-up times and deadlines are unit. Special cases which
are polynomially solvable are discussed. For the general problem, a family
fDP '' g of approximation algorithms is constructed. A new dynamic rounding
technique is used to develop DP '' . For any '' ? 0, DP '' delivers a schedule in
which the completion time of each group is at most (1 + '') times the value
of its deadline if there exists a schedule which is feasible with respect to the
deadlines. The time complexity of DP '' is O(G 2m+1 ='' 2m ).
parallel machine scheduling, batching, fully polynomial approximation scheme, computational complexity
This paper was published in:
Annals of Operations Research 83, 1998, 23 - 40.