CHI-SHENG SHIHLiu, Jane W.-S.Jane W.-S.LiuCheong, Infan KuokInfan KuokCheong2020-05-042020-05-042003https://scholars.lib.ntu.edu.tw/handle/123456789/487931https://www.scopus.com/inward/record.uri?eid=2-s2.0-35048890656&doi=10.1007%2f978-3-540-24686-2_4&partnerID=40&md5=7a78ed5a12f1dac6dd11cf3aee5fef6fThis 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.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 schedulingconference paper10.1007/978-3-540-24686-2_42-s2.0-35048890656https://doi.org/10.1007/978-3-540-24686-2_4