A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint

Research output: Journal article publicationJournal articleAcademic researchpeer-review

23 Citations (Scopus)

Abstract

We study a two identical parallel-machine scheduling problem in which one machine is available to process jobs in a limited time interval while the other machine is always available over the scheduling horizon. The objective is to maximize the number of on-time jobs. As the problem is NP-hard, we develop a heuristic to tackle it by incorporating the backward adjusting and two-step look-ahead strategies into some existing heuristics for similar problems without the machine availability constraint. We show that our heuristic has a worst-case ratio bound of 4/3 and the bound is tight.
Original languageEnglish
Pages (from-to)74-82
Number of pages9
JournalInternational Journal of Production Economics
Volume161
DOIs
Publication statusPublished - 1 Jan 2015

Keywords

  • Heuristic
  • Identical parallel machines
  • Scheduling
  • Worst-case ratio bound

ASJC Scopus subject areas

  • Business, Management and Accounting(all)
  • Economics and Econometrics
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Cite this