Real-Time Scheduling of Weighted Jobs with Multiple Feasible Intervals

Time-critical jobs in many real-time applications have multiple feasible intervals. Such a job must be executed within one of its feasible intervals. In this paper, we are interested in maximizing the sum of the weights of the multiple feasible interval jobs that complete in time when jobs are associated with weights for its in-time completion. We develop heuristic algorithms that apply the least-earliest-completion-time-first (LECF) strategy as a schedulability test or apply variations of the LECF strategy with job evictions. The capability of our proposed algorithms is verified by a series of simulations.