Batch scheduling with deadlines on parallel machines

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 contiguously) 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 {DPepsilon} of approximation algorithms is constructed. 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 deadline 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)).