• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of a computational complexity

Portmann, Marie-Claude; Kovalyov, Mikhail Y.; Aloulou, Mohamed Ali (2007), Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of a computational complexity, RAIRO, 41, 1, p. 1-18. http://dx.doi.org/10.1051/ro:20070012

Type
Article accepté pour publication ou publié
Date
2007
Journal name
RAIRO
Volume
41
Number
1
Publisher
EDP Sciences
Pages
1-18
Publication identifier
http://dx.doi.org/10.1051/ro:20070012
Metadata
Show full item record
Author(s)
Portmann, Marie-Claude
Kovalyov, Mikhail Y.
Aloulou, Mohamed Ali
Abstract (EN)
We study a deterministic problem of evaluating the worst case performance of flexible solutions in the single machine scheduling. A flexible solution is a set of schedules following a given structure de- termined by a partial order of jobs and a type of the schedules. In this paper, the schedules of active and non-delay type are considered. A flexible solution can be used on-line to absorb the impact of data disturbances related to, for example, job arrival, tool availability or machine breakdowns. The performance of a flexible solution includes the best case and the worst case performances. The best case perfor- mance is an ideal performance that can be achieved only if the on-line conditions allow to implement the best schedule of the set of schedules characterizing the flexible solution. In contrast, the worst case perfor- mance indicates how poorly the flexible solution may perform when fol- lowing the given structure in the on-line circumstances. The best-case and the worst-case performances are usually evaluated by the minimum and maximum values of the considered objective function, respectively. We present algorithmic and computational complexity results for some maximization scheduling problems. In these problems, the jobs to be scheduled have different release dates and precedence constraints may be given on the set of jobs.
Subjects / Keywords
Scheduling; single machine; maxi- mization problems

Related items

Showing items related by title and author.

  • Thumbnail
    Worst case performance evaluation of flexible solutions in single machine scheduling 
    Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.; Portmann, Marie-Claude (2003) Communication / Conférence
  • Thumbnail
    Maximization of single machine scheduling 
    Aloulou, Mohamed Ali; Kovalyov, Mikhail Y.; Portmann, Marie-Claude (2004) Article accepté pour publication ou publié
  • Thumbnail
    A flexible proactive-reactive approach: the case of an assembly workshop 
    Aloulou, Mohamed Ali; Portmann, Marie-Claude (2008) Chapitre d'ouvrage
  • Thumbnail
    Minimizing the number of late jobs on a single machine under due date uncertainty 
    Aissi, Hassene; Aloulou, Mohamed Ali; Kovalyov, Mikhail Y. (2011) Article accepté pour publication ou publié
  • Thumbnail
    Flexible solutions in disjunctive scheduling: general formulation and study of the flow-shop case 
    Aloulou, Mohamed Ali; Artigues, Christian (2010) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo