# Scheduling with Predictions

Woo-Hyung Cho<EMAIL_ADDRESS>Cornell University  Shane Henderson
<EMAIL_ADDRESS>Cornell University  David Shmoys<EMAIL_ADDRESS>Cornell University

###### Abstract

There is significant interest in deploying machine learning algorithms for
diagnostic radiology, as modern learning techniques have made it possible to
detect abnormalities in medical images within minutes. While machine-assisted
diagnoses cannot yet reliably replace human reviews of images by a
radiologist, they could inform prioritization rules for determining the order
by which to review patient cases so that patients with time-sensitive
conditions could benefit from early intervention.

We study this scenario by formulating it as a learning-augmented online
scheduling problem. We are given information about each arriving patient’s
urgency level in advance, but these predictions are inevitably error-prone. In
this formulation, we face the challenges of decision making under imperfect
information, and of responding dynamically to prediction error as we observe
better data in real-time. We propose a simple online policy and show that this
policy is in fact the best possible in certain stylized settings. We also
demonstrate that our policy achieves the two desiderata of online algorithms
with predictions: consistency (performance improvement with prediction
accuracy) and robustness (protection against the worst case). We complement
our theoretical findings with empirical evaluations of the policy under
settings that more accurately reflect clinical scenarios in the real world.

##  1 Introduction

Modern machine learning algorithms have been tremendously successful in a
variety of application domains, and healthcare is no exception. In recent
years, we have seen significant interest in deploying these algorithms for
diagnostic radiology, a branch of medicine that uses imaging techniques such
as X-rays, ultrasounds, and Magnetic Resonance Imaging (MRI) to diagnose a
patient. The idea is to use these images as inputs to machine learning
algorithms, which would then search for patterns that imply the presence of an
abnormality. Advances in pattern recognition techniques for image processing
and computer vision have made it possible for machine learning algorithms to
detect abnormal conditions in medical images within minutes, or even seconds.
Because this is still a nascent area of research, these algorithmic, machine-
assisted diagnoses cannot yet reliably replace the thorough, human reviews of
images by a radiologist. Meanwhile, they could be used to prioritize and speed
up the review of images that are flagged as likely to contain time-sensitive
conditions.

To make this more concrete, imagine a group of patients who have had
diagnostic images taken after a referral. Radiologists are tasked with
processing each patient case, which typically consists of reading images, then
communicating any findings by filing a radiology report and sending it back to
the referring provider. Appropriate patient care and treatment begin only upon
case completion at the radiology department, so it is in the best interest of
the patient for radiologists to organize their workflow in a way that
prioritizes cases by urgency. This is especially true for patients with time-
sensitive conditions such as stroke, intercranial hemorrhage, or pneumothorax,
for which early intervention is key. In the case of acute stroke due to large
vessel occlusion, for example, studies have shown that an interventional
radiology procedure called mechanical thrombectomy could achieve a favorable
clinical outcome when performed within 4 to 6 hours of symptom onset [24].
This is where machine learning could be helpful. Leveraging the speed and the
predictive power of machine learning, radiologists could use algorithmic
outputs to prioritize cases that are deemed urgent.

True urgency, however, cannot be fully assessed until a case is opened and
images are at least partially read. For this reason, many imaging clinics
including those in the New York-Presbyterian hospital network tend to rely on
the referring providers’ communication of expectations as well as on their own
insights, expertise and experience when prioritizing cases. In some sense,
current practices rely on human predictions of urgency. The use of predictions
powered by machine learning algorithms could augment current best practices
and streamline the process of determining the order by which patient cases
should be read.

But predictions, human-made or machine-learned, are rarely perfect. There will
always exist never-before-seen cases that further compound the error. Good
predictions have the potential to expedite the detection and treatment of
time-sensitive conditions, but mispredictions could cause delays that are
extremely costly. Given this understanding, the central question that we ask
in this paper is, how can we take advantage of predictions to improve
radiologists’ workflow while accounting for prediction error?

We abstract the setting described above and model it as a single-machine
scheduling problem. A radiologist tasked with reviewing patient cases can be
viewed as a single machine that is able to process one job at a time. Case
urgencies are captured in the form of job weights, where the higher the
weight, the greater the urgency. Patient treatment plans are often established
upon completion of case review from the radiology department, so a natural
objective would be to minimize the total sum of urgency-weighted completion
times across all patients.

This single-machine problem of minimizing the weighted sum of job completion
times is a decades-old problem that has already been extensively studied (see
[29, 10], for example). In this paper, we study this problem with the addition
of a key feature: imperfect predictions of urgency. Patient cases randomly
arrive into the system. At each job’s time of arrival, we observe its
predicted level of urgency given by some black-box predictive mechanism. True
urgency is unknown and unobservable at this time, so priority decisions are
necessarily made based on imperfect information. However, when radiologists
are working through a patient case, interpreting the associated images and
deciding if an abnormality is present, they are also gradually learning
whether or not the case on hand is truly urgent (or non-urgent). Anecdotal
evidence suggests that an image study is roughly a process of elimination via
inspection from different angles [16, 27], so it is likely that a job’s true
urgency is known even before its processing is complete. We therefore allow
radiologists to preempt a job midway then return to the remaining work for
completion at a later point in time. With a preemptive strategy, we have an
opportunity to hedge against prediction error by responding early to what is
in hindsight a suboptimal decision made in the face of less-than-perfect
information. We aim to find a policy for deciding which job or remainder
thereof to process at any given time so that the total expected urgency-
weighted sum of job completion times is minimized.

Our scheduling formulation allows for a wide range of models for describing
the problem setting in ways that more accurately reflect clinical settings in
the real world. For example, by using job weights to capture case urgencies,
we are able to handle granularity in prioritization schemes beyond a binary
classification of urgent vs. non-urgent. Our preemptive framework also allows
flexibility in modeling the many different ways in which radiologists gain
information as they process each patient case. Nevertheless, in this paper, we
focus on a highly stylized version of this model. We assume that each job can
be categorized as one of two types: urgent or non-urgent. All jobs are
available before any decisions are made, and we are able to observe each job’s
predicted priority class at this time. We further assume that every job shares
the same processing time requirement. Without loss of generality, we assume
unit processing time requirements. A fixed parameter $\alpha\in(0,1)$ is used
to denote the fraction of a job that must be processed before we learn its
true type. We call this time point a job’s $\alpha$-point. In our model, we
allow preemptions to occur only at these $\alpha$-points, and assume that the
residual work needed to complete an interrupted job is exactly the same as if
the job had not been interrupted.

Our problem of scheduling with predictions is an exercise in online decision
making even when all jobs are available to us in advance. Decisions are made
with incomplete information in the form of imperfect predictions, to which we
respond over time based on our observations of true job types. Classic results
in online decision making have focused on finding solutions that are robust
with provably good performance guarantees over all possible inputs and even in
the worst case. An emerging line of research in this area leverages
predictions to design algorithms that not only remain robust to worst-case
inputs but also achieve performance guarantees that improve with prediction
accuracy (see [23] for a survey). We continue this line of research and extend
it to our problem setting. In what follows, we first find a threshold-based
policy for deciding which job to process at any given time, and show that our
proposed policy is the best possible over all non-anticipating policies. We
then show that performance guarantees for this policy degrade gracefully as a
function of prediction error. Our results indicate that our policy
simultaneously achieves consistency (improvement with prediction accuracy) and
robustness (protection against the worst case).

#### Related Work

There has been an explosion of research activity in recent years that seeks to
augment online algorithms with machine-learned predictions. In this framework,
the goal is to design algorithms with near-optimal performance when
predictions are accurate while maintaining prediction-less guarantees in the
worst case. The idea is that good predictions can help circumvent worst-case
behavior. Classic optimization problems that are being reexamined under this
framework include caching [20], matching [11, 2, 9, 18], secretary [12],
knapsack [14] and facility location [1]. Problems in Nash social welfare [7],
mechanism design [33] and revenue management [6] are also actively being
studied in this context.

In online scheduling, problems that are being newly examined with learning
augmentation include problems for minimizing average flow time [22, 23, 4],
average completion time [25, 15], average weighted completion time [19], and
makespan [17, 5]. Many of these studies with min-sum objectives assume that
job processing requirements are not known to us in advance. In these settings,
it is natural to use predictions of individual job processing times [25, 15,
22, 23, 4]. More recent work examines the use of permutation predictions,
directly predicting algorithmic actions rather than input characteristics
[19]. Our work studies the min-sum weighted completion time objective using
predictions of an input characteristic that has not been considered in
previous work: job weights.

Job weights are used to capture urgencies or priorities in our problem
setting. Outside the realm of online scheduling with predictions, there is an
extensive body of work that investigates the effect of priority classes. In
the context of prediction error, our work is closely related to the works of
Argon and Ziya [3] and McLay and Mayorga [21]. In a priority queue model,
Argon and Ziya [3] make priority assignments for arriving customers based on
imperfect indicators of priority types. The signal available to the decision
maker is the probability that a customer is high priority. McLay and Mayorga
[21] study the problem of dispatching ambulances when operators make
classification errors in assessing patient risk via a Markov Decision Process.
Our model is fundamentally different not just in framework, but more
importantly in that we respond dynamically to real-time information gained
while processing each job. Despite these major modeling differences, there are
striking similarities in some of the insights and conclusions we draw. With
Argon and Ziya [3], we share the same optimal policy structure given two
priority classes with linear waiting costs. Both works have a signal (or, in
our case, prediction)-based thresholding policy with strong ties to the
generalized $c\mu$ rule. Our threshold policy also reveals how prediction
quality impacts decision making. Similar insights are given by McLay and
Mayorga [21] on when to over- or under-respond to perceived patient risk based
on rates of classification error. It is clear that there are connections in
our approaches despite their differences. In future work, it would be
interesting to see when and how these frameworks converge.

In other related work, van der Zee and Theil [31] directly model
misclassification rates in a single-server queue where priority assignments
are made based on a probabilistic classifier. Steady-state results are derived
when classification errors are known and very small. Singh et al. [28]
eliminates the use of priority types as a middle-man altogether and directly
prescribes placement into the priority queue. Finally, very recent work by
Thompson et al. [30] explores the impact of prediction-driven prioritization
schemes using a preemptive priority queue. Their simulated clinical impact
assumes a fixed prediction error based on the expected diagnostic performance
of machine-learned algorithms.

The remainder of this paper is organized as follows. In Section 2, we
introduce our model as well as a scheduling formulation of the problem. We
present our main results in Section 3, where we show that a simple threshold-
based policy is in fact the best possible in certain stylized settings.
Section 5 extends this idea to a number of settings that more accurately
reflect realistic scenarios. Finally, we conclude and lay out some additional
thoughts for future research in Section 6.

##  2 Problem Formulation

We have a set of patient cases that must be processed by a radiologist. At
time of arrival, each patient case is labeled with its predicted urgency
level. These labels are observable. At every decision point, the radiologist
decides which patient case to process. After processing a pre-specified
fraction of a patient case, the radiologist learns the true priority of the
case on hand and has the option to preempt that case in favor of another
patient case. We capture this decision making process with a preemptive
scheduling model. Our goal is to find a policy for minimizing the expected
urgency-weighted sum of completion times across all patients. We describe the
problem data and model, followed by a scheduling formulation of the problem.

#### Problem Data

We have one radiologist (a single machine) processing patient cases (jobs)
indexed by $[n]=\\{1,\dots,n\\}$. A machine can only process one job at a
time, and each job requires 1 unit in processing time. All jobs are assumed
available at time 0 in advance of any decision making, i.e., release dates
$r_{j}=0$ for each job $j\in[n]$.

There are two priority classes, type 0 (urgent) and type 1 (non-urgent), each
with its associated cost per unit delay (weights) $\omega_{0}$ and
$\omega_{1}$, respectively, where $\omega_{0}>\omega_{1}>0$. Each job is
independently an urgent job with probability $\rho\in(0,1)$, which we assume
is known based on historical data. Job $j$’s true urgency
$true(j)\in\\{0,1\\}$ is unknown a priori, and is revealed only after
partially completing some fixed $\alpha\in(0,1)$ fraction of the job. On the
other hand, its predicted priority $pred(j)\in\\{0,1\\}$ is immediately
observable at its release date $r_{j}$. A binary classification system
predicts the urgency level of each job independently according to the
following probability matrix.

| predicted 0 | predicted 1
---|---|---
true 0 | $1-\varepsilon_{0}$ | $\varepsilon_{0}$
true 1 | $\varepsilon_{1}$ | $1-\varepsilon_{1}$
Table 1: Prediction probability matrix

The probability of misclassifying a true type 0 job is the false negative rate
$\varepsilon_{0}$, and the probability of misclassifying a true type 1 job is
the false positive rate $\varepsilon_{1}$. We assume that $\varepsilon_{0}\leq
1/2$ and $\varepsilon_{1}\leq 1/2$, and that these prediction errors are
known. We expect that they could be inferred from historical data or from
expected generalization error rates associated with the machine learning
algorithm that we use.

By Bayes’ rule, job $j$ is a type 0 job with probability $p_{j}$, where

$p_{j}=\mathbb{P}(true(j)=0|pred(j)=0)=\frac{(1-\varepsilon_{0})\rho}{(1-\varepsilon_{0})\rho+\varepsilon_{1}(1-\rho)}$
(1)

if job $j$ is predicted to be of high priority, and

$p_{j}=\mathbb{P}(true(j)=0|pred(j)=1)=\frac{\varepsilon_{0}\rho}{\varepsilon_{0}\rho+(1-\varepsilon_{1})(1-\rho)}$
(2)

otherwise. It is easy to verify that
$\mathbb{P}(true(j)=0|pred(j)=0)\geq\mathbb{P}(true(j)=0|pred(j)=1)$ given our
assumptions that $\varepsilon_{0}$ and $\varepsilon_{1}$ are both at most one
half. Finally, the weight of job $j$ is

$\displaystyle w_{j}$
$\displaystyle=\omega_{0}\cdot\mathbf{1}\left\\{true(j)=0\right\\}+\omega_{1}\cdot\mathbf{1}\left\\{true(j)=1\right\\}$
$\displaystyle=\omega_{1}+(\omega_{0}-\omega_{1})\cdot\mathbf{1}\left\\{true(j)=0\right\\}.$
(3)

######  Assumption 1.

$\omega_{1}<\omega_{0}(1-\alpha)$ holds.

Intuitively, Assumption 1 ensures that there is a large enough weight
differential between urgent and non-urgent jobs to make preemption meaningful.
The technical reasons for making this assumption will be discussed in the next
section when it becomes relevant.

#### Model

A decision point occurs whenever a job completes or a job’s true priority is
revealed. We call the latter decision point an $\alpha$-point. Our model
allows preemptions; at each $\alpha$-point, we can either complete the job
immediately, or preempt then process the remaining $1-\alpha$ units of work at
a later point in time.

At each decision point $t$, we observe the state, which consists of the set of
unopened jobs sorted in some order, and the set of partially processed jobs of
which true types are already known. Of unopened jobs, only predicted
priorities are known. Based on the state, we decide whether to open a new job
of as-yet-unknown urgency or complete a job of known priority that only has
$1-\alpha$ units of work remaining. Our decisions at each decision point are
therefore made based on the predicted priorities of unopened jobs and the true
priorities of partially processed jobs. If we decide to open a new job, we
process a job chosen according to some predetermined order and meet our next
decision point at the next $\alpha$-point $t+\alpha$, at which time we observe
the job’s true type. We then update the state by moving this job from the set
of unopened to the set of partially processed jobs. Otherwise, we complete a
job at $t+(1-\alpha)$, incur a weighted cost to the objective based on the
true urgency of the job just completed, and remove that job from the system
entirely.

#### Objective

Each of the $n$ arriving jobs is independently a high priority job with
probability $\rho$, and is assigned a predictive label according to the
probability matrix given in Table 1. Letting $C_{j}$ denote the completion
time of job $j$, our goal is to minimize
$\mathbb{E}\left(\sum_{j=1}^{n}w_{j}C_{j}\right)$ where $w_{j}$ is the true
weight of job $j$ as defined in Equation (3).

#### Scheduling Formulation

We first consider the offline version of this problem in which jobs’ true
types are known a priori. This is a single-machine problem of minimizing the
weighted sum of completion times, written $1||\sum w_{j}C_{j}$ in the
scheduling notation of Graham et al. [13], and can be solved using the
following result given by Smith [29].

######  Theorem 1 (Smith’s WSPT Rule).

For the single-machine problem of minimizing the weighted sum of completion
times, the Weighted Shortest Processing Time (WSPT) rule is optimal.

The WSPT rule sorts jobs in nonincreasing order of weight-to-processing-time
ratios. Given our unit processing time assumption, sorting jobs in WSPT order
is equivalent to sorting jobs in nonincreasing order of true priorities. Then,
processing job $j$ for completion at time $j$ yields an optimal schedule, so
$\mathbb{E}(\mathsf{OPT})=\mathbb{E}\left(\sum_{j=1}^{n}jw_{j}\right).$

Our problem, however, is a non-clairvoyant online decision making problem in
which jobs’ true priorities are not known until jobs are at least partially
processed. We follow the WSPT rule and sort jobs in nonincreasing order of
predicted weights, breaking ties arbitrarily. We then proceed by opening jobs
in this sorted order. The rest of this paper is focused on showing that the
performance gap between the online and offline versions of this problem can be
reduced with the use of predictions, especially when the predictor has low
error.

#### Example

Consider the following deterministic 9-job example where each column
represents a single job.

true types (unknown) | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1
---|---|---|---|---|---|---|---|---|---
predicted types (observed) | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0

At each job’s release date, we observe its predicted type. True types are not
known at this time. We proceed by sorting jobs in WSPT order of predicted
priorities.

predicted types (sorted) | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1
---|---|---|---|---|---|---|---|---|---
true types (permutation $\pi$) | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1
Table 2: An example of a possible job ordering

Among the five jobs predicted to be of high priority, there are two jobs that
are actually of type 1. Similarly, there is one true type 0 job among the four
jobs that are predicted to be of low priority. Therefore, in this example,
there are ${5\choose 2}{4\choose 1}$ possible misprediction-driven ways of
sequencing jobs by true priority. One such permutation $\pi$ is given as an
example above.

Once a job is opened, we learn its true type after processing $\alpha$ units
of the job. At this $\alpha$-point, we have the option of either completing
the remaining $1-\alpha$ units of work, or opening the next job in $\pi$.
Decisions are made over time with the goal of minimizing
$\mathbb{E}\left(\sum_{j=1}^{n}w_{j}C_{j}\right)$ across all possible
permutations of job orderings.

##  3 The $\beta$-Threshold Rule: An Optimal Policy

We provide an optimal policy for our problem in this section. Before we do so,
we first discuss an old scheduling result by Schrage [26].

######  Theorem 2 (Schrage’s SRPT Rule).

In the preemptive single-machine problem of minimizing the sum of completion
times, where jobs are arriving over time, the Shortest Remaining Processing
Time (SRPT) rule is optimal.

By the SRPT rule, given any two jobs of the same weight, we should process the
job with the shorter amount of remaining work first. SRPT applied to our
problem confirms a general intuition that it is never optimal to preempt a job
that is revealed to be of high priority; type 0 jobs will always be processed
nonpreemptively. This does not change our model, but it does help simplify
some aspects of it. Since preemption only occurs on type 1 jobs, we are able
to eliminate $\alpha$-points with respect to type 0 jobs. It also suffices to
track the number of partially processed jobs as these jobs are all of type 1.

We now present a thresholding policy that minimizes our objective across all
non-anticipating policies. Without loss of generality, we sort jobs according
to their predicted priorities, breaking ties arbitrarily. This is equivalent
to sorting jobs in nonincreasing order of their type 0 probabilities $p_{j}$
as defined in equations (1)-(2). As we proceed with our policy, we open jobs
in this order. Define a constant

$\beta=\frac{\alpha}{1-\alpha}\cdot\frac{\omega_{1}}{\omega_{0}-\omega_{1}}.$

At each decision point, we observe the state $(\mathcal{S},\ell)$, where
$\mathcal{S}$ is the set of unopened jobs and $\ell$ is the number of
partially processed type 1 jobs. If either $\mathcal{S}=\emptyset$ or
$\ell=0$, we do not have a decision to make; if the former, we complete a
partially processed type 1 job, and if the latter, we open a new job. If
$\mathcal{S}=\emptyset$ and $\ell=0$, we are done. Thus, we assume that
$\ell>0$ and $\mathcal{S}\neq\emptyset$ with $k=\min(\mathcal{S})$, which
means that job $k$ is the next job in line. We make our decisions by comparing
$p_{k}$ against $\beta$: if $p_{k}\leq\beta$, we process the remaining
$1-\alpha$ units of a partially completed low priority job and reach our next
decision point at completion. If $p_{k}>\beta$, we open job $k$ and process
$\alpha$ units of the job, at which time we learn of job $k$’s true type. If
job $k$ is a type 1 job, we are at our new decision point. Otherwise, we
process job $k$ to completion for another $1-\alpha$ units and make our next
decision when job $k$’s processing is complete.

Algorithm 1 The $\beta$-Threshold Rule

1:jobs sorted in nonincreasing order of $p_{j}$

2:Initialize:

3: $t\leftarrow 0$ $\triangleright$ time
$\mathcal{S}\leftarrow[n]$ $\triangleright$ set of unopened jobs
$\ell\leftarrow 0$ $\triangleright$ number of partially completed type 1 jobs

4:procedure CompleteLow($t,\mathcal{S},\ell$) $\triangleright$ complete a
known low priority job

5: $\ell\leftarrow\ell-1$

6: $t\leftarrow t+(1-\alpha)$

7:end procedure

8:procedure OpenNext($t,\mathcal{S},\ell$) $\triangleright$ open a new job,
then stop at the $\alpha$-point

9: $k\leftarrow\min(\mathcal{S})$

10: $\mathcal{S}\leftarrow\mathcal{S}\setminus\\{k\\}$

11: $t\leftarrow t+\alpha$

12: if $true(k)=0$ then$\triangleright$ nonpreemptively complete a type 0 job

13: $t\leftarrow t+(1-\alpha)$

14: else

15: $\ell\leftarrow\ell+1$

16: end if

17:end procedure

18:while $(\mathcal{S},\ell)$ is not $(\emptyset,0)$ do

19: if $\mathcal{S}=\emptyset$ then

20: CompleteLow$(t,\mathcal{S},\ell)$

21: else if $\ell=0$ then

22: OpenNext$(t,\mathcal{S},\ell)$

23: else

24: $k\leftarrow\min(\mathcal{S})$

25: if $p_{k}>\beta$ then

26: OpenNext$(t,\mathcal{S},\ell)$

27: else

28: CompleteLow$(t,\mathcal{S},\ell)$

29: end if

30: end if

31:end while

######  Theorem 3.

The $\beta$-threshold rule is optimal.

###### Proof.

Suppose on the contrary that there exists an optimal policy that does not
follow the $\beta$-threshold rule. By assumption, if we run this policy on any
instance of our problem input, there exists at least one decision point where
the optimal policy observes the given state and makes a decision that deviates
from ours. We consider the last such decision point and call it time $t$, and
further assume that the observed state at that time is $(\mathcal{S},\ell)$,
where $\mathcal{S}$ is the set of unopened jobs such that
$k=\min(\mathcal{S})$ and $\ell>0$ is the number of partially processed type 1
jobs.

Two things may have occurred at time $t$: $p_{k}>\beta$ and the optimal policy
processes a low priority job for completion at time $t+(1-\alpha)$, or
$p_{k}\leq\beta$ and the optimal policy proceeds by opening job $k$. In both
cases, we show that choosing the alternative improves the objective value and
ensures that the resulting schedule is consistent with the $\beta$-threshold
rule.

  1. i

$p_{k}>\beta$: according to the $\beta$-threshold rule, we should have opened
job $k$ at time $t$; the optimal policy decided otherwise and completed a type
1 job (let us call this job $i$) at time $t+(1-\alpha)$. We proceed by
identifying another point in time in the schedule generated by the optimal
policy to process job $i$, which would allow job $k$ to be processed at time
$t$ instead. We then show by an interchange argument that doing so improves
the objective value.

Starting from time $t$, trace time forward in the schedule generated by the
optimal policy. Since $t$ is the last decision point that deviates from the
$\beta$-threshold rule by assumption and the set of unopened jobs at the next
decision point $t+(1-\alpha)$ remains unchanged so that $k=\min(\mathcal{S})$,
the optimal policy opens job $k$ at time $t+(1-\alpha)$. We continue to trace
time forward until some time $u$, when the optimal policy begins processing
the remaining $1-\alpha$ units of a previously preempted, true low priority
job for the first time since completing job $i$ at time $t+(1-\alpha)$. We
show that within the interval $[t,u)$, we can improve the objective by
delaying the completion of job $i$ to $C_{i}=u$ and moving up the schedule in
$[t+1-\alpha,u)$ by $1-\alpha$ units to $[t,u-1+\alpha)$.

By our assumptions, $u$ is the time at which either $\mathcal{S}=\emptyset$
(every job has been opened), or the next job’s type 0 probability falls below
$\beta$, whichever happens first. Therefore, all jobs opened in
$[t+1-\alpha,u)$ are above the probability threshold $\beta$. Let $z\geq 1$
denote the number of jobs opened in $[t+1-\alpha,u)$ including job $k$. Among
these $z$ jobs, suppose there are $z_{0}$ jobs of true type 0 that are
completed immediately where
$z_{0}=\sum_{j=k}^{k+z-1}\mathbf{1}\left\\{true(j)=0\right\\}$. The remaining
$z-z_{0}$ jobs are revealed to be of true type 1 after $\alpha$ units of
processing, then are preempted. These preempted jobs are not processed until
at least time $u$.

By interchange, each of the $z_{0}$ type 0 jobs complete $1-\alpha$ units
earlier. On the other hand, completion of job $i$, a type 1 job, is delayed by
$u-(t+1-\alpha)=z_{0}+(z-z_{0})\alpha$, which sums one unit of delay for every
completed type 0 job and an $\alpha$ unit of delay for every preempted type 1
job. None of the other jobs are affected by this interchange. Thus, the
overall change to the objective is

$\displaystyle-
z_{0}\omega_{0}(1-\alpha)+\omega_{1}\left(z\alpha+z_{0}(1-\alpha)\right)$
$\displaystyle=$ $\displaystyle-
z_{0}(\omega_{0}-\omega_{1})(1-\alpha)+\alpha\omega_{1}z$ $\displaystyle=$
$\displaystyle-(\omega_{0}-\omega_{1})(1-\alpha)\left(z_{0}-\frac{\alpha}{1-\alpha}\cdot\frac{\omega_{1}}{\omega_{0}-\omega_{1}}z\right)$
$\displaystyle=$
$\displaystyle-(\omega_{0}-\omega_{1})(1-\alpha)\left(z_{0}-\beta z\right)$
$\displaystyle=$
$\displaystyle-(\omega_{0}-\omega_{1})(1-\alpha)\sum_{j=k}^{k+z-1}\left(\mathbf{1}\left\\{true(j)=0\right\\}-\beta\right).$

In expectation,

$-(\omega_{0}-\omega_{1})(1-\alpha)\sum_{j=k}^{k+z-1}\left(p_{j}-\beta\right)<0$

since $p_{j}>\beta$ for each $j=k,\dots,k+z-1$, which establishes a
contradiction. We have also shown how to choose the interval $[t,u)$ for
interchange to ensure that the schedule is consistent with the
$\beta$-threshold rule from time $t$ onward.

  2. ii

$p_{k}\leq\beta$: according to the $\beta$-threshold rule, we should have
completed a type 1 job for completion at time $t+1-\alpha$. Instead, the
optimal policy opened job $k$. The proof proceeds similarly to the above in
that we first identify an appropriate point in time in the schedule generated
by the optimal policy to open job $k$, then use interchange. The main
difference lies in that the amount of delay from opening job $k$ is not
immediately clear, since that depends on job $k$’s true type.

We first argue that in fact, regardless of type, job $k$ completes at $t+1$ in
the schedule generated by the optimal policy. This is trivially true if job
$k$ is a type 0 job. Otherwise, the optimal policy meets its next decision
point at $t+\alpha$, where the set of unopened jobs is
$\mathcal{S}=[n]\setminus[k]$ and there are now $\ell+1$ true type 1 jobs that
are not yet fully processed including job $k$. By our assumption that time $t$
is the last decision point at which the optimal policy deviates from the
$\beta$-threshold rule, the optimal policy completes a type 1 job at
$(t+\alpha)+(1-\alpha)=t+1$ since $\beta\geq p_{k}\geq p_{k+1}$ at time
$t+\alpha$. We are free to label this job as job $k$. Then, starting from
$t+1$, the optimal policy will complete the remaining $\ell$ type 1 jobs in
succession, completing the last type 1 job at time $t+\ell(1-\alpha)+1$.

We show that within the interval $[t,t+\ell(1-\alpha)+1)$, we can improve the
objective by delaying the opening of job $k$ to time $t+\ell(1-\alpha)$, when
$\ell$ type 1 jobs have each completed the remaining $1-\alpha$ units of work.
Even with this interchange, since $\beta\geq p_{k+1}$, job $k$ will be
processed nonpreemptively regardless of type so that
$C_{k}=t+\ell(1-\alpha)+1$. None of the other jobs are affected. The overall
change to the objective is

$\displaystyle-\ell\omega_{1}+w_{k}\ell(1-\alpha)$ $\displaystyle=$
$\displaystyle-\ell\omega_{1}+\left(\omega_{1}+(\omega_{0}-\omega_{1})\cdot\mathbf{1}\left\\{true(k)=0\right\\}\right)\ell(1-\alpha)\qquad\qquad\qquad\
\text{by \eqref{eq:job-weight}}$ $\displaystyle=$
$\displaystyle-\ell\omega_{1}+\omega_{1}\ell(1-\alpha)+(\omega_{0}-\omega_{1})\mathbf{1}\left\\{true(k)=0\right\\}\ell(1-\alpha)$
$\displaystyle=$
$\displaystyle-\ell\alpha\omega_{1}+(\omega_{0}-\omega_{1})\mathbf{1}\left\\{true(k)=0\right\\}\ell(1-\alpha)$
$\displaystyle=$
$\displaystyle-\ell(\omega_{0}-\omega_{1})(1-\alpha)\left(\frac{\alpha}{1-\alpha}\cdot\frac{\omega_{1}}{\omega_{0}-\omega_{1}}-\mathbf{1}\left\\{true(k)=0\right\\}\right)$
$\displaystyle=$
$\displaystyle-\ell(\omega_{0}-\omega_{1})(1-\alpha)\left(\beta-\mathbf{1}\left\\{true(k)=0\right\\}\right).$

In expectation,

$-\ell(\omega_{0}-\omega_{1})(1-\alpha)\left(\beta-p_{k}\right)\leq 0$

since $p_{k}\leq\beta$ by assumption. The resulting schedule is consistent
with the $\beta$-threshold rule from time $t$ onward. This establishes the
desired contradiction and concludes the proof.∎

Given our results in Theorem 3, we now provide a technical reason behind
Assumption 1 which requires $\omega_{1}<\omega_{0}(1-\alpha)$. Suppose on the
contrary that $\omega_{1}\geq\omega_{0}(1-\alpha)$. Rearranging inequalities,
this also implies that $\alpha\geq 1-\omega_{1}/\omega_{0}$. Then,

$\beta=\frac{\alpha}{1-\alpha}\cdot\frac{\omega_{1}}{\omega_{0}-\omega_{1}}\geq\frac{\alpha\omega_{0}}{\omega_{0}-\omega_{1}}=\frac{\alpha}{1-\omega_{1}/\omega_{0}}\geq
1$

and so by the $\beta$-threshold rule we would complete every job
nonpreemptively. Because this is not a particularly interesting case, we focus
our efforts where preemption offers room for improvement. All the same, we
provide a performance upper bound for this case in Corollary 5.

The $\beta$-threshold rule may seem arbitrary at first, but there is an
intuitive explanation for it that reveals a strong connection with the
celebrated $c\mu$ rule. Recall that for any job $j$,
$\mathbb{E}(w_{j})=\omega_{1}+(\omega_{0}-\omega_{1})p_{j}$ by Equation (3).

######  Proposition 1.

$\frac{\mathbb{E}(w_{j})}{1}>\frac{\omega_{1}}{1-\alpha}\iff p_{j}>\beta.$

###### Proof.

Expanding the left hand side of the inequality,

$\displaystyle(1-\alpha)\left(\omega_{1}+(\omega_{0}-\omega_{1})p_{j}\right)>\omega_{1}$
$\displaystyle\iff(1-\alpha)(\omega_{0}-\omega_{1})p_{j}>\alpha\omega_{1}$
$\displaystyle\iff
p_{j}>\frac{\alpha}{1-\alpha}\cdot\frac{\omega_{1}}{\omega_{0}-\omega_{1}}$
$\displaystyle\iff p_{j}>\beta,$

which is equivalent to the conditions given in the $\beta$-threshold rule.
Inequality in the other direction holds analogously. ∎

At every decision point, applying the $\beta$-threshold rule is equivalent to
comparing the $c\mu$ of an unopened job $j$ against the $c\mu$ of a known low
priority job with $1-\alpha$ units of residual work, and choosing the job with
the higher $c\mu$ value.

Depending on our chosen parameter values, the $\beta$-threshold rule may give
rise to three modes of decision making: a nonpreemptive policy, a preemptive
policy, and a hybrid policy that switches from a preemptive policy to a
nonpreemptive policy sometime in between.

Let us first assume that jobs are sorted in WSPT order of predicted
priorities. A nonpreemptive policy completes every job in sorted order without
preemption. A schedule generated by a nonpreemptive policy is a nonpreemptive
schedule. A policy is preemptive if, opening jobs in sorted order, every type
1 job is preempted at its $\alpha$-point. These low priority jobs will only be
revisited once all $n$ jobs have been opened and every high priority job has
completed its processing. The resulting schedule is a preemptive schedule.
Preemptive and nonpreemptive schedules are two non-adaptive special cases of a
schedule generated by the $\beta$-threshold rule.

The hybrid policy, on the other hand, is an adaptive policy that switches
between the preemptive and nonpreemptive regimes based on the predictive label
of the job being processed. More specifically, a preemptive strategy is used
on jobs that are expected to be type 0, while a nonpreemptive strategy is used
on the remaining jobs that are predicted to be non-urgent. Given our initial
sort, we make this switch exactly once.

In what follows, we specify the conditions that give rise to each of our
policies.

######  Corollary 1.

A nonpreemptive policy is optimal if

$\min\left(\rho(1-\beta),\beta(1-\rho)\right)\leq\rho(1-\beta)\varepsilon_{0}+\beta(1-\rho)\varepsilon_{1}\text{
and }\rho\leq\beta.$

###### Proof.

The statement follows directly from Theorem 3. We employ a nonpreemptive
policy if $\beta\geq\mathbb{P}(true(\cdot)=0|pred(\cdot)=0)$ where the
probability is as defined in (1)-(2). Rearranging the inequality, we obtain
the result. ∎

######  Corollary 2.

A preemptive policy is optimal if

$\min\left(\rho(1-\beta),\beta(1-\rho)\right)\leq\rho(1-\beta)\varepsilon_{0}+\beta(1-\rho)\varepsilon_{1}\text{
and }\rho>\beta.$

######  Corollary 3.

A hybrid policy is optimal if

$\rho(1-\beta)\varepsilon_{0}+\beta(1-\rho)\varepsilon_{1}<\min\left(\rho(1-\beta),\beta(1-\rho)\right).$

The $\beta$-threshold rule admits a hybrid policy if

$\mathbb{P}(true(\cdot)=0|pred(\cdot)=1)\leq\beta<\mathbb{P}(true(\cdot)=0|pred(\cdot)=0).$
(6)

It follows naturally from Bayes’ rule that the gap between the two conditional
probabilities in (6) is large when prediction error is low. When that is the
case, $\beta$ is much more likely to fall in between these two probabilities
for our chosen parameter values, resulting in an adaptive hybrid policy. On
the other hand, when we have a predictor with high prediction error, this
conditional probability gap is likely to be smaller, in which case a non-
adaptive policy would be best.

##  4 Analysis of the $\beta$-Threshold Rule

###  4.1 Performance Analysis

We now quantify the performance of our policies as a function of prediction
error. More specifically, we fix the number of urgent jobs among our $n$
available jobs, then obtain exact expressions for expected performance
conditional on this quantity, which we denote $n_{0}$. Performance is measured
against the offline optimum $\mathsf{OPT}$ given $n_{0}$. This focus on
conditional expectation allows us to remove one layer of randomness from our
problem and isolate the effects of misprediction. The expressions we derive in
this section will also be useful for competitive analysis in our next section.
Extending our results to obtain expressions for unconditional expectations of
performance can be easily done by using the first and second moments of
$n_{0}$.

######  Proposition 2.

Let $C_{j}^{\phi}$ and $C_{j}^{\alpha}$ each denote job $j$’s completion time
in nonpreemptive and preemptive schedules, respectively. Given $n_{0}$,

$\displaystyle\mathsf{OPT}$
$\displaystyle=(\omega_{0}-\omega_{1})\frac{n_{0}(n_{0}+1)}{2}+\omega_{1}\frac{n(n+1)}{2}$
(7)
$\displaystyle\mathbb{E}\left(\sum_{j=1}^{n}w_{j}C_{j}^{\phi}\middle|n_{0}\right)$
$\displaystyle=\mathsf{OPT}+(\omega_{0}-\omega_{1})\mathbb{E}(X|n_{0})$ (8)
$\displaystyle\mathbb{E}\left(\sum_{j=1}^{n}w_{j}C_{j}^{\alpha}\middle|n_{0}\right)$
$\displaystyle=\mathsf{OPT}+\alpha\omega_{0}\mathbb{E}(X|n_{0})+\alpha\omega_{1}\mathbb{E}(Y|n_{0})$
(9)

where, letting $n_{1}=n-n_{0}$,

$\displaystyle\mathbb{E}(X|n_{0})=\frac{(\varepsilon_{0}+\varepsilon_{1})n_{0}n_{1}}{2},\
\mathbb{E}(Y|n_{0})=\frac{n_{1}(n_{1}-1)}{2}.$ (10)

###### Proof.

The offline optimum is easy to compute by WSPT:

$\displaystyle\mathsf{OPT}=\sum_{j=1}^{n}jw_{j}$
$\displaystyle=\sum_{j=1}^{n_{0}}\omega_{0}j+\sum_{j=n_{0}+1}^{n}\omega_{1}j$
$\displaystyle=(\omega_{0}-\omega_{1})\frac{n_{0}(n_{0}+1)}{2}+\omega_{1}\frac{n(n+1)}{2}.$

For (8) and (9), recall that sorting jobs in WSPT order of predicted
priorities results in a number of possible permutations of true priorities. We
evaluate the objective for some fixed permutation $\pi$ of true types, then
take the expectation across all possible permutations.

In a nonpreemptive schedule, each pair of jobs whose true types are out of
order, i.e., a pair of (true 1, true 0), adds $\omega_{0}-\omega_{1}$ to the
objective relative to the offline optimum. Letting $X$ denote the number of
such inversions in $\pi$,
$\sum_{j=1}^{n}w_{j}C_{j}^{\phi}=\mathsf{OPT}+(\omega_{0}-\omega_{1})X$.

In a preemptive schedule, the cost of one inversion is $\alpha\omega_{0}$,
since a type 1 job preempts after processing $\alpha$ units and allows a type
0 job to be processed and completed before resuming its $1-\alpha$ units of
residual work. This schedule also incurs a cost of $\alpha\omega_{1}$ for
every pair of (true 1, true 1) jobs, because the policy requires that we open
and preempt both jobs before we begin processing any remaining work for
completion. Thus, letting $Y$ denote the number of (true 1, true 1) pairs in
$\pi$,
$\sum_{j=1}^{n}w_{j}C_{j}^{\alpha}=\mathsf{OPT}+\alpha\omega_{0}X+\alpha\omega_{1}Y$.

We conclude the proof by computing $\mathbb{E}(X|n_{0})$.

$\displaystyle X$
$\displaystyle=\sum_{j=1}^{n}\sum_{k>j}\mathbbm{1}\left\\{\pi(j)=1\right\\}\mathbbm{1}\left\\{\pi(k)=0\right\\}$
$\displaystyle=\sum_{j=1}^{n}\sum_{k>j}\mathbbm{1}\left\\{\pi(j)=1,pred(j)=0\right\\}\mathbbm{1}\left\\{\pi(k)=0,pred(k)=0\right\\}$
$\displaystyle\qquad+\sum_{j=1}^{n}\sum_{k>j}\mathbbm{1}\left\\{\pi(j)=1,pred(j)=0\right\\}\mathbbm{1}\left\\{\pi(k)=0,pred(k)=1\right\\}$
$\displaystyle\qquad+\sum_{j=1}^{n}\sum_{k>j}\cancel{\mathbbm{1}\left\\{\pi(j)=1,pred(j)=1\right\\}\mathbbm{1}\left\\{\pi(k)=0,pred(k)=0\right\\}}$
$\displaystyle\qquad+\sum_{j=1}^{n}\sum_{k>j}\mathbbm{1}\left\\{\pi(j)=1,pred(j)=1\right\\}\mathbbm{1}\left\\{\pi(k)=0,pred(k)=1\right\\}$

where the third term cancels because of our initial sort in WSPT order of
predicted priorities. Accounting for the order of jobs, we can replace
$\pi(\cdot)$ with $true(\cdot)$:

$\displaystyle X$
$\displaystyle=\frac{1}{2}\left(\sum_{j=1}^{n}\mathbbm{1}\left\\{true(j)=1,pred(j)=0\right\\}\right)\left(\sum_{k=1}^{n}\mathbbm{1}\left\\{true(k)=0,pred(k)=0\right\\}\right)$
$\displaystyle\qquad+\left(\sum_{j=1}^{n}\mathbbm{1}\left\\{true(j)=1,pred(j)=0\right\\}\right)\left(\sum_{k=1}^{n}\mathbbm{1}\left\\{true(k)=0,pred(k)=1\right\\}\right)$
$\displaystyle\qquad+\frac{1}{2}\left(\sum_{j=1}^{n}\mathbbm{1}\left\\{true(j)=1,pred(j)=1\right\\}\right)\left(\sum_{k=1}^{n}\mathbbm{1}\left\\{true(k)=0,pred(k)=1\right\\}\right).$

Order in the second term is, again, automatically satisfied by how we sort the
jobs. Taking the conditional expectation given $n_{0}$ and letting
$n_{1}=n-n_{0}$, we obtain

$\displaystyle\mathbb{E}(X|n_{0})$
$\displaystyle=\frac{\varepsilon_{1}(1-\varepsilon_{0})n_{0}n_{1}}{2}+\varepsilon_{0}\varepsilon_{1}n_{0}n_{1}+\frac{\varepsilon_{0}(1-\varepsilon_{1})n_{0}n_{1}}{2}$
(11) $\displaystyle=\frac{(\varepsilon_{0}+\varepsilon_{1})n_{0}n_{1}}{2}.$

Finally, $\mathbb{E}(Y|n_{0})={n_{1}\choose 2}=n_{1}(n_{1}-1)/2$. ∎

Given the proposition above, we can combine (8)-(9) to give expressions for
the performance of the $\beta$-threshold rule. In essence, the
$\beta$-threshold rule dictates when to move from a preemptive regime to a
nonpreemptive regime. Based on our previous analyses, this cutoff occurs once
we complete the last job that is predicted to be of high priority.

######  Proposition 3.

Let $C_{j}^{\beta}$ denote job $j$’s completion time in a schedule generated
by the $\beta$-threshold rule. This schedule is nonpreemptive with performance
given in (8) if $\beta\geq\max_{j}p_{j}$, and preemptive with performance
given in (9) if $\beta<\min_{j}p_{j}$. Otherwise, relative to $\mathsf{OPT}$
as defined in (7), the conditional expectation given $n_{0}$ is

$\displaystyle\mathbb{E}\left(\sum_{j=1}^{n}w_{j}C_{j}^{\beta}\middle|n_{0}\right)=\mathsf{OPT}+\mathbb{E}\left(\underbrace{\alpha\omega_{0}X_{0}+\alpha\omega_{1}Y_{0}}_{\text{preemptive}}+\underbrace{(\omega_{0}-\omega_{1})(X-X_{0})}_{\text{nonpreemptive}}\middle|n_{0}\right)$
(12)

where, letting $n_{1}=n-n_{0}$,

$\displaystyle\mathbb{E}(X_{0}|n_{0})=\frac{\varepsilon_{1}(1-\varepsilon_{0})n_{0}n_{1}}{2},\
\mathbb{E}(Y_{0}|n_{0})=\frac{\varepsilon_{1}^{2}\left(n_{1}^{2}-n_{1}\right)}{2}$

and $\mathbb{E}(X|n_{0})$ is as defined in (10).

###### Proof.

$X_{0}$ and $Y_{0}$ count the number of (true 1, true 0) and (true 1, true 1)
pairs, respectively, from the set of jobs that are predicted to be of type 0.
The expected value of $X_{0}$ given $n_{0}$ is given in the first term of (11)
in Proposition 2. The expected value of $Y_{0}$ given $n_{0}$ is the expected
value of ${\mathsf{Bin}(n_{1},\varepsilon_{1})\choose 2}$ where
$\mathsf{Bin}(n_{1},\varepsilon_{1})$ denotes a binomial random variable with
parameters $n_{1}$ and $\varepsilon_{1}$. The remainder of the proof is
identical to the one given in the proposition above. ∎

The expression in (12) makes it clear that the impacts of false positive and
false negative rates to performance may vary.

######  Corollary 4.

If the false positive rate $\varepsilon_{1}=0$, a hybrid policy gives a
nonpreemptive schedule.

Figure 1: Expected performance

Figure 1 plots the unconditional expected performance of each of our policies
as a function of prediction error, where performance is normalized by the
offline optimum. For illustrative purposes, we assume
$\varepsilon_{0}=\varepsilon_{1}$ and choose parameter values of $\alpha=0.4$,
$\rho=0.1$, and $\omega_{0}/\omega_{1}=20$. Since our problem is a
minimization problem, the lower the ratio of
$\mathbb{E}(\mathsf{ALG})/\mathsf{OPT}$, the better.

The nonpreemptive policy performs very well when prediction error is low, in
fact recovering the offline optimum when we are given perfect predictions.
This policy blindly trusts the predictor, however, resulting in poor
performance when prediction quality is low. On the other hand, the preemptive
policy opts not to trust the predictions and searches for high priority jobs
regardless of the advice it receives. It performs well when prediction quality
is low, but is overly aggressive against non-urgent jobs when predictions are
accurate, penalizing them unnecessarily. The $\beta$-threshold rule takes the
best of both worlds. When prediction error is low, our optimal policy
strategically shifts from a preemptive to a nonpreemptive policy,
outperforming each of the individual non-adaptive policies. Once prediction
error reaches a certain point and predictive labels lose meaning, the
$\beta$-threshold rule shifts to a preemptive policy.

Figure 2: Expected performance

Needless to say, performance depends heavily on our chosen parameter values.
Figure 2 gives two examples in which performance improvements from the
$\beta$-threshold rule are modest at best. The plot on the left panel
considers a case where relative priority values are set very high at
$\omega_{0}/\omega_{1}=100$. Analytically, our chosen parameter values push
down the $\beta$ value significantly so that it becomes unlikely that $\beta$
will fall between the two conditional probabilities given in (6) unless the
predictor is very accurate. Intuitively, the relative priority of urgent jobs
is so great that there is simply no room for prediction error. This explains
the low tolerance for error before our optimal policy switches from a hybrid
policy to a preemptive policy. The hybrid policy still outperforms both non-
adaptive policies when predictions are accurate.

The second plot in Figure 2 is a rare example in which a nonpreemptive policy
outperforms a preemptive policy throughout. Here, we consider a high value of
$\alpha$ where $\alpha=0.7$, which pushes up the $\beta$ value and the cost of
preemption at the same time. In this case, the high cost of preemption makes
it preferable to complete a low priority job than to open a new job that may
or may not be high priority. We again observe that the hybrid policy
outperforms both non-adaptive policies, but the improvements are small.

###  4.2 Competitive Analysis

We provide performance guarantees for our policies in this section.

######  Definition 1.

The _competitive ratio_ of an online algorithm $\mathsf{ALG}$ is $\mathsf{CR}$
if the inequality

$\mathbb{E}(\mathsf{ALG})\leq\mathsf{CR}\cdot\mathsf{OPT}$

holds for all possible inputs. Then, we can also say that $\mathsf{ALG}$ is
$\mathsf{CR}$-_competitive_.

In our competitive analysis, an adversary deliberately choosing a difficult
input has control over the mix of urgent and non-urgent jobs. Let $q$ denote
the fraction of urgent jobs among all available jobs. We shall aim to find the
worst case values of $q$. This analysis addresses a known weakness in our
model. Our model assumes that each arriving job is independently a high
priority job with probability $\rho\in(0,1)$, and our proposed
$\beta$-threshold rule is optimal with respect to this parameter. While $\rho$
could be inferred from historical data, it also tends to be highly volatile
and sensitive to environmental changes. Mass casualty events or insurance
policy changes are some examples that could drive the value of $\rho$ up or
down. With competitive analysis, we are able to guarantee performance for all
possible values of $\rho$. Furthermore, as a byproduct of our analyses, we can
observe which values of $\rho$ result in the worst case.

######  Lemma 1.

The performance of a nonpreemptive policy is bounded above by
$\mathsf{CR}^{\phi}\cdot\mathsf{OPT}$ where

$\mathsf{CR}^{\phi}=1+\varepsilon\left(\sqrt{\frac{\omega_{0}}{\omega_{1}}}-1\right)$

and $\varepsilon=(\varepsilon_{0}+\varepsilon_{1})/2$ is the average of the
false negative and false positive rates $\varepsilon_{0}$ and
$\varepsilon_{1}$.

###### Proof.

Let $C_{j}^{\phi}$ denote job $j$’s completion time in a nonpreemptive
schedule. Based on (8),

$\frac{\mathbb{E}\left(\sum_{j=1}^{n}w_{j}C_{j}^{\phi}\middle|n_{0}\right)}{\mathsf{OPT}}-1=\frac{(\omega_{0}-\omega_{1})\mathbb{E}(X|n_{0})}{\mathsf{OPT}}.$

Expanding the terms as given in Proposition 2 and letting $q=n_{0}/n$,

$\displaystyle\frac{(\omega_{0}-\omega_{1})\mathbb{E}(X|n_{0})}{\mathsf{OPT}}$
$\displaystyle=\frac{2\varepsilon(\omega_{0}-\omega_{1})n_{0}(n-n_{0})}{(\omega_{0}-\omega_{1})n_{0}(n_{0}+1)+\omega_{1}n(n+1)}$
$\displaystyle=\frac{2\varepsilon(\omega_{0}-\omega_{1})q(1-q)n^{2}}{(\omega_{0}-\omega_{1})(q^{2}n^{2}+qn)+\omega_{1}(n^{2}+n)}$

then, we approach the limit from below as $n\rightarrow\infty$ so the upper
bound is

$\displaystyle\frac{2\varepsilon(\omega_{0}-\omega_{1})q(1-q)}{(\omega_{0}-\omega_{1})q^{2}+\omega_{1}}.$

It is straightforward calculus to show that

$\max_{0\leq q\leq 1}\
\frac{2\varepsilon(\omega_{0}-\omega_{1})q(1-q)}{(\omega_{0}-\omega_{1})q^{2}+\omega_{1}}=\varepsilon\left(\sqrt{\frac{\omega_{0}}{\omega_{1}}}-1\right),$

which implies the result. The maximum is attained by choosing

$q=\sqrt{\frac{\omega_{1}}{\omega_{0}-\omega_{1}}+\left(\frac{\omega_{1}}{\omega_{0}-\omega_{1}}\right)^{2}}-\frac{\omega_{1}}{\omega_{0}-\omega_{1}}.$

∎

An immediate consequence of the above lemma is a performance bound for the
schedule when Assumption 1 does not hold. Recall that without Assumption 1, a
nonpreemptive schedule is an optimal schedule.

######  Corollary 5.

If $\omega_{1}\geq\omega_{0}(1-\alpha)$, the competitive ratio is
$1+\varepsilon\left(\sqrt{\frac{1}{1-\alpha}}-1\right)$.

######  Lemma 2.

The competitive ratio $\mathsf{CR}^{\alpha}$ of a preemptive policy is

$\mathsf{CR}^{\alpha}=\begin{dcases*}1+\alpha&if
$\varepsilon\leq\omega_{1}/\omega_{0}$, and\\\
1+\frac{\alpha}{2}\frac{\omega_{0}}{\omega_{0}-\omega_{1}}\left(1-2\varepsilon+\sqrt{1-4\varepsilon+4\varepsilon^{2}\left(\frac{\omega_{0}}{\omega_{1}}\right)}\right)&otherwise,\end{dcases*}$

where $\varepsilon=(\varepsilon_{0}+\varepsilon_{1})/2$ is the average of the
false negative and false positive rates $\varepsilon_{0}$ and
$\varepsilon_{1}$.

###### Proof.

The first part of the proof proceeds similarly. Let $C_{j}^{\alpha}$ denote
job $j$’s completion time in a preemptive schedule. Letting $n_{1}=n-n_{0}$
and $q=n_{0}/n$,

$\displaystyle\frac{\mathbb{E}\left(\sum_{j=1}^{n}w_{j}C_{j}^{\alpha}\middle|n_{0}\right)}{\mathsf{OPT}}-1$
$\displaystyle=\frac{\alpha\omega_{0}\mathbb{E}(X|n_{0})+\alpha\omega_{1}\mathbb{E}(Y|n_{0})}{\mathsf{OPT}}$
$\displaystyle=\alpha\cdot\frac{2\varepsilon\omega_{0}n_{0}n_{1}+\omega_{1}n_{1}(n_{1}-1)}{(\omega_{0}-\omega_{1})n_{0}(n_{0}+1)+\omega_{1}n(n+1)}$
$\displaystyle=\alpha\cdot\frac{2\varepsilon\omega_{0}q(1-q)n^{2}+\omega_{1}\left((1-q)^{2}n^{2}-(1-q)n\right)}{(\omega_{0}-\omega_{1})\left(q^{2}n^{2}+qn\right)+\omega_{1}(n^{2}+n)}$

then, we approach the limit from below as $n\rightarrow\infty$ so the upper
bound is

$\displaystyle\alpha\cdot\frac{2\varepsilon\omega_{0}q(1-q)+\omega_{1}(1-q)^{2}}{(\omega_{0}-\omega_{1})q^{2}+\omega_{1}}.$
(13)

We want to maximize (13) with respect to $q$ where $0\leq q\leq 1$. Taking the
derivative,

$\displaystyle\alpha\cdot\frac{\left(\begin{multlined}\left(2\varepsilon\omega_{0}(1-2q)-2\omega_{1}(1-q)\right)\left((\omega_{0}-\omega_{1})q^{2}+\omega_{1}\right)\\\
-2(\omega_{0}-\omega_{1})q\left(2\varepsilon\omega_{0}q(1-q)+\omega_{1}(1-q)^{2}\right)\end{multlined}\left(2\varepsilon\omega_{0}(1-2q)-2\omega_{1}(1-q)\right)\left((\omega_{0}-\omega_{1})q^{2}+\omega_{1}\right)\\\
-2(\omega_{0}-\omega_{1})q\left(2\varepsilon\omega_{0}q(1-q)+\omega_{1}(1-q)^{2}\right)\right)}{\left((\omega_{0}-\omega_{1})q^{2}+\omega_{1}\right)^{2}}$
$\displaystyle=$
$\displaystyle\alpha\cdot\frac{2(\omega_{0}-\omega_{1})(\omega_{1}-\varepsilon\omega_{0})q^{2}+2\omega_{1}(2(\omega_{1}-\varepsilon\omega_{0})-\omega_{0})q-2\omega_{1}(\omega_{1}-\varepsilon\omega_{0})}{\left((\omega_{0}-\omega_{1})q^{2}+\omega_{1}\right)^{2}}.$

We first evaluate this derivative at the boundaries. At $q=1$, the numerator
is always non-positive with $-2\varepsilon\omega_{0}^{2}\leq 0$. When $q=0$,
the numerator is $-2\omega_{1}(\omega_{1}-\varepsilon\omega_{0})$. If this
quantity is non-positive, i.e., $\varepsilon\leq\omega_{1}/\omega_{0}$, then
the coefficient for $q^{2}$ given by
$2(\omega_{0}-\omega_{1})(\omega_{1}-\varepsilon\omega_{0})$ is also non-
negative, which implies that (13) decreases in $q$ everywhere in the domain
$0\leq q\leq 1$. Thus, if $\varepsilon\leq\omega_{1}/\omega_{0}$, we obtain
the competitive ratio $1+\alpha$ by setting $q=0$ in (13).

If $\varepsilon>\omega_{1}/\omega_{0}$, the expression in (13) attains a
maximum in the interior of the domain. The rest of the proof is
straightforward calculus. We achieve the maximum given in the statement of the
lemma by setting

$q=\sqrt{\frac{\omega_{1}}{\omega_{0}-\omega_{1}}+\left(\frac{\omega_{1}}{\omega_{0}-\omega_{1}}\cdot\frac{2\varepsilon\omega_{0}-2\omega_{1}+\omega_{0}}{2\varepsilon\omega_{0}-2\omega_{1}}\right)^{2}}-\frac{\omega_{1}}{\omega_{0}-\omega_{1}}\cdot\frac{2\varepsilon\omega_{0}-2\omega_{1}+\omega_{0}}{2\varepsilon\omega_{0}-2\omega_{1}}.$

∎

A preemptive policy aggressively searches for high priority jobs by preempting
every type 1 job it encounters, completing any low priority residual work only
after all jobs are open and all type 0 jobs have completed their processing.
Lemma 2 confirms our intuition that this policy performs poorly when
prediction error is low. Consider for example an instance that consists
exclusively of type 1 jobs. Indiscriminate preemption offers no advantage, as
there are no urgent jobs to search for. In this case, a preemptive policy
causes on average an $\alpha$ unit of delay in the completion of every job,
resulting in a constant $1+\alpha$ competitive ratio when error rates are
small ($\varepsilon\leq\omega_{1}/\omega_{0}$). Given our assumption that
prediction errors are at most one half, we are able to deduce the following
corollary.

######  Corollary 6.

If $\omega_{0}<2\omega_{1}$, a fully preemptive policy is
$(1+\alpha)$-competitive.

Thus, preemption offers little advantage when the relative weight differential
is small.

######  Lemma 3.

A hybrid policy achieves a competitive ratio of

$\mathsf{CR}^{\beta}:=1+\frac{1}{2}\left(\alpha\varepsilon_{1}^{2}-\lambda+\sqrt{\frac{\omega_{0}}{\omega_{1}}\lambda^{2}+\frac{\omega_{0}}{\omega_{0}-\omega_{1}}\left(\alpha\varepsilon_{1}^{2}\right)^{2}}\right)$
(15)

where

$\lambda=\varepsilon_{0}(1+\varepsilon_{1})+\frac{\alpha\omega_{0}}{\omega_{0}-\omega_{1}}\varepsilon_{1}(1-\varepsilon_{0})-\frac{\alpha\omega_{1}}{\omega_{0}-\omega_{1}}\varepsilon_{1}^{2}.$
(16)

###### Proof.

The proof proceeds similarly where $C_{j}^{\beta}$ denotes job $j$’s
completion time in a hybrid policy. Letting $n_{1}=n-n_{0}$ and $q=n_{0}/n$,

$\displaystyle\frac{\mathbb{E}\left(\sum_{j=1}^{n}w_{j}C_{j}^{\beta}\middle|n_{0}\right)}{\mathsf{OPT}}-1$
$\displaystyle=$
$\displaystyle\frac{\mathbb{E}\left(\alpha\omega_{0}X_{0}+\alpha\omega_{1}Y_{0}+(\omega_{0}-\omega_{1})(X-X_{0})\middle|n_{0}\right)}{\mathsf{OPT}}$
$\displaystyle=$
$\displaystyle\frac{\left(\begin{multlined}\alpha\omega_{0}\varepsilon_{1}(1-\varepsilon_{0})q(1-q)n^{2}+\alpha\omega_{1}\varepsilon_{1}^{2}\left((1-q)^{2}n^{2}-(1-q)n\right)\\\
+(\omega_{0}-\omega_{1})\varepsilon_{0}(1+\varepsilon_{1})q(1-q)n^{2}\end{multlined}\alpha\omega_{0}\varepsilon_{1}(1-\varepsilon_{0})q(1-q)n^{2}+\alpha\omega_{1}\varepsilon_{1}^{2}\left((1-q)^{2}n^{2}-(1-q)n\right)\\\
+(\omega_{0}-\omega_{1})\varepsilon_{0}(1+\varepsilon_{1})q(1-q)n^{2}\right)}{(\omega_{0}-\omega_{1})\left(q^{2}n^{2}+qn\right)+\omega_{1}(n^{2}+n)}$

then, we approach the limit from below as $n\rightarrow\infty$ so the upper
bound is

$\displaystyle\frac{\left(\alpha\omega_{0}\varepsilon_{1}(1-\varepsilon_{0})+(\omega_{0}-\omega_{1})\varepsilon_{0}(1+\varepsilon_{1})\right)q(1-q)+\alpha\omega_{1}\varepsilon_{1}^{2}(1-q)^{2}}{(\omega_{0}-\omega_{1})q^{2}+\omega_{1}}.$
(18)

Using arguments similar to those given in the previous lemma, (18) always
attains a maximum in the domain $0\leq q\leq 1$ when

$q=\sqrt{\frac{\omega_{1}}{\omega_{0}-\omega_{1}}+\left(\frac{\omega_{1}}{\omega_{0}-\omega_{1}}\cdot\frac{\lambda+\alpha\varepsilon_{1}^{2}}{\lambda-\alpha\left(\frac{\omega_{1}}{\omega_{0}-\omega_{1}}\right)\varepsilon_{1}^{2}}\right)^{2}}-\frac{\omega_{1}}{\omega_{0}-\omega_{1}}\cdot\frac{\lambda+\alpha\varepsilon_{1}^{2}}{\lambda-\alpha\left(\frac{\omega_{1}}{\omega_{0}-\omega_{1}}\right)\varepsilon_{1}^{2}}$

where $\lambda$ is as defined above. ∎

An interpretable upper bound for (15) can be derived using the inequality
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$, which yields

$\mathsf{CR}^{\beta}\leq
1+\frac{\lambda}{2}\left(\sqrt{\frac{\omega_{0}}{\omega_{1}}}-1\right)+\frac{\alpha\varepsilon_{1}^{2}}{2}\left(1+\sqrt{\frac{\omega_{0}}{\omega_{0}-\omega_{1}}}\right).$

Rearranging (16), we have

$\lambda=\varepsilon_{0}+\varepsilon_{1}\left(\alpha+(1-\alpha)\varepsilon_{0}+\frac{\alpha\omega_{1}}{\omega_{0}-\omega_{1}}(1-\varepsilon_{0}-\varepsilon_{1})\right).$
(19)

We first show that $\lambda/2\leq\varepsilon$, where $\varepsilon$ is the
average of $\varepsilon_{0}$ and $\varepsilon_{1}$. To do so, it suffices to
show that the coefficient to $\varepsilon_{1}$ in (19) is no greater than 1.

$\displaystyle
1-\left(\alpha+(1-\alpha)\varepsilon_{0}+\frac{\alpha\omega_{1}}{\omega_{0}-\omega_{1}}(1-\varepsilon_{0}-\varepsilon_{1})\right)$
$\displaystyle=$
$\displaystyle(1-\alpha)(1-\varepsilon_{0})-\frac{\alpha\omega_{1}}{\omega_{0}-\omega_{1}}(1-\varepsilon_{0}-\varepsilon_{1})$
$\displaystyle=$
$\displaystyle(1-\alpha)\left(1-\varepsilon_{0}-\frac{\alpha}{1-\alpha}\cdot\frac{\omega_{1}}{\omega_{0}-\omega_{1}}(1-\varepsilon_{0}-\varepsilon_{1})\right)$
$\displaystyle=$
$\displaystyle(1-\alpha)\left(1-\varepsilon_{0}-\beta(1-\varepsilon_{0}-\varepsilon_{1})\right)$
$\displaystyle=$
$\displaystyle(1-\alpha)\left(\left(1-\beta\right)(1-\varepsilon_{0})+\beta\varepsilon_{1}\right)\geq
0.$

The last inequality follows since every term in the expression is nonnegative,
so we have the desired inequality. Recalling that the nonpreemptive
competitive ratio is
$\mathsf{CR}^{\phi}=1+\varepsilon\left(\sqrt{\omega_{0}/\omega_{1}}-1\right)$,
we are able to decompose the competitive ratio as follows:

$\mathsf{CR}^{\beta}\leq\underbrace{1+\frac{\lambda}{2}\left(\sqrt{\frac{\omega_{0}}{\omega_{1}}}-1\right)}_{\begin{subarray}{c}\text{$\leq\mathsf{CR}^{\phi}$}\\\
\text{gains relative to
$\mathsf{CR}^{\phi}$}\end{subarray}}+\underbrace{\frac{\alpha\varepsilon_{1}^{2}}{2}\left(1+\sqrt{\frac{\omega_{0}}{\omega_{0}-\omega_{1}}}\right)}_{\text{losses
relative to $\mathsf{CR}^{\phi}$}}.$ (20)

When the relative urgency $\omega_{0}/\omega_{1}\gg 1$, gains in the
$\beta$-threshold policy relative to a nonpreemptive policy are large since
the multiplier $\sqrt{\omega_{0}/\omega_{1}}-1$ is large. In comparison, the
losses are approximately equal to $\alpha\varepsilon_{1}^{2}$ and small, which
implies a guaranteed performance improvement.

######  Theorem 4.

The $\beta$-threshold policy achieves a competitive ratio

$\begin{cases}\mathsf{CR}^{\phi}&\text{if
}\rho(1-\beta)\varepsilon_{0}+\beta(1-\rho)\varepsilon_{1}\geq\min\left(\rho(1-\beta),\beta(1-\rho)\right)\text{
and }\rho\leq\beta,\\\ \mathsf{CR}^{\alpha}&\text{if
}\rho(1-\beta)\varepsilon_{0}+\beta(1-\rho)\varepsilon_{1}\geq\min\left(\rho(1-\beta),\beta(1-\rho)\right)\text{
and }\rho>\beta,\text{ and}\\\ \mathsf{CR}^{\beta}&\text{if
}\rho(1-\beta)\varepsilon_{0}+\beta(1-\rho)\varepsilon_{1}<\min\left(\rho(1-\beta),\beta(1-\rho)\right).\end{cases}$

###### Proof.

The theorem combines Lemmas 1, 2 and 16 and the conditions in Corollaries 1, 2
and 3. ∎

An immediate observation from our competitive analyses is that the worst-case
fraction of urgent jobs is inversely proportional to relative priority levels
$\omega_{0}/\omega_{1}$. But more importantly, we are able to characterize how
the competitive ratio evolves as a function of prediction error.

Figure 3: Competitive ratios

For analytical purposes, let us assume
$\varepsilon=\varepsilon_{0}=\varepsilon_{1}$ and $\omega_{0}/\omega_{1}\gg
1$. We can easily see from our expression of $\mathsf{CR}^{\phi}$ in Lemma 1
that the competitive ratio of a nonpreemptive policy grows linearly in
$O(\varepsilon)$, i.e., performance improves with prediction accuracy. In the
case of a preemptive policy, the competitive ratio stays constant at
$1+\alpha$ before it starts growing linearly in $O(\alpha\varepsilon)$.
Compared with that of a nonpreemptive policy, its growth rate is scaled down
by a factor of $\alpha$ where $0<\alpha<1$. Finally, Lemma 16 shows that the
competitive ratio of a hybrid policy grows quadratically in
$O\left(\varepsilon^{2}\right)$. Given $\varepsilon\leq 1/2$, this rate of
growth is slower than that of a nonpreemptive policy, offering yet another
interpretation of the decomposition of $\mathsf{CR}^{\beta}$ given in (20).
These findings are illustrated in Figure 3.

Our analyses indicate that, for all three policies that the $\beta$-threshold
rule admits, performance degrades gracefully as a function of prediction
error. As such, we achieve the two qualities that an online algorithm with
advice should exhibit: consistency and robustness [20]. Consistency requires
performance improvement when the predictor has low error. The idea is that
performance with good advice should be better than performance with poor
advice. At the same time, an algorithm should be robust to all inputs, with or
without predictions. All three of our policies show improved performance with
prediction accuracy. The nonpreemptive and hybrid policies even recover the
offline optimum when offered perfect predictions. Our three policies are also
robust in that the competitive ratios are bounded above when error rates are
equal to one half. When $\varepsilon=1/2$, predictions are truly random, i.e.,
there are no predictions at play.

##  5 Extensions

In this section, we consider a number of extensions to our model that more
accurately reflect real-world settings.

###  5.1 Probabilistic Classifiers

We first consider a probabilistic classifier that is able to predict with what
probability a job is of high priority. Rather than providing a binary
predictive label of urgent vs. non-urgent, this probabilistic classifier
directly offers an estimate of $p_{j}$. Let us denote these estimated
probabilities as $\hat{p}_{j}$.

We first sort jobs in nonincreasing order of $\hat{p}_{j}$, breaking ties
arbitrarily. As we proceed with our policy, jobs are opened in sorted order.
Then, we have the following corollary to Theorem 3.

######  Corollary 7.

The $\beta$-threshold rule is optimal given a probabilistic classifier.

The $\beta$-threshold rule proceeds similarly even with a probabilistic
classifier. A preemptive policy is applied to those jobs whose estimated
probabilities lie above $\beta$, and a nonpreemptive policy is applied to
those jobs whose $\hat{p}_{j}$ values fall below that threshold. The
$\beta$-threshold rule remains optimal, minimizing the objective across all
non-anticipating policies.

What differs from our original model is the measure of error. Beyond binary
classification, the false negative and false positive rates $\varepsilon_{0}$
and $\varepsilon_{1}$ no longer apply. A more appropriate measure of error in
this case would be the logarithmic loss function (also called the cross-
entropy loss function) given as follows:

$\eta=-\frac{1}{n}\sum_{j=1}^{n}(1-true(j))\cdot\log\left(\hat{p}_{j}\right)+true(j)\cdot\log\left(1-\hat{p}_{j}\right).$

The $\beta$-threshold rule is the best possible policy for decision-making
based on available information that is both imperfect and incomplete. However,
its performance depends heavily on the accuracy of the classifier on hand. An
exact characterization of performance as a function of the log-loss $\eta$
remains an open problem.

###  5.2 Probabilistic Learning Outcome

Our model assumes that a radiologist is always able to determine a job’s true
type at its $\alpha$-point with probability 1. Perhaps a more realistic model
would be to leave some room for doubt. Suppose that at job $j$’s
$\alpha$-point, we learn that job $j$ is an urgent job with some probability
$\theta_{j}\in[0,1]$. Probability $\theta_{j}$ is a posterior probability that
offers a better likelihood of job $j$’s urgency based on $\alpha$ units of
observed data.

In our notation, $\mathcal{S}$ denotes the set of unopened jobs. Every job in
set $\mathcal{S}$ has one unit in remaining work, with an associated a prior
probability of being an urgent job. These prior probabilities are as defined
in (1)-(2). Let $\mathcal{I}$ denote the set of interrupted, previously
preempted jobs that each have $1-\alpha$ units in residual work. Every job in
$\mathcal{I}$ has an associated posterior probability. At every decision
point, we make the decision of whether to open a job $k$ with the largest
prior probability $p_{k}=\max_{j\in\mathcal{S}}p_{j}$, or to complete the
remaining $1-\alpha$ units of work of job $i$, where job $i$ has the largest
posterior probability among all jobs in $\mathcal{I}$ such that
$\theta_{i}=\max_{j\in\mathcal{I}}\theta_{j}$. For this decision problem, the
following modified version of the $\beta$-threshold rule is the best possible
across all non-anticipating policies.

######  Theorem 5.

The
$\left(\beta+\frac{\alpha}{1-\alpha}\frac{\omega_{0}}{\omega_{0}-\omega_{1}}\frac{\theta_{i}}{1-\theta_{i}}\right)$-threshold
rule is optimal where $\theta_{i}=\max_{j\in\mathcal{I}}\theta_{j}$.

###### Proof.

The proof is nearly identical to the interchange argument given in Theorem 3,
with small modifications. The main difference is in recognizing that the low
priority job (job $i$) competing against the next unopened job (job $k$) in
the proof of Theorem 3 is now a low priority job with probability
$1-\theta_{i}$, and a high priority job with probability $\theta_{i}$.

As before, we consider the last decision point that deviates from this
modified $\beta$-threshold rule. If

$p_{k}>\beta+\frac{\alpha}{1-\alpha}\frac{\omega_{0}}{\omega_{0}-\omega_{1}}\frac{\theta_{i}}{1-\theta_{i}}$

and job $i$ is being processed at this decision point, the net change to the
objective upon interchange is

$\underbrace{\left(-z_{0}\omega_{0}(1-\alpha)+\omega_{1}\left(z\alpha+z_{0}(1-\alpha)\right)\right)}_{\text{from
}\eqref{eq:thm3-change1}}(1-\theta_{i})+z(\omega_{0}\alpha)\theta_{i}$

where $z$ is the number of jobs opened whose prior probabilities lie above the
modified $\beta$ threshold, and $z_{0}$ is the number of type 0 jobs among
them. The first half of this expression comes directly from our earlier proof,
weighted by the probability that job $i$ is a low priority job. If job $i$ is
an urgent job with weight $\omega_{0}$, it incurs an $\alpha$ unit of delay in
completion for each of the $z$ jobs opened during interchange. Then,

$\displaystyle\left(-z_{0}\omega_{0}(1-\alpha)+\omega_{1}\left(z\alpha+z_{0}(1-\alpha)\right)\right)(1-\theta_{i})+z(\omega_{0}\alpha)\theta_{i}$
$\displaystyle=$
$\displaystyle-(\omega_{0}-\omega_{1})(1-\alpha)(1-\theta_{i})\left(z_{0}-\underbrace{\left(\beta+\frac{\alpha}{1-\alpha}\frac{\omega_{0}}{\omega_{0}-\omega_{1}}\frac{\theta_{i}}{1-\theta_{i}}\right)}_{\text{modified
$\beta$}}z\right).$

In expectation, the overall change to the objective is negative since each of
the $z$ jobs have prior probabilities that lie above the modified $\beta$
threshold.

The second case uses an identical argument. We modify (ii) to account for the
possibility that job $i$ is a type 0 job. Then,

$\underbrace{\left(-\ell\omega_{1}+w_{k}\ell(1-\alpha)\right)}_{\text{from
}\eqref{eq:thm3-change2}}(1-\theta_{i})-\ell(\omega_{0}\alpha)\theta_{i}$

and the rest of the proof proceeds similarly. ∎

We recover the original $\beta$-threshold rule when $\theta_{i}=0$, which is
equivalent to learning that job $i$ is a non-urgent job with probability 1.
This added uncertainty raises the $\beta$ threshold bar for opening new jobs
to account for the possibility that job $i$ is an urgent job.

###  5.3 Job Arrivals Over Time

We had previously assumed that all jobs are available for processing at time
0. In this section, we consider the case where jobs arrive over time and are
released for processing at various points in time. Each job $j$ has an
associated release date $r_{j}\geq 0$ and cannot be processed before then. At
any given time, we assume no knowledge of jobs arriving in the future.

The offline version of this problem in which jobs’ true types are known a
priori can be written as
$1|r_{j},p_{j}=1,pmtn|\sum\\{\omega_{0},\omega_{1}\\}C_{j}$ in the scheduling
notation of Graham et al. [13]. The following theorem identifies an optimal
policy for this offline problem.

######  Theorem 6.

The weighted shortest remaining processing time (WSRPT) rule is an optimal
policy for $1|r_{j},p_{j}=1,pmtn|\sum\\{\omega_{0},\omega_{1}\\}C_{j}$.

###### Proof.

Consider an optimal schedule where job $k$ is being processed at time $t$.
Suppose there exists another available job $j$ at $t$ such that

$\frac{w_{k}}{x_{k}(t)}<\frac{w_{j}}{x_{j}(t)}$ (21)

where $x_{j}(t)$ denotes the amount of work remaining in job $j$ at time $t$.
If $w_{j}=w_{k}$, the optimal policy is in violation of the SRPT rule so we
immediately have a contradiction [26]. We therefore assume that $w_{j}\neq
w_{k}$. In addition, we also assume without loss of generality that job $j$ is
the job with the largest weight-to-remaining-work ratio among all available
jobs at $t$. We establish a contradiction by interchange.

Despite our assumption that the optimal schedule prioritizes job $k$ over job
$j$ at time $t$, we do not know whether job $k$ was actually completed prior
to job $j$. We let $C_{j}$ and $C_{k}$ denote the completion times of jobs $j$
and $k$ in the optimal schedule, respectively, and consider both cases.

  1. i

$C_{j}<C_{k}$ : we use a pairwise interchange argument similar to that used in
the proof of optimality of SRPT. Starting from $t$, we take the first
$x_{j}(t)$ units devoted to processing jobs $j$ or $k$ in the optimal
schedule, and use that time to process job $j$ to completion at $\hat{C}_{j}$.
The remaining $x_{k}(t)$ units of time are then used to process job $k$ with
completion time $\hat{C}_{k}=C_{k}$. This interchange only affects the
completion time of job $j$, and $\hat{C}_{j}<C_{j}$ by construction, so we
have our desired contradiction.

  2. ii

$C_{k}<C_{j}$ : in this case, we require some additional pieces that are
unique to our problem with two distinct weights. We first claim that job $j$
is the only job of weight $w_{j}$ that is processed in the interval
$[t,C_{j})$. At time $t$, job $j$ has the largest weight-to-remaining-work
ratio, so it would be against the SRPT rule to process any other available job
of weight $w_{j}$ until job $j$ is complete. The same is true of any job of
weight $w_{j}$ released in the interval $[t,C_{j})$ since $x_{j}(t)\leq 1$ and
every newly arriving job has 1 unit of remaining work. Using a similar
argument for job $k$ in the interval $[t,C_{k})$, we can conclude that only
jobs $j$ and $k$ are processed in $[t,\min(C_{k},C_{j}))=[t,C_{k})$.

It is possible, however, that other jobs are processed in $[C_{k},C_{j})$. By
our earlier claim, only jobs of weight $w_{k}$ can be processed in this
interval. Let $\mathcal{A}$ denote the set of jobs processed in
$[C_{k},C_{j})$ where, for every job $\ell\in\mathcal{A}$, $w_{\ell}=w_{k}$
holds. We claim that every job $\ell\in\mathcal{A}$ satisfies

$\frac{w_{\ell}}{x_{\ell}(t)}<\frac{w_{j}}{x_{j}(t)}.$ (22)

For notational convenience, we shall continue to use $x_{\ell}(t)$ on jobs
that are released after $t$, as we can simply set $x_{\ell}(t)=1$ without
affecting the analysis. If job $\ell$ has release date $r_{\ell}\leq t$, then
$x_{\ell}(t)\geq x_{k}(t)$ since the optimal schedule would otherwise be in
violation of the SRPT rule by processing job $k$ instead of $\ell$ at time
$t$. Combined with (21), we obtain the inequality. The same is true if job
$\ell$ has release date $r_{\ell}\in[t,C_{j})$ since $x_{k}(t)\leq
x_{\ell}(t)=1$.

Lastly, we argue that every job $\ell\in\mathcal{A}$ has completion time
$C_{\ell}\in[C_{k},C_{j})$. Suppose on the contrary that there exists a job
that is partially processed in $[C_{k},C_{j})$ that completes sometime after
$C_{j}$. Then, shifting the time units devoted to processing this job to the
end of the $[C_{k},C_{j})$ interval allows job $j$ to be completed earlier
without affecting the completion time of any other job. Doing so strictly
improves the objective and contradicts the fact that we have an optimal
schedule.

We finally have all the ingredients we need to proceed with the interchange.
We first process job $j$ in the first $x_{j}(t)$ units of $[t,C_{j})$,
followed by jobs in $\mathcal{A}\cup\\{k\\}$ in the remainder of the interval
$[t+x_{j}(t),C_{j})$. Then, for each job in $\mathcal{A}\cup\\{k\\}$, there is
a delay in completion of at most $x_{j}(t)$ units. Job $j$, on the other hand,
completes $x_{k}(t)+\sum_{\ell\in\mathcal{A}}x_{\ell}(t)$ units earlier in the
schedule. The net effect to the objective is thus bounded above by

$\displaystyle-
w_{j}\left(x_{k}(t)+\sum_{\ell\in\mathcal{A}}x_{\ell}(t)\right)+|\mathcal{A}\cup\\{k\\}|w_{k}x_{j}(t)$
$\displaystyle=$ $\displaystyle-
w_{j}x_{k}(t)+w_{k}x_{j}(t)-w_{j}\left(\sum_{\ell\in\mathcal{A}}x_{\ell}(t)\right)+|\mathcal{A}|w_{k}x_{j}(t)$
$\displaystyle=$
$\displaystyle\underbrace{-w_{j}x_{k}(t)+w_{k}x_{j}(t)}_{\text{$<0$ by
\eqref{eq:cont-
wsrpt}}}+\sum_{\ell\in\mathcal{A}}\underbrace{\left(-w_{j}x_{\ell}(t)+w_{\ell}x_{j}(t)\right)}_{\text{$<0$
by \eqref{eq:cont-wsrpt-add}}}<0$

which contradicts the fact that we have an optimal schedule.∎

It is worth adding that the theorem above does not generalize to problems of
the same setting with three or more distinct weights. In particular, given our
assumptions in (21), our interchange argument relies on job $j$ being the job
with the largest weight-to-remaining-work ratio among all jobs completing in
the interval $[t,C_{j})$. We have shown with (22) that this condition always
holds when there are two distinct weights. When there are three or more
distinct weights, we can easily construct examples for which this condition no
longer holds, for example, by scheduling the arrival of a job with very large
weight in $[t,C_{j})$.

The WSRPT rule combines two well-known scheduling results: the WSPT rule
(Theorem 1) and the SRPT rule (Theorem 2). The WSRPT rule itself is not new;
it has been used in other works as a popular heuristic (see [8, 32], for
example). Nevertheless, to our knowledge, Theorem 6 is the first result on
WSRPT optimality, and
$1|r_{j},p_{j}=1,pmtn|\sum\\{\omega_{0},\omega_{1}\\}C_{j}$ is the first
scheduling problem for which WSRPT is shown to be optimal.

#### Competitive Analysis

We now consider the $\beta$-threshold rule when jobs arrive into the system
over time. At each decision point, we make decisions based on an updated set
of unopened jobs that accounts for any new job arrivals since our last
decision point. These newly added jobs enter the queue according to their
predicted priorities. Whereas our hybrid policy previously allowed a one-time
switch from a preemptive policy to a nonpreemptive policy, the arrival of a
high priority job could trigger preemptions when necessary, resulting in
alternating preemptive and nonpreemptive regimes.

Online job arrivals add yet another layer of randomness and complexity to our
model. Our efforts in competitive analysis incorporating both job arrivals and
imperfect predictions were not yet fruitful. In what follows, we present our
results when job arrivals are present with perfect type predictions.

Let $\mathsf{OPT}$ denote the offline optimum obtained by WSRPT, and let
$\mathsf{ALG_{0}}$ denote the performance of the online $\beta$-threshold
policy when job priorities are known a priori. The main difference between
these two policies under consideration is that we are able to preempt a job
whenever necessary in $\mathsf{OPT}$, but may do so at most once at a job’s
$\alpha$-point in $\mathsf{ALG}$.

The online policy $\mathsf{ALG_{0}}$ assumes that true job priorities are
given to us at time of job arrival. This is a deterministic online problem
where preemptions are limited to $\alpha$-points, so we might express this
problem as
$1|r_{j},p_{j}=1,\alpha\text{-}pmtn|\sum\\{\omega_{0},\omega_{1}\\}C_{j}$ in
the scheduling notation of Graham et al. [13]. We follow the $\beta$-threshold
rule at each decision point, where our set of unopened jobs includes jobs that
have arrived since our last decision point. We review each decision in detail
to highlight that each of our decisions are consistent with WSRPT. First, the
existence of any unprocessed type 0 job will trigger a preemption at an
$\alpha$-point. Preempting a type 1 job at an $\alpha$-point is WSRPT-
consistent since, by Assumption 1,

$\omega_{1}<\omega_{0}(1-\alpha)\iff\frac{\omega_{1}}{1-\alpha}<\frac{\omega_{0}}{1}.$

Type 0 jobs will then complete nonpreemptively. When only type 1 jobs remain,
any partially processed type 1 job will be processed to completion before we
move on to an unopened type 1 job. This is consistent with the
$\beta$-threshold rule, the SRPT rule, and by extension, the WSRPT rule. Thus,
when true job types are known a priori, $\mathsf{ALG_{0}}$ is an optimal
policy for
$1|r_{j},p_{j}=1,\alpha\text{-}pmtn|\sum\\{\omega_{0},\omega_{1}\\}C_{j}$. We
now compare its performance against $\mathsf{OPT}$. Our proofs frequently rely
on the following inequality, widely known as the mediant inequality.

#### The Mediant Inequality.

For any positive real numbers $a,b,c,d>0$,

$\frac{a+b}{c+d}\leq\max\left(\frac{a}{c},\frac{b}{d}\right).$

######  Theorem 7.

$\mathsf{ALG_{0}}$ is
$\max\left(1+\alpha,\frac{2}{1+\alpha}\right)$-competitive, and
$\sqrt{2}$-competitive if we choose $\alpha=\sqrt{2}-1$.

###### Proof.

We proceed by running the online $\beta$-threshold policy and WSRPT in
parallel. Both policies schedule the same set of $n$ jobs arriving over time,
where true job priorities are immediately observable upon job arrival. We
refer to the schedule generated by WSRPT as the optimal schedule.

We first discuss some reasonable assumptions we can impose on the data.
Without loss of generality, we assume $\min_{j}r_{j}=0$, and that there is at
least one job of each type in the dataset. We also assume that each of these
$n$ jobs are processed without idle time in the optimal schedule so that the
last job completes at time $n$. To see why, first observe that both policies
are work-conserving. Any dataset that prompts a machine to become idle in an
optimal schedule will simultaneously create idle time in a schedule generated
by our online policy. Let us partition the dataset whenever there is idle
time. Because our objective functions are linear, we can apply the mediant
inequality to the competitive ratio based on said partition. Thus it suffices
to consider a set of jobs that does not generate idle time.

We proceed by identifying ways to further partition our set of jobs until we
have a minimal set of jobs that gives the worst case performance. In order to
do so, we need the following claims.

######  Claim 1.

Type 1 jobs begin processing at the same time in $\mathsf{OPT}$ and in
$\mathsf{ALG_{0}}$. This start time is always integer.

###### Proof of Claim 1.

Let $t>0$ be any time at which a type 1 job begins its processing in an
optimal schedule. By the optimality of the WSRPT rule, every type 0 job
released prior to $t$ has completed by $t$, and no type 1 job that has begun
its processing prior to $t$ is left unfinished. Integrality of $t$ follows
naturally.

Type 1 jobs also start at integer time points in the schedule generated by our
online $\beta$-threshold policy because the policy requires that any partially
processed jobs be completed before opening a new type 1 job. Consider time $t$
as defined above. The optimal schedule implies that all type 0 jobs released
prior to $t$ have release dates no later than $t-1$. Because there is at least
one decision point in the interval $[t-1,t)$, any type 0 job released prior to
$t$ must have completed by $t$ in the schedule generated by the online policy.
Then, by our assumption that precludes any idle time in the schedule, integer
units of work have been done on type 1 jobs by $t$ and the result follows. ∎

Claim 1 allows us to partition the schedule whenever a type 1 job begins its
processing. Within each partitioned block, the same set of jobs will have
completed processing in both policies. Thus, by the mediant inequality, we
consider one such block. This implies that it suffices to consider a dataset
with exactly one type 1 job. We call this job $k$. Without loss of generality,
we assume that job $k$ begins its processing at time 0. Let $C_{k}^{*}$ and
$C_{k}^{0}$ denote the completion time of job $k$ in $\mathsf{OPT}$ and
$\mathsf{ALG_{0}}$, respectively.

######  Claim 2.

$C_{k}^{*}\geq C_{k}^{0}$.

###### Proof of Claim 2.

First observe that $C_{k}^{*}$ and $C_{k}^{0}$ are positive integers for the
same reasons given in the proof of Claim 1. Suppose on the contrary that
$C_{k}^{*}<C_{k}^{0}$. Then there exists some job $\ell\neq k$ of type 0 that
is not processed prior to $C_{k}^{*}$ in the optimal schedule that is being
processed in $\mathsf{ALG_{0}}$ at time $C_{k}^{*}$. Preemptions only occur at
$\alpha$-points in $\mathsf{ALG_{0}}$, so job $\ell$ must have begun its
processing at $C_{k}^{*}-(1-\alpha)$, which implies that $r_{\ell}\leq
C_{k}^{*}-(1-\alpha)$. By Assumption 1, it follows that $r_{\ell}\leq
C_{k}^{*}-(1-\alpha)<C_{k}^{*}-(\omega_{1}/\omega_{0})$.

The optimal schedule follows WSRPT, so delaying the processing of any type 0
job in favor of completing job $k$ would occur only if a type 0 job arrives at
such a time that the remaining work in job $k$, $x_{k}$, satisfies
$\omega_{1}/x_{k}>\omega_{0}/1\iff x_{k}<\omega_{1}/\omega_{0}$. Said
differently, only those type 0 jobs arriving after time
$C_{k}^{*}-(\omega_{1}/\omega_{0})$ would be processed outside of the
$\left[0,C_{k}^{*}\right)$ interval in an optimal schedule, and by Assumption
1, also outside of $\left[0,C_{k}^{*}\right)$ in $\mathsf{ALG_{0}}$. Since
$r_{\ell}<C_{k}^{*}-(\omega_{1}/\omega_{0})$, job $\ell$ should have completed
before job $k$ in an optimal schedule, which establishes the desired
contradiction. ∎

An important byproduct of the proof of Claim 2 is that every job that
completes in the interval $\left[0,C_{k}^{*}\right)$ in $\mathsf{ALG_{0}}$
also completes within the same interval in an optimal schedule. Both policies
are work-conserving, so the converse also holds. Let $\mathcal{A}$ denote the
set of jobs completing in this interval. Then, by another application of the
mediant inequality, it suffices to consider the set of jobs $\mathcal{A}$,
where job $k$ is the only type 1 job therein. An immediate consequence of this
is an upper bound of $\max(\alpha,1-\alpha)$ on the delay in type 0 job
completion times in $\mathsf{ALG_{0}}$ relative to those in $\mathsf{OPT}$.
Intuitively, this bound captures how long a type 0 job will have to wait until
the next decision point while job $k$ is being processed. Thus,

$\displaystyle\frac{\mathsf{ALG_{0}}}{\mathsf{OPT}}$
$\displaystyle=\frac{\omega_{1}C_{k}^{0}+\sum_{j\in\mathcal{A}\setminus\\{k\\}}\omega_{0}C_{j}^{0}}{\omega_{1}C_{k}^{*}+\sum_{j\in\mathcal{A}\setminus\\{k\\}}\omega_{0}C_{j}^{*}}$
$\displaystyle\leq\frac{\sum_{j\in\mathcal{A}\setminus\\{k\\}}\cancel{\omega_{0}}C_{j}^{0}}{\sum_{j\in\mathcal{A}\setminus\\{k\\}}\cancel{\omega_{0}}C_{j}^{*}}$
by the mediant inequality, since $C_{k}^{*}\geq C_{k}^{0}$
$\displaystyle\leq\max_{j\in\mathcal{A}\setminus\\{k\\}}\left(\frac{C_{j}^{0}}{C_{j}^{*}}\right)$
by the mediant inequality
$\displaystyle=\max_{j\in\mathcal{A}\setminus\\{k\\}}\left(\frac{C_{j}^{*}+\delta_{j}}{C_{j}^{*}}\right)$

where $\delta_{j}$ is job $j$’s delay in completion in $\mathsf{ALG_{0}}$
relative to $\mathsf{OPT}$. Finally, using
$\delta_{j}\leq\max(\alpha,1-\alpha)$ and finding the earliest possible
completion time in the optimal schedule for each type of delay,

$\displaystyle\max_{j\in\mathcal{A}\setminus\\{k\\}}\left(\frac{C_{j}^{*}+\delta_{j}}{C_{j}^{*}}\right)$
$\displaystyle\leq\max\left(1+\frac{\alpha}{1},1+\frac{1-\alpha}{1+\alpha}\right)$
$\displaystyle=\max\left(1+\alpha,\frac{2}{1+\alpha}\right),$

which proves the result. ∎

Our results offer some guidance as to which values of $\alpha$ might be
effective when dealing with limited preemption points. But given job arrivals
and perfect predictions, the $\beta$-threshold rule is 2-competitive
regardless of the $\alpha$ value that we choose. Given imperfect predictions
without job arrivals, on the other hand, we obtain our earlier result given in
Theorem 4. Competitive analysis featuring both uncertainties remains an open
problem.

Figure 4: Expected performance when jobs arrive over time

Despite the lack of theoretical guarantees, empirical evaluations of the
$\beta$-threshold rule under realistic job arrival scenarios and imperfect
prediction show that our policy still performs very well. Figure 4 plots the
expected performance of the $\beta$-threshold rule as a function of prediction
error, where performance is normalized by the offline optimum obtained by
WSRPT. For illustrative purposes, we assume $\varepsilon_{0}=\varepsilon_{1}$.
In this plot, we assume that jobs are arriving according to a Poisson arrival
process with mean interarrival time 0.9 (given unit processing times). The
figure shows that our policies exhibit near-optimal performance, and that our
$\beta$-threshold rule of alternating between the nonpreemptive and preemptive
regimes outperforms both non-adaptive policies when we are given high quality
advice.

Our experiments thus far reveal that our original stylized model without job
arrivals results in the worst-case performance. This is surprising to us, and
also somewhat counterintuitive given classic results in scheduling theory
involving job release dates. One possible explanation for this could be the
higher opportunity costs of misprediction stemming from having a long line of
jobs waiting in the queue, but we do not have a good answer for this yet.

##  6 Discussion and Future Directions

The work presented in this paper was motivated by recent interest in using
machine learning algorithms for patient triage and prioritization. We modeled
this as a learning-augmented online scheduling problem in which we are given
good but imperfect predictions of patient risk, and sought to capture the
trade-off between the need to prioritize emergency cases and the potential
costs of misprediction. We presented a simple threshold-based policy that
addressed these concerns and proved that our policy is in fact the best
possible in certain stylized settings. The policy was also shown to remain
effective in more realistic settings.

The model that we studied is grounded in reality. For many radiologists,
preemptions and interruptions are simply facts of life, as is the fact that
they are trained to collect information in real time while processing each
patient case. In that sense, our policy recommendation is intuitive and easy
to implement, and more importantly, does not require an overhaul of existing
systems and Modality Worklists that are already in place. While it would be
impossible to implement the $\beta$-threshold rule by the book in a clinical
setting, we do believe that our policy can offer qualitative guidance on how
to think about and respond to predictions of patient risk in connection with
other input parameters.

That said, our work in this area is far from complete. Several concrete next
steps have been outlined in Section 5, including exact characterizations of
performance with probabilistic classifiers or with probabilistic learning
outcomes. Theoretical guarantees of performance of the $\beta$-threshold rule
with online job arrivals also remain an open problem.

Even beyond these extensions, there are many interesting directions that we
can explore for future research. One natural direction would be to generalize
our stylized model by allowing granularity in prioritization schemes beyond a
binary classification of urgent vs. non-urgent. From a practical perspective,
clinics tend to have their own internal methods of categorizing urgency
levels. For example, the Department of Radiology at the Weill Cornell Medical
Center categorizes urgency levels by the following:

  * •

Critical (JCAHO111Joint Commission on Accreditation of Healthcare
Organizations-designated): immediate communication required

  * •

Emergent: immediate communication required

  * •

Urgent: communication required in under 4 hours

  * •

Important: closed-loop communication required but not in an urgent time frame
(1-2 week limit).

While this is clearly a natural next step to consider, it is less evident
whether our optimal policy structure extends under this more general setting.
We have observed, for example, that the optimality of the WSRPT rule breaks
immediately upon adding a third priority class.

Another direction would be to consider various preemptive strategies that
better reflect clinical scenarios. In our scheduling formulation, preemptions
could be used to model the many different ways in which radiologists learn
true job types over time. One extension might be to consider multiple
$\alpha$-points of preemption. For example, given
$0<\alpha_{1}<\alpha_{2}<\dots<1$, we might imagine radiologists having
improved confidence about a job’s true priority with additional time spent
processing that job. We could also consider varying preemption points for each
job, for instance by letting job $j$ preempt at a unique $\alpha_{j}$-point
once a radiologist meets a certain level of confidence. It would then be
interesting to observe how performance evolves as a function of these
preemption confidence levels.

In a similar vein, it is often the case that preemption comes at a cost. Our
model assumes that the work required to complete an interrupted job is exactly
the same as if it had not been interrupted. Realistically, it might take a
while for a radiologist to warm up to a job, in which case restarting a
previously preempted job may require an extra factor of $\gamma>1$ in
processing time. Early attempts at tackling this problem with friction costs
have not been successful due to difficulties in having to differentiate
decision points by continuity in job processing.

Continued advances in machine learning techniques mean that, over time,
algorithms will likely become better at detecting abnormalities in medical
images. Our current model assumes fixed error rates based on guarantees on
expected generalization error, but we could also consider applying Bayesian
inference techniques to update error rates over time based on observed data.
This might lead to an adaptive $\beta$-threshold policy for which we might
seek convergence results.

Finally, in the spirit of scheduling research, we could consider how the
policy performs when there are multiple radiologists, i.e., parallel machines.

## References

  * Almanza et al. [2021] Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re.  Online facility location with multiple advice.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 4661–4673. Curran Associates, Inc., 2021.  URL https://proceedings.neurips.cc/paper/2021/file/250473494b245120a7eaf8b2e6b1f17c-Paper.pdf.
  * Antoniadis et al. [2020] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev.  Secretary and online matching problems with machine learned advice, 2020\.  URL https://arxiv.org/abs/2006.01026.
  * Argon and Ziya [2009] Nilay Tanık Argon and Serhan Ziya.  Priority assignment under imperfect information on customer type identities.  _Manufacturing & Service Operations Management_, 11(4):674–693, 2009.  doi: 10.1287/msom.1080.0246.  URL https://doi.org/10.1287%2Fmsom.1080.0246.
  * Azar et al. [2021] Yossi Azar, Stefano Leonardi, and Noam Touitou.  Flow time scheduling with uncertain processing time.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_. ACM, 2021.  doi: 10.1145/3406325.3451023.  URL https://doi.org/10.1145%2F3406325.3451023.
  * Balkanski et al. [2022] Eric Balkanski, Tingting Ou, Clifford Stein, and Hao-Ting Wei.  Scheduling with speed predictions, 2022.  URL https://arxiv.org/abs/2205.01247.
  * Balseiro et al. [2022] Santiago Balseiro, Christian Kroer, and Rachitesh Kumar.  Single-leg revenue management with advice, 2022.  URL https://arxiv.org/abs/2202.10939.
  * Banerjee et al. [2022] Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin.  Online nash social welfare maximization with predictions.  In _Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , pages 1–19. Society for Industrial and Applied Mathematics, 2022.  doi: 10.1137/1.9781611977073.1.  URL https://doi.org/10.1137%2F1.9781611977073.1.
  * Batsyn et al. [2013] Mikhail Batsyn, Boris Goldengorin, Panos M. Pardalos, and Pavel Sukhov.  Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time.  _Optimization Methods and Software_ , 29(5):955–963, 2013.  doi: 10.1080/10556788.2013.854360.  URL https://doi.org/10.1080%2F10556788.2013.854360.
  * Chen et al. [2022] Justin Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang.  Faster fundamental graph algorithms via learned predictions.  In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 3583–3602. PMLR, 2022\.  URL https://proceedings.mlr.press/v162/chen22v.html.
  * Conway et al. [1967] Richard Walter Conway, William L. Maxwell, and Louis W. Miller.  _Theory of Scheduling_.  Addison-Wesley Publishing Company, 1967.
  * Dinitz et al. [2021] Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Faster matchings via learned duals, 2021.  URL https://arxiv.org/abs/2107.09770.
  * Dütting et al. [2021] Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii.  Secretaries with advice.  In _Proceedings of the 22nd ACM Conference on Economics and Computation_. ACM, 2021.  doi: 10.1145/3465456.3467623.  URL https://doi.org/10.1145%2F3465456.3467623.
  * Graham et al. [1979] Ronald L. Graham, Eugene L. Lawler, Jan Karel Lenstra, and Alexander Hendrik George Rinnooy Kan.  Optimization and approximation in deterministic sequencing and scheduling: A survey.  In _Discrete Optimization II_ , volume 5 of _Annals of Discrete Mathematics_ , pages 287–326. Elsevier, 1979.  doi: https://doi.org/10.1016/S0167-5060(08)70356-X.  URL https://www.sciencedirect.com/science/article/pii/S016750600870356X.
  * Im et al. [2021a] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit.  Online knapsack with frequency predictions.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , volume 34, pages 2733–2743. Curran Associates, Inc., 2021a.  URL https://proceedings.neurips.cc/paper/2021/file/161c5c5ad51fcc884157890511b3c8b0-Paper.pdf.
  * Im et al. [2021b] Sungjin Im, Ravi Kumar, Mahshid Montazer Qaem, and Manish Purohit.  Non-clairvoyant scheduling with predictions.  In _Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures_. ACM, 2021b.  doi: 10.1145/3409964.3461790.  URL https://doi.org/10.1145%2F3409964.3461790.
  * Klitsch [2016] Neal Klitsch.  How I read imaging studies, 2016.  URL http://www.neighborhoodradiologist.com/how-i-read-imaging-studies/.
  * Lattanzi et al. [2020] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 1859–1877. Society for Industrial and Applied Mathematics, 2020.  doi: 10.1137/1.9781611975994.114.  URL https://doi.org/10.1137%2F1.9781611975994.114.
  * Lavastida et al. [2021] Thomas Lavastida, Benjamin Moseley, R. Ravi, and Chenyang Xu.  Using predicted weights for ad delivery.  In _SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21)_ , pages 21–31. Society for Industrial and Applied Mathematics, 2021.  doi: 10.1137/1.9781611976830.3.  URL https://doi.org/10.1137%2F1.9781611976830.3.
  * Lindermayr and Megow [2022] Alexander Lindermayr and Nicole Megow.  Permutation predictions for non-clairvoyant scheduling, 2022.  URL https://arxiv.org/abs/2202.10199.
  * Lykouris and Vassilvitskii [2021] Thodoris Lykouris and Sergei Vassilvitskii.  Competitive caching with machine learned advice.  _Journal of the ACM_ , 68(4):1–25, 2021.  doi: 10.1145/3447579.  URL https://doi.org/10.1145%2F3447579.
  * McLay and Mayorga [2013] Laura A. McLay and Maria E. Mayorga.  A model for optimally dispatching ambulances to emergency calls with classification errors in patient priorities.  _IIE Transactions_ , 45(1):1–24, 2013.  doi: 10.1080/0740817x.2012.665200.  URL https://doi.org/10.1080%2F0740817x.2012.665200.
  * Mitzenmacher [2020] Michael Mitzenmacher.  Scheduling with predictions and the price of misprediction.  2020\.  doi: 10.4230/LIPICS.ITCS.2020.14.  URL https://drops.dagstuhl.de/opus/volltexte/2020/11699/.
  * Mitzenmacher and Vassilvitskii [2020] Michael Mitzenmacher and Sergei Vassilvitskii.  Algorithms with predictions.  _CoRR_ , arXiv: https://arxiv.org/abs/2006.09123, 2020.  doi: 10.48550/ARXIV.2006.09123.  URL https://arxiv.org/abs/2006.09123.
  * Mokin et al. [2019] Maxim Mokin, Sameer A Ansari, Ryan A McTaggart, Ketan R Bulsara, Mayank Goyal, Michael Chen, and Justin F Fraser.  Indications for thrombectomy in acute ischemic stroke from emergent large vessel occlusion (ELVO): report of the SNIS standards and guidelines committee.  _Journal of NeuroInterventional Surgery_ , 11(3):215–220, 2019.  doi: 10.1136/neurintsurg-2018-014640.  URL https://doi.org/10.1136%2Fneurintsurg-2018-014640.
  * Purohit et al. [2018] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ml predictions.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31, 2018.  URL https://proceedings.neurips.cc/paper/2018/file/73a427badebe0e32caa2e1fc7530b7f3-Paper.pdf.
  * Schrage [1968] Linus Schrage.  A proof of the optimality of the shortest remaining processing time discipline.  _Operations Research_ , 16(3):687–690, 1968.  doi: 10.1287/opre.16.3.687.  URL https://doi.org/10.1287%2Fopre.16.3.687.
  * Shih [2022] George Shih.  Private communication, 2022.
  * Singh et al. [2020] Simrita Singh, Itai Gurvich, and Jan Albert Van Mieghem.  Feature-based design of priority queues: Digital triage in healthcare.  _SSRN Electronic Journal_ , 2020.  doi: 10.2139/ssrn.3731865.  URL https://doi.org/10.2139%2Fssrn.3731865.
  * Smith [1956] Wayne E. Smith.  Various optimizers for single-stage production.  _Naval Research Logistics Quarterly_ , 3(1-2):59–66, 1956.  doi: 10.1002/nav.3800030106.  URL https://doi.org/10.1002%2Fnav.3800030106.
  * Thompson et al. [2022] Yee Lam Elim Thompson, Gary Levine, Weijie Chen, Berkman Sahiner, Qin Li, Nicholas Petrick, and Frank W. Samuelson.  Wait-time-saving analysis and clinical effectiveness of computer-aided triage and notification (CADt) devices based on queueing theory.  In Claudia R. Mello-Thoms and Sian Taylor-Phillips, editors, _Medical Imaging 2022: Image Perception, Observer Performance, and Technology Assessment_. SPIE, 2022.  doi: 10.1117/12.2603184.  URL https://doi.org/10.1117%2F12.2603184.
  * van der Zee and Theil [1961] S. P. van der Zee and H. Theil.  Priority assignment in waiting-line problems under conditions of misclassification.  _Operations Research_ , 9(6):875–885, 1961.  doi: 10.1287/opre.9.6.875.  URL https://doi.org/10.1287%2Fopre.9.6.875.
  * Xiong and Chung [2012] Bo Xiong and Christine Chung.  Completion time scheduling and the WSRPT algorithm.  In _Lecture Notes in Computer Science_ , pages 416–426. Springer Berlin Heidelberg, 2012.  doi: 10.1007/978-3-642-32147-4˙37.  URL https://doi.org/10.1007%2F978-3-642-32147-4_37.
  * Xu and Lu [2022] Chenyang Xu and Pinyan Lu.  Mechanism design with predictions, 2022.  URL https://arxiv.org/abs/2205.11313.