In many scheduling problems involving sporadic tasks with multiple deadlines, there is typically a large degree of flexibility in determining which tasks to serve at each time step. Given a cost function it is often possible to cast a scheduling problem as an optimization problem to obtain the most suitable schedule. However, in several applications, especially when the schedule has to be computed in-line or periodically adjusted, the cost function may not be completely known a priori but only partially. For example, in some applications only the cost of the current allocation of resources to the tasks could be available. Under this scenario, a sensible approach is to optimally allocate resources without compromising the schedulability of the tasks. The article tackles this problem by introducing a notion of partial ordering on the set of feasible schedules. This partial ordering is particularly useful to characterize which allocations of resources at the current time preserve the feasibility of the problem in the future. This enables the realization of fast algorithms for real-time scheduling. The model and algorithm presented in this article can be utilized in different applications such as electric vehicle charging, cloud computing and advertising on websites.
|Original language||English (US)|
|Title of host publication||2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||6|
|State||Published - Jan 18 2018|
|Event||56th IEEE Annual Conference on Decision and Control, CDC 2017 - Melbourne, Australia|
Duration: Dec 12 2017 → Dec 15 2017
|Name||2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017|
|Other||56th IEEE Annual Conference on Decision and Control, CDC 2017|
|Period||12/12/17 → 12/15/17|
Bibliographical noteFunding Information:
V. ACKNOWLEDGMENTS The authors D. Materassi and S. Haque acknowledge ARPA-E for supporting this research through the project titled A Robust Distributed Framework for Flexible Power Grids.
© 2017 IEEE.