An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)

Abstract

We study the problems of scheduling a set of nonpreemptive jobs on a single machine and identical parallel machines, where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objective is to minimize makespan. We first give a fully polynomial-time approximation scheme (FPTAS) for the case with a single machine. We then generalize the result to the case with m identical machines.
Original languageEnglish
Pages (from-to)41-47
Number of pages7
JournalInformation Processing Letters
Volume102
Issue number2-3
DOIs
Publication statusPublished - 30 Apr 2007

Keywords

  • Approximation algorithms
  • Machine scheduling
  • Makespan
  • Start time-dependent processing times

ASJC Scopus subject areas

  • Computational Theory and Mathematics

Cite this