Displaying similar documents to “Maintaining the feasibility of hard real-time systems with a reduced number of priority levels”

A new sufficient schedulability analysis for hybrid scheduling

Fengxiang Zhang, Yanfeng Zhai, Jianwei Liao (2016)

International Journal of Applied Mathematics and Computer Science

Similarity:

Earliest deadline first (EDF) and fixed priority (FP) are the most commonly used and studied scheduling algorithms for real-time systems. This paper focuses on combining the EDF and FP strategies in one system. We provide a new sufficient schedulability analysis for real-time hybrid task systems which are scheduled by EDF and FP. The proposed analysis has a polynomial time complexity and no restrictions on task parameters, where the relative deadline of each task could be less than,...

Scheduling with periodic availability constraints and irregular cost functions

Francis Sourd (2007)

RAIRO - Operations Research

Similarity:

This paper addresses a one-machine scheduling problem in which the efficiency of the machine is not constant, that is the duration of a task is longer in badly efficient time periods. Each task has an irregular completion cost. Under the assumption that the efficiency constraints are time-periodic, we show that the special case where the sequence is fixed can be solved in polynomial time. The general case is NP-complete so that we propose a two-phase heuristic to find good solutions....

Scheduling multiprocessor tasks on two parallel processors

Jacek Błażewicz, Paolo Dell'Olmo, Maciej Drozdowski (2002)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this work scheduling multiprocessor tasks on two parallel identical processors is considered. Multiprocessor tasks can be executed by more than one processor at the same moment of time. We analyze scheduling unit execution time and preemptable tasks to minimize schedule length and maximum lateness. Cases with ready times, due-dates and precedence constraints are discussed.

A tabu search algorithm to schedule university examinations.

Ramón Alvarez-Valdés, Enric Crespo, José M. Tamarit (1997)

Qüestiió

Similarity:

Scheduling examinations in a large university is an increasingly complex problem, due to its size, the growing flexibility of students' curricula and the interest in including a wide set of objectives and constraints. In this paper we present a new algorithm for this problem and its application to a university in Spain. A combination of heuristics, based on Tabu Search, first finds a solution in which no student has two exams simultaneously and then improves it by evenly...

Reservation table scheduling: branch-and-bound based optimization . integer linear programming techniques

Hadda Cherroun, Alain Darte, Paul Feautrier (2007)

RAIRO - Operations Research

Similarity:

The recourse to operation research solutions has strongly increased the performances of scheduling task in the High-Level Synthesis (called hardware compilation). Scheduling a whole program is not possible as too many constraints and objectives interact. We decompose high-level scheduling in three steps. Step 1: Coarse-grain scheduling tries to exploit parallelism and locality of the whole program (in particular in loops, possibly imperfectly nested) with a rough view of the target...

France Telecom workforce scheduling problem: a challenge

Sebastian Pokutta, Gautier Stauffer (2009)

RAIRO - Operations Research

Similarity:

In this paper, we describe the methodology used to tackle France Telecom workforce scheduling problem (the subject of the Roadef Challenge 2007) and we report the results obtained on the different data sets provided for the competition. Since the problem at hand appears to be NP-hard and due to the high dimensions of the instance sets, we use a two-step heuristical approach. We first devise a problem-tailored heuristic that provides good feasible solutions and then we use a meta-heuristic...

Scheduling problems with a common due window assignment: A survey

Adam Janiak, Tomasz Kwiatkowski, Maciej Lichtenstein (2013)

International Journal of Applied Mathematics and Computer Science

Similarity:

In this article a survey of studies on scheduling problems with a common due window assignment and earliness/tardiness penalty functions is presented. A due window is a generalization of the classical due date and describes a time interval in which a job should be finished. If a job is completed before or after the due window, it incurs an earliness or a tardiness penalty, respectively. In this survey we separately analyse the classical models with job-independent and job-dependent earliness/tardiness...