Single machine batch scheduling with sequential job processing

The problem of scheduling n jobs on a single machine in batches to minimize some regular cost functions is studied. Jobs within each batch are process ed sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs in the same batch are completed at the same time when the last job of the batch has finished its processing. A constant set-up time precedes the processing of each bat ch. The number of jobs in each batch is bounded by some value b. If b < n, then the problem is called bounded. Otherwise, it is unbounded. For both th e bounded and unbounded problems, dynamic programming algorithms are presen ted for minimizing the maximum lateness, the number of late jobs, the total tardiness, the total weighted completion time, and the total weighted tard iness when all due dates are equal, which are polynomial if there is a fixe d number of distinct due dates or processing times. More efficient algorith ms are derived for some special cases of both the bounded and unbounded pro blems in which all due dates and/or processing times are equal. Several spe cial cases of the bounded problem are shown to be NP-hard. Thus, a comprehe nsive classification of the computational complexities of the special cases is provided.