no. 2
Scheduling with periodic availability constraints and irregular cost functions
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 2, pp. 141-154

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.

DOI : 10.1051/ro:2007016
Classification : 90B35
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},
     year = {2007},
     publisher = {EDP Sciences},
     volume = {41},
     number = {2},
     doi = {10.1051/ro:2007016},
     mrnumber = {2341437},
     language = {en},
     url = {https://www.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  - https://www.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 https://www.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

[1] N. Brauner, Y. Crama, A. Grigoriev and van de Klundert, A framework for the complexity of high-multiplicity scheduling problems. J. Combin. Optim. 9 (2005) 313-323. | Zbl

[2] J.J. Clifford and M.E. Posner, High multiplicity in earliness-tardiness scheduling. Oper. Res. 48 (2000) 788-800. | Zbl

[3] M.R. Garey, R.E. Tarjan and G.T. Wilfong, One-processor scheduling with symmetric earliness and tardiness penalties. Math. Oper. Res. 13 (1988) 330-348. | Zbl

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

[5] C. Hanen and A. Munier, 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] Y. Hendel and F. Sourd, Efficient neighborhood search for the one-machine ealiness-tardiness scheduling problems. Eur. J. Oper. Res. 173 (2006) 108-119. | Zbl

[7] D. S. Hochbaum and R. Shamir, 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] C.-Y. Lee, 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] W. Nuijten, T. Bousonville, F. Focacci, D. Godard and C. Le Pape, Towards a real-life manufacturing scheduling problem and test bed, in Proceedings of PMS'04, http://www2.ilog.com/masclib (2004) 162-165.

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

[12] F. Sourd and S. Kedad-Sidhoum, 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 :