by Brucker, P., Kovalyov, M.Y., Shafransky, Y.M., Werner, F..

**Series:** 1995-10, Preprints

- MSC:
- 90B35 Scheduling theory, deterministic

**Abstract:**

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 ).

**Keywords:**

parallel machine scheduling, batching, fully polynomial approximation scheme, computational complexity

**This paper was published in:**

Annals of Operations Research 83, 1998, 23 - 40.