Scheduling problems with batching machines and compatibility constraints
Identifieur interne : 002951 ( Hal/Checkpoint ); précédent : 002950; suivant : 002952Scheduling problems with batching machines and compatibility constraints
Auteurs : Adrien Bellanger [France]Source :
Descripteurs français
English descriptors
Abstract
This thesis deals with 2-stages hybrid flowshop scheduling problems with batching ma- chines on the second stage and compatibility constraints. The processing times of tasks are given by intervals and tasks are compatible if they share a same second stage processing time. We developped 6 heuristics with worth-case analysis for the makespan minimization problem. The experimental results show that these heuristics give good schedules with an average gap of 1% on 200 task instances. For small instances, we presented 2 exact methods, Branch & Bounds, which solves up to 20 task instances. For the particular case with identical processing times on first stage and uniform processing time intervals we developped a Polynomial Time Approximation Scheme (PTAS). The second part of this thesis deal with scheduling problems on one batching machine with infinite capacity and regular criteria minimization. We developped pseudo-polynomial dynamic programming algorithm for minimization total completion time, maximal lateness and total tardiness. Finally we show the NP-completeness of problems with due dates.
Url:
Links toward previous steps (curation, corpus...)
Links to Exploration step
Hal:tel-00606383Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Scheduling problems with batching machines and compatibility constraints</title><title xml:lang="fr">Ordonnancement sur les machines à traitement par batches et contraintes de compatibilité.</title><author><name sortKey="Bellanger, Adrien" sort="Bellanger, Adrien" uniqKey="Bellanger A" first="Adrien" last="Bellanger">Adrien Bellanger</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-44715" status="VALID"><orgName>Operations research for Complex HybrId Decision Sytems</orgName><orgName type="acronym">ORCHIDS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/orchids</ref></desc><listRelation><relation active="#struct-423085" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-423085" type="direct"><org type="department" xml:id="struct-423085" status="VALID"><orgName>Department of Networks, Systems and Services</orgName><orgName type="acronym">LORIA - NSS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/networks-systems-and-services</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:tel-00606383</idno><idno type="halId">tel-00606383</idno><idno type="halUri">https://tel.archives-ouvertes.fr/tel-00606383</idno><idno type="url">https://tel.archives-ouvertes.fr/tel-00606383</idno><date when="2009-11-23">2009-11-23</date><idno type="wicri:Area/Hal/Corpus">004393</idno><idno type="wicri:Area/Hal/Curation">004393</idno><idno type="wicri:Area/Hal/Checkpoint">002951</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">002951</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Scheduling problems with batching machines and compatibility constraints</title><title xml:lang="fr">Ordonnancement sur les machines à traitement par batches et contraintes de compatibilité.</title><author><name sortKey="Bellanger, Adrien" sort="Bellanger, Adrien" uniqKey="Bellanger A" first="Adrien" last="Bellanger">Adrien Bellanger</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-44715" status="VALID"><orgName>Operations research for Complex HybrId Decision Sytems</orgName><orgName type="acronym">ORCHIDS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche/equipes/orchids</ref></desc><listRelation><relation active="#struct-423085" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-423085" type="direct"><org type="department" xml:id="struct-423085" status="VALID"><orgName>Department of Networks, Systems and Services</orgName><orgName type="acronym">LORIA - NSS</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/networks-systems-and-services</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><settlement type="city">Metz</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université de Lorraine</orgName></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Scheduling</term><term>batching machines</term><term>graph compatibility</term><term>hybrid flowshop.</term></keywords><keywords scheme="mix" xml:lang="fr"><term>Ordonnancement</term><term>batch</term><term>compatibilité</term><term>flowshop hybride.</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">This thesis deals with 2-stages hybrid flowshop scheduling problems with batching ma- chines on the second stage and compatibility constraints. The processing times of tasks are given by intervals and tasks are compatible if they share a same second stage processing time. We developped 6 heuristics with worth-case analysis for the makespan minimization problem. The experimental results show that these heuristics give good schedules with an average gap of 1% on 200 task instances. For small instances, we presented 2 exact methods, Branch & Bounds, which solves up to 20 task instances. For the particular case with identical processing times on first stage and uniform processing time intervals we developped a Polynomial Time Approximation Scheme (PTAS). The second part of this thesis deal with scheduling problems on one batching machine with infinite capacity and regular criteria minimization. We developped pseudo-polynomial dynamic programming algorithm for minimization total completion time, maximal lateness and total tardiness. Finally we show the NP-completeness of problems with due dates.</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="en">Scheduling problems with batching machines and compatibility constraints</title><title xml:lang="fr">Ordonnancement sur les machines à traitement par batches et contraintes de compatibilité.</title><author role="aut"><persName><forename type="first">Adrien</forename><surname>Bellanger</surname></persName><email>adrien.bellanger@loria.fr</email><idno type="halauthor">212105</idno><orgName ref="#struct-364081"></orgName><affiliation ref="#struct-44715"></affiliation></author><editor role="depositor"><persName><forename>Ammar</forename><surname>Oulamara</surname></persName><email>oulamara@loria.fr</email></editor></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2011-07-07 08:40:35</date><date type="whenModified">2015-09-21 11:24:56</date><date type="whenReleased">2011-07-07 10:26:17</date><date type="whenProduced">2009-11-23</date><date type="whenEndEmbargoed">2011-07-07</date><ref type="file" target="https://tel.archives-ouvertes.fr/tel-00606383/document"><date notBefore="2011-07-07"></date></ref><ref type="file" n="1" target="https://tel.archives-ouvertes.fr/tel-00606383/file/2009_BELLANGER_A-3.pdf"><date notBefore="2011-07-07"></date></ref></edition><respStmt><resp>contributor</resp><name key="113646"><persName><forename>Ammar</forename><surname>Oulamara</surname></persName><email>oulamara@loria.fr</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">tel-00606383</idno><idno type="halUri">https://tel.archives-ouvertes.fr/tel-00606383</idno><idno type="halBibtex">bellanger:tel-00606383</idno><idno type="halRefHtml">Informatique [cs]. Institut National Polytechnique de Lorraine - INPL, 2009. Français</idno><idno type="halRef">Informatique [cs]. Institut National Polytechnique de Lorraine - INPL, 2009. Français</idno></publicationStmt><seriesStmt><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="LABO-LORIA-SET" p="LORIA">LABO-LORIA-SET</idno><idno type="stamp" n="LORIA2">Publications du LORIA</idno><idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno><idno type="stamp" n="LORIA-NSS" p="LORIA">Réseaux, systèmes et services</idno><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno></seriesStmt><notesStmt></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Scheduling problems with batching machines and compatibility constraints</title><title xml:lang="fr">Ordonnancement sur les machines à traitement par batches et contraintes de compatibilité.</title><author role="aut"><persName><forename type="first">Adrien</forename><surname>Bellanger</surname></persName><email>adrien.bellanger@loria.fr</email><idno type="halAuthorId">212105</idno><orgName ref="#struct-364081"></orgName><affiliation ref="#struct-44715"></affiliation></author></analytic><monogr><imprint><date type="dateDefended">2009-11-23</date></imprint><authority type="institution">Institut National Polytechnique de Lorraine - INPL</authority><authority type="supervisor">Marie-Claude Portmann, Ammar Oulamara(oulamara@loria.fr)</authority><authority type="jury">Christian PRINS (Examinateur)</authority><authority type="jury">Pierre LOPEZ (Rapporteur)</authority><authority type="jury">Bernard PENZ (Rapporteur)</authority><authority type="jury">Jean-Charles BILLAUT (Examinateur)</authority><authority type="jury">Emmanuel JEANNOT (Examinateur)</authority><authority type="jury">Francis SOURD (Examinateur)</authority><authority type="jury">Marie-Claude PORTMANN (Directeur)</authority><authority type="jury">Ammar OULAMARA (Directeur)</authority></monogr><ref type="seeAlso">http://pegase.scd.inpl-nancy.fr/theses/2009_BELLANGER_A.pdf</ref></biblStruct></sourceDesc><profileDesc><langUsage><language ident="fr">French</language></langUsage><textClass><keywords scheme="author"><term xml:lang="en">Scheduling</term><term xml:lang="en">batching machines</term><term xml:lang="en">graph compatibility</term><term xml:lang="en">hybrid flowshop.</term><term xml:lang="fr">compatibilité</term><term xml:lang="fr">batch</term><term xml:lang="fr">Ordonnancement</term><term xml:lang="fr">flowshop hybride.</term></keywords><classCode scheme="halDomain" n="info">Computer Science [cs]</classCode><classCode scheme="halTypology" n="THESE">Theses</classCode></textClass><abstract xml:lang="en">This thesis deals with 2-stages hybrid flowshop scheduling problems with batching ma- chines on the second stage and compatibility constraints. The processing times of tasks are given by intervals and tasks are compatible if they share a same second stage processing time. We developped 6 heuristics with worth-case analysis for the makespan minimization problem. The experimental results show that these heuristics give good schedules with an average gap of 1% on 200 task instances. For small instances, we presented 2 exact methods, Branch & Bounds, which solves up to 20 task instances. For the particular case with identical processing times on first stage and uniform processing time intervals we developped a Polynomial Time Approximation Scheme (PTAS). The second part of this thesis deal with scheduling problems on one batching machine with infinite capacity and regular criteria minimization. We developped pseudo-polynomial dynamic programming algorithm for minimization total completion time, maximal lateness and total tardiness. Finally we show the NP-completeness of problems with due dates.</abstract><abstract xml:lang="fr">Dans cette thèse, nous avons traité les problèmes d'ordonnancement d'ateliers de type flow- shop hybride à deux étages avec machines à traitement par batches sur le second étage et compatibilité entre les tâches. Les durées opératoires des tâches sont données par des intervalles, et les tâches sont dites compatibles si elles partagent une même durée d'exécution. Pour le problème de minimisation de la date de fin d'ordonnancement de ce type d'atelier, nous avons développé 6 heuristiques à performances garanties. D'après les expériences réalisées, ces heuristiques sont efficaces sur de grandes instances. Pour les petites instances, nous avons présenté deux méthodes exactes de type procédures par séparation évaluation qui permettent de résoudre des instances de 20 tâches. Nous avons également développé un schéma d'approximation polynomial (PTAS) utilisable lorsque les durées d'exécution sur le premier étage sont identiques. En complément de ces travaux, nous avons également étudié d'autres problèmes de minimisation de critères réguliers sur une machine à traitement par batches. Nous avons développé des algorithmes de programmation dynamiques pseudo-polynomiaux pour les problèmes de minimisation de la somme des dates de fin d'exécution et pour les problèmes avec dates de fin souhaitées. Afin de compléter ces résultats de complexité, nous avons montré la NP-complétude des problèmes avec dates de fin souhaitées.</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002951 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Checkpoint/biblio.hfd -nk 002951 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Hal
|étape= Checkpoint
|type= RBID
|clé= Hal:tel-00606383
|texte= Scheduling problems with batching machines and compatibility constraints
}}
| This area was generated with Dilib version V0.6.33. |  |