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 language | English |
---|---|
Pages (from-to) | 41-47 |
Number of pages | 7 |
Journal | Information Processing Letters |
Volume | 102 |
Issue number | 2-3 |
DOIs | |
Publication status | Published - 30 Apr 2007 |
Keywords
- Approximation algorithms
- Machine scheduling
- Makespan
- Start time-dependent processing times
ASJC Scopus subject areas
- Computational Theory and Mathematics