Optimal scheduling of contract algorithms with soft deadlines

Spyros Angelopoulos, Alejandro López-Ortiz () and Angèle Hamel
Additional contact information
Spyros Angelopoulos: Sorbonne Universités, UPMC Univ Paris 06, UMR 7606, LIP6
Alejandro López-Ortiz: University of Waterloo
Angèle Hamel: Wilfrid Laurier University

Journal of Scheduling, 2017, vol. 20, issue 3, No 4, 267-277

Abstract: Abstract A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time, and may not return useful results if interrupted prior to that time. In contrast, an interruptible algorithm will always output some meaningful (albeit suboptimal) solution, even if interrupted during its execution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a well-studied problem with significant applications in AI. In the standard model, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper, we study the more general setting of scheduling contract algorithms in the presence of soft deadlines. In particular, we address the setting in which if an interruption occurs at time t, then the system is given an additional window of time $$w(t)\le c \cdot t$$ w ( t ) ≤ c · t , for constant c, within which the simulation must be completed. We formulate extensions to performance measures of schedules under this setting and derive schedules of optimal performance for all concave functions w.

Keywords: Anytime computation; Contract algorithms; Interruptible algorithms; Acceleration ratio; Scheduling problems in Artificial Intelligence (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-016-0483-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:20:y:2017:i:3:d:10.1007_s10951-016-0483-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-016-0483-z

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().