Parallel machine scheduling with machine availability and eligibility constraints

Lu Wen Liao, Gwo Ji Sheen

Research output: Contribution to journalArticlepeer-review

61 Scopus citations

Abstract

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.

Original languageEnglish
Pages (from-to)458-467
Number of pages10
JournalEuropean Journal of Operational Research
Volume184
Issue number2
DOIs
StatePublished - 16 Jan 2008

Keywords

  • Availability constraint
  • Eligibility constraint
  • Network flows
  • Parallel machines
  • Scheduling

Fingerprint

Dive into the research topics of 'Parallel machine scheduling with machine availability and eligibility constraints'. Together they form a unique fingerprint.

Cite this