Show simple item record

dc.contributor.authorAloulou, Mohamed Ali
dc.contributor.authorArtigues, Christian
HAL ID: 15435
dc.date.accessioned2011-04-04T13:10:28Z
dc.date.available2011-04-04T13:10:28Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5884
dc.language.isoenen
dc.subjectSchedulingen
dc.subjectflexibilityen
dc.subjectworst case performanceen
dc.subjectflow-shopen
dc.subject.ddc003en
dc.titleWorst-case evaluation of flexible solutions in disjunctive scheduling problemsen
dc.typeCommunication / Conférence
dc.description.abstractenIn 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.en
dc.identifier.citationpages1027-1036en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber4707
dc.relation.ispartoftitleComputational Science and Its Applications - ICCSA 2007 International Conference, Kuala Lumpur, Malaysia, August 26-29, 2007. Proceedings, Part IIIen
dc.relation.ispartofeditorGervasi, Osvaldo
dc.relation.ispartofeditorGavrilova, Marina
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2007
dc.relation.ispartofpages1205en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-540-74484-9en
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00170394/en/en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-74482-5en
dc.relation.conftitle2007 International Conference on Computational Science and its Applications (ICCSA 2007)en
dc.relation.confdate2007-08
dc.relation.confcityKuala Lumpuren
dc.relation.confcountryMalaisieen
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-540-74484-9_89


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record