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

64 Citations (Scopus)

Abstract

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
Volume55
Issue number4
DOIs
Publication statusPublished - 1 Jun 2008

Keywords

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

ASJC Scopus subject areas

  • Management Science and Operations Research

Cite this