Branch and bound crossed with GA to solve hybrid flowshops
Identifieur interne :
000C84 ( PascalFrancis/Curation );
précédent :
000C83;
suivant :
000C85
Branch and bound crossed with GA to solve hybrid flowshops
Auteurs : M.-C. Portmann [
France] ;
A. Vignier [
France] ;
D. Dardilhac [
France] ;
D. Dezalay [
France]
Source :
-
European journal of operational research [ 0377-2217 ] ; 1998.
RBID : Pascal:98-0455270
Descripteurs français
English descriptors
Abstract
This article deals with an optimal methods for solving a k-stage hybrid flowshop scheduling problem. This problem is known to be NP-hard. In 1991, Brah and Hunsucker proposed a branch and bound algorithm to solve this problem. However, for some medium size problems, the computation time is not acceptable. The aim of this article is to present an improvement of this algorithm. As a matter of fact, we prove that the value of their lower bound (LB) may decrease along a path of the search tree. First of all, we present an improvement of their LB. Then, we introduce several heuristics at the beginning of the search in order to compute an initial upper bound and genetic algorithm (GA) to improve during the search the value of the upper bound. More precisely, our GA takes into account the set of partial decisions made by the branch and bound and builds a series of populations of complete solutions with the aim of improving the upper bound (the best found criterion value corresponding to a complete solution). Experimentation show that the optimality of branch and bound is more often reached and the value of criterion is improved when our improvements are taken into account.
| pA |
| A01 | 01 | 1 | | @0 0377-2217 |
|---|
| A02 | 01 | | | @0 EJORDT |
|---|
| A03 | | 1 | | @0 Eur. j. oper. res. |
|---|
| A05 | | | | @2 107 |
|---|
| A06 | | | | @2 2 |
|---|
| A08 | 01 | 1 | ENG | @1 Branch and bound crossed with GA to solve hybrid flowshops |
|---|
| A11 | 01 | 1 | | @1 PORTMANN (M.-C.) |
|---|
| A11 | 02 | 1 | | @1 VIGNIER (A.) |
|---|
| A11 | 03 | 1 | | @1 DARDILHAC (D.) |
|---|
| A11 | 04 | 1 | | @1 DEZALAY (D.) |
|---|
| A12 | 01 | 1 | | @1 WEGLARZ (Jan) @9 ed. |
|---|
| A12 | 02 | 1 | | @1 JOZEFOWSKA (Joanna) @9 ed. |
|---|
| A14 | 01 | | | @1 CRIN - CNRS URA 262, Ecole des Mines de Nancy, Parc de Saurupt @2 54 042 Nancy @3 FRA @Z 1 aut. |
|---|
| A14 | 02 | | | @1 Laboratoire d'Informatique, E3i, 64, Avenue Jean Portalis @2 37200 Tours @3 FRA @Z 2 aut. @Z 3 aut. @Z 4 aut. |
|---|
| A15 | 01 | | | @1 Politechnika Poznańska, Instytut Informatyká @2 Poznań @3 POL @Z 1 aut. @Z 2 aut. |
|---|
| A18 | 01 | 1 | | @1 EURO. Working Group on Project Management and Scheduling @3 EUR @9 patr. |
|---|
| A20 | | | | @1 389-400 |
|---|
| A21 | | | | @1 1998 |
|---|
| A23 | 01 | | | @0 ENG |
|---|
| A43 | 01 | | | @1 INIST @2 17566 @5 354000076452950120 |
|---|
| A44 | | | | @0 0000 @1 © 1998 INIST-CNRS. All rights reserved. |
|---|
| A45 | | | | @0 14 ref. |
|---|
| A47 | 01 | 1 | | @0 98-0455270 |
|---|
| A60 | | | | @1 P @2 C |
|---|
| A61 | | | | @0 A |
|---|
| A64 | | 1 | | @0 European journal of operational research |
|---|
| A66 | 01 | | | @0 NLD |
|---|
| C01 | 01 | | ENG | @0 This article deals with an optimal methods for solving a k-stage hybrid flowshop scheduling problem. This problem is known to be NP-hard. In 1991, Brah and Hunsucker proposed a branch and bound algorithm to solve this problem. However, for some medium size problems, the computation time is not acceptable. The aim of this article is to present an improvement of this algorithm. As a matter of fact, we prove that the value of their lower bound (LB) may decrease along a path of the search tree. First of all, we present an improvement of their LB. Then, we introduce several heuristics at the beginning of the search in order to compute an initial upper bound and genetic algorithm (GA) to improve during the search the value of the upper bound. More precisely, our GA takes into account the set of partial decisions made by the branch and bound and builds a series of populations of complete solutions with the aim of improving the upper bound (the best found criterion value corresponding to a complete solution). Experimentation show that the optimality of branch and bound is more often reached and the value of criterion is improved when our improvements are taken into account. |
|---|
| C02 | 01 | X | | @0 001D01A12 |
|---|
| C03 | 01 | X | FRE | @0 Ordonnancement @5 01 |
|---|
| C03 | 01 | X | ENG | @0 Scheduling @5 01 |
|---|
| C03 | 01 | X | GER | @0 Netzplantechnik @5 01 |
|---|
| C03 | 01 | X | SPA | @0 Ordonamiento @5 01 |
|---|
| C03 | 02 | X | FRE | @0 Système production @5 02 |
|---|
| C03 | 02 | X | ENG | @0 Production system @5 02 |
|---|
| C03 | 02 | X | SPA | @0 Sistema producción @5 02 |
|---|
| C03 | 03 | X | FRE | @0 Flow shop @5 03 |
|---|
| C03 | 03 | X | ENG | @0 Flow shop @5 03 |
|---|
| C03 | 03 | X | SPA | @0 Flow shop @5 03 |
|---|
| C03 | 04 | X | FRE | @0 Modèle hybride @5 04 |
|---|
| C03 | 04 | X | ENG | @0 Hybrid model @5 04 |
|---|
| C03 | 04 | X | SPA | @0 Modelo híbrido @5 04 |
|---|
| C03 | 05 | X | FRE | @0 Méthode séparation et évaluation @5 05 |
|---|
| C03 | 05 | X | ENG | @0 Branch and bound method @5 05 |
|---|
| C03 | 05 | X | SPA | @0 Método branch and bound @5 05 |
|---|
| C03 | 06 | X | FRE | @0 Algorithme génétique @5 06 |
|---|
| C03 | 06 | X | ENG | @0 Genetic algorithm @5 06 |
|---|
| C03 | 06 | X | SPA | @0 Algoritmo genético @5 06 |
|---|
| C03 | 07 | X | FRE | @0 Borne inférieure @5 07 |
|---|
| C03 | 07 | X | ENG | @0 Lower bound @5 07 |
|---|
| C03 | 07 | X | SPA | @0 Cota inferior @5 07 |
|---|
| C03 | 08 | X | FRE | @0 Borne supérieure @5 08 |
|---|
| C03 | 08 | X | ENG | @0 Upper bound @5 08 |
|---|
| C03 | 08 | X | SPA | @0 Cota superior @5 08 |
|---|
| N21 | | | | @1 299 |
|---|
|
|---|
| pR |
| A30 | 01 | 1 | ENG | @1 Project Management and Scheduling: International Workshop @2 5 @3 Poznań POL @4 1996-04-11 |
|---|
|
|---|
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000B90
Links to Exploration step
Pascal:98-0455270
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Branch and bound crossed with GA to solve hybrid flowshops</title>
<author><name sortKey="Portmann, M C" sort="Portmann, M C" uniqKey="Portmann M" first="M.-C." last="Portmann">M.-C. Portmann</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>CRIN - CNRS URA 262, Ecole des Mines de Nancy, Parc de Saurupt</s1>
<s2>54 042 Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><country>France</country>
</affiliation><author><name sortKey="Vignier, A" sort="Vignier, A" uniqKey="Vignier A" first="A." last="Vignier">A. Vignier</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Laboratoire d'Informatique, E3i, 64, Avenue Jean Portalis</s1>
<s2>37200 Tours</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14><country>France</country>
</affiliation><author><name sortKey="Dardilhac, D" sort="Dardilhac, D" uniqKey="Dardilhac D" first="D." last="Dardilhac">D. Dardilhac</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Laboratoire d'Informatique, E3i, 64, Avenue Jean Portalis</s1>
<s2>37200 Tours</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14><country>France</country>
</affiliation><author><name sortKey="Dezalay, D" sort="Dezalay, D" uniqKey="Dezalay D" first="D." last="Dezalay">D. Dezalay</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Laboratoire d'Informatique, E3i, 64, Avenue Jean Portalis</s1>
<s2>37200 Tours</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14><country>France</country>
</affiliation><publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">98-0455270</idno>
<date when="1998">1998</date>
<idno type="stanalyst">PASCAL 98-0455270 INIST</idno>
<idno type="RBID">Pascal:98-0455270</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000B90</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000C84</idno>
</publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Branch and bound crossed with GA to solve hybrid flowshops</title>
<author><name sortKey="Portmann, M C" sort="Portmann, M C" uniqKey="Portmann M" first="M.-C." last="Portmann">M.-C. Portmann</name>
<affiliation wicri:level="1"><inist:fA14 i1="01"><s1>CRIN - CNRS URA 262, Ecole des Mines de Nancy, Parc de Saurupt</s1>
<s2>54 042 Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><country>France</country>
</affiliation><author><name sortKey="Vignier, A" sort="Vignier, A" uniqKey="Vignier A" first="A." last="Vignier">A. Vignier</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Laboratoire d'Informatique, E3i, 64, Avenue Jean Portalis</s1>
<s2>37200 Tours</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14><country>France</country>
</affiliation><author><name sortKey="Dardilhac, D" sort="Dardilhac, D" uniqKey="Dardilhac D" first="D." last="Dardilhac">D. Dardilhac</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Laboratoire d'Informatique, E3i, 64, Avenue Jean Portalis</s1>
<s2>37200 Tours</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14><country>France</country>
</affiliation><author><name sortKey="Dezalay, D" sort="Dezalay, D" uniqKey="Dezalay D" first="D." last="Dezalay">D. Dezalay</name>
<affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Laboratoire d'Informatique, E3i, 64, Avenue Jean Portalis</s1>
<s2>37200 Tours</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14><country>France</country>
</affiliation><series><title level="j" type="main">European journal of operational research</title>
<title level="j" type="abbreviated">Eur. j. oper. res.</title>
<idno type="ISSN">0377-2217</idno>
<imprint><date when="1998">1998</date>
</imprint><seriesStmt><title level="j" type="main">European journal of operational research</title>
<title level="j" type="abbreviated">Eur. j. oper. res.</title>
<idno type="ISSN">0377-2217</idno>
</seriesStmt><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Branch and bound method</term>
<term>Flow shop</term>
<term>Genetic algorithm</term>
<term>Hybrid model</term>
<term>Lower bound</term>
<term>Production system</term>
<term>Scheduling</term>
<term>Upper bound</term>
</keywords><keywords scheme="Pascal" xml:lang="fr"><term>Ordonnancement</term>
<term>Système production</term>
<term>Flow shop</term>
<term>Modèle hybride</term>
<term>Méthode séparation et évaluation</term>
<term>Algorithme génétique</term>
<term>Borne inférieure</term>
<term>Borne supérieure</term>
</keywords><front><div type="abstract" xml:lang="en">This article deals with an optimal methods for solving a k-stage hybrid flowshop scheduling problem. This problem is known to be NP-hard. In 1991, Brah and Hunsucker proposed a branch and bound algorithm to solve this problem. However, for some medium size problems, the computation time is not acceptable. The aim of this article is to present an improvement of this algorithm. As a matter of fact, we prove that the value of their lower bound (LB) may decrease along a path of the search tree. First of all, we present an improvement of their LB. Then, we introduce several heuristics at the beginning of the search in order to compute an initial upper bound and genetic algorithm (GA) to improve during the search the value of the upper bound. More precisely, our GA takes into account the set of partial decisions made by the branch and bound and builds a series of populations of complete solutions with the aim of improving the upper bound (the best found criterion value corresponding to a complete solution). Experimentation show that the optimality of branch and bound is more often reached and the value of criterion is improved when our improvements are taken into account.</div>
</front><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0377-2217</s0>
</fA01><fA02 i1="01"><s0>EJORDT</s0>
</fA02><fA03 i2="1"><s0>Eur. j. oper. res.</s0>
</fA03><fA05><s2>107</s2>
</fA05><fA08 i1="01" i2="1" l="ENG"><s1>Branch and bound crossed with GA to solve hybrid flowshops</s1>
</fA08><fA11 i1="01" i2="1"><s1>PORTMANN (M.-C.)</s1>
</fA11><fA11 i1="02" i2="1"><s1>VIGNIER (A.)</s1>
</fA11><fA11 i1="03" i2="1"><s1>DARDILHAC (D.)</s1>
</fA11><fA11 i1="04" i2="1"><s1>DEZALAY (D.)</s1>
</fA11><fA12 i1="01" i2="1"><s1>WEGLARZ (Jan)</s1>
<s9>ed.</s9>
</fA12><fA12 i1="02" i2="1"><s1>JOZEFOWSKA (Joanna)</s1>
<s9>ed.</s9>
</fA12><fA14 i1="01"><s1>CRIN - CNRS URA 262, Ecole des Mines de Nancy, Parc de Saurupt</s1>
<s2>54 042 Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14><fA14 i1="02"><s1>Laboratoire d'Informatique, E3i, 64, Avenue Jean Portalis</s1>
<s2>37200 Tours</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</fA14><fA15 i1="01"><s1>Politechnika Poznańska, Instytut Informatyká</s1>
<s2>Poznań</s2>
<s3>POL</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</fA15><fA18 i1="01" i2="1"><s1>EURO. Working Group on Project Management and Scheduling</s1>
<s3>EUR</s3>
<s9>patr.</s9>
</fA18><fA20><s1>389-400</s1>
</fA20><fA21><s1>1998</s1>
</fA21><fA23 i1="01"><s0>ENG</s0>
</fA23><fA43 i1="01"><s1>INIST</s1>
<s2>17566</s2>
<s5>354000076452950120</s5>
</fA43><fA44><s0>0000</s0>
<s1>© 1998 INIST-CNRS. All rights reserved.</s1>
</fA44><fA45><s0>14 ref.</s0>
</fA45><fA47 i1="01" i2="1"><s0>98-0455270</s0>
</fA47><fA60><s1>P</s1>
<s2>C</s2>
</fA60><fA64 i2="1"><s0>European journal of operational research</s0>
</fA64><fA66 i1="01"><s0>NLD</s0>
</fA66><fC01 i1="01" l="ENG"><s0>This article deals with an optimal methods for solving a k-stage hybrid flowshop scheduling problem. This problem is known to be NP-hard. In 1991, Brah and Hunsucker proposed a branch and bound algorithm to solve this problem. However, for some medium size problems, the computation time is not acceptable. The aim of this article is to present an improvement of this algorithm. As a matter of fact, we prove that the value of their lower bound (LB) may decrease along a path of the search tree. First of all, we present an improvement of their LB. Then, we introduce several heuristics at the beginning of the search in order to compute an initial upper bound and genetic algorithm (GA) to improve during the search the value of the upper bound. More precisely, our GA takes into account the set of partial decisions made by the branch and bound and builds a series of populations of complete solutions with the aim of improving the upper bound (the best found criterion value corresponding to a complete solution). Experimentation show that the optimality of branch and bound is more often reached and the value of criterion is improved when our improvements are taken into account.</s0>
</fC01><fC02 i1="01" i2="X"><s0>001D01A12</s0>
</fC02><fC03 i1="01" i2="X" l="FRE"><s0>Ordonnancement</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="ENG"><s0>Scheduling</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="GER"><s0>Netzplantechnik</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="SPA"><s0>Ordonamiento</s0>
<s5>01</s5>
</fC03><fC03 i1="02" i2="X" l="FRE"><s0>Système production</s0>
<s5>02</s5>
</fC03><fC03 i1="02" i2="X" l="ENG"><s0>Production system</s0>
<s5>02</s5>
</fC03><fC03 i1="02" i2="X" l="SPA"><s0>Sistema producción</s0>
<s5>02</s5>
</fC03><fC03 i1="03" i2="X" l="FRE"><s0>Flow shop</s0>
<s5>03</s5>
</fC03><fC03 i1="03" i2="X" l="ENG"><s0>Flow shop</s0>
<s5>03</s5>
</fC03><fC03 i1="03" i2="X" l="SPA"><s0>Flow shop</s0>
<s5>03</s5>
</fC03><fC03 i1="04" i2="X" l="FRE"><s0>Modèle hybride</s0>
<s5>04</s5>
</fC03><fC03 i1="04" i2="X" l="ENG"><s0>Hybrid model</s0>
<s5>04</s5>
</fC03><fC03 i1="04" i2="X" l="SPA"><s0>Modelo híbrido</s0>
<s5>04</s5>
</fC03><fC03 i1="05" i2="X" l="FRE"><s0>Méthode séparation et évaluation</s0>
<s5>05</s5>
</fC03><fC03 i1="05" i2="X" l="ENG"><s0>Branch and bound method</s0>
<s5>05</s5>
</fC03><fC03 i1="05" i2="X" l="SPA"><s0>Método branch and bound</s0>
<s5>05</s5>
</fC03><fC03 i1="06" i2="X" l="FRE"><s0>Algorithme génétique</s0>
<s5>06</s5>
</fC03><fC03 i1="06" i2="X" l="ENG"><s0>Genetic algorithm</s0>
<s5>06</s5>
</fC03><fC03 i1="06" i2="X" l="SPA"><s0>Algoritmo genético</s0>
<s5>06</s5>
</fC03><fC03 i1="07" i2="X" l="FRE"><s0>Borne inférieure</s0>
<s5>07</s5>
</fC03><fC03 i1="07" i2="X" l="ENG"><s0>Lower bound</s0>
<s5>07</s5>
</fC03><fC03 i1="07" i2="X" l="SPA"><s0>Cota inferior</s0>
<s5>07</s5>
</fC03><fC03 i1="08" i2="X" l="FRE"><s0>Borne supérieure</s0>
<s5>08</s5>
</fC03><fC03 i1="08" i2="X" l="ENG"><s0>Upper bound</s0>
<s5>08</s5>
</fC03><fC03 i1="08" i2="X" l="SPA"><s0>Cota superior</s0>
<s5>08</s5>
</fC03><fN21><s1>299</s1>
</fN21><pR><fA30 i1="01" i2="1" l="ENG"><s1>Project Management and Scheduling: International Workshop</s1>
<s2>5</s2>
<s3>Poznań POL</s3>
<s4>1996-04-11</s4>
</fA30>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C84 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Curation/biblio.hfd -nk 000C84 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Curation
|type= RBID
|clé= Pascal:98-0455270
|texte= Branch and bound crossed with GA to solve hybrid flowshops
}}
| This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022 |  |
