1818. General load-balancing problems
Invited abstract in session MB-7: Advances in scheduling: From theory to practice, stream Scheduling and Project Management.
Monday, 10:30-12:00Room: Clarendon GR.01
Authors (first author is the speaker)
| 1. | Péter Györgyi
|
| Institute for Computer Science and Control | |
| 2. | Tamas Kis
|
| Institute for Computer Science and Control | |
| 3. | Evelin Szögi
|
| Institute for Computer Science and Control |
Abstract
We study a scheduling problem, where unit-time jobs require given quantities from a common resource throughout their execution. Each job has a set of time intervals, and a schedule is feasible if each job is scheduled within one of its time intervals. A special variant of the problem is when each job has a single time interval, i.e., when we have release dates and deadlines. The objective is to find a feasible schedule that minimizes a convex function of the load of the resource throughout the scheduling horizon.
Several variants of this problem have been studied under different names, e.g., the problem is a generalization of the load balancing problem, where each job requires a single unit from the resource. In the last decade, interest in the topic has increased as different energy management problems have become more important.
The presentation provides an overview on some recent results, mainly focusing on polynomial algorithms for various extensions of the problem. We have new results
1) for problems, where the jobs have more general processing times,
2) for problems, with more complex objective functions,
3) and for a problem, where the jobs need to be scheduled on parallel machines.
Acknowledgement: This research has been supported by the TKP2021-NKTA-01 NRDIO grant on "Research on cooperative production and logistics systems to support a competitive and sustainable economy".
Keywords
- Scheduling
- Algorithms
- Combinatorial Optimization
Status: accepted
Back to the list of papers