Scheduling parallel machines with inclusive processing set restrictions

Jinwen Ou, Joseph Y.T. Leung, Chung Lun Li

Research output: Contribution to journalArticlepeer-review

75 Scopus citations


We consider the problem of assigning a set of jobs to different parallel machines of the same processing speed, where each job is compatible to only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. The objective is to minimize the makespan of the schedule. This problem is motivated by industrial applications such as cargo handling by cranes with nonidentical weight capacities, computer processor scheduling with memory constraints, and grades of service provision by parallel servers. We develop an efficient algorithm for this problem with a worst-case performance ratio of 4/3 + ε, where ε is a positive constant which may be set arbitrarily close to zero. We also present a polynomial time approximation scheme for this problem, which answers an open question in the literature.

Original languageEnglish (US)
Pages (from-to)328-338
Number of pages11
JournalNaval Research Logistics
Issue number4
StatePublished - Jun 2008

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


  • Parallel machines
  • Polynomial time approximation scheme
  • Scheduling
  • Worst-case analysis


Dive into the research topics of 'Scheduling parallel machines with inclusive processing set restrictions'. Together they form a unique fingerprint.

Cite this