Interruptible algorithms for multiproblem solving

DOI10.1007/S10951-020-00644-9MaRDI QIDQ2197326zbMATH OpenOpenAlexFDO

Authors Spyros Angelopoulos, Alejandro Lopez-Ortiz

Publication date 31 August 2020

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.11291

zbMATH Keywords

acceleration ratioanytime computationcontract algorithmsinterruptible algorithmsperformance measures in schedulingscheduling problems in artificial intelligence

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Deterministic scheduling theory in operations research (90B35)

Abstract: In this paper we address the problem of designing an interruptible system in a setting in which $n$ problem instances, all equally important, must be solved concurrently. The system involves scheduling executions of contract algorithms (which offer a trade-off between allowable computation time and quality of the solution) in m identical parallel processors. When an interruption occurs, the system must report a solution to each of the $n$ problem instances. The quality of this output is then compared to the best-possible algorithm that has foreknowledge of the interruption time and must, likewise, produce solutions to all $n$ problem instances. This extends the well-studied setting in which only one problem instance is queried at interruption time. In this work we first introduce new measures for evaluating the performance of interruptible systems in this setting. In particular, we propose the deficiency of a schedule as a performance measure that meets the requirements of the problem at hand. We then present a schedule whose performance we prove that is within a small factor from optimal in the general, multiprocessor setting. We also show several lower bounds on the deficiency of schedules on a single processor. More precisely, we prove a general lower bound of (n+1)/n, an improved lower bound for the two-problem setting (n=2), and a tight lower bound for the class of round-robin schedules. Our techniques can also yield a simpler, alternative proof of the main result of [Bernstein et al, IJCAI 2003] concerning the performance of cyclic schedules in multiprocessor environments.

Recommendations

• Optimal scheduling of contract algorithms for anytime problem-solving
• Optimal scheduling of contract algorithms with soft deadlines
• Synthesizing a multiprocessor system for scheduling with interruptions and execution intervals
• scientific article; zbMATH DE number 3978371
• scientific article; zbMATH DE number 1157215

Cites work

• Algorithm portfolios
• Bounds for Certain Multiprocessing Anomalies
• scientific article; zbMATH DE number 67465 (Why is no real title available?)
• Hyperbolic Dovetailing
• Lower bounds in on-line geometric searching
• Optimal scheduling of contract algorithms for anytime problem-solving
• Optimal scheduling of contract algorithms with soft deadlines
• Optimal sequencing of contract algorithms
• Search games
• The Oil Searching Problem
• The theory of search games and rendezvous.

Cited in

(6)

• Optimal composition of real-time systems
• Optimal scheduling of contract algorithms for anytime problem-solving
• scientific article; zbMATH DE number 1953323 (Why is no real title available?)
• scientific article; zbMATH DE number 2086769 (Why is no real title available?)
• Etude des interruptions dans l'algorithme de Jacobi–Perron
• Contract scheduling with predictions

This page was built for publication: Interruptible algorithms for multiproblem solving

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197326)