BATCH SCHEDULING AND COMMON DUE-DATE ASSIGNMENT ON A SINGLE-MACHINE

We consider the problem of scheduling n groups of jobs on a single mac hine where three types of decisions are combined: scheduling, batching and due-date assignment. Each group includes identical jobs and may b e split into batches; jobs within each batch are processed jointly. A sequence independent machine set-up time is needed between each two co nsecutively scheduled batches of different groups. A due-date common t o all jobs has to be assigned. A schedule specifies the size of each b atch, i.e. the number of jobs it contains, and a processing order for the batches. The objective is to determine a value for the common due- date and a schedule so as to minimize the sum of the due date assignme nt penalty and the weighted number of tardy jobs. Several special case s of this problem are shown to be ordinary NP-hard. Some cases are sol ved in O(n log n) time. Two pseudopolynomial dynamic programming algor ithms are presented for the general problem, as well as a fully polyno mial approximation scheme.