EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO Oper. Res.
Volume 41, Number 2, April-June 2007
ROADEF 05
Page(s) 141 - 154
DOI 10.1051/ro:2007016
Published online 15 June 2007

RAIRO Oper. Res. 41 (2007) 141-154
DOI: 10.1051/ro:2007016

Scheduling with periodic availability constraints and irregular cost functions

Francis Sourd

CNRS-LIP6. 4, place Jussieu 75252 Paris Cedex 05, France; Francis.Sourd@lip6.fr

(Received September 30, 2005. Accepted June 10, 2006. Published online 15 June 2007.)

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.


Mathematics Subject Classification. 90B35

Key words: Scheduling, earliness-tardiness, availability, break


© EDP Sciences, ROADEF, SMAI 2007


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.