Stochastically minimizing total delay of jobs subject to random deadlines. (English) Zbl 1134.68326
Summary: This paper analyzes a scheduling system where a fixed number of nonpreemptive jobs is to be processed on multiple parallel processors with different processing speeds. Each processor has an exponential processing time distribution and the processors are ordered in ascending order of their mean processing times. Each job has its own deadline that is exponentially distributed with rate \(\beta\), independent of the deadlines of other jobs and also independent of job processing times. A job departs the system as soon as either its processing completes or its deadline occurs. We show that there exists a simple threshold strategy that stochastically minimizes the total delay of all jobs. The policy depends on distributions of processing times and deadlines, but is independent of the rate of deadlines. When the rate of the deadline distribution is 0 (no dead-lines), the total delay reduces to the flowtime (the sum of completion times of all jobs). If each job has its own probability of being correctly processed, then an extension of this policy stochastically maximizes the total number of correctly processed, nontardy jobs. We discuss possible generalizations and limitations of this result.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 60K30 | Applications of queueing theory (congestion, allocation, storage, traffic, etc.) |
| 90B36 | Stochastic scheduling theory in operations research |
References:
| [1] | DOI: 10.1016/0167-6911(88)90009-6 · Zbl 0658.90051 · doi:10.1016/0167-6911(88)90009-6 |
| [2] | DOI: 10.2307/3213970 · Zbl 0576.60091 · doi:10.2307/3213970 |
| [3] | DOI: 10.2307/1427379 · Zbl 0617.90044 · doi:10.2307/1427379 |
| [4] | DOI: 10.1109/TC.1984.1676440 · Zbl 0528.68022 · doi:10.1109/TC.1984.1676440 |
| [5] | DOI: 10.2307/3214654 · Zbl 0719.90090 · doi:10.2307/3214654 |
| [6] | Xu, Operations Research 39 (1991) |
| [7] | Ross, Introduction to stochastic dynamic programming (1983) · Zbl 0567.90065 |
| [8] | DOI: 10.2307/3214828 · Zbl 0728.90045 · doi:10.2307/3214828 |
| [9] | DOI: 10.1016/0167-6377(91)90013-F · Zbl 0751.90040 · doi:10.1016/0167-6377(91)90013-F |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
