# Scheduling with periodic availability constraints and irregular cost functions

RAIRO - Operations Research (2007)

- Volume: 41, Issue: 2, page 141-154
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topSourd, Francis. "Scheduling with periodic availability constraints and irregular cost functions." RAIRO - Operations Research 41.2 (2007): 141-154. <http://eudml.org/doc/250086>.

@article{Sourd2007,

abstract = {
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.
},

author = {Sourd, Francis},

journal = {RAIRO - Operations Research},

keywords = {Scheduling; earliness-tardiness; availability; break},

language = {eng},

month = {6},

number = {2},

pages = {141-154},

publisher = {EDP Sciences},

title = {Scheduling with periodic availability constraints and irregular cost functions},

url = {http://eudml.org/doc/250086},

volume = {41},

year = {2007},

}

TY - JOUR

AU - Sourd, Francis

TI - Scheduling with periodic availability constraints and irregular cost functions

JO - RAIRO - Operations Research

DA - 2007/6//

PB - EDP Sciences

VL - 41

IS - 2

SP - 141

EP - 154

AB -
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.

LA - eng

KW - Scheduling; earliness-tardiness; availability; break

UR - http://eudml.org/doc/250086

ER -

## References

top- 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. Zbl1079.90049
- J.J. Clifford and M.E. Posner, High multiplicity in earliness-tardiness scheduling. Oper. Res.48 (2000) 788–800. Zbl1106.90330
- 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. Zbl0671.90033
- 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. Zbl1056.90062
- 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. Zbl0830.68009
- Y. Hendel and F. Sourd, Efficient neighborhood search for the one-machine ealiness-tardiness scheduling problems. Eur. J. Oper. Res.173 (2006) 108–119. Zbl1125.90017
- D. S. Hochbaum and R. Shamir, Strongly polynomial algorithms for the high multiplicity scheduling problem. Oper. Res.39 (1991) 648–653. Zbl0736.90043
- ILOG Inc., ILOG Scheduler 6.0 User's Manual and Reference Manual (October 2003).
- 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).
- 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, (2004) 162–165. URIhttp://www2.ilog.com/masclib
- F. Sourd, Optimal timing of a sequence of tasks with general completion costs. Eur. J. Oper. Res.165 (2005) 82–96. Zbl1112.90340
- 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.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.