Scheduling resumable simple linear deteriorating jobs on a single machine with an availability constraint to minimize makespan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

15 Citations (Scopus)

Abstract

We consider a single-machine scheduling problem in which the processing time of each job is a simple linear deteriorating function of its waiting time. The machine is subject to an availability constraint. Jobs interrupted by machine unavailability can resume their processing. The objective is to minimize the makespan. We first show that the problem can be solved optimally by 0-1 integer programming. We then prove that the problem is NP-hard in the ordinary sense and there exists a fully polynomial time approximation scheme for it.
Original languageEnglish
Pages (from-to)794-798
Number of pages5
JournalComputers and Industrial Engineering
Volume59
Issue number4
DOIs
Publication statusPublished - 1 Nov 2010

Keywords

  • 0-1 integer programming
  • Availability constraint
  • Computational complexity
  • FPTAS
  • Scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this