Scheduling problems with various types of resources  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
112881
Type K
Principal investigator Kis, Tamás
Title in Hungarian Ütemezési problémák különféle erőforrás korlátokkal
Title in English Scheduling problems with various types of resources
Keywords in Hungarian ütemezéselmélet, erőforrás korlátok, optimalizálás, algoritmusok, approximáció
Keywords in English scheduling theory, resource constraints, optimization, algorithms, approximation
Discipline
Operational Research (Council of Physical Sciences)70 %
Ortelius classification: Operations research
Information Technology (Council of Physical Sciences)30 %
Ortelius classification: Informatics
Panel Mathematics and Computing Science
Department or equivalent HUN-REN Institute for Computer Science and Control
Participants Drótos, Márton
Egri, Péter
Horváth, Markó
Starting date 2014-09-01
Closing date 2018-07-31
Funding (in million HUF) 8.871
FTE (full time equivalent) 4.77
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.

Ütemezési problémák egyik lehetséges kiterjesztése, hogy a műveletek különféle megújuló, és nem megújuló erőforrásokat is
igényelnek egy-egy alap erőforráson (gép / jármű) túl, és olyan ütemtervet kell találni, ami betartja az alap ütemezési probléma korlátozásait, valamint az erőforrások használatából eredő további korlátozásokat is.
Részben erőforrásokkal kiegészített gépütemezési, részben pedig kombinált jármű, és a vezető ütemezési problémákat kívánunk vizsgálni.

Különösen ígéretes irány a nem megújuló erőforrásokkal kiegészített gépütemezési problémák esetében a hátizsák feladat különféle változataival való kapcsolat vizsgálata. A kombinált jármű és vezető ütemezési probléma szorosan kapcsolódik az erőforrás korlátos legrövidebb út problémához, ahol egy irányított gráfban,
melynek élei egy hossz paraméteren túl erőforrás igényekkel is cimkézettek) keresünk olyan s-t utat, amely teljesíti azt a további feltételt is, hogy az út éleinek erőforrás igénye(i) nem haladja meg az adott korlátokat.

Célunk a fentebb megfogalmazott ütemezési problémák elméleti vizsgálata a diszkrét matematika eszközeivel. Az elérni kívánt eredmények:
1) Néhány erőforrás korlátos gépütemezési problémára új, polinomiális időben megoldható speciális eset azonosítása, és az NP-nehéz esetekre approximációs algoritmusok kidolgozása.
2) Az erőforrás korlátos legrövidebb út probléma vizsgálata a poliéderes kombinatorika eszközeivel.
3) Új matematikai modellek, és azokra épülő egzakt és heurisztikus algoritmusok kidolgozása a fent nevezett problémákra, valamint azok számítógépes implementálása, és tesztelése.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.

A kutatás során olyan ütemezési problémákat vizsgálunk, ahol az elvégzendő feladatok egy alap erőforráson túl
további megújuló, ill. nem megújuló erőforrásokat is igényelnek.
A következő problémákat és kérdéseket vizsgáljuk:
1) Ütemezés nem megújuló erőforrásokkal.
Erőforrást csak fogyasztó, csak előállító, illetve vegyes jobokat tartalmazó ütemezési problémáit szeretnénk vizsgálni, egy és többgépes környezetben, különféle további feltételek és célfüggvények mellett. Alapkérdés az approximálhatóság, ill. hatékony egzakt és heurisztikus módszerek kidolgozása.
Fel szeretnénk tárni a nem-megújuló erőforrásos gépütemezési problémák kapcsolatát a hátizsák probléma különböző változataival, valamint az erőforrás korlátos legrövidebb út problémával.


2) Kombinált jármű és vezető ütemezés. Erre a problémára csak kevés eredmény létezik, bár önmagában a jármű, ill. a vezető ütemezési problémákra számos megoldás létezik. Alapkérdés a kombinált feladat korábbiaknál jobb modellezése, és hatékony megoldása.

3) Célunk az erőforrás korlátos legrövidebb út probléma poliéderes vizsgálata, valamint hatékony szétválasztás-és-vágás típusú módszer kidolgozása.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!

A felvetett problémák néhány alap ütemezési probléma kiterjesztései, vizsgálatuk mind elméleti, mind pedig gyakorlati szempontból fontos.
A kutatás során remélt egzakt és approximációs algoritmusok várhatóan új megközelítést igényelnek, amelyek új fényt vethetnek az erőforrás korlátos gépütemezési problémákra, illetve az erőforrás korlátos jármű útvonal tervezési problémára.

A nem megújuló erőforrásokkal kibővített gépütemezési problémák esetén ígéretes irány a hátizsák probléma különféle változataival való kapcsolatok vizsgálata. A gépütemezés, mint keret azt jelenti, hogy az azonos géphez
rendelt műveleteket sorrendezni kell, szemben az általánosabb projekt ütemezési problémákkal. Ezt a specialitást ki lehet, és ki is kell használni az algoritmusokban.

A kombinált jármű és vezető ütemezési probléma akár a tömegközlekedés (buszok / vezetők), akár a légi közlekedésben (repülők / pilóták) felmerül, a korábbiaknál hatékonyabb megoldás jelentős gazdasági előnnyel járhat.

A kutatást a gyakorlati életben felmerülő gyártásütemezési, illetve közlekedés optimalizálási problémák motiválják, amelyek elméleti hátteréül szolgálnak a fentebb megfogalmazott problémák. A heurisztikus és egzakt módszerek alapul szolgálhatnak gyakorlati problémák megoldásának.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.

Az ütemezés célja az erőforrások minél jobb kihasználása, ezáltal a hatékonyság növelése, és a
költségek csökkentése. A gyártásütemezésnek, illetve a jármű, és vezető ütemezésnek komoly matematikai háttere van, a kutatás célja ennek a háttérnek a
kiszélesítése olyan problémák megoldása érdekében, ahol egyidejűleg több erőforrást veszünk figyelembe.
Gyártásütemezés esetében gépeket, szerszámokat, beépülő anyagokat, energiát, sőt, a gépeket kezelő embereket is; míg jármű ütemezésnél a jármű, és a vezető együttes ütemezése a feladat.
Bár a valós körülmények között a felvázolt problémák nap-mint-nap felmerülnek, de a létező döntéstámogató rendszerek ad-hoc megoldásokra, egymás után
meghozott döntésekre épülnek, nem pedig a probléma egészét veszik figyelembe. Ebből következően a döntések minőségét
sem lehet garantálni. A kutatás célja olyan döntéstámogató rendszerek matematikai hátterének
kidolgozása, amelyek az erőforrásokat együttesen veszik figyelembe, és az eredmények minőségének mérésére is keretet biztosítanak.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.

A possible extension of scheduling problems that jobs require renewable and/or non-renewable resources in addition to some common resources (like machines, or vehicles), and one seeks optimal or suboptimal schedules that respect the ordinary problem constraints, and the extra resource constraints as well. In this framework, we plan to study machine scheduling problems augmented with renewable and non-renewable resources, and combined vehicle and driver scheduling problems.

In case of machine scheduling extended with non-renewable resources it is a promising direction to investigate the connections to variants of the knapsack problem. The combined vehicle and driver scheduling problem problem is strongly related to the resource constrained shortest path problem, where in a directed graph a shortest s-t path is sought such that the resource requirements of the
arcs of the path (each arc has a new parameter representing some resource requirements) do not exceed some bounds.

Our goal is to investigate the above mentioned problems with the tools of discrete mathematics. The desired results are:
1) For some of the machine scheduling problems with resource constraints, identification of new polynomially solvable special cases, and development of approximation algorithms for NP-hard variants.
2) New approaches for solving the resource constrained shortest path problem based on polyhedral combinatorics.
3) New mathematical models and based on them, new exact and heuristical methods, along with implementation and testing on benchmark instances for each problem class.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.

In the course of the project, we plan to investigate scheduling problems in which the jobs beside some basic resource also require some additional renewable or non-renewable resources.
We will study the following problems and questions:

1) Scheduling with non-renewable resources. We will focus on scheduling problems with resource consuming / resource producing, and both consuming and producing jobs in case of single and multiple machine environments, and under additional assumptions and with various objective functions. The basic question is approximability, and efficient exact and heuristic procedures. We also wish to explore the links with variants of the knapsack problem, and also with the resource constrained shortest path problem.

2) Combined vehicle and driver scheduling problem. There are only a few approaches in the literature, although for the vehicle scheduling- and also for the driver scheduling problems separately a number of methods have been developed.
The basic questions are the clever modeling of the problem and efficient solution approaches.

3) The polyhedral study and efficient solution of the resource constrained shortest path problem by branch-and-cut type methods is a challenging task which we want to address as well.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.

The problems of interest are extensions of basic scheduling problems, their study is important both from the theoretical and from the practical point of view.
The expected exact and approximation algorithms are likely to require new approaches, which may shed new light on resource constrained machine scheduling problems, and on the combined vehicle and driver scheduling problems.

In case of machine scheduling extended with non-renewable resources, it is promising to explore the link with the variants of the knapsack problem. Machine scheduling means that jobs assigned to the same machine must be sequenced, in contrast to the more general project scheduling problems. This property may be, and will be exploited.

The combined vehicle and driver scheduling problem emerges in public transport (buses / drivers), or in civil aviation (air planes / pilots), algorithms better than the state-of-the-art may be of considerable interest.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.

The goal of scheduling is to support the better use of resources, and in this ways to improve efficiency, and the reduction of the costs. Production scheduling, and vehicle and driver scheduling have serious mathematical background and the goal of the proposed research is to widen it in order to solve scheduling problems which involve various types of resources at the same time.
In case of production scheduling, we consider machines, tools, raw materials, energy, and human operators,
whereas in case of vehicle scheduling, our goal is the combined scheduling of vehicles and drivers.
Although these problems frequently emerge in practice, existing decision support systems are based on ad-hoc solutions, frequently the decision process in separated into steps and decisions on the various resources are taken separately, instead of considering the problem as a whole. Consequently, the quality of decisions cannot be guaranteed. The goal of the research is to develop the mathematical background of decision support systems
which take all the resources into account simultaneously, and provide adequate means to assess the quality of decisions.





 

Final report

 
Results in Hungarian
1. Olyan ütemezési problémákat vizsgáltunk, ahol a gépeken/processzorokon túl további nem-megújuló erőforrások (pl. felhasznált nyersanyag, energia, pénz) is szükségesek a munkák elvégzéséhez. Az egyik alapkérdés az approximálhatóság volt korlátos számítási kapacitás mellett, a másik pedig az, hogy hogyan lehet őket hatékonyan megoldani a gyakorlatban. Az approximálhatóságot illetően pozitív és negatív eredményeket is kaptunk különféle célfüggvényekre. Továbbá egy hatékony egzakt módszert is kidolgoztunk a maximális késés minimalizálására. 2. Az integrált jármű, és vezető ütemezési problémában járműveket, és a járművezetőket egyidejűleg kell ütemezni a járatokra, különféle szabályok betartása mellett. Kidolgoztunk egy új egzakt módszert ami korlátozás-és-árazás elven működik. Az új módszer heurisztikaként is alkalmazható, amennyiben nem várjuk meg a keresés befejeződését. Ismert tesztfeladatokon futtatva, a korábbiaknál jobb eredményeket kaptunk, ráadásul rövidebb idő alatt, mint más eljárások. 3. Új egzakt módszereket dolgoztunk ki az erőforrás korlátos legrövidebb út problémára, ahol egy hálózatban keresünk egy olyan minimális élköltségű utat két rögzített csúcs között, ami további költség korátokat is teljesít. Az egzakt módszerünkben logikai következtetési, és heurisztikus eljárásokat kombinálunk a keresés felgyorsítása érdekében. Új, a megengedett megoldásokra érvényes egyenlőtlenségeket is meghatároztunk, es azok hasznosságát szintén teszteltük.
Results in English
1. We thoroughly studied the extension of machine scheduling problems with non-renewable resources (like raw materials, energy, or money). Our basic question was how well such problems can be approximated with limited computational resources, and also, how to solve them efficiently in practice. We obtained both positive and negative results for single and parallel machine problems with s the maximum job completion time, or the total weighted completion time objective. We also developed an exact methods that solves single machine problems with the maximum lateness objective. 2. In the combined vehicle and driver scheduling problem, one seeks the simultaneous solution of a vehicle scheduling problem and the corresponding driver scheduling problem. We developed a new exact method, based on branch-and-price. The new method can also be used as a heuristic if the procedure is stopped before termination. We evaluated it on well-known benchmark instances, and in several cases we obtained better results than those available in the literature. 3. We have also studied the resource constrained shortest path problem, in which a shortest path between given two points of a network is sought which additional resource (or budget) constraints. We have designed a new linear programming based exact method, in which we apply logical deductions and heuristics to speed-up the search. We have also devised new cutting planes, and evaluated their effectiveness in the solution process.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=112881
Decision
Yes





 

List of publications

 
Györgyi Péter, Kis Tamás: Approximation schemes for parallel machine scheduling with non-renewable resources, European Journal of Operational Research, Vol. 258, 113-123, 2017
Györgyi Péter, Kis Tamás: Minimizing the maximum lateness on a single machine with raw material constraints by branch-and-cut, Computers & Industrial Engineering, Vol. 115, 220-225., 2018
Péter Györgyi, Tamás Kis: Approximability of scheduling problems with resource consuming jobs, Annals of Operations Research, 2015
Péter Györgyi, Tamás Kis: Reductions between scheduling problems with non-renewable resources and knapsack problems, Theoretical Computer Science, Vol. 565, pp. 63-76., 2015
Kis Tamás: Approximability of total weighted completion time with resource consuming jobs, Operations Research Letters Vol. 43, pp. 595–598., 2015
Drótos Márton, Kis Tamás: Hard planning and scheduling problems in the digital factory, Math for the Digital Factory, chapter in edited book, in press, 2016
Balas Egon, Kis Tamás: On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts, Mathematical Programming, Vol. 160, pp. 85-114., 2016
Györgyi Péter: A PTAS for a resource scheduling problem with arbitrary number of parallel machines, Operations Research Letters, in press, 2016
Györgyi Péter, Kis Tamás: Approximation schemes for parallel machine scheduling with non-renewable resources, European Journal of Operational Research, 113-123, 2017
Horváth Markó, Kis Tamás: Computing strong lower and upper bounds for the integrated multiple-depot vehicle and crew scheduling problem with branch-and-price., CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH, accepted, 2017
Egri Péter, Kis Tamás: Serial Dictatorship Mechanism for Project Scheduling with Non-Renewable Resources, JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, submitted, 2017
Györgyi Péter, Kis Tamás: Minimizing the maximum lateness on a single machine with raw material constraints by branch-and-cut., Computers & Industrial Engineering, submitted, 2017
Péter Györgyi, Tamás Kis: A probabilistic approach to pickup and delivery problems with time window uncertainty, Transportation Science, submitted, 2017
Horváth Markó, Kis Tamás: Multi-criteria approximation schemes for the resource constrained shortest path problem, OPTIMIZATION LETTERS, submitted, 2017
Madarasi Péter, Kis Tamás: Exact methods for the Strip Packing problem., Munkabeszámoló, 2017
Drótos Márton, Kis Tamás: Hard planning and scheduling problems in the digital factory, Math for the Digital Factory, chapter in edited book, pp. 3-19, 2017
Györgyi Péter: A PTAS for a resource scheduling problem with arbitrary number of parallel machines, Operations Research Letters, Vol 45, 604-609, 2017
Horváth Markó, Kis Tamás: Multi-criteria approximation schemes for the resource constrained shortest path problem, OPTIMIZATION LETTERS, Vol. 12, 475–483, 2018
Péter Györgyi, Tamás Kis: A probabilistic approach to pickup and delivery problems with time window uncertainty, European Journal of Operational Research, first revision submitted, 2017
Györgyi Péter, Kis Tamás: Minimizing total weighted completion time on a single machine subject to non-renewable resource constraints, Journal of Scheduling, submitted, 2017
Horváth Markó, Kis Tamás: Polyhedral results for position based scheduling of chains on a single machine, Annals of Operations Research, submitted, 2017
Györgyi P, Kis T: Approximation schemes for parallel machine scheduling with non-renewable resources, EJOR 258: (1) 113-123, 2017
Balas Egon, Kis Tamás: On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts, MATH PROGRAM 160: 85-114, 2016
Horváth Markó, Kis Tamás: Computing strong lower and upper bounds for the integrated multiple-depot vehicle and crew scheduling problem with branch-and-price, Central European Journal of Operations Research (megjelenés alatt), https://doi.org/10.1007/s10100-017-0489-4, 2017
Péter Györgyi, Tamás Kis: Approximability of scheduling problems with resource consuming jobs, Annals of Operations Research, 2015
Péter Györgyi, Tamás Kis: Reductions between scheduling problems with non-renewable resources and knapsack problems, Theoretical Computer Science, 2015
Kis Tamás: Approximability of total weighted completion time with resource consuming jobs, Operations Research Letters (elfogadva), 2015
Drótos Márton, Kis Tamás: Planning and Scheduling in the Digital Factory, Math for the Digital Factory, edited book (közlésre beköldve), 2015
Horváth Markó, Kis Tamás: Solving resource constrained shortest path problems with Branch-and-Cut, Computers & Operations Research (közlésre beküldve), 2014
Balas Egon, Kis Tamás: On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts, Mathematical Programming (első revízió beküldve), 2015
Kis Tamás: Approximability of total weighted completion time with resource consuming jobs, Operations Research Letters Vol. 43, pp. 595–598., 2015
Drótos Márton, Kis Tamás: Hard planning and scheduling problems in the digital factory, Math for the Digital Factory, chapter in edited book (accpeted), 2016
Horváth Markó, Kis Tamás: Solving resource constrained shortest path problems with LP-based methods, Computers & Operations Research, vol 73, pp. 150–164., 2016
Balas Egon, Kis Tamás: On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts, Mathematical Programming (accepted), 2016
Horváth Markó, Kis Tamás: Solving resource constrained shortest path problems with LP-based methods, Computers & Operations Research, vol 73, pp. 150–164., 2016
Györgyi Péter: A PTAS for a resource scheduling problem with arbitrary number of parallel machines, Operations Research Letters, submitted, 2016
Györgyi Péter, Kis Tamás: Approximation schemes for parallel machine scheduling with non-renewable resources, European Journal of Operational Research, elfogadva, nyomdaban, 2016
Kis Tamás: Approximability of total weighted completion time with resource consuming jobs, Operations Research Letters Vol. 43, pp. 595–598., 2015
Drótos Márton, Kis Tamás: Hard planning and scheduling problems in the digital factory, Math for the Digital Factory, chapter in edited book (megjelenés alatt), ISBN 978-3-319-63955-0, 2017
Györgyi P, Kis T: Approximability of scheduling problems with resource consuming jobs, ANN OPER RES 235: 319-336, 2015
Györgyi Péter: A PTAS for a resource scheduling problem with arbitrary number of parallel machines, Operations Research Letters, közlésre elfogadva, doi: 10.1016/j.orl.2017.09.007, 2017
Péter Györgyi, Tamás Kis: Reductions between scheduling problems with non-renewable resources and knapsack problems, Theoretical Computer Science: 565, 63-76, 2015
Egri Péter, Kis Tamás: Serial Dictatorship Mechanism for Project Scheduling with Non-Renewable Resources, Journal of Artificial Intelligence Research, bírálás alatt, 2017
Györgyi Péter, Kis Tamás: A probabilistic approach to pickup and delivery problems with time window uncertainty, Transportation Sceince, bírálás alatt, 2017
Györgyi Péter, Kis Tamás: Minimizing the maximum lateness on a single machine with raw material constraints by branch-and-cut, Computers & Industrial Engineering, bírálás alatt, 2017
Horváth Markó, Kis Tamás: Multi-criteria approximation schemes for the resource constrained shortest path problem, Optimization Letters, bírálás alatt, 2017
Madarasi Péter, Kis Tamás: Exact methods for the Strip Packing problem, kutatási jelentés, MTA SZTAKI, 2017
Egri Péter, Kis Tamás: Serial Dictatorship Mechanism for Project Scheduling with Non-Renewable Resources, International J. Production Economics, submitted, 2018




Back »