• 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 - No thumbnail

Worst-case evaluation of flexible solutions in disjunctive scheduling problems

Aloulou, Mohamed Ali; Artigues, Christian (2007), Worst-case evaluation of flexible solutions in disjunctive scheduling problems, in Gervasi, Osvaldo; Gavrilova, Marina, Computational Science and Its Applications - ICCSA 2007 International Conference, Kuala Lumpur, Malaysia, August 26-29, 2007. Proceedings, Part III, Springer : Berlin, p. 1027-1036. http://dx.doi.org/10.1007/978-3-540-74484-9_89

Type
Communication / Conférence
External document link
http://hal.archives-ouvertes.fr/hal-00170394/en/
Date
2007
Conference title
2007 International Conference on Computational Science and its Applications (ICCSA 2007)
Conference date
2007-08
Conference city
Kuala Lumpur
Conference country
Malaisie
Book title
Computational Science and Its Applications - ICCSA 2007 International Conference, Kuala Lumpur, Malaysia, August 26-29, 2007. Proceedings, Part III
Book author
Gervasi, Osvaldo; Gavrilova, Marina
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
4707
Published in
Berlin
ISBN
978-3-540-74482-5
Number of pages
1205
Pages
1027-1036
Publication identifier
http://dx.doi.org/10.1007/978-3-540-74484-9_89
Metadata
Show full item record
Author(s)
Aloulou, Mohamed Ali
Artigues, Christian
Abstract (EN)
In this paper, we consider the problem of evaluating the worst case performance of flexible solutions in non-preemptive disjunctive scheduling. A flexible solution represents a set of semi-active schedules and is characterized by a partial order on each machine. A flexible solution can be used on-line to absorb the impact of some data disturbances related for example to job arrival, tool availability and machine breakdowns. Providing a flexible solution is useful in practice only if it can be assorted with an evaluation of the complete schedules that can be obtained by extension. For this purpose, we suggest to use only the best case and the worst case performance. The best case performance is an ideal performance that can be achieved only if the on-line conditions allow to implement the best schedule among the set of schedules characterized by the flexible solution. In contrast, the worst case performance indicates how poorly the flexible solution may perform. These performances can be obtained by solving corresponding minimization and maximization problems. We focus here on maximization problems when a regular minmax objective function is considered. In this case, the worse objective function value can be determined by computing the worse completion time of each operation separately. We show that this problem can be solved by finding an elementary longest path in the disjunctive graph representing the problem with additional constraints. In the special case of the flow-shop problem with release dates and additional precedence constraints, we give a polynomial algorithm that determines the worst case performance of a flexible solution.
Subjects / Keywords
Scheduling; flexibility; worst case performance; flow-shop

Related items

Showing items related by title and author.

  • 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é
  • 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
    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) Article accepté pour publication ou publié
  • Thumbnail
    Solving one-to-one integrated production and outbound distribution scheduling problems with job release dates and deadlines 
    Fu, Liangliang; Aloulou, Mohamed Ali; Artigues, Christian (2014) Communication / Conférence
  • Thumbnail
    Integrated production and outbound distribution scheduling problems with job release dates and deadlines 
    Fu, Liangliang; Aloulou, Mohamed Ali; Artigues, Christian (2017) 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