In this paper, we study the problem of scheduling n independent jobs non-preemptively on m unrelated parallel machines. Each job j has a processing time and a deadline, the time at which the job must be completed. On each machine, jobs may be grouped to form batches containing continuously scheduled jobs. For each batch, a constant set-up time is needed before the first job of the batch is processed. The completion time of each job in a batch is equal to the time when the latest job in the batch has finished its processing. A schedule stipulates the sequence of batches on each machine. The objective is to find a schedule which is feasible with respect to the deadlines assuming one exists. We note that the problem is strongly NP-complete, establish a number of useful properties of a feasible schedule and present a dynamic programming algorithm and a family of approximation algorithms {Aϵ}. For any ϵ > 0, Aϵ constructs a schedule in which the completion time of each job is at most (1 + ϵ) times the value of its deadline if there exists a feasible schedule with respect to the deadlines. The time complexity of Aϵ is O(n2m+1/ϵm). We prove that the problem with identical jobs and uniform machines, unlike its polynomially solvable classical counterpart, in which the set-up time is zero, is strongly NP-complete. We also show that this problem is solvable in O(m2n2m+1) time, while the problem with identical machines and identical set-up and job processing times is solvable in O(n log n) time.
