LOW-COMPLEXITY ALGORITHMS FOR SEQUENCING JOBS WITH A FIXED NUMBER OF JOB-CLASSES

In this paper we consider the problem of scheduling n jobs such that m akespan is minimized. It is assumed that the jobs can be divided into K job-classes and that the change-over time between two consecutive jo bs depends on the job-classes to which the two jobs belong. In this se tting, we discuss the one machine scheduling problem with arbitrary pr ocessing times and the parallel machines scheduling problem with ident ical processing times. In both cases it is assumed that the number of job-classes K is fixed. By using an appropriate integer programming fo rmulation with a fixed number of variables and constraints, it is show n that these two problems are solvable in polynomial time. For the one machine scheduling case it is shown that the complexity of our algori thm is linear in the number of jobs pr. Moreover, if the problem is en coded according to the high multiplicity model of Hochbaum and Shamir, the time complexity of the algorithm is shown to be a polynomial in l og n. In the parallel machine scheduling case, it is shown that if the number of machines is fixed the same results hold. Copyright (C) 1996 Elsevier Science Ltd