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.
Mots-clés : 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, Tome 41 (2007) no. 2, pp. 141-154. doi : 10.1051/ro:2007016. http://archive.numdam.org/articles/10.1051/ro:2007016/
[1] ,, and van de Klundert, A framework for the complexity of high-multiplicity scheduling problems. J. Combin. Optim. 9 (2005) 313-323. | Zbl
[2] and, High multiplicity in earliness-tardiness scheduling. Oper. Res. 48 (2000) 788-800. | Zbl
[3] , and, One-processor scheduling with symmetric earliness and tardiness penalties. Math. Oper. Res. 13 (1988) 330-348. | Zbl
[4] , and, An enhanced dynasearch neighborhood for the single-machine total weighted tardiness scheduling problem. Oper. Res. Lett. 32 (2004) 68-72. | Zbl
[5] and, 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.
[6] and, Efficient neighborhood search for the one-machine ealiness-tardiness scheduling problems. Eur. J. Oper. Res. 173 (2006) 108-119. | Zbl
[7] and, Strongly polynomial algorithms for the high multiplicity scheduling problem. Oper. Res. 39 (1991) 648-653. | Zbl
[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] ,,, and, Towards a real-life manufacturing scheduling problem and test bed, in Proceedings of PMS'04, http://www2.ilog.com/masclib (2004) 162-165.
[11] , Optimal timing of a sequence of tasks with general completion costs. Eur. J. Oper. Res. 165 (2005) 82-96. | Zbl
[12] and, 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.
Cité par Sources :
