Scheduling jobs with release dates, equal processing times, and inclusive processing set restrictions

Chung Lun Li, Qingying Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n 2 +mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.
Original languageEnglish
Pages (from-to)516-523
Number of pages8
JournalJournal of the Operational Research Society
Volume66
Issue number3
DOIs
Publication statusPublished - 5 Mar 2015

Keywords

  • equal processing time jobs
  • inclusive processing sets
  • parallel machines
  • Scheduling

ASJC Scopus subject areas

  • Management Information Systems
  • Strategy and Management
  • Management Science and Operations Research
  • Marketing

Cite this