Line search method for solving a non-preemptive strictly periodic scheduling problem

Line search method for solving a non-preemptive strictly periodic scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20162388
Volume: 19
Issue: 3
Start Page Number: 227
End Page Number: 243
Publication Date: Jun 2016
Journal: Journal of Scheduling
Authors: ,
Keywords: computers, combinatorial optimization, game theory
Abstract:

We study a non‐preemptive strictly periodic scheduling problem. This problem arises for example in the avionic field where a set of N equ1 periodic tasks (measure of a sensor, data presentation, etc.) has to be scheduled on P equ2 processors distributed on the plane. In this article, we consider an existing heuristic which is based on the notion of equilibrium. Following a game theory analogy, each task tries successively to optimize its own schedule and, therefore, to produce the best response, given the other schedules. This iterative process continues until an equilibrium is reached. We present a new method to compute the best response which significantly improves the previously proposed heuristic, and compares favorably with MILP solutions.

Reviews

Required fields are marked *. Your email address will not be published.