 |
Scheduling problems with various types of resources
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
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.
|
|
|
|
|
|
|
|
| |
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 |
|
|
|
|
|
|
|
|
|
