Scheduling with periodic availability constraints and irregular cost functions
CNRS-LIP6. 4, place Jussieu 75252 Paris Cedex 05, France; Francis.Sourd@lip6.fr
Accepted: 10 June 2006
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.
Mathematics Subject Classification: 90B35
Key words: Scheduling / earliness-tardiness / availability / break
© EDP Sciences, ROADEF, SMAI, 2007