Scheduling Jobs with Multiple Feasible Intervals.
Journal
Real-Time and Embedded Computing Systems and Applications, 9th International Conference, RTCSA 2003, Tainan, Taiwan, February 18-20, 2003. Revised Papers
Pages
53-71
Date Issued
2003
Author(s)
Abstract
This paper addresses the problem of scheduling real-time jobs that have multiple feasible intervals. The problem is NP-hard. We present an optimal branch-and-bound algorithm. When there is time to compute the schedule, this algorithm can be used. Otherwise, the simple heuristics presented here can be used. In addition, a priority-boosting EDF algorithm is designed to enhance the timeliness of jobs. Simulation results show that the combined use of the heuristics and the priority boosting EDF algorithm performs nearly as well as the optimal algorithm. © Springer-Verlag 2004.
Other Subjects
Algorithms; Branch and bound method; Embedded systems; Optimization; Real time systems; Scheduling; Scheduling algorithms; Branch-and-bound algorithms; EDF algorithm; NP-hard; Optimal algorithm; Real time; Scheduling jobs; Simple heuristics; Job shop scheduling
Type
conference paper