Dynamic job scheduling with strict deadline
- 1 January 1990
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 116-121 vol.1
- https://doi.org/10.1109/cdc.1990.203556
Abstract
Dynamic job scheduling on one processor is considered. In the problem, multiple types of jobs arrive randomly with deterministic processing time requirements, values and deadlines. If a job cannot be processed within its deadline, its value is lost. The objective is to schedule jobs so as to minimize the overall expected loss over an infinite horizon. The single processor scheduling problem is NP-hard. To solve the problem within a polynomial computation time, this study assumes that a job is to be scheduled upon its arrival and that it cannot bump previously scheduled ones. The problem is then solved within a stochastic dynamic programming framework. For I types of jobs the T units of initial time available, an algorithm of O(T/sup 2/(I+1)) operations is developed to obtain the optimal policy. Using the algorithm, extensive numerical tests are performed to examine various properties of the optimal policy.Keywords
This publication has 4 references indexed in Scilit:
- Stochastic task selection and renewable resource allocationIEEE Transactions on Automatic Control, 1989
- Scheduling Tasks with Resource Requirements in Hard Real-Time SystemsIEEE Transactions on Software Engineering, 1987
- Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling ProblemsMathematics of Operations Research, 1983
- A Functional Equation and its Application to Resource Allocation and Sequencing ProblemsManagement Science, 1969