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 "rst 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 "nished its processing. A schedule stipulates the sequence of batches on each machine. The objective is to "nd a schedule which is feasible with respect to the deadlines assuming one exists. We note that the problem is strongly NPcomplete, establish a number of useful properties of a feasible schedule and present a dynamic programming algorithm and a family of approximation algorithms +A C ,. For any '0, A C constructs a schedule in which the completion times 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 C
is O(nK>/ K). 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(mnK>) time, while the problem with identical machines and identical set-up and job processing times is solvable in O(n log n) time.