Scheduling with job release dates, delivery times and preemption penalties

Research output: Journal article publicationJournal articleAcademic researchpeer-review

31 Citations (Scopus)

Abstract

The single-machine preemptive scheduling problem with job release dates, delivery times and preemption penalties was discussed. Such problems require a job-dependent setup to take place each time a job is started. It was proved that the problem is strongly NP-hard. A dynamic programming algorithm and a polynomial time approximation scheme were also presented for solving the problem.
Original languageEnglish
Pages (from-to)107-111
Number of pages5
JournalInformation Processing Letters
Volume82
Issue number2
DOIs
Publication statusPublished - 30 Apr 2002

Keywords

  • Approximation scheme
  • Preemption penalty
  • Scheduling
  • Setup time

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this