Scheduling parallel machines with inclusive processing set restrictions

Jinwen Ou, Joseph Y T Leung, Chung Lun Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

74 Citations (Scopus)


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
Pages (from-to)328-338
Number of pages11
JournalNaval Research Logistics
Issue number4
Publication statusPublished - 1 Jun 2008


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

ASJC Scopus subject areas

  • Management Science and Operations Research


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

Cite this