Scheduling an unbounded batching machine with job processing time compatibilities
Identifieur interne : 000101 ( PascalFrancis/Checkpoint ); précédent : 000100; suivant : 000102Scheduling an unbounded batching machine with job processing time compatibilities
Auteurs : A. Bellanger [France] ; A. Janiak [Pologne] ; M. Y. Kovalyov [Biélorussie] ; A. Oulamara [France]Source :
- Discrete applied mathematics [ 0166-218X ] ; 2012.
Descripteurs français
- Pascal (Inist)
- Informatique théorique, Optimisation, Combinatoire, Ordonnancement, Temps traitement, Compatibilité, Fonction objectif, Intervalle temps, Traitement par lot, Intersection, Horaire, Algorithme, Complétion, Minimisation, Programmation dynamique, Temps total achèvement, Maximum, Complexité, 68M20, 68Wxx, 49Lxx.
English descriptors
- KwdEn :
Abstract
The problem of scheduling n jobs on an unbounded batching machine to minimize a regular objective function is studied. In this problem intervals for job processing times are given. The machine can process any number of jobs in a batch, provided that the processing time intervals of these jobs have a non-empty intersection. The jobs in the same batch start and complete together, and the batch processing time is equal to the left endpoint of the intersection of the processing time intervals in this batch. Properties of an optimal schedule are established and an enumerative algorithm based on these properties is developed. For the total completion time minimization, a dynamic programming algorithm is developed. Minimizing the makespan is shown to be solvable in 0(n log n) time and minimizing the maximum lateness is proved to be NP-hard.
Affiliations:
Links toward previous steps (curation, corpus...)
Links to Exploration step
Pascal:12-0046320Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Scheduling an unbounded batching machine with job processing time compatibilities</title><author><name sortKey="Bellanger, A" sort="Bellanger, A" uniqKey="Bellanger A" first="A." last="Bellanger">A. Bellanger</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy University, LORIA laboratory, Ecole des Mines de Nancy, Parc de Saurupt</s1><s2>54042 Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Janiak, A" sort="Janiak, A" uniqKey="Janiak A" first="A." last="Janiak">A. Janiak</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Institute of Engineering Cybernetics, Wroclaw University of Technology, Janiszewskiego 11/17</s1><s2>50-372 Wroclaw</s2><s3>POL</s3><sZ>2 aut.</sZ></inist:fA14><country>Pologne</country><wicri:noRegion>50-372 Wroclaw</wicri:noRegion></affiliation></author><author><name sortKey="Kovalyov, M Y" sort="Kovalyov, M Y" uniqKey="Kovalyov M" first="M. Y." last="Kovalyov">M. Y. Kovalyov</name><affiliation wicri:level="1"><inist:fA14 i1="03"><s1>United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6</s1><s2>220012 Minsk</s2><s3>BLR</s3><sZ>3 aut.</sZ></inist:fA14><country>Biélorussie</country><wicri:noRegion>220012 Minsk</wicri:noRegion></affiliation></author><author><name sortKey="Oulamara, A" sort="Oulamara, A" uniqKey="Oulamara A" first="A." last="Oulamara">A. Oulamara</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy University, LORIA laboratory, Ecole des Mines de Nancy, Parc de Saurupt</s1><s2>54042 Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">12-0046320</idno><date when="2012">2012</date><idno type="stanalyst">PASCAL 12-0046320 INIST</idno><idno type="RBID">Pascal:12-0046320</idno><idno type="wicri:Area/PascalFrancis/Corpus">000128</idno><idno type="wicri:Area/PascalFrancis/Curation">000883</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000101</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000101</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Scheduling an unbounded batching machine with job processing time compatibilities</title><author><name sortKey="Bellanger, A" sort="Bellanger, A" uniqKey="Bellanger A" first="A." last="Bellanger">A. Bellanger</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy University, LORIA laboratory, Ecole des Mines de Nancy, Parc de Saurupt</s1><s2>54042 Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author><author><name sortKey="Janiak, A" sort="Janiak, A" uniqKey="Janiak A" first="A." last="Janiak">A. Janiak</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Institute of Engineering Cybernetics, Wroclaw University of Technology, Janiszewskiego 11/17</s1><s2>50-372 Wroclaw</s2><s3>POL</s3><sZ>2 aut.</sZ></inist:fA14><country>Pologne</country><wicri:noRegion>50-372 Wroclaw</wicri:noRegion></affiliation></author><author><name sortKey="Kovalyov, M Y" sort="Kovalyov, M Y" uniqKey="Kovalyov M" first="M. Y." last="Kovalyov">M. Y. Kovalyov</name><affiliation wicri:level="1"><inist:fA14 i1="03"><s1>United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6</s1><s2>220012 Minsk</s2><s3>BLR</s3><sZ>3 aut.</sZ></inist:fA14><country>Biélorussie</country><wicri:noRegion>220012 Minsk</wicri:noRegion></affiliation></author><author><name sortKey="Oulamara, A" sort="Oulamara, A" uniqKey="Oulamara A" first="A." last="Oulamara">A. Oulamara</name><affiliation wicri:level="3"><inist:fA14 i1="01"><s1>Nancy University, LORIA laboratory, Ecole des Mines de Nancy, Parc de Saurupt</s1><s2>54042 Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>4 aut.</sZ></inist:fA14><country>France</country><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Nancy</settlement></placeName></affiliation></author></analytic><series><title level="j" type="main">Discrete applied mathematics</title><title level="j" type="abbreviated">Discrete appl. math.</title><idno type="ISSN">0166-218X</idno><imprint><date when="2012">2012</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Discrete applied mathematics</title><title level="j" type="abbreviated">Discrete appl. math.</title><idno type="ISSN">0166-218X</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term><term>Batch processing</term><term>Combinatorics</term><term>Compatibility</term><term>Completion</term><term>Complexity</term><term>Computer theory</term><term>Dynamic programming</term><term>Intersection</term><term>Makespan</term><term>Maximum</term><term>Minimization</term><term>Objective function</term><term>Optimization</term><term>Processing time</term><term>Schedule</term><term>Scheduling</term><term>Time interval</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Informatique théorique</term><term>Optimisation</term><term>Combinatoire</term><term>Ordonnancement</term><term>Temps traitement</term><term>Compatibilité</term><term>Fonction objectif</term><term>Intervalle temps</term><term>Traitement par lot</term><term>Intersection</term><term>Horaire</term><term>Algorithme</term><term>Complétion</term><term>Minimisation</term><term>Programmation dynamique</term><term>Temps total achèvement</term><term>Maximum</term><term>Complexité</term><term>68M20</term><term>68Wxx</term><term>49Lxx</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">The problem of scheduling n jobs on an unbounded batching machine to minimize a regular objective function is studied. In this problem intervals for job processing times are given. The machine can process any number of jobs in a batch, provided that the processing time intervals of these jobs have a non-empty intersection. The jobs in the same batch start and complete together, and the batch processing time is equal to the left endpoint of the intersection of the processing time intervals in this batch. Properties of an optimal schedule are established and an enumerative algorithm based on these properties is developed. For the total completion time minimization, a dynamic programming algorithm is developed. Minimizing the makespan is shown to be solvable in 0(n log n) time and minimizing the maximum lateness is proved to be NP-hard.</div></front></TEI><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0166-218X</s0></fA01><fA02 i1="01"><s0>DAMADU</s0></fA02><fA03 i2="1"><s0>Discrete appl. math.</s0></fA03><fA05><s2>160</s2></fA05><fA06><s2>1-2</s2></fA06><fA08 i1="01" i2="1" l="ENG"><s1>Scheduling an unbounded batching machine with job processing time compatibilities</s1></fA08><fA11 i1="01" i2="1"><s1>BELLANGER (A.)</s1></fA11><fA11 i1="02" i2="1"><s1>JANIAK (A.)</s1></fA11><fA11 i1="03" i2="1"><s1>KOVALYOV (M. Y.)</s1></fA11><fA11 i1="04" i2="1"><s1>OULAMARA (A.)</s1></fA11><fA14 i1="01"><s1>Nancy University, LORIA laboratory, Ecole des Mines de Nancy, Parc de Saurupt</s1><s2>54042 Nancy</s2><s3>FRA</s3><sZ>1 aut.</sZ><sZ>4 aut.</sZ></fA14><fA14 i1="02"><s1>Institute of Engineering Cybernetics, Wroclaw University of Technology, Janiszewskiego 11/17</s1><s2>50-372 Wroclaw</s2><s3>POL</s3><sZ>2 aut.</sZ></fA14><fA14 i1="03"><s1>United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6</s1><s2>220012 Minsk</s2><s3>BLR</s3><sZ>3 aut.</sZ></fA14><fA20><s1>15-23</s1></fA20><fA21><s1>2012</s1></fA21><fA23 i1="01"><s0>ENG</s0></fA23><fA43 i1="01"><s1>INIST</s1><s2>18287</s2><s5>354000505995140030</s5></fA43><fA44><s0>0000</s0><s1>© 2012 INIST-CNRS. All rights reserved.</s1></fA44><fA45><s0>21 ref.</s0></fA45><fA47 i1="01" i2="1"><s0>12-0046320</s0></fA47><fA60><s1>P</s1></fA60><fA61><s0>A</s0></fA61><fA64 i1="01" i2="1"><s0>Discrete applied mathematics</s0></fA64><fA66 i1="01"><s0>GBR</s0></fA66><fC01 i1="01" l="ENG"><s0>The problem of scheduling n jobs on an unbounded batching machine to minimize a regular objective function is studied. In this problem intervals for job processing times are given. The machine can process any number of jobs in a batch, provided that the processing time intervals of these jobs have a non-empty intersection. The jobs in the same batch start and complete together, and the batch processing time is equal to the left endpoint of the intersection of the processing time intervals in this batch. Properties of an optimal schedule are established and an enumerative algorithm based on these properties is developed. For the total completion time minimization, a dynamic programming algorithm is developed. Minimizing the makespan is shown to be solvable in 0(n log n) time and minimizing the maximum lateness is proved to be NP-hard.</s0></fC01><fC02 i1="01" i2="X"><s0>001D02A05</s0></fC02><fC02 i1="02" i2="X"><s0>001A02B01</s0></fC02><fC02 i1="03" i2="X"><s0>001D02B10</s0></fC02><fC02 i1="04" i2="X"><s0>001A02E18</s0></fC02><fC03 i1="01" i2="X" l="FRE"><s0>Informatique théorique</s0><s5>01</s5></fC03><fC03 i1="01" i2="X" l="ENG"><s0>Computer theory</s0><s5>01</s5></fC03><fC03 i1="01" i2="X" l="SPA"><s0>Informática teórica</s0><s5>01</s5></fC03><fC03 i1="02" i2="X" l="FRE"><s0>Optimisation</s0><s5>02</s5></fC03><fC03 i1="02" i2="X" l="ENG"><s0>Optimization</s0><s5>02</s5></fC03><fC03 i1="02" i2="X" l="SPA"><s0>Optimización</s0><s5>02</s5></fC03><fC03 i1="03" i2="X" l="FRE"><s0>Combinatoire</s0><s5>03</s5></fC03><fC03 i1="03" i2="X" l="ENG"><s0>Combinatorics</s0><s5>03</s5></fC03><fC03 i1="03" i2="X" l="SPA"><s0>Combinatoria</s0><s5>03</s5></fC03><fC03 i1="04" i2="X" l="FRE"><s0>Ordonnancement</s0><s5>17</s5></fC03><fC03 i1="04" i2="X" l="ENG"><s0>Scheduling</s0><s5>17</s5></fC03><fC03 i1="04" i2="X" l="SPA"><s0>Reglamento</s0><s5>17</s5></fC03><fC03 i1="05" i2="X" l="FRE"><s0>Temps traitement</s0><s5>18</s5></fC03><fC03 i1="05" i2="X" l="ENG"><s0>Processing time</s0><s5>18</s5></fC03><fC03 i1="05" i2="X" l="SPA"><s0>Tiempo proceso</s0><s5>18</s5></fC03><fC03 i1="06" i2="X" l="FRE"><s0>Compatibilité</s0><s5>19</s5></fC03><fC03 i1="06" i2="X" l="ENG"><s0>Compatibility</s0><s5>19</s5></fC03><fC03 i1="06" i2="X" l="SPA"><s0>Compatibilidad</s0><s5>19</s5></fC03><fC03 i1="07" i2="X" l="FRE"><s0>Fonction objectif</s0><s5>20</s5></fC03><fC03 i1="07" i2="X" l="ENG"><s0>Objective function</s0><s5>20</s5></fC03><fC03 i1="07" i2="X" l="SPA"><s0>Función objetivo</s0><s5>20</s5></fC03><fC03 i1="08" i2="X" l="FRE"><s0>Intervalle temps</s0><s5>21</s5></fC03><fC03 i1="08" i2="X" l="ENG"><s0>Time interval</s0><s5>21</s5></fC03><fC03 i1="08" i2="X" l="SPA"><s0>Intervalo tiempo</s0><s5>21</s5></fC03><fC03 i1="09" i2="X" l="FRE"><s0>Traitement par lot</s0><s5>22</s5></fC03><fC03 i1="09" i2="X" l="ENG"><s0>Batch processing</s0><s5>22</s5></fC03><fC03 i1="09" i2="X" l="SPA"><s0>Procesamiento por lote</s0><s5>22</s5></fC03><fC03 i1="10" i2="X" l="FRE"><s0>Intersection</s0><s5>23</s5></fC03><fC03 i1="10" i2="X" l="ENG"><s0>Intersection</s0><s5>23</s5></fC03><fC03 i1="10" i2="X" l="SPA"><s0>Intersección</s0><s5>23</s5></fC03><fC03 i1="11" i2="X" l="FRE"><s0>Horaire</s0><s5>24</s5></fC03><fC03 i1="11" i2="X" l="ENG"><s0>Schedule</s0><s5>24</s5></fC03><fC03 i1="11" i2="X" l="SPA"><s0>Horario</s0><s5>24</s5></fC03><fC03 i1="12" i2="X" l="FRE"><s0>Algorithme</s0><s5>25</s5></fC03><fC03 i1="12" i2="X" l="ENG"><s0>Algorithm</s0><s5>25</s5></fC03><fC03 i1="12" i2="X" l="SPA"><s0>Algoritmo</s0><s5>25</s5></fC03><fC03 i1="13" i2="X" l="FRE"><s0>Complétion</s0><s5>26</s5></fC03><fC03 i1="13" i2="X" l="ENG"><s0>Completion</s0><s5>26</s5></fC03><fC03 i1="13" i2="X" l="SPA"><s0>Compleción</s0><s5>26</s5></fC03><fC03 i1="14" i2="X" l="FRE"><s0>Minimisation</s0><s5>27</s5></fC03><fC03 i1="14" i2="X" l="ENG"><s0>Minimization</s0><s5>27</s5></fC03><fC03 i1="14" i2="X" l="SPA"><s0>Minimización</s0><s5>27</s5></fC03><fC03 i1="15" i2="X" l="FRE"><s0>Programmation dynamique</s0><s5>28</s5></fC03><fC03 i1="15" i2="X" l="ENG"><s0>Dynamic programming</s0><s5>28</s5></fC03><fC03 i1="15" i2="X" l="SPA"><s0>Programación dinámica</s0><s5>28</s5></fC03><fC03 i1="16" i2="X" l="FRE"><s0>Temps total achèvement</s0><s5>29</s5></fC03><fC03 i1="16" i2="X" l="ENG"><s0>Makespan</s0><s5>29</s5></fC03><fC03 i1="16" i2="X" l="SPA"><s0>Tiempo total acabamiento</s0><s5>29</s5></fC03><fC03 i1="17" i2="X" l="FRE"><s0>Maximum</s0><s5>30</s5></fC03><fC03 i1="17" i2="X" l="ENG"><s0>Maximum</s0><s5>30</s5></fC03><fC03 i1="17" i2="X" l="SPA"><s0>Máximo</s0><s5>30</s5></fC03><fC03 i1="18" i2="X" l="FRE"><s0>Complexité</s0><s5>31</s5></fC03><fC03 i1="18" i2="X" l="ENG"><s0>Complexity</s0><s5>31</s5></fC03><fC03 i1="18" i2="X" l="SPA"><s0>Complejidad</s0><s5>31</s5></fC03><fC03 i1="19" i2="X" l="FRE"><s0>68M20</s0><s4>INC</s4><s5>70</s5></fC03><fC03 i1="20" i2="X" l="FRE"><s0>68Wxx</s0><s4>INC</s4><s5>71</s5></fC03><fC03 i1="21" i2="X" l="FRE"><s0>49Lxx</s0><s4>INC</s4><s5>72</s5></fC03><fN21><s1>023</s1></fN21><fN44 i1="01"><s1>OTO</s1></fN44><fN82><s1>OTO</s1></fN82></pA></standard></inist><affiliations><list><country><li>Biélorussie</li><li>France</li><li>Pologne</li></country><region><li>Grand Est</li><li>Lorraine (région)</li></region><settlement><li>Nancy</li></settlement></list><tree><country name="France"><region name="Grand Est"><name sortKey="Bellanger, A" sort="Bellanger, A" uniqKey="Bellanger A" first="A." last="Bellanger">A. Bellanger</name></region><name sortKey="Oulamara, A" sort="Oulamara, A" uniqKey="Oulamara A" first="A." last="Oulamara">A. Oulamara</name></country><country name="Pologne"><noRegion><name sortKey="Janiak, A" sort="Janiak, A" uniqKey="Janiak A" first="A." last="Janiak">A. Janiak</name></noRegion></country><country name="Biélorussie"><noRegion><name sortKey="Kovalyov, M Y" sort="Kovalyov, M Y" uniqKey="Kovalyov M" first="M. Y." last="Kovalyov">M. Y. Kovalyov</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000101 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Checkpoint/biblio.hfd -nk 000101 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= PascalFrancis
|étape= Checkpoint
|type= RBID
|clé= Pascal:12-0046320
|texte= Scheduling an unbounded batching machine with job processing time compatibilities
}}
| This area was generated with Dilib version V0.6.33. |  |