This paper considers the following sequencing problem: n jobs coming from m different orders need to be processed on the same machine, and these jobs belong to k different classes. A setup time Sj is needed before the machine processes a job coming from class j when the just finished job belongs to a different class, and a setup time Sb is also needed before the machine processes the first job in class b. The goal is to minimize the aggregate time for completion of these m orders. Corresponding to three different models of this sequencing problem, this paper gives a polynomial algorithm, a branch and bound algorithm and a heuristic method, respectively.
