An efficient partial-order representation of feasible schedules for online decisions

Saajid Haque, Donatello Materassi, Saverio Bolognani, Mardavij Roozbehani, Munther A. Dahleh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 languageEnglish (US)
Title of host publication2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2641-2646
Number of pages6
ISBN (Electronic)9781509028733
DOIs
StatePublished - Jan 18 2018
Externally publishedYes
Event56th IEEE Annual Conference on Decision and Control, CDC 2017 - Melbourne, Australia
Duration: Dec 12 2017Dec 15 2017

Publication series

Name2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
Volume2018-January

Other

Other56th IEEE Annual Conference on Decision and Control, CDC 2017
CountryAustralia
CityMelbourne
Period12/12/1712/15/17

Fingerprint Dive into the research topics of 'An efficient partial-order representation of feasible schedules for online decisions'. Together they form a unique fingerprint.

  • Cite this

    Haque, S., Materassi, D., Bolognani, S., Roozbehani, M., & Dahleh, M. A. (2018). An efficient partial-order representation of feasible schedules for online decisions. In 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017 (pp. 2641-2646). (2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017; Vol. 2018-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2017.8264042