Stochastic scheduling concerns scheduling problems involving random attributes, such as random processing times, random due dates, random weights, and stochastic machine breakdowns. Major applications arise in manufacturing systems, computer systems, communication systems, logistics and transportation, and machine learning, among others.
Introduction The objective of the stochastic scheduling problems can be regular objectives such as minimizing the total flowtime, the makespan, or the total tardiness cost of missing the due dates; or can be irregular objectives such as minimizing both earliness and tardiness costs of completing the jobs, or the total cost of scheduling tasks under likely arrival of a disastrous event such as a severe typhoon. The performance of such systems, as evaluated by a regular performance measure or an irregular performance measure, can be significantly affected by the scheduling policy adopted to prioritize over time the access of jobs to resources. The goal of stochastic scheduling is to identify scheduling policies that can optimize the objective. Stochastic scheduling problems can be classified into three broad types: problems concerning the scheduling of a batch of stochastic jobs, multi-armed bandit problems, and problems concerning the scheduling of queueing systems. These three types are usually under the assumption that complete information is available in the sense that the probability distributions of the random variables involved are known in advance. When such distributions are not fully specified and there are multiple competing distributions to model the random variables of interest, the problem is referred to as incomplete information. The Bayesian method has been applied to treat stochastic scheduling problems with incomplete information.
Scheduling of a batch of stochastic jobs In this class of models, a fixed batch of n {\displaystyle n} jobs with random process times, whose distributions are known, have to be completed by a set of m {\displaystyle m} machines to optimize a given performance objective. The simplest model in this class is the problem of sequencing a set of n {\displaystyle n} jobs on a single machine to minimize the expected weighted flowtime. Job processing times are independent random variables with a general distribution G i ( ⋅ ) {\displaystyle G_{i}(\cdot )} with mean p i {\displaystyle p_{i}} for job i {\displaystyle i} . Admissible policies must be nonanticipative (scheduling decisions are based on the system's history up to and including the present time) and nonpreemptive (processing of a job must proceed uninterruptedly to completion once started). Let w i ≥ 0 {\displaystyle w_{i}\geq 0} denote the cost rate incurred per unit time in the system for job i {\displaystyle i} , and let C ~ i {\displaystyle {\tilde {C}}_{i}} denote its random completion time. Let Π {\displaystyle \Pi } denote the class of all admissible policies, and let E π [ ⋅ ] {\displaystyle E_{\pi }[\cdot ]} denote expectation under policy π ∈ Π {\displaystyle \pi \in \Pi } . The problem can be stated as
min π ∈ Π w 1 E π [ C ~ 1 ] + ⋯ + w n E π [ C ~ n ] . {\displaystyle \min _{\pi \in \Pi }w_{1}E_{\pi }[{\tilde {C}}_{1}]+\cdots +w_{n}E_{\pi }[{\tilde {C}}_{n}].}
The optimal solution in the special deterministic case is given by the Shortest Weighted Processing Time rule of Smith: sequence jobs in nonincreasing order of the priority index w i p i {\displaystyle w_{i}p_{i}} . The natural extension of Smith's rule is also optimal to the above stochastic model. In general, the rule that assigns higher priority to jobs with shorter expected processing time is optimal for the flowtime objective under the following assumptions: when all the job processing time distributions are exponential; when all the jobs have a common general processing time distribution with a nondecreasing hazard rate function; and when job processing time distributions are stochastically ordered.
… excerpt ends here. Continue reading the full article.
