Article ID: | iaor20081742 |
Country: | France |
Volume: | 41 |
Issue: | 2 |
Start Page Number: | 141 |
End Page Number: | 154 |
Publication Date: | Apr 2007 |
Journal: | RAIRO Operations Research |
Authors: | Sourd Francis |
This paper addresses a one-machine scheduling problem in which the efficiency of the machine is not constant, that is the duration of a task is longer in badly efficient time periods. Each task has an irregular completion cost. Under the assumption that the efficiency constraints are time-periodic, we show that the special case where the sequence is fixed can be solved in polynomial time. The general case is NP-complete so that we propose a two-phase heuristic to find good solutions. Our approach is tested on problems with earliness–tardiness costs.