Abstract
We consider a single machine scheduling problem in which the processing time of a job is a simple linear increasing function of its starting time and the machine is subject to an availability constraint. We consider the non-resumable case. The objectives are to minimize the makespan and the total completion time. We show that both problems are NP-hard and present pseudo-polynomial time optimal algorithms to solve them. Furthermore, for the makespan problem, we present an optimal approximation algorithm for the on-line case, and a fully polynomial time approximation scheme for the off-line case. For the total completion time problem, we provide a heuristic and evaluate its efficiency by computational experiments.
Original language | English |
---|---|
Pages (from-to) | 115-126 |
Number of pages | 12 |
Journal | Theoretical Computer Science |
Volume | 362 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 11 Oct 2006 |
Keywords
- Approximation algorithms
- Availability constraint
- Computational complexity
- Deteriorating job
- Scheduling
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)