Low-complexity algorithms for sequencing jobs with a fixed number of job-classes

Jack A.A. Van Der Veen, Shuzhong Zhang

Research output: Contribution to journalArticle

10 Scopus citations

Abstract

In this paper we consider the problem of scheduling n jobs such that makespan is minimized. It is assumed that the jobs can be divided into K job-classes and that the change-over time between two consecutive jobs depends on the job-classes to which the two jobs belong. In this setting, we discuss the one machine scheduling problem with arbitrary processing times and the parallel machines scheduling problem with identical processing times. In both cases it is assumed that the number of job-classes K is fixed. By using an appropriate integer programming formulation with a fixed number of variables and constraints, it is shown that these two problems are solvable in polynomial time. For the one machine scheduling case it is shown that the complexity of our algorithm is linear in the number of jobs n. Moreover, if the problem is encoded according to the high multiplicity model of Hochbaum and Shamir, the time complexity of the algorithm is shown to be a polynomial in log n. In the parallel machine scheduling case, it is shown that if the number of machines is fixed the same results hold.

Original languageEnglish (US)
Pages (from-to)1059-1067
Number of pages9
JournalComputers and Operations Research
Volume23
Issue number11
DOIs
StatePublished - Nov 1996

Fingerprint Dive into the research topics of 'Low-complexity algorithms for sequencing jobs with a fixed number of job-classes'. Together they form a unique fingerprint.

  • Cite this