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.

Keywords: scheduling, earliness-tardiness, availability, break

@article{RO_2007__41_2_141_0, author = {Sourd, Francis}, title = {Scheduling with periodic availability constraints and irregular cost functions}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {141--154}, publisher = {EDP-Sciences}, volume = {41}, number = {2}, year = {2007}, doi = {10.1051/ro:2007016}, mrnumber = {2341437}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro:2007016/} }

TY - JOUR AU - Sourd, Francis TI - Scheduling with periodic availability constraints and irregular cost functions JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2007 SP - 141 EP - 154 VL - 41 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro:2007016/ DO - 10.1051/ro:2007016 LA - en ID - RO_2007__41_2_141_0 ER -

%0 Journal Article %A Sourd, Francis %T Scheduling with periodic availability constraints and irregular cost functions %J RAIRO - Operations Research - Recherche Opérationnelle %D 2007 %P 141-154 %V 41 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro:2007016/ %R 10.1051/ro:2007016 %G en %F RO_2007__41_2_141_0

Sourd, Francis. Scheduling with periodic availability constraints and irregular cost functions. RAIRO - Operations Research - Recherche Opérationnelle, Volume 41 (2007) no. 2, pp. 141-154. doi : 10.1051/ro:2007016. http://archive.numdam.org/articles/10.1051/ro:2007016/

[1] Zbl

, , and van de Klundert, A framework for the complexity of high-multiplicity scheduling problems. J. Combin. Optim. 9 (2005) 313-323. |[2] High multiplicity in earliness-tardiness scheduling. Oper. Res. 48 (2000) 788-800. | Zbl

and ,[3] One-processor scheduling with symmetric earliness and tardiness penalties. Math. Oper. Res. 13 (1988) 330-348. | Zbl

, and ,[4] An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem. Oper. Res. Lett. 32 (2004) 68-72. | Zbl

, and ,[5] Cyclic scheduling on parallel processors: an overview, Scheduling Theory and its applications, edited by P. Chrétienne, E.G. Coffman, J.K. Lenstra and Z. Liu, John Wiley & Sons (1995) 193-226.

and ,[6] Efficient neighborhood search for the one-machine ealiness-tardiness scheduling problems. Eur. J. Oper. Res. 173 (2006) 108-119. | Zbl

and ,[7] Strongly polynomial algorithms for the high multiplicity scheduling problem. Oper. Res. 39 (1991) 648-653. | Zbl

and ,[8] ILOG Inc., ILOG Scheduler 6.0 User's Manual and Reference Manual (October 2003).

[9] Machine scheduling with availability constraints, Handbook of scheduling: Algorithms, models and performance analysis, edited by J.Y.-T. Leung, Chapman & Hall/CRC (2004). | MR

,[10] Towards a real-life manufacturing scheduling problem and test bed, in Proceedings of PMS'04, http://www2.ilog.com/masclib (2004) 162-165.

, , , and ,[11] Optimal timing of a sequence of tasks with general completion costs. Eur. J. Oper. Res. 165 (2005) 82-96. | Zbl

,[12] A new branch-and-bound algorithm for the minimization of earliness and tardiness on a single machine, in 7th workshop on Models and Algorithms for Planning and Scheduling Problems (2005) 258-261.

and ,*Cited by Sources: *