Minimizing the range of order lateness with multiple job classes

This paper considers a single machine scheduling problem with m customer orders and multiple job classes. Each customer places an order that contains several jobs. The jobs in total can be grouped into different classes. When the machine changes its processing from the job in a class to a job in a different class, say class i, a non-productive time si is required for set up. There exists a due date for each order. The finish time of an order is the finish time of all its jobs. We wish to schedule these n jobs such that the lateness range of orders is minimized. Corresponding to this scheduling problem, following two different models are considered in this paper: the jobs in the same class must be processed continuously, and the job's completion time is the completion time of the batch to which this job is assigned, we denote it by GT, Ba; the jobs in the same class must be processed continuously, and a job is considered completed at the time when it is completed itself, we denote it by GT, Ja. We proved that the scheduling problems corresponding to these two models are NP-hard and construct the branch and bound algorithms for them, respectively.