BATCH SCHEDULING WITH DEADLINES ON PARALLEL MACHINES

The problem of scheduling G groups of jobs on m parallel machines is c onsidered. Each group consists of several identical jobs. We have to f ind splittings of groups into batches (i.e. sets of jobs to be process ed contiguously) and to schedule the batches on the machines. It is po ssible for different batches of the same group to be processed concurr ently on different machines. However, at any time, a batch can be proc essed on at most one machine. A sequence-independent machine set-up ti me is required immediately before a batch of a group is processed. A d eadline is associated with each group. The objective is to find a sche dule which is feasible with respect to deadlines. The problem is shown to be NP-hard even for the case of two identical machines, unit proce ssing times, unit set-up times and a common deadline. It is strongly N P-hard if machines are uniform, the number of jobs in each group is eq ual and processing times, set-up times and deadlines are unit. Special cases which are polynomially solvable are discussed. For the general problem, a family {DPepsilon} of approximation algorithms is construct ed. A new dynamic rounding technique is used to develop DPepsilon. For any epsilon>0, DPepsilon delivers a schedule in which the completion time of each group is at most (1 + epsilon) times the value of its dea dline if there exists a schedule which is feasible with respect to the deadlines. The time complexity of DPepsilon is O(G(2m+1/)epsilon(2m)) .