# Randomized algorithms for fully online multiprocessor scheduling with
testing

Mingyang Gong Department of Computing Science, University of Alberta.
Edmonton, Alberta T6G 2E8, Canada. {mgong4<EMAIL_ADDRESS>Zhi-Zhong Chen
Division of Information System Design, Tokyo Denki University. Saitama
350-0394, Japan<EMAIL_ADDRESS>Guohui Lin∗ Correspondence author.
Email<EMAIL_ADDRESS>Lusheng Wang Department of Computer Science, City
University of Hong Kong. Hong Kong SAR, China<EMAIL_ADDRESS>
###### Abstract

We contribute the first randomized algorithm that is an integration of
arbitrarily many deterministic algorithms for the fully online multiprocessor
scheduling with testing problem. When there are only two machines, we show
that with two component algorithms its expected competitive ratio is already
strictly smaller than the best proven deterministic competitive ratio lower
bound. Such algorithmic results are rarely seen in the literature.

Multiprocessor scheduling is one of the first combinatorial optimization
problems that have received numerous studies. Recently, several research
groups examined its testing variant, in which each job $J_{j}$ arrives with an
upper bound $u_{j}$ on the processing time and a testing operation of length
$t_{j}$; one can choose to execute $J_{j}$ for $u_{j}$ time, or to test
$J_{j}$ for $t_{j}$ time to obtain the exact processing time $p_{j}$ followed
by immediately executing the job for $p_{j}$ time. Our target problem is the
fully online version, in which the jobs arrive in sequence so that the testing
decision needs to be made at the job arrival as well as the designated
machine. We propose an expected $(\sqrt{\varphi+3}+1)(\approx
3.1490)$-competitive randomized algorithm as a non-uniform probability
distribution over arbitrarily many deterministic algorithms, where
$\varphi=\frac{\sqrt{5}+1}{2}$ is the Golden ratio. When there are only two
machines, we show that our randomized algorithm based on two deterministic
algorithms is already expected $\frac{3\varphi+3\sqrt{13-7\varphi}}{4}(\approx
2.1839)$-competitive. Besides, we use Yao’s principle to prove lower bounds of
$1.6682$ and $1.6522$ on the expected competitive ratio for any randomized
algorithm at the presence of at least three machines and only two machines,
respectively, and prove a lower bound of $2.2117$ on the competitive ratio for
any deterministic algorithm when there are only two machines.

##### Keywords:

Scheduling; multiprocessor scheduling; scheduling with testing; makespan;
randomized algorithm

#### Acknowledgments.

This research is supported by the NSERC Canada, the Grant-in-Aid for
Scientific Research of the Ministry of Education, Science, Sports and Culture
of Japan, under Grant No. 18K11183, the National Science Foundation of China
(NSFC: 61972329), and GRF grants for Hong Kong Special Administrative Region,
China (CityU 11210119, CityU 11206120, CityU11218821).

##  1 Introduction

We study the fully online multiprocessor scheduling with testing [6, 7, 2, 3]
problem in this paper, and study it from the randomized algorithm perspective.
Multiprocessor scheduling [10] is one of the first well-known NP-hard
combinatorial optimization problems, having received extensive research in the
past several decades.

An instance $I$ of multiprocessor scheduling consists of a set of $n$ jobs
$\mathcal{J}=\\{J_{1},J_{2},\ldots,J_{n}\\}$, each to be executed non-
preemptively on one of a set of $m$ parallel identical machines
$\mathcal{M}=\\{M_{1},M_{2},\ldots,M_{m}\\}$; and the goal is to minimize the
makespan $C_{\max}$, that is, the maximum job completion time. Different from
the classic setting where each job $J_{j}$ comes with the processing time
$p_{j}$, in scheduling with testing each job $J_{j}$ arrives with an upper
bound $u_{j}$ on the processing time $p_{j}$ and a testing operation of length
$t_{j}$, but $p_{j}$ remains unknown until the job is tested. The job $J_{j}$
can either be executed on one of the machines for $u_{j}$ time or be tested
for $t_{j}$ time followed by immediately executing for $p_{j}$ time on the
same machine.

If all the jobs arrive at time zero, multiprocessor scheduling with testing is
a semi-online problem, denoted as $P\mid t_{j},0\leq p_{j}\leq u_{j}\mid
C_{\max}$. In this paper, we investigate the fully online problem in which the
jobs arrive in sequence such that the testing decision needs to be made at the
job arrival as well as the designated machine for testing and/or executing,
denoted as $P\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$.
Apparently, semi-online is a special case of fully online, and in both cases
the scheduler should take advantage of the known information about a job upon
its arrival to decide whether or not to test the job so as to best balance the
total time spent on the job due to the unknown processing time.

Given a polynomial time deterministic algorithm for the semi-online or fully
online problem, let $C(I)$ be the makespan produced by the algorithm on an
instance $I$ and $C^{*}(I)$ be the makespan of the optimal offline schedule,
respectively. The performance of the algorithm is measured by the competitive
ratio defined as $\sup_{I}\\{C(I)/C^{*}(I)\\}$, where $I$ runs over all
instances of the problem, and the algorithm is said
$\sup_{I}\\{C(I)/C^{*}(I)\\}$-competitive. Switching to a randomized
algorithm, we correspondingly collect its expected makespan $E[C(I)]$ on the
instance $I$ and the randomized algorithm is said expected
$\sup_{I}\\{E[C(I)]/C^{*}(I)\\}$-competitive. For online problems, randomized
algorithms sometimes can better deal with uncertainties leading to lower
expected competitive ratios than the competitive ratios of the best
deterministic algorithms. We contribute such a randomized algorithm for $P\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$, and furthermore, when there
are only two machines, we show that its expected competitive ratio is strictly
smaller than the best proven competitive ratio lower bound of any
deterministic algorithm.

We remind the readers that in our problem the job processing is non-
preemptive. In the literature, researchers have also considered preemptive job
processing [6, 7, 2, 3], where any testing or execution operation can be
interrupted and resumed later, or the more restricted test-preemptive variant
[3], where the testing and execution operations of a tested job are non-
preemptive but the execution operation does not have to follow immediately the
testing operation or on the same machine. Also, our goal is to minimize the
makespan $C_{\max}$, that is, the min-max objective; while another important
goal to minimize the total job completion time, or the min-sum objective, has
received much research too [6, 7].

###  1.1 Previous work on fully online case

There are not too many existing, deterministic or randomized, approximation
algorithms for the fully online problem $P\mid online,t_{j},0\leq p_{j}\leq
u_{j}\mid C_{\max}$. We first distinguish a special case where all the testing
operations have a unit time, i.e., $t_{j}=1$ for every job $J_{j}$, called the
uniform testing case [6, 7, 3], denoted as $P\mid online,t_{j}=1,0\leq
p_{j}\leq u_{j}\mid C_{\max}$. Note that in the general testing case, the
testing times can be any non-negative values.

When there is only a single machine, the job processing order on the machine
is irrelevant to the makespan. This hints that the fully online and the semi-
online problems are the same. The first set of results is on the semi-online
uniform testing problem $P1\mid t_{j}=1,0\leq p_{j}\leq u_{j}\mid C_{\max}$,
due to Dürr et al. [6, 7]. They proposed to test the job $J_{j}$ if
$u_{j}\geq\varphi=\frac{\sqrt{5}+1}{2}$, or to test it with probability
$f(u_{j})=\max\left\\{0,\frac{u_{j}(u_{j}-1)}{u_{j}(u_{j}-1)+1}\right\\}$,
leading to a deterministic $\varphi$-competitive algorithm and a randomized
expected $\frac{4}{3}$-competitive algorithm, respectively. Let
$r_{j}=\frac{u_{j}}{t_{j}}$; Albers and Eckl [2] extended the above two
algorithms for the general testing case $P1\mid t_{j},0\leq p_{j}\leq
u_{j}\mid C_{\max}$, to test the job $J_{j}$ if $r_{j}\geq\varphi$ or to test
it with probability $f(r_{j})$, and achieved the same competitive ratio and
expected competitive ratio, respectively. The authors [6, 7, 2] showed that
both algorithms are the best possible, that is, $\varphi$ is a lower bound on
the competitive ratio for any deterministic algorithm and $\frac{4}{3}$ is a
lower bound on the expected competitive ratio for any randomized algorithm by
Yao’s principle [17], respectively.

When there are at least two machines, fully online is more general than semi-
online. Albers and Eckl [3] proposed to test the job $J_{j}$ if
$r_{j}\geq\varphi$ in the list scheduling rule [13] that assigns each job to
the least loaded machine for processing (possible testing and then executing).
They showed that such an algorithm is $\varphi(2-\frac{1}{m})$-competitive and
the analysis is tight, where $m$ is the number of machines. They also showed a
lower bound of $2$ on the competitive ratio for any deterministic algorithm
even in the uniform testing case $P\mid online,t_{j}=1,0\leq p_{j}\leq
u_{j}\mid C_{\max}$ [3], and a slightly better lower bound of $2.0953$ for the
two-machine general testing case $P2\mid online,t_{j},0\leq p_{j}\leq
u_{j}\mid C_{\max}$, i.e., when there are only two machines [3].

###  1.2 Previous work on semi-online case

See the above reviewed results when there is only a single machine.

When there are at least two machines, recall that in the semi-online problems,
all jobs arrive at time zero, and therefore the scheduler can take advantage
of all the known $u_{j}$ and $t_{j}$ values at time zero for not only job
testing decision making but also to form certain job processing orders to
better reduce the makespan. Indeed this is the case in the pioneering so-
called SBS algorithm by Albers and Eckl [3] for the general testing case,
which is $3.1016$-competitive (when $m$ tends to infinity). For the uniform
testing case, Albers and Eckl [3] also proposed a $3$-competitive algorithm,
along with a lower bound of $\max\\{\varphi,2-\frac{1}{m}\\}$ on the
competitive ratio for any deterministic algorithm.

The above two competitive ratios for the general and the uniform testing cases
had been improved to $2.9513$ and $2.8081$ by Gong and Lin [12], respectively,
and the state-of-the-art ratios are $2.8019$ and $2.5276$ by Gong et al. [11],
respectively.

For proving the lower bound of $2-\frac{1}{m}$ on the competitive ratio,
Albers and Eckl [3] presented an instance of $P\mid t_{j}=1,0\leq p_{j}\leq
u_{j}\mid C_{\max}$ that forces any deterministic algorithm to test all the
jobs. This implies that the lower bound is not only on the competitive ratio
for any deterministic algorithm, but also on the expected competitive ratio
for any randomized algorithm by Yao’s principle [17]. Furthermore, the lower
bound of $2-\frac{1}{m}$ is then on the expected competitive ratio for any
randomized algorithm for the fully online uniform testing problem $P\mid
online,t_{j}=1,0\leq p_{j}\leq u_{j}\mid C_{\max}$.

All the above reviewed competitive ratios and lower bounds are plotted in
Figure 1. We point out that for both the fully online and the semi-online
problems at the presence of at least two machines, there is no existing
randomized algorithm, except deterministic algorithms trivially treated as
randomized.

general testing:uniform testing:randomized axisdeterministic
axis$\dots$$1$$2.8019-\frac{1}{m}$[11]$2.9513-\frac{4}{3m}$[12]$3.1016(1-\frac{1}{3m})$[3]$\triangleleft$$2\varphi$[3]$\triangleleft$$3.1490$(this
paper)$\triangleleft$$2.1839$(this
paper)$2.5276(1-\frac{1}{4m})$[11]$2.8081-\frac{2}{3m}$[12]$3(1-\frac{1}{3m})$[3]$\frac{4}{3}$[2]$\varphi$[2]$\varphi$[6,
7]$\frac{4}{3}$[6,
7]$\max\\{\varphi,2-\frac{1}{m}\\}$[3]$\triangleright$$2-\frac{1}{m}$[3]$\blacktriangleright$2
[3]$\triangleright$2.0953 [3]$\triangleright$$2.2117$(this
paper)$\triangleright$$1.6682$(this paper)$\triangleright$$1.6522$(this paper)
Figure 1: Competitive ratios of the existing deterministic and randomized
algorithms for the fully online and semi-online multiprocessor scheduling with
testing problems. On the $x$-axes, the red-colored symbols indicate lower
bounds; the triangles ($\triangleleft$’s and $\triangleright$’s for general
testing and $\blacktriangleright$ for uniform testing) refer to the results
for the fully online problems, while the circles ($\circ$’s for general
testing and $\bullet$’s for uniform testing) refer to those for the semi-
online problems. Between the two $x$-axes, the lower one is for deterministic
algorithms, while the upper is for randomized ones; the results above the axes
are for the general testing case, while those below are for the uniform
testing case.

###  1.3 Other related work

We will not review the existing deterministic algorithms for the min-sum
objective, but would like to point out that Dürr et al. [6, 7] presented an
expected $1.7453$-competitive randomized algorithm for the single machine
uniform testing problem $P1\mid t_{j}=1,0\leq p_{j}\leq
u_{j}\mid\sum_{j}C_{j}$, which tests the to-be-tested jobs in a uniform random
order. They also proved a lower bound of $1.6257$ on the expected competitive
ratio. Albers and Eckl [2] designed a randomized algorithm for the general
testing case $P1\mid t_{j},0\leq p_{j}\leq u_{j}\mid\sum_{j}C_{j}$, in which
the job $J_{j}$ is tested with a rather complex probability function in the
ratio $r_{j}$; the algorithm is expected $3.3794$-competitive.

We next review the state-of-the-art randomized algorithms for the classic
online multiprocessor scheduling problem $P\mid online\mid C_{\max}$, in which
the jobs arrive in sequence, the processing time $p_{j}$ is revealed when the
job $J_{j}$ arrives, and upon arrival the job must be assigned to a machine
irrevocably for execution in order to minimize the makespan. It is well-known
that for this problem, the improvement from the competitive ratio $2$, by the
first deterministic algorithm list-scheduling [13], to the current best
$1.9201$ [8] took a long time.

For every online approximation algorithm, one of the most challenging parts in
performance analysis is to precisely estimate the optimal offline makespan.
The three most typical lower bounds are $\frac{1}{m}\sum_{j=1}^{n}p_{j}$ (the
average machine load), $\max_{j=1}^{n}p_{j}$ (the largest job processing
time), and $p_{[m]}+p_{[m+1]}$ where $p_{[j]}$ is the $j$-th largest
processing time among all the jobs. Albers [1] proved that if only the above
three lower bounds are used, then the competitive ratio of any deterministic
algorithm cannot be smaller than $1.919$ when $m$ tends to infinity.

On the positive side, Albers [1] presented an expected $1.916$-competitive
randomized algorithm, and in the performance analysis only the above three
lower bounds on the optimal offline makespan are used. In more details, Albers
proposed two deterministic algorithms $A_{0}$ and $A_{1}$, and proposed to
execute each with probability $0.5$. The author showed that if the expected
makespan is too large compared to the three lower bounds, that is, both
$A_{0}$ and $A_{1}$ produce large makespans, then there are many large jobs
present in the instance so that the optimal offline makespan cannot be too
small.

Such a randomized algorithm that is a distribution of a constant number of
deterministic algorithms is referred to as a barely randomized algorithm [14],
which takes advantage of its good component algorithms, in that it performs
well if at least one component algorithm performs well, and if no component
algorithm performs well then the optimal offline makespan is also far away
from the lower bounds. This design idea has been used in approximating many
other optimization problems and achieved breakthrough results, for example,
other scheduling problems [16, 9] and the $k$-server problem [4]. In fact, for
the online multiprocessor scheduling problem $P\mid online\mid C_{\max}$,
prior to [1], Seiden [16] modified the non-barely randomized algorithms of
Bartal et al. [5] and Seiden [15], both of which assign the current job to one
of the two least loaded machines with certain probability, to be barely
randomized algorithms that are a uniform distribution of $k$ deterministic
algorithms, where $k$ is the number of schedules to be created inside the
algorithm and was chosen big enough to guarantee the expected competitive
ratios. While succeeding for small $m$ (specifically, for $m\leq 7$), Albers
[1] observed that the analysis of the algorithms in [5, 15, 16] does not work
for general large $m$, and subsequently proposed the new barely randomized
algorithm based on only two deterministic algorithms.

###  1.4 Our results

For the fully online and semi-online multiprocessor scheduling with testing to
minimize the makespan, we have seen that the only existing randomized
algorithms are the optimal expected $\frac{4}{3}$-competitive algorithms for
the case of a single machine [6, 7, 2]. Their expected competitive ratios are
strictly smaller than the lower bound of $\varphi$ on the competitive ratio
for any deterministic algorithm. For the classic online multiprocessor
scheduling, only when $2\leq m\leq 5$, the expected competitive ratios of the
algorithms by Bartal et al. [5] and Seiden [15] are strictly smaller than the
corresponding lower bounds on the competitive ratio for any deterministic
algorithm; the expected competitive ratio $1.916$ of the algorithm by Albers
[1] is also strictly smaller than the deterministic lower bound $1.919$, but
conditional on using only the three offline makespan lower bounds.

In this paper, we always assume the presence of at least two machines in the
fully online problem $P\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$.
We propose a barely randomized algorithm that is an integration of an
arbitrary number of component deterministic algorithms, each is run with
certain probability, and show that the expected competitive ratio is at most
$\left(\sqrt{(1-\frac{1}{m})^{2}\varphi^{2}+2(1-\frac{1}{m})}+1\right)$, where
$m$ is the number of machines. This expected competitive ratio is strictly
increasing in $m$, is strictly smaller than the competitive ratio
$\varphi(2-\frac{1}{m})$ of the best known deterministic algorithm by Albers
and Eckl [3], and approaches $(\sqrt{\varphi+3}+1)\approx 3.1490$ when $m$
tends to infinity. To the best of our knowledge, barely randomized algorithms
in the literature are mostly uniform distributions of its component
deterministic algorithms, while ours is the first non-uniform distribution of
its arbitrary many component algorithms.

When there are only two machines, that is, for $P2\mid online,t_{j},0\leq
p_{j}\leq u_{j}\mid C_{\max}$, we show that employing two component
deterministic algorithms in the randomized algorithm leads to an expected
competitive ratio of $\frac{3\varphi+3\sqrt{13-7\varphi}}{4}\approx 2.1839$.
For this two-machine case, Albers and Eckl [3] proved a lower bound of
$2.0953$ on the competitive ratio for any deterministic algorithm. We improve
it to $2.2117$, thus showing that our randomized algorithm beats any
deterministic algorithm in terms of the expected competitive ratio. Such
algorithmic results are rarely seen in the literature, except those we
reviewed in the above.

It is worth noting that our randomized algorithm performs well for both large
and small numbers of machines, and better than the current best deterministic
algorithms for all $m$’s in terms of the expected competitive ratios; while
most randomized multiprocessor scheduling algorithms in the literature work
only for either a fixed and typically small number of machines or for
sufficiently large numbers of machines. For example, the above mentioned
Albers’ randomized algorithm for the classic online multiprocessor scheduling
requires large numbers of machines, and the algorithms by Bartal et al. [5]
and Seiden [15] perform well only when there are no more than seven machines.

On the inapproximability, we prove a lower bound of $1.6682$ on the expected
competitive ratio of any randomized algorithm for $P\mid online,t_{j},0\leq
p_{j}\leq u_{j}\mid C_{\max}$ at the presence of at least three machines, and
a lower bound of $1.6522$ on the expected competitive ratio for $P2\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$, both using a slightly
revised Yao’s principle [17]. These two lower bounds are strictly better than
the lower bound of $2-\frac{1}{m}$ by Albers and Eckl [3] at the presence of
three and two machines, respectively. All our results are plotted in Figure 1
as well, highlighted with “this paper”.

The rest of the paper is organized as follows. In Section 2, we introduce some
basic notations and definitions. Next, in Section 3, we present the randomized
algorithm for the fully online problem $P\mid t_{j},0\leq p_{j}\leq u_{j}\mid
C_{\max}$ and its performance analysis, as well as the slightly modified
randomized algorithm for the two-machine case and its performance analysis. We
prove in Section 4 the expected competitive ratio lower bounds of $1.6682$ and
$1.6522$ for the problem at the presence of at least three machines and only
two machines, respectively, and the lower bound of $2.2117$ on the competitive
ratio for any deterministic algorithm for $P2\mid online,t_{j},0\leq p_{j}\leq
u_{j}\mid C_{\max}$. Lastly, we conclude the paper in Section 5.

##  2 Preliminaries

We study the fully online multiprocessor scheduling with testing to minimize
the makespan, denoted as $P\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid
C_{\max}$, in which the jobs arrive in sequence. Our goal is to design
randomized algorithms with expected competitive ratios that are better than
the competitive ratios of the state-of-the-art deterministic algorithms, or
even further better than the best proven deterministic competitive ratio lower
bounds. The special case where the jobs all arrive at time zero is called
semi-online and denoted as $P\mid t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$.
When applicable, we will prove lower bounds for the semi-online variant.

An instance $I$ of multiprocessor scheduling with testing consists of a job
set $\mathcal{J}=\\{J_{1},J_{2},\ldots,J_{n}\\}$, each to be executed on one
of a set of $m$ parallel identical machines
$\mathcal{M}=\\{M_{1},M_{2},\ldots,M_{m}\\}$, where $n$ and $m\geq 2$ are part
of the input. Each job $J_{j}$ arrives with a known upper bound $u_{j}$ on its
processing time $p_{j}$ and a testing operation of length $t_{j}$. The $p_{j}$
remains unknown until the testing operation is executed. That is, the
scheduler can choose not to test the job $J_{j}$ but execute it for $u_{j}$
time, or to test it for $t_{j}$ time followed by immediately execute it on the
same machine for $p_{j}$ time.

A deterministic algorithm $A$ makes a binary decision on whether or not to
test a job. Let $p_{j}^{A}$ and $\rho_{j}$ denote the total time spent on the
job $J_{j}$ in the algorithm $A$ and in the optimal offline schedule,
respectively. One sees that $p_{j}^{A}=t_{j}+p_{j}$ if the job is tested or
otherwise $p_{j}^{A}=u_{j}$, and $\rho_{j}=\min\\{u_{j},t_{j}+p_{j}\\}$. Let
$C_{j}$ denote the completion time of $J_{j}$ in the schedule generated by the
algorithm $A$. The objective of the problem is to minimize the makespan
$C_{\max}=\max_{j}C_{j}$. We use $C^{A}(I)$ (or $C^{A}$ when the instance $I$
is clear from the context) and $C^{*}(I)$ (or $C^{*}$, correspondingly) to
denote the makespan by the algorithm $A$ and of the optimal offline schedule
for the instance $I$, respectively. Switching to a more general randomized
algorithm $A$, its expected makespan on the instance $I$ is denoted by
$E[C^{A}(I)]$.

###### Definition 1

(Competitive ratio) For a deterministic algorithm $A$, the competitive ratio
is the worst-case ratio between the makespan of the schedule produced by the
algorithm $A$ and of the optimal offline schedule, that is,
$\sup_{I}\\{C^{A}(I)/C^{*}(I)\\}$ where $I$ runs over all instances of the
problem.

For a more general randomized algorithm $A$, its expected competitive ratio is
$\sup_{I}\\{E[C^{A}(I)]/C^{*}(I)\\}$.

Given that the processing time $p_{j}$ for the job $J_{j}$ could go to two
extremes of $0$ and $u_{j}$, a deterministic algorithm often sets up a
threshold function on the ratio $r_{j}=\frac{u_{j}}{t_{j}}$ for binary testing
decision making. Intuitively, a randomized algorithm should tests the job
$J_{j}$ with probability $f(r_{j})$, and such a probability function should be
increasing in the ratio $r_{j}$ and $f(r_{j})=0$ for all $r_{j}\leq 1$.
Indeed, Dürr et al. [6, 7] and Albers and Eckl [2] used the following
probability function

$f(r)=\left\\{\begin{array}[]{ll}0,&\mbox{ if }r\leq 1,\\\
\frac{r(r-1)}{r(r-1)+1},&\mbox{ if }r>1\end{array}\right.$ (1)

in their optimal expected $\frac{4}{3}$-competitive randomized algorithms for
the single machine problems $P1\mid online,t_{j}=1,0\leq p_{j}\leq u_{j}\mid
C_{\max}$ and $P1\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$,
respectively. Their success unfortunately cannot be easily extended to
multiple machines, since one key fact used in their performance analysis is
that, for a single machine, the expected makespan equals to the sum of the
expected processing times of all the jobs. We show below that, for multiple
machines, if a randomized algorithm tests jobs using the probability function
in Eq. (1), then its expected competitive ratio is unbounded when the number
of machines tends to infinity.

###### Lemma 1

For $P\mid online,t_{j}=1,0\leq p_{j}\leq u_{j}\mid C_{\max}$, if a randomized
algorithm tests jobs using the probability function in Eq. (1), then its
expected competitive ratio is unbounded when the number of machines tends to
infinity.

Proof.  Consider an instance consisting of $m=k(k-1)+1$ machines and
$n=k(k-1)+1$ jobs, where $k$ is a positive integer. For each job $J_{j}$,
$u_{j}=k$, $t_{j}=1$ and $p_{j}=0$.

Since $\rho_{j}=\min\\{u_{j},t_{j}+p_{j}\\}=1$ for each job $J_{j}$, in the
optimal offline schedule, $J_{j}$ is tested and scheduled on the machine
$M_{j}$, leading to a makespan of $1$.

The randomized algorithm tests each job with the same probability
$\frac{k(k-1)}{k(k-1)+1}$. So the probability that at least one job is
untested in the algorithm is

$1-\left(\frac{k(k-1)}{k(k-1)+1}\right)^{k(k-1)+1}=1-\left(1-\frac{1}{k(k-1)+1}\right)^{k(k-1)+1}.$

Since the processing time of an untested job is $k$, the makespan is at least
$k$. It follows that the expected competitive ratio of the randomized
algorithm on this instance is at least

$k-k\left(1-\frac{1}{k(k-1)+1}\right)^{k(k-1)+1}.$

When $m=k(k-1)+1$ tends to infinity, the above becomes $(1-\frac{1}{e})k$ and
approaches infinity too. $\Box$

The proof of Lemma 1 suggests to some extent that, when the ratio $r_{j}$ of
$J_{j}$ is large enough, one should test the job instead of leaving even only
a tiny fraction of probability for untesting. Indeed, later we will see that
in our proposed randomized algorithm, there is a threshold on $r_{j}$’s for
absolutely testing jobs.

On the other hand, at the presence of at least two machines, we are no longer
sure which jobs are assigned to each machine due to random job testing
decisions if using a job testing probability function as in Eq. (1).
Therefore, we discard the randomized algorithm design idea in [6, 7, 2], but
extend the idea of Albers [1] to design multiple component deterministic
algorithms $A_{0},A_{1},\ldots,A_{\ell}$ that complement each other, where
$\ell$ can be made arbitrarily large, and then to run each $A_{i}$ with
certain probability $\alpha_{i}$. Let $p_{j}^{A_{i}}$ denote the total time
spent on the job $J_{j}$ in $A_{i}$, for any $i=0,1,\ldots,\ell$. The expected
processing time of $J_{j}$ in the randomized algorithm $A$ is

$E[p_{j}^{A}]=\sum_{i=0}^{\ell}\alpha_{i}p_{j}^{A_{i}}.$ (2)

Similarly, let $C^{A_{i}}$ be the makespan of the schedule produced by
$A_{i}$, for any $i=0,1,\ldots,\ell$. The expected makespan is

$E[C^{A}]=\sum_{i=0}^{\ell}\alpha_{i}C^{A_{i}}.$ (3)

The following three lemmas hold for any component deterministic algorithms
$A_{0},A_{1},\ldots,A_{\ell}$ run with the probability distribution
$(\alpha_{0},\alpha_{1},\ldots,\alpha_{\ell})$, while assuming without loss of
generality none of them tests any job $J_{j}$ with $r_{j}\leq 1$.

###### Lemma 2

For any $i=0,1,\ldots,\ell$, if $J_{j}$ with $r_{j}>1$ is tested in $A_{i}$,
then $p_{j}^{A_{i}}\leq(1+\frac{1}{r_{j}})\rho_{j}$.

Proof.  Note that $p_{j}^{A_{i}}=t_{j}+p_{j}$. If $\rho_{j}=t_{j}+p_{j}$, then
$p_{j}^{A_{i}}=\rho_{j}$ and the lemma is proved. Otherwise, $\rho_{j}=u_{j}$;
then from $p_{j}\leq u_{j}$ and $u_{j}=r_{j}t_{j}$, we have
$p_{j}^{A_{i}}=t_{j}+p_{j}\leq(\frac{1}{r_{j}}+1)u_{j}=(\frac{1}{r_{j}}+1)\rho_{j}$
and the lemma is also proved. $\Box$

###### Lemma 3

For any $i=0,1,\ldots,\ell$, if $J_{j}$ with $r_{j}>1$ is untested in $A_{i}$,
then $p_{j}^{A_{i}}\leq r_{j}\rho_{j}$.

Proof.  Note that $p_{j}^{A_{i}}=u_{j}$. If $\rho_{j}=u_{j}$, then
$p_{j}^{A_{i}}=\rho_{j}<r_{j}\rho_{j}$ and the lemma is proved. Otherwise,
$\rho_{j}=t_{j}+p_{j}$; then from $p_{j}\geq 0$ and $u_{j}=r_{j}t_{j}$, we
have $p_{j}^{A_{i}}=r_{j}t_{j}\leq r_{j}(t_{j}+p_{j})=r_{j}\rho_{j}$ and the
lemma is also proved. $\Box$

###### Lemma 4

If $J_{j}$ with $r_{j}>1$ is tested in a subset ${\cal T}$ of the algorithms
but untested in any of $\\{A_{0},A_{1},\ldots,A_{\ell}\\}\setminus{\cal T}$,
then

$E[p_{j}^{A}]\leq\max\left\\{\theta+(1-\theta)r_{j},1+\frac{\theta}{r_{j}}\right\\}\rho_{j},\mbox{
where }\theta=\sum_{A_{i}\in{\cal T}}\alpha_{i}.$

Proof.  By Eq. (2), $E[p_{j}^{A}]=\theta(t_{j}+p_{j})+(1-\theta)u_{j}$.

If $\rho_{j}=t_{j}+p_{j}$, then $p_{j}^{A_{i}}=\rho_{j}$ for any
$A_{i}\in{\cal T}$, and by Lemma 3 $p_{j}^{A_{i}}\leq r_{j}\rho_{j}$ for any
$A_{i}\notin{\cal T}$; therefore,
$E[p_{j}^{A}]\leq(\theta+(1-\theta)r_{j})\rho_{j}$. Otherwise,
$\rho_{j}=u_{j}$; then $p_{j}^{A_{i}}=\rho_{j}$ for any $A_{i}\notin{\cal T}$,
and by Lemma 2 $p_{j}^{A_{i}}\leq(1+\frac{1}{r_{j}})\rho_{j}$ for any
$A_{i}\in{\cal T}$, and therefore
$E[p_{j}^{A}]\leq\theta(1+\frac{1}{r_{j}})\rho_{j}+(1-\theta)\rho_{j}=(1+\frac{\theta}{r_{j}})\rho_{j}$.
This proves the lemma. $\Box$

###### Lemma 5

[1] The following two lower bounds on the optimal offline makespan $C^{*}$
hold:

$C^{*}\geq\max\left\\{\frac{1}{m}\sum_{j=1}^{n}\rho_{j},\max_{j=1}^{n}\rho_{j}\right\\}.$
(4)

In the fully online problem $P\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid
C_{\max}$, the jobs arrive in sequence and it is assumed to be $\langle
J_{1},J_{2},\dots,J_{n}\rangle$. In the semi-online problem $P\mid t_{j},0\leq
p_{j}\leq u_{j}\mid C_{\max}$, all the jobs arrive at time zero and an
algorithm can take advantage of all the known $u_{j}$’s and $t_{j}$’s to
process them in any order.

##  3 Randomized algorithms

In this section, we first present a randomized algorithm for the fully online
multiprocessor scheduling with testing problem $P\mid online,t_{j},0\leq
p_{j}\leq u_{j}\mid C_{\max}$ at the presence of at least two machines, and
show that its expected competitive ratio is $(\sqrt{\varphi+3}+1)\approx
3.1490$. When there are only two machines, we revise slightly the parameters
in the algorithm leading to an improved expected competitive ratio of
$\frac{3\varphi+3\sqrt{13-7\varphi}}{4}\approx 2.1839$.

For the fully online multiprocessor scheduling with testing problem $P\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$, Albers and Eckl [3] proposed
to test the job $J_{j}$ if $r_{j}\geq\varphi$ in the list scheduling rule [13]
that assigns each job to the least loaded machine for processing (possible
testing and then executing). They showed that such a deterministic algorithm
is tight $\varphi(2-\frac{1}{m})$-competitive, where $m$ is the number of
machines. We employ it as our first component algorithm $A_{0}$, and it is run
with probability $\alpha_{0}=\alpha(m,\ell)$ as in Eq. (5), where $\ell\geq 1$
is a fixed constant chosen by our randomized algorithm.

$\alpha_{0}=\alpha(m,\ell)=\sqrt{\frac{(1-\frac{1}{m})(\ell+1)\varphi^{2}}{(1-\frac{1}{m})(\ell+1)\varphi^{2}+2\ell}},\
\mbox{ and }\alpha_{i}=\beta(m,\ell)=\frac{1-\alpha(m,\ell)}{\ell},\mbox{ for
}i=1,2,\ldots,\ell.$ (5)

Below we simplify $\alpha(m,\ell)$ and $\beta(m,\ell)$ as $\alpha$ and
$\beta$, respectively.

One sees that when $r_{j}\leq 1$, the job $J_{j}$ should not be tested, as
this is the case in $A_{0}$. On the other hand, when $r_{j}$ is large, testing
does not waste too much time even if $p_{j}$ is very close to $u_{j}$, as this
is also the case in $A_{0}$. The “risk” of making wrong testing decision
happens when $r_{j}$ is close to $\varphi$, in that $p_{j}$ could be very
close to $0$ if $J_{j}$ is untested while be very close to $u_{j}$ if tested.
Nevertheless, we have also seen from the proof of Lemma 1 that even a tiny
fraction of probability for untesting jobs with large ratio $r_{j}$ could lead
to an unbounded expected competitive ratio, when the number $m$ of machines
tends to infinity. Therefore, in each of the other component algorithms
$A_{i}$, $i=1,2,\ldots,\ell$, we set up a threshold $y_{i}(m,\ell)>\varphi$ as
in Eq. (6) such that a job $J_{j}$ with $r_{j}\geq y_{i}(m,\ell)$ is tested in
$A_{i}$; we then set up another threshold
$x_{i}(m,\ell)=1+\frac{1}{y_{i}(m,\ell)}$ such that a job $J_{j}$ with
$r_{j}\leq x_{i}(m,\ell)$ is untested in $A_{i}$.

$y_{i}(m,\ell)=\frac{\varphi(\alpha+i\beta)}{\alpha},\
x_{i}(m,\ell)=1+\frac{1}{y_{i}(m,\ell)},\mbox{ for }i=0,1,\ldots,\ell.$ (6)

Similarly, below we simplify $y_{i}(m,\ell)$ and $x_{i}(m,\ell)$ as $y_{i}$
and $x_{i}$, respectively. When $r_{j}\in(x_{i},y_{i})$, we invert the testing
decision as in $A_{0}$ to test $J_{j}$ if $r_{j}\leq\varphi$ or untest $J_{j}$
if $r_{j}>\varphi$ in $A_{i}$. Our randomized algorithm, denoted as GCL,
chooses to run $A_{i}$ with probability $\alpha_{i}$, for $i=0,1,\ldots,\ell$.

From Eqs. (5, 6), one sees that $\alpha,\beta>0$, and

$1<x_{\ell}<\ldots<x_{1}<x_{0}=\varphi=y_{0}<y_{1}<\ldots<y_{\ell}=\frac{\varphi}{\alpha}.$
(7)

A high-level description of the algorithm GCL is presented in Figure 2.

Algorithm GCL: Input: $m$ machines, and $n$ jobs arriving in sequence $\langle
J_{1},J_{2},\ldots,J_{n}\rangle$; Output: A schedule in which each job is
tested or not and the machine processing the job. 1. Choose $\ell$ and set up
parameters $\alpha_{i}$, $y_{i}$ and $x_{i}$ as in Eqs. (5, 6), for
$i=0,1,\ldots,\ell$; 2. Component algorithm $A_{i}$, $i=0,1,\ldots,\ell$: For
each job $J_{j}$, 2.1 if $r_{j}\leq x_{i}$ or $\varphi<r_{j}\leq y_{i}$, then
assign $J_{j}$ untested on the least loaded machine for executing; 2.2
otherwise, assign $J_{j}$ on the least loaded machine for testing and
executing; 3. Choose to run $A_{i}$ with probability $\alpha_{i}$, for
$i=0,1,\ldots,\ell$.

Figure 2: A high level description of the algorithm GCL.

The inequalities in the next lemma will be convenient in the performance
analysis for the algorithm GCL.

###### Lemma 6

$\frac{1-\alpha}{x_{\ell}}<\frac{\alpha}{\varphi}$,  and
$(\ell-i)\beta(y_{i+1}-1)<\frac{\alpha}{\varphi}$ for every
$i=0,1,\ldots,\ell-1$.

Proof.  By its definition in Eq. (5), $\alpha$ is strictly increasing in $m$.
Therefore,

$\sqrt{\frac{(\ell+1)\varphi^{2}}{(\ell+1)\varphi^{2}+2\ell}}>\alpha=\alpha(m,\ell)\geq\alpha(2,\ell)=\sqrt{\frac{(\ell+1)\varphi^{2}}{(\ell+1)\varphi^{2}+4\ell}}\geq\sqrt{\frac{\varphi^{2}}{\varphi^{2}+4}}>\varphi-1.$
(8)

Using $y_{\ell}=\frac{\varphi}{\alpha}$ and
$x_{\ell}=1+\frac{\alpha}{\varphi}$, we have
$x_{\ell}>1+\frac{\varphi-1}{\varphi}=3-\varphi$. It follows that
$(\varphi+x_{\ell})\alpha>3(\varphi-1)>\varphi$, and thus

$\frac{\alpha}{\varphi}-\frac{1-\alpha}{x_{\ell}}=\frac{(\varphi+x_{\ell})\alpha-\varphi}{\varphi
x_{\ell}}>0,$

which is the first inequality.

Define $g(i)=(\ell-i)\beta(y_{i+1}-1)$ for $i=0,1,\ldots,\ell-1$, which is a
concave quadratic function in $i$ and its axis of symmetry is
$i=i_{0}=\frac{1}{2}(\ell-1-\frac{\alpha}{(\varphi+1)\beta})$. Note that when
$\ell=1$, Eq. (8) implies
$\sqrt{\frac{\varphi^{2}}{\varphi^{2}+1}}>\alpha\geq\sqrt{\frac{\varphi^{2}}{\varphi^{2}+2}}$;
thus by Eq. (6), we have
$g(0)=\beta(\frac{\varphi}{\alpha}-1)=(1-\alpha)(\frac{\varphi}{\alpha}-1)<\frac{\alpha}{\varphi}$
and the lemma is proved. When $\ell=2$, Eq. (8) implies
$\sqrt{\frac{3\varphi^{2}}{3\varphi^{2}+4}}>\alpha\geq\sqrt{\frac{3\varphi^{2}}{3\varphi^{2}+8}}$;
thus by Eq. (6), we have $g(i)\leq
2\beta(\frac{\varphi}{\alpha}-1)=(1-\alpha)(\frac{\varphi}{\alpha}-1)<\frac{\alpha}{\varphi}$
for $i=0,1$ and the lemma is proved.

Below we assume that $\ell\geq 3$. Note that when $i\leq(2-\varphi)\ell-1$,
Eqs. (5, 6, 8) together imply

$y_{i+1}\leq\frac{\varphi(\alpha+(2-\varphi)\ell\beta)}{\alpha}=\frac{\alpha+\varphi-1}{\alpha}<2$

and thus

$g(i)\leq(\ell-i)\beta\leq
1-\alpha<2-\varphi=\frac{\varphi-1}{\varphi}<\frac{\alpha}{\varphi}.$

Using $\beta=\frac{1}{\ell}(1-\alpha)\leq\frac{1}{3}(1-\alpha)$ and Eq. (8),
one sees that

$(2-\varphi)\ell-1-i_{0}=\frac{\varphi\alpha-(\varphi-1)-(\varphi+1)\beta}{2(\varphi+1)\beta}>\frac{5-3\varphi}{6(\varphi+1)\beta}>0,$

that is, $(2-\varphi)\ell-1$ is to the right of the axis of symmetry.
Therefore, for every $i=0,1,\ldots,\ell-1$, $g(i)<\frac{\alpha}{\varphi}$.
This completes the proof of the lemma. $\Box$

###### Lemma 7

In the algorithm $A_{i}$, $p_{j}^{A_{i}}\leq y_{i}\rho_{j}$ for every job
$J_{j}$, for any $i=0,1,\ldots,\ell$.

Proof.  In the algorithm $A_{0}$, a job $J_{j}$ is untested if and only if
$r_{j}\leq\varphi$. By Lemmas 2 and 3,
$p_{j}^{A_{0}}\leq\max\\{1+\frac{1}{\varphi},\varphi\\}\rho_{j}=y_{0}\rho_{j}$.

Consider the algorithm $A_{i}$, for any $i=1,2,\ldots,\ell$. If $r_{j}\leq
x_{i}$ or $\varphi<r_{j}\leq y_{i}$, then $J_{j}$ is untested in $A_{i}$ and,
by Lemma 3, $p_{j}^{A_{i}}\leq y_{i}\rho_{j}$. Otherwise,
$x_{i}<r_{j}\leq\varphi$ or $r_{j}>y_{i}$, $J_{j}$ is tested and, by Lemma 2,
$p_{j}^{A_{i}}\leq(1+\frac{1}{x_{i}})\rho_{j}$. In conclusion, for each job
$J_{j}$, we have

$p_{j}^{A_{i}}\leq\max\left\\{y_{i},1+\frac{1}{x_{i}}\right\\}\rho_{j}=\max\left\\{y_{i},1+\frac{y_{i}}{y_{i}+1}\right\\}\rho_{j}=y_{i}\rho_{j},$

since $y_{i}\geq\varphi$. This proves the lemma. $\Box$

###### Lemma 8

In the algorithm GCL, $E[p_{j}^{A}]\leq x_{\ell}\rho_{j}$ for every job
$J_{j}$.

Proof.  If $r_{j}>y_{\ell}$, then $J_{j}$ is tested in every algorithm
$A_{i}$, for $i=0,1,\ldots,\ell$. So, by Lemma 4,
$E[p_{j}^{A}]\leq(1+\frac{1}{y_{\ell}})\rho_{j}=x_{\ell}\rho_{j}$. If
$r_{j}\leq x_{\ell}$, then $J_{j}$ is untested in every algorithm $A_{i}$,
$i=0,1,\ldots,\ell$. So, by Lemma 4, $E[p_{j}^{A}]\leq x_{\ell}\rho_{j}$.

If $y_{h}<r_{j}\leq y_{h+1}$, for some $h=0,1,\ldots,\ell-1$, then $J_{j}$ is
tested in $A_{0},A_{1},\ldots,A_{h}$ but untested in
$A_{h+1},A_{h+2},\ldots,A_{\ell}$. Lemma 4 and then Eq. (6) and Lemma 6
together imply that

$\displaystyle E[p_{j}^{A}]$ $\displaystyle\leq$
$\displaystyle\max\left\\{\alpha+h\beta+(\ell-h)\beta
y_{h+1},1+\frac{\alpha+h\beta}{y_{h}}\right\\}\rho_{j}$ $\displaystyle=$
$\displaystyle\max\left\\{1+(\ell-h)\beta(y_{h+1}-1),1+\frac{\alpha}{\varphi}\right\\}\rho_{j}$
$\displaystyle\leq$
$\displaystyle(1+\frac{\alpha}{\varphi})\rho_{j}=x_{\ell}\rho_{j}.$

Lastly, if $x_{h+1}<r_{j}\leq x_{h}$, for some $h=0,1,\ldots,\ell-1$, then
$J_{j}$ is untested in $A_{0},A_{1},\ldots,A_{h}$ but tested in
$A_{h+1},A_{h+2},\ldots,A_{\ell}$. Lemma 4 and then Eq. (6), Lemma 6 and Eq.
(8) together imply that

$\displaystyle E[p_{j}^{A}]$ $\displaystyle\leq$
$\displaystyle\max\left\\{(\ell-h)\beta+(1-(\ell-h)\beta)x_{h},1+\frac{(\ell-h)\beta}{x_{h+1}}\right\\}\rho_{j}$
$\displaystyle=$
$\displaystyle\max\left\\{1+\frac{\alpha}{\varphi},1+\frac{(\ell-h)\beta}{x_{h+1}}\right\\}\rho_{j}$
$\displaystyle\leq$
$\displaystyle\max\left\\{1+\frac{\alpha}{\varphi},1+\frac{1-\alpha}{x_{\ell}}\right\\}\rho_{j}$
$\displaystyle\leq$
$\displaystyle(1+\frac{\alpha}{\varphi})\rho_{j}=x_{\ell}\rho_{j}.$

This proves the lemma. $\Box$

###### Theorem 1

The expected competitive ratio of GCL for the problem $P\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$ is at most
$\sqrt{(1-\frac{1}{m})^{2}(1+\frac{1}{\ell})^{2}\varphi^{2}+2(1-\frac{1}{m})(1+\frac{1}{\ell})}+1-(1-\frac{1}{m})\frac{\varphi}{\ell}$
by setting $\alpha(m,\ell),\beta(m,\ell)$ as in Eq. (5) and
$y_{i}(m,\ell),x_{i}(m,\ell)$ for every $i=0,1,\ldots,\ell$ as in Eq. (6),
where $m\geq 2$ is the number of machines and $\ell\geq 1$ is a fixed
constant.

Proof.  Suppose the job $J_{n_{i}}$ determines the makespan of the schedule
produced by the component algorithm $A_{i}$, for each $i=0,1,\ldots,\ell$,
respectively. Note that $J_{n_{i}}$ is assigned to the least loaded machine by
the algorithm $A_{i}$. Therefore, the makespan

$C^{A_{i}}\leq\frac{1}{m}\sum_{j=1}^{n_{i}-1}p_{j}^{A_{i}}+p_{n_{i}}^{A_{i}}=\frac{1}{m}\sum_{j=1}^{n_{i}}p_{j}^{A_{i}}+(1-\frac{1}{m})p_{n_{i}}^{A_{i}}\leq\frac{1}{m}\sum_{j=1}^{n}p_{j}^{A_{i}}+(1-\frac{1}{m})p_{n_{i}}^{A_{i}}.$

Using Eqs. (3), (7), Lemmas 7, 8 and the lower bounds in Lemma 5, the expected
makespan is at most

$\displaystyle E[C^{A}]$ $\displaystyle=$ $\displaystyle\alpha
C^{A_{0}}+\sum_{i=1}^{\ell}\beta C^{A_{i}}$ $\displaystyle\leq$
$\displaystyle\frac{1}{m}\sum_{j=1}^{n}E[p_{j}^{A}]+\alpha(1-\frac{1}{m})p^{A_{0}}_{n_{0}}+\sum_{i=1}^{\ell}\beta(1-\frac{1}{m})p^{A_{i}}_{n_{i}}$
$\displaystyle\leq$
$\displaystyle\frac{x_{\ell}}{m}\sum_{j=1}^{n}\rho_{j}+\alpha(1-\frac{1}{m})\varphi\rho_{n_{0}}+\sum_{i=1}^{\ell}\beta(1-\frac{1}{m})y_{i}\rho_{n_{i}}$
$\displaystyle\leq$
$\displaystyle\left(x_{\ell}+(1-\frac{1}{m})\left(\alpha\varphi+\beta\sum_{i=1}^{\ell}y_{i}\right)\right)C^{*}$
$\displaystyle=$
$\displaystyle\left(1+\frac{\alpha}{\varphi}+(1-\frac{1}{m})\left(\alpha\varphi+\ell\beta\varphi+\frac{\ell(\ell+1)\beta^{2}\varphi}{2\alpha}\right)\right)C^{*}$
$\displaystyle=$
$\displaystyle\left(\sqrt{(1-\frac{1}{m})^{2}(1+\frac{1}{\ell})^{2}\varphi^{2}+2(1-\frac{1}{m})(1+\frac{1}{\ell})}+1-(1-\frac{1}{m})\frac{\varphi}{\ell}\right)C^{*},$

and thus the theorem is proved. $\Box$

By choosing a sufficiently large $\ell$, the expected competitive ratio of the
algorithm GCL approaches
$\sqrt{(1-\frac{1}{m})^{2}\varphi^{2}+2(1-\frac{1}{m})}+1$, which is
increasing in $m$ and approaches $\sqrt{\varphi+3}+1\approx 3.1490$ when $m$
tends to infinity. Correspondingly, one can check that $\alpha$, $y_{\ell}$
and $x_{\ell}$ approach $\sqrt{\frac{\varphi+1}{\varphi+3}}\approx 0.7529$,
$\sqrt{\varphi+3}\approx 2.1490$ and $1+\frac{1}{\sqrt{\varphi+3}}\approx
1.4653$, respectively.

In the algorithm GCL, we can determine the testing probability $f(r)$ of a job
as a function in its ratio $r$. For example, $f(r)=1$ if $r\geq y_{\ell}$ and
$f(r)=0$ if $r\leq x_{\ell}$. With a fixed constant $\ell$, one sees that such
a probability function $f(r)$ is staircase and increasing. The limit of this
probability function when $\ell$ tends to infinity, still denoted as $f(r)$,
is interesting. First, note that $\alpha(m,\ell)$ approaches
$\alpha(m)=\sqrt{\frac{(1-\frac{1}{m})\varphi^{2}}{(1-\frac{1}{m})\varphi^{2}+2}}$,
$y_{\ell}(m,\ell)$ and $x_{\ell}(m,\ell)$ approach
$y(m)=\frac{\varphi}{\alpha(m)}$ and $x(m)=1+\frac{1}{y(m)}$, respectively.
Then, by Eq.(6), we have

$f(r)=\left\\{\begin{array}[]{ll}0,&\mbox{ when }r\leq x(m),\\\
1-\frac{\alpha(m)}{\varphi(r-1)},&\mbox{ when }x(m)<r\leq\varphi,\\\
\frac{\alpha(m)r}{\varphi},&\mbox{ when }\varphi<r\leq y(m),\\\ 1,&\mbox{ when
}r>y(m),\end{array}\right.$

which is increasing, and continuous everywhere except at $\varphi$.

We remark that our GCL algorithm for $P\mid online,t_{j},0\leq p_{j}\leq
u_{j}\mid C_{\max}$ has its expected competitive ratio beating the best known
deterministic competitive ratio of $\varphi(2-\frac{1}{m})$.

When there are only two machines, i.e., $m=2$, by choosing a sufficiently
large $\ell$, the algorithm GCL is already expected
$\frac{1}{2}\sqrt{\varphi+5}+1\approx 2.2863$-competitive for the problem
$P2\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$. Note that inside the
algorithm, the probability of choosing the algorithm $A_{0}$ approaches
$\alpha(2)=\frac{\varphi}{\sqrt{\varphi+5}}\approx 0.6290$. We next show that,
by choosing another probability for running $A_{0}$, the revised GCL algorithm
based on two component algorithms is expected
$\frac{3\varphi+3\sqrt{13-7\varphi}}{4}\approx 2.1839$-competitive.

###### Theorem 2

The expected competitive ratio of the revised GCL algorithm for the problem
$P2\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$ is at most
$\frac{3\varphi+3\sqrt{13-7\varphi}}{4}$ by using two component algorithms and
by setting

$\alpha=\varphi-1\approx
0.6180,x_{1}=\frac{\varphi+\sqrt{13-7\varphi}}{2}\approx 1.4559,\mbox{ and
}y_{1}=\frac{1}{x_{1}-1}\approx 2.1935.$ (9)

Furthermore, the expected competitive ratio is tight.

Proof.  The three parameters in Eq. (9) satisfy the algorithm design:
$1<x_{1}<\varphi<y_{1}$ and $\alpha<1$.

Furthermore, they imply that $1-\alpha+\alpha\varphi=3-\varphi<x_{1}$ and
$1+\frac{\alpha}{\varphi}=2-\frac{1}{\varphi}<x_{1}$. Also noticing that
$x_{1}$ is a root to the quadratic equation $x^{2}-\varphi x+2\varphi-3=0$, we
have $x_{1}^{2}=\varphi x_{1}+3-2\varphi$. It follows that

$y_{1}-1-\frac{1}{x_{1}}=\frac{1+x_{1}-x_{1}^{2}}{x_{1}(x_{1}-1)}=\frac{(\varphi-1)(2-x_{1})}{x_{1}(x_{1}-1)}>0,$
$x_{1}-1-\frac{1-\alpha}{x_{1}}=\frac{x_{1}^{2}-x_{1}-(2-\varphi)}{x_{1}}=\frac{(\varphi-1)(x_{1}-1)}{x_{1}}>0,$

and

$x_{1}-\alpha-(1-\alpha)y_{1}=\frac{x_{1}^{2}-\varphi
x_{1}+2\varphi-3}{x_{1}-1}=0.$

For each job $J_{j}$, if $r_{j}\leq x_{1}$, then it is not tested in any of
$A_{0}$ and $A_{1}$ and thus $p_{j}^{A_{i}}=u_{j}$, for $i=0,1$. When
$r_{j}\leq 1$, $\rho_{j}=u_{j}$ and thus $p_{j}^{A_{i}}=\rho_{j}$; when
$1<r_{j}\leq x_{1}$, by Lemma 3 we have $p_{j}^{A_{i}}\leq x_{1}\rho_{j}$.
That is, if $r_{j}\leq x_{1}$, then we always have

$p_{j}^{A_{i}}\leq x_{1}\rho_{j},\mbox{ for }i=0,1.$ (10)

If $r_{j}>y_{1}$, then $J_{j}$ is tested in both $A_{0}$ and $A_{1}$, and thus
by Lemma 2 and Eq. (9) we have

$p_{j}^{A_{i}}\leq(1+\frac{1}{y_{1}})\rho_{j}=x_{1}\rho_{j},\mbox{ for
}i=0,1.$ (11)

If $x_{1}<r_{j}\leq\varphi$, then $J_{j}$ is untested in $A_{0}$ but tested in
$A_{1}$. By Lemmas 2–4, we have

$p_{j}^{A_{0}}\leq\varphi\rho_{j}\mbox{,
}p_{j}^{A_{1}}\leq(1+\frac{1}{x_{1}})\rho_{j}\mbox{, and
}E[p_{j}^{A}]\leq\max\left\\{1-\alpha+\alpha\varphi,1+\frac{1-\alpha}{x_{1}}\right\\}\rho_{j}.$
(12)

Lastly, if $\varphi<r_{j}\leq y_{1}$, then $J_{j}$ is tested in $A_{0}$ but
untested in $A_{1}$. By Lemmas 2–4, we have

$p_{j}^{A_{0}}\leq\varphi\rho_{j}\mbox{, }p_{j}^{A_{1}}\leq
y_{1}\rho_{j}\mbox{, and
}E[p_{j}^{A}]\leq\max\left\\{\alpha+(1-\alpha)y_{1},1+\frac{\alpha}{\varphi}\right\\}\rho_{j}.$
(13)

The processing time of $J_{j}$ in the two algorithms in all the four cases, in
Eqs. (10–13), can be merged as

$p_{j}^{A_{0}}\leq\varphi\rho_{j}\mbox{ and
}p_{j}^{A_{1}}\leq\max\left\\{1+\frac{1}{x_{1}},y_{1}\right\\}\rho_{j}=y_{1}\rho_{j};$
(14)

and the expected processing time of $J_{j}$ in the revised GCL algorithm in
all the four cases can be merged as

$E[p_{j}^{A}]\leq\max\left\\{x_{1},1+\frac{1-\alpha}{x_{1}},\alpha+(1-\alpha)y_{1}\right\\}\rho_{j}=x_{1}\rho_{j}.$
(15)

Suppose the job $J_{n_{i}}$ determines the makespan of the schedule produced
by the algorithm $A_{i}$, for $i=0,1$, respectively. Note that $J_{n_{i}}$ is
assigned to the least loaded machine by the algorithm. Therefore,

$C^{A_{i}}\leq\frac{1}{2}\sum_{j=1}^{n_{i}-1}p_{j}^{A_{i}}+p_{n_{i}}^{A_{i}}=\frac{1}{2}\sum_{j=1}^{n_{i}}p_{j}^{A_{i}}+\frac{1}{2}p_{n_{i}}^{A_{i}}.$
(16)

We distinguish the following three cases.

Case 1: $n_{1}=n_{2}$. Using Eqs. (14, 15, 16) and the lower bounds in Lemma
5, we have

$\displaystyle E[C^{A}]$ $\displaystyle=$ $\displaystyle\alpha
C^{A_{0}}+(1-\alpha)C^{A_{1}}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\sum_{j=1}^{n_{1}}(\alpha
p_{j}^{A_{0}}+(1-\alpha)p_{j}^{A_{1}})+\frac{1}{2}(\alpha
p_{n_{1}}^{A_{0}}+(1-\alpha)p_{n_{1}}^{A_{1}})$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{j=1}^{n_{1}}E[p_{j}^{A}]+\frac{1}{2}E[p_{n_{1}}^{A}]$
$\displaystyle\leq$
$\displaystyle\frac{x_{1}}{2}\sum_{j=1}^{n_{1}}\rho_{j}+\frac{x_{1}}{2}\rho_{n_{1}}$
$\displaystyle\leq$ $\displaystyle\frac{3x_{1}}{2}C^{*}.$

Case 2: $n_{1}>n_{2}$. Eq. (16) becomes

$C^{A_{0}}\leq\frac{1}{2}\sum_{j=1}^{n_{1}}p_{j}^{A_{0}}+\frac{1}{2}p_{n_{1}}^{A_{0}},\mbox{
and
}C^{A_{1}}\leq\frac{1}{2}\sum_{j=1}^{n_{1}}p_{j}^{A_{1}}+\frac{1}{2}p_{n_{2}}^{A_{1}}-\frac{1}{2}p_{n_{1}}^{A_{1}}.$

Then using $p_{n_{1}}^{A_{1}}\geq\rho_{n_{1}}$, Eqs. (9, 14, 15) and the lower
bounds in Lemma 5, we have

$\displaystyle E[C^{A}]$ $\displaystyle=$ $\displaystyle\alpha
C^{A_{0}}+(1-\alpha)C^{A_{1}}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\sum_{j=1}^{n_{1}}E[p_{j}^{A}]+\frac{\alpha}{2}p_{n_{1}}^{A_{0}}+\frac{1-\alpha}{2}p_{n_{2}}^{A_{1}}-\frac{1-\alpha}{2}p_{n_{1}}^{A_{1}}$
$\displaystyle\leq$
$\displaystyle\frac{x_{1}}{2}\sum_{j=1}^{n_{1}}\rho_{j}+\frac{\alpha\varphi}{2}\rho_{n_{1}}+\frac{1-\alpha}{2}y_{1}\rho_{n_{2}}-\frac{1-\alpha}{2}\rho_{n_{1}}$
$\displaystyle=$
$\displaystyle\frac{x_{1}}{2}\sum_{j=1}^{n_{1}}\rho_{j}+\frac{\varphi-1}{2}\rho_{n_{1}}+\frac{x_{1}-\varphi+1}{2}\rho_{n_{2}}$
$\displaystyle\leq$ $\displaystyle\frac{3x_{1}}{2}C^{*}.$

Case 3: $n_{1}<n_{2}$. Eq. (16) becomes

$C^{A_{0}}\leq\frac{1}{2}\sum_{j=1}^{n_{2}}p_{j}^{A_{0}}+\frac{1}{2}p_{n_{1}}^{A_{0}}-\frac{1}{2}p_{n_{2}}^{A_{0}},\mbox{
and
}C^{A_{1}}\leq\frac{1}{2}\sum_{j=1}^{n_{2}}p_{j}^{A_{1}}+\frac{1}{2}p_{n_{2}}^{A_{1}}.$

Then using $p_{n_{2}}^{A_{0}}\geq\rho_{n_{2}}$, Eqs. (9, 14, 15) and the lower
bounds in Lemma 5, we have

$\displaystyle E[C^{A}]$ $\displaystyle=$ $\displaystyle\alpha
C^{A_{0}}+(1-\alpha)C^{A_{1}}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\sum_{j=1}^{n_{2}}E[p_{j}^{A}]+\frac{\alpha}{2}p_{n_{1}}^{A_{0}}+\frac{1-\alpha}{2}p_{n_{2}}^{A_{1}}-\frac{\alpha}{2}p_{n_{2}}^{A_{0}}$
$\displaystyle\leq$
$\displaystyle\frac{x_{1}}{2}\sum_{j=1}^{n_{2}}\rho_{j}+\frac{\alpha\varphi}{2}\rho_{n_{1}}+\frac{1-\alpha}{2}y_{1}\rho_{n_{2}}-\frac{\alpha}{2}\rho_{n_{2}}$
$\displaystyle=$
$\displaystyle\frac{x_{1}}{2}\sum_{j=1}^{n_{2}}\rho_{j}+\frac{1}{2}\rho_{n_{1}}+\frac{x_{1}-2\varphi+2}{2}\rho_{n_{2}}$
$\displaystyle\leq$
$\displaystyle\left(\frac{3x_{1}}{2}+\frac{3-2\varphi}{2}\right)C^{*}$
$\displaystyle\leq$ $\displaystyle\frac{3x_{1}}{2}C^{*}.$

In all the above three cases, we have
$E[C^{A}]\leq\frac{3x_{1}}{2}C^{*}=\frac{3\varphi+3\sqrt{13-7\varphi}}{4}C^{*}$.
This proves that the expected competitive ratio of the revised GCL algorithm
is at most $\frac{3\varphi+3\sqrt{13-7\varphi}}{4}\approx 2.1839$.

We next give a three-job instance of the two-machine problem $P2\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$ in Instance 1 to show the
expected competitive ratio of the revised GCL algorithm is tight.

###### Instance 1

In this three-job instance of $P2\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid
C_{\max}$, the job order is $\langle J_{1},J_{2},J_{3}\rangle$, with

$\left\\{\begin{array}[]{lll}u_{1}=x_{1},&t_{1}=1,&p_{1}=0,\\\
u_{2}=x_{1},&t_{2}=1,&p_{2}=0,\\\
u_{3}=2x_{1},&t_{3}=2,&p_{3}=0.\end{array}\right.$

One sees that for this instance, $\rho_{1}=\rho_{2}=1$ and $\rho_{3}=2$.
Therefore, the optimal offline makespan is $C^{*}=2$ by testing all the jobs
and assigning $J_{1},J_{2}$ on one machine and $J_{3}$ on the other machine.
On the other hand, $r_{j}=x_{1}<\varphi$ for any $j=1,2,3$ and so they are all
untested in either algorithm of $A_{0}$ and $A_{1}$. It follows that
$C^{A_{0}}=C^{A_{1}}=3x_{1}$ and thus $E[C^{A}]=3x_{1}$ too. The expected
competitive ratio of GCL on this instance is $\frac{3x_{1}}{2}$. This finishes
the proof of the theorem. $\Box$

##  4 Lower bounds on competitive ratios

In this section, we show lower bounds of $1.6682$ and $1.6522$ on the expected
competitive ratio of any randomized algorithm for the fully online problem
$P\mid t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$ at the presence of at least
three machines and only two machines, respectively. One thus sees that the
expected competitive ratios of the GCL algorithm are far away from these two
lower bounds and $2-\frac{1}{m}$ [3] on the expected competitive ratio at the
presence of two, three and $m\geq 4$ machines, respectively. These gaps
certainly welcome future research. We also prove an improved lower bound of
$2.2117$ on the competitive ratio for any deterministic algorithm for $P2\mid
t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$, implying that the GCL algorithm is
better than any deterministic algorithm in terms of expected competitive
ratio.

###  4.1 On expected competitive ratios

Yao’s principle [17] is an efficient tool in proving the lower bounds for
randomized algorithms. Below we prove a theorem which is a slight modification
of Yao’s principle. Let $\mathcal{I}$ and $\mathcal{A}$ be the deterministic
instance space and the deterministic algorithm space, respectively, for an
optimization problem. For distinction, let $I$ and $I_{r}$ denote a
deterministic instance and a randomized instance, respectively, and let $A$
and $A_{r}$ denote a deterministic algorithm and a randomized algorithm,
respectively. Note that in a randomized instance $I_{r}$ of the multiprocessor
scheduling with testing problem, each job $J_{j}$ is given known $u_{j}$ and
$t_{j}$ values and, after the testing is done, a probability distribution of
$p_{j}$ value.

###### Theorem 3

For any randomized algorithm $A_{r}$ and any randomized instance $I_{r}$, the
expected competitive ratio of $A_{r}$ satisfies

$\sup_{I\in\mathcal{I}}\frac{E[C^{A_{r}}(I)]}{C^{*}(I)}\geq\inf_{A\in\mathcal{A}}\frac{E[C^{A}(I_{r})]}{E[C^{*}(I_{r})]},$

where $E[C^{A}(I_{r})]$ and $E[C^{*}(I_{r})]$ are the expected objective value
for a deterministic algorithm $A$ and the expected optimal objective value on
the instance $I_{r}$, respectively.

Proof.  For any deterministic algorithm $A$, we have

$E[C^{A}(I_{r})]=\sum_{I\in\mathcal{I}}Pr[I_{r}=I]C^{A}(I),$

where $Pr[I_{r}=I]$ is the probability that the randomized instance $I_{r}$
happens to be the deterministic instance $I$. Note that
$\sum_{A\in\mathcal{A}}Pr[A_{r}=A]=1$ and
$E[C^{A_{r}}(I)]=\sum_{A\in\mathcal{A}}Pr[A_{r}=A]C^{A}(I)$. It follows that

$\displaystyle\inf_{A\in\mathcal{A}}E[C^{A}(I_{r})]$ $\displaystyle=$
$\displaystyle\inf_{A\in\mathcal{A}}\sum_{I\in\mathcal{I}}Pr[I_{r}=I]C^{A}(I)$
$\displaystyle\leq$
$\displaystyle\sum_{A\in\mathcal{A}}Pr[A_{r}=A]\sum_{I\in\mathcal{I}}Pr[I_{r}=I]C^{A}(I)$
$\displaystyle=$
$\displaystyle\sum_{I\in\mathcal{I}}Pr[I_{r}=I]\sum_{A\in\mathcal{A}}Pr[A_{r}=A]C^{A}(I)$
$\displaystyle=$
$\displaystyle\sum_{I\in\mathcal{I}}Pr[I_{r}=I]E[C^{A_{r}}(I)].$

Since $E[C^{*}(I_{r})]=\sum_{I\in\mathcal{I}}Pr[I_{r}=I]C^{*}(I)$, at the end
we obtain

$\inf_{A\in\mathcal{A}}\frac{E[C^{A}(I_{r})]}{E[C^{*}(I_{r})]}\leq\frac{\sum_{I\in\mathcal{I}}Pr[I_{r}=I]E[C^{A_{r}}(I)]}{\sum_{I\in\mathcal{I}}Pr[I_{r}=I]C^{*}(I)}\leq\sup_{I\in\mathcal{I}}\frac{E[C^{A_{r}}(I)]}{C^{*}(I)},$

which proves the theorem. $\Box$

For the semi-online single machine uniform testing problem $P1\mid
t_{j}=1,0\leq p_{j}\leq u_{j}\mid C_{\max}$, the following randomized instance
shows the tight lower bound of $\frac{4}{3}$ on expected competitive ratios
[6, 7, 2].

###### Instance 2

In this randomized instance of $P1\mid t_{j}=1,0\leq p_{j}\leq u_{j}\mid
C_{\max}$, there is only a single job $J_{1}$ with $u_{1}=2$ and $t_{1}=1$,
and $p_{1}=0$ or $2$ each of probability $0.5$.

In any deterministic algorithm $A$, $J_{1}$ is either tested or untested. If
$J_{1}$ is untested, then $p_{1}^{A}=u_{1}=2$; otherwise $J_{1}$ is tested and
thus $p_{1}^{A}=t_{1}+p_{1}$ which is $1$ or $3$ each of probability $0.5$. It
follows that the expected total execution time is $E[p_{1}^{A}]=2$,
disregarding $J_{1}$ is tested or not.

On the other hand, the optimal offline execution time is $\rho_{1}=1$ if
$p_{1}=0$, or $2$ if $p_{1}=2$; that is, the expected optimal execution time
is $E[\rho_{1}]=1.5$. By Theorem 3,
$\frac{E[p_{1}^{A}]}{E[\rho_{1}]}=\frac{4}{3}$ is a lower bound on expected
competitive ratios for the semi-online single machine uniform testing problem
$P1\mid t_{j}=1,0\leq p_{j}\leq u_{j}\mid C_{\max}$.

When there are multiple machines, the following deterministic instance shows a
lower bound of $2-\frac{1}{m}$ on expected competitive ratios [3].

###### Instance 3

In this deterministic instance of $P\mid t_{j}=1,0\leq p_{j}\leq u_{j}\mid
C_{\max}$, every job has $u_{i}=M$ and $t_{i}=1$, where $M$ is sufficiently
large, there are $m(m-1)$ small jobs with $p_{i}=0$, and additionally a large
job with its $p_{i}=m-1$.

The optimal offline schedule tests all the jobs, giving rise to $C^{*}=m$.

On the other hand, the sufficiently large $M$ forces any deterministic
algorithm to also test all the jobs. Noting that all these jobs are
indistinguishable at the arrival. The adversary decides the processing time of
a particular job to be $m-1$, which is the first job assigned by the algorithm
to a machine that has a load of $m-1$. This way, the makespan of the generated
schedule is $C_{\max}\geq 2m-1$.

For the randomized instance consisting of only this deterministic instance,
Theorem 3 implies that $2-\frac{1}{m}$ is a lower bound on expected
competitive ratios for the semi-online multiprocessor uniform testing problem
$P\mid t_{j}=1,0\leq p_{j}\leq u_{j}\mid C_{\max}$.

The above two lower bounds on expected competitive ratios for the most special
semi-online uniform testing case hold surely for the fully online general
testing case too. In the next two theorems, we prove lower bounds specifically
for the fully online general testing problem $P\mid online,t_{j},0\leq
p_{j}\leq u_{j}\mid C_{\max}$, using randomized instances constructed out of
the following deterministic instance. These two lower bounds are better than
$2-\frac{1}{m}$ when $m=2,3$.

###### Instance 4

In this deterministic instance $I$ of $P\mid online,t_{j},0\leq p_{j}\leq
u_{j}\mid C_{\max}$, there are $m$ machines and $m+1$ jobs arriving in
sequence $\langle J_{1},J_{2},\cdots,J_{m+1}\rangle$, with

$u_{j}=2,t_{j}=1,\mbox{ for any }j=1,2,\cdots,m+1.$

That is, these $m+1$ jobs are indistinguishable at the arrivals. For a
deterministic algorithm, the adversary sets the first two untested jobs, if
exist, or otherwise the last two jobs in the sequence to have their exact
executing times $0$; the other $m-1$ jobs have their exact executing times
$2$.

For example, when $m=4$ and the algorithm does not test any job, then the
sequence of exact executing times is $\langle 0,0,2,2,2\rangle$; if the
algorithm does not test any of $J_{3},J_{4}$ and $J_{5}$, then the sequence of
exact executing times is $\langle 2,2,0,0,2\rangle$; if the algorithm does not
test $J_{1}$ only, then the sequence of exact executing times is $\langle
0,2,2,2,0\rangle$; if the algorithm tests all the five jobs, then the sequence
of exact executing times is $\langle 2,2,2,0,0\rangle$.

Given a deterministic algorithm $A$, let $C^{A}_{\min}(I)$ denote the minimum
machine load in the schedule produced by $A$ for the instance $I$.

###### Lemma 9

When $m\geq 3$, on the instance $I$ in Instance 4, for any deterministic
algorithm $A$, either $C^{A}(I)\geq 4$, or $C^{A}(I)=3$ and $C_{\min}(I)\geq
2$.

Proof.  If the algorithm $A$ does not test two or more jobs, then one sees
that the total processing time of every job is at least $2$, leading to the
makespan $C^{A}(I)\geq 4$ by the Pigeonhole Principle.

If the algorithm $A$ tests all but at most one job, then among the first $m$
jobs $\langle J_{1},J_{2},\cdots,J_{m}\rangle$, the total processing time of
each but one of them is $3$, and the total processing time of the exceptional
job is either $1$ if it is tested or $2$ if it is untested. One sees that when
a machine is assigned with any two of these $m$ jobs, the makespan
$C^{A}(I)\geq 4$ by the Pigeonhole Principle. In the other case where each
machine is assigned with exactly one of these $m$ jobs, assigning the last job
$J_{m+1}$ to any one of the machines would lead to either $C^{A}(I)\geq 4$, or
$C^{A}(I)=3$ and $C_{\min}(I)\geq 2$. This finishes the proof. $\Box$

###### Lemma 10

When $m=2$, on the instance $I$ in Instance 4, for any deterministic algorithm
$A$, either $C^{A}(I)\geq 5$, or $C^{A}(I)\geq 4$ and $C_{\min}(I)\geq 1$, or
$C^{A}(I)\geq 3$ and $C_{\min}(I)\geq 2$.

Proof.  Note that $I$ is now a three-job instance.

We distinguish the two cases on whether $A$ tests the first job $J_{1}$ or
not. If $J_{1}$ is tested, then $p_{1}=2$ and thus $p_{1}^{A}=3$. Note that
the total processing times of $J_{2}$ and $J_{3}$ are at least $1$. These
three values $\\{3,1,1\\}$ guarantee one of the makespan scenarios.

If $J_{1}$ is untested, then $p_{1}^{A}=2$. Note that the total processing
time of one of $J_{2}$ and $J_{3}$ is at least $2$ (which is either untested,
or tested with the exact executing time $2$), and of the other is at least
$1$. These three values $\\{2,2,1\\}$ guarantee one of the makespan scenarios.
$\Box$

###### Theorem 4

The expected competitive ratio of any randomized algorithm for $P\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{max}$ at the presence of three or
more machines is at least $\frac{21}{2}-\sqrt{78}\approx 1.6682$.

Proof.  We consider a randomized instance $I_{r}$, which is a probability
distribution over three deterministic instances $I_{1},I_{2}$ and $I_{3}$.
These three instances are all extended from $I$ in Instance 4, by appending a
job $J_{m+2}$ at the end of the job sequence. Specifically, for $J_{m+2}$,

$(u_{m+2},t_{m+2},p_{m+2})=\left\\{\begin{array}[]{ll}(0,0,0),&\mbox{ in
}I_{1},\\\ (2+\frac{1}{\alpha},3,0),&\mbox{ in }I_{2},\\\
(2+\frac{1}{\alpha},3,2+\frac{1}{\alpha}),&\mbox{ in
}I_{3},\end{array}\right.$

where $\alpha=\frac{2\sqrt{78}-5}{41}\approx 0.3089$, and its probability
distribution is
$(\beta_{1},\beta_{2},\beta_{3})=(\frac{2-\alpha}{3},\alpha,\frac{1-2\alpha}{3})$.

Note that exactly two of $\rho_{1},\rho_{2},\cdots,\rho_{m+1}$ are $1$, while
the others are $2$. For the job $J_{m+2}$, $\rho_{m+2}=0,3,2+\frac{1}{\alpha}$
in $I_{1},I_{2},I_{3}$, respectively. It follows from $m\geq 3$ that the
optimal offline makespans of $I_{1},I_{2},I_{3}$ are
$C^{*}=2,3,2+\frac{1}{\alpha}$, respectively. Therefore, the expected optimal
offline makespan of $I_{r}$ is

$E[C^{*}(I_{r})]=2\beta_{1}+3\beta_{2}+(2+\frac{1}{\alpha})\beta_{3}=\frac{4}{3}+\alpha+\frac{1}{3\alpha}.$

For any deterministic algorithm $A$, it performs the same on the prefix
instance $I$ of all the three instances $I_{1},I_{2}$ and $I_{3}$, including
which jobs of the first $m+1$ ones are tested, to which machines they are
assigned to, and all the $m$ machine loads when the last job $J_{m+2}$
arrives. In particular, since $u_{m+2}$ and $t_{m+2}$ are the same in $I_{2}$
and $I_{3}$, $J_{m+2}$ is either both tested or both untested by $A$. By Lemma
9, we have either $C^{A}(I_{1})=C^{A}(I)\geq 4$, or $C^{A}(I_{1})=C^{A}(I)=3$
and $C^{A}_{\min}(I_{1})=C^{A}_{\min}(I)\geq 2$. We distinguish the following
four cases on $C^{A}(I)$ and whether $J_{m+2}$ of $I_{2}$ is tested by $A$ or
not.

The first case is that $C^{A}(I)\geq 4$ and $J_{m+2}$ of $I_{2}$ is tested by
$A$. Clearly, $C^{A}(I_{2})\geq 4$ and $C^{A}(I_{3})\geq
p_{m+2}^{A}=5+\frac{1}{\alpha}$. Therefore,

$E[C^{A}(I_{r})]\geq
4\beta_{1}+4\beta_{2}+(5+\frac{1}{\alpha})\beta_{3}=\frac{11}{3}-\frac{2\alpha}{3}+\frac{1}{3\alpha}.$

The second case is that $C^{A}(I)\geq 4$ and $J_{m+2}$ of $I_{2}$ is untested
by $A$. We have $C^{A}(I_{i})\geq p_{m+2}^{A}=2+\frac{1}{\alpha}$ for both
$i=2,3$. Therefore,

$E[C^{A}(I_{r})]\geq
4\beta_{1}+(2+\frac{1}{\alpha})(\beta_{2}+\beta_{3})=\frac{11}{3}-\frac{2\alpha}{3}+\frac{1}{3\alpha}.$

The third case is that $C^{A}(I)=3$, $C^{A}_{\min}(I)\geq 2$, and $J_{m+2}$ of
$I_{2}$ is tested by $A$. For $I_{2}$, $p_{m+2}^{A}=3$ and thus
$C^{A}(I_{2})\geq 5$ no matter which machine $J_{m+2}$ is assigned to; for
$I_{3}$, $p_{m+2}^{A}=5+\frac{1}{\alpha}$ and thus $C^{A}(I_{3})\geq
7+\frac{1}{\alpha}$. Therefore,

$E[C^{A}(I_{r})]\geq
3\beta_{1}+5\beta_{2}+(7+\frac{1}{\alpha})\beta_{3}=\frac{11}{3}-\frac{2\alpha}{3}+\frac{1}{3\alpha}.$

The last case is that $C^{A}(I)=3$, $C_{\min}(I)\geq 2$, and $J_{m+2}$ of
$I_{2}$ is untested by $A$. For both $I_{2}$ and $I_{3}$,
$p_{m+2}^{A}=2+\frac{1}{\alpha}$ and thus $C^{A}(I_{i})\geq
4+\frac{1}{\alpha}$ no matter which machine $J_{m+2}$ is assigned to, for both
$i=2,3$. Therefore,

$E[C^{A}(I_{r})]\geq
3\beta_{1}+(4+\frac{1}{\alpha})(\beta_{2}+\beta_{3})=\frac{11}{3}+\frac{\alpha}{3}+\frac{1}{3\alpha}>\frac{11}{3}-\frac{2\alpha}{3}+\frac{1}{3\alpha}.$

To conclude, by Theorem 3, the expected competitive ratio of any randomized
algorithm for $P\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$ at the
presence of three or more machines is at least

$\inf_{A}\frac{E[C^{A}(I_{r})]}{E[C^{*}(I_{r})]}\geq\frac{\frac{11}{3}-\frac{2\alpha}{3}+\frac{1}{3\alpha}}{\frac{4}{3}+\alpha+\frac{1}{3\alpha}}=\frac{21}{2}-\sqrt{78}.$

This completes the proof of the theorem. $\Box$

###### Theorem 5

The expected competitive ratio of any randomized algorithm for $P2\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{max}$ is at least
$\frac{21+4\sqrt{51}}{30}\approx 1.6522$.

Proof.  Again we consider a randomized instance $I_{r}$, which is a
probability distribution over three deterministic instances $I_{1},I_{2}$ and
$I_{3}$. These three instances are all extended from the three-job instance
$I$ in Instance 4 when $m=2$, by appending a job $J_{4}$ at the end of the job
sequence. Specifically, for $J_{4}$,

$(u_{4},t_{4},p_{4})=\left\\{\begin{array}[]{ll}(0,0,0),&\mbox{ in }I_{1},\\\
(\frac{2}{\alpha},4,0),&\mbox{ in }I_{2},\\\
(\frac{2}{\alpha},4,\frac{2}{\alpha}),&\mbox{ in }I_{3},\end{array}\right.$

where $\alpha=\frac{\sqrt{51}-4}{10}\approx 0.3141$, and its probability
distribution is
$(\beta_{1},\beta_{2},\beta_{3})=(\frac{1}{2},\alpha,\frac{1}{2}-\alpha)$.

Recall that two of $\rho_{1},\rho_{2},\rho_{3}$ are $1$ while the other is
$2$. For the job $J_{4}$, $\rho_{4}=0,4,\frac{2}{\alpha}$ in
$I_{1},I_{2},I_{3}$, respectively. It follows that the optimal offline
makespans of $I_{1},I_{2},I_{3}$ are $C^{*}=2,4,\frac{2}{\alpha}$,
respectively. Therefore, the expected optimal offline makespan of $I_{r}$ is

$E[C^{*}(I_{r})]=2\beta_{1}+4\beta_{2}+\frac{2}{\alpha}\beta_{3}=4\alpha+\frac{1}{\alpha}-1.$

For any deterministic algorithm $A$, it performs the same on the prefix
instance $I$ of all the three instances $I_{1},I_{2}$ and $I_{3}$, including
which of the first three jobs are tested, to which machines they are assigned
to, and the two machine loads when the last job $J_{4}$ arrives. In
particular, since $u_{4}$ and $t_{4}$ are the same in $I_{2}$ and $I_{3}$,
$J_{4}$ is either both tested or both untested by $A$. By Lemma 10, we have
either $C^{A}(I_{1})=C^{A}(I)\geq 5$, or $C^{A}(I_{1})=C^{A}(I)\geq 4$ and
$C^{A}_{\min}(I_{1})=C^{A}_{\min}(I)\geq 1$, or $C^{A}(I_{1})=C^{A}(I)\geq 3$
and $C^{A}_{\min}(I_{1})=C^{A}_{\min}(I)\geq 2$. We distinguish the following
six cases on $C^{A}(I)$ and whether $J_{4}$ of $I_{2}$ is tested by $A$ or
not.

When $C^{A}(I)\geq 5$ and $J_{4}$ of $I_{2}$ is tested by $A$, we have
$C^{A}(I_{2})\geq 5$ and $C^{A}(I_{3})\geq p_{4}^{A}=4+\frac{2}{\alpha}$,
leading to

$E[C^{A}(I_{r})]\geq
5\beta_{1}+5\beta_{2}+(4+\frac{2}{\alpha})\beta_{3}=\frac{5}{2}+\alpha+\frac{1}{\alpha}>\frac{5}{2}+\frac{1}{\alpha}.$

When $C^{A}(I)\geq 5$ and $J_{4}$ of $I_{2}$ is untested by $A$, we have
$C^{A}(I_{i})\geq p_{4}^{A}=\frac{2}{\alpha}$ for both $i=2,3$, leading to

$E[C^{A}(I_{r})]\geq
5\beta_{1}+\frac{2}{\alpha}(\beta_{2}+\beta_{3})=\frac{5}{2}+\frac{1}{\alpha}.$

When $C^{A}(I)\geq 4$ and $C_{\min}(I)\geq 1$, and $J_{4}$ of $I_{2}$ is
tested by $A$, we have $p_{4}^{A}=4$ in $I_{2}$ and thus $C^{A}(I_{2})\geq
p_{4}^{A}+1=5$, and similarly $C^{A}(I_{3})\geq
p_{4}^{A}+1=5+\frac{2}{\alpha}$. They lead to

$E[C^{A}(I_{r})]\geq
4\beta_{1}+5\beta_{2}+(5+\frac{2}{\alpha})\beta_{3}=\frac{5}{2}+\frac{1}{\alpha}.$

When $C^{A}(I)\geq 4$ and $C_{\min}(I)\geq 1$, and $J_{4}$ of $I_{2}$ is
untested by $A$, we have $p_{4}^{A}=\frac{2}{\alpha}$ in both $I_{2}$ and
$I_{3}$ and thus $C^{A}(I_{i})\geq p_{4}^{A}+1=1+\frac{2}{\alpha}$ for both
$i=2,3$. They lead to

$E[C^{A}(I_{r})]\geq
4\beta_{1}+(1+\frac{2}{\alpha})(\beta_{2}+\beta_{3})=\frac{5}{2}+\frac{1}{\alpha}.$

When $C^{A}(I)\geq 3$ and $C_{\min}(I)\geq 2$, and $J_{4}$ of $I_{2}$ is
tested by $A$, we have $p_{4}^{A}=4$ in $I_{2}$ and thus $C^{A}(I_{2})\geq
p_{4}^{A}+2=6$, and similarly $C^{A}(I_{3})\geq
p_{4}^{A}+2=6+\frac{2}{\alpha}$. They lead to

$E[C^{A}(I_{r})]\geq
3\beta_{1}+6\beta_{2}+(6+\frac{2}{\alpha})\beta_{3}=\frac{5}{2}+\frac{1}{\alpha}.$

Lastly, when $C^{A}(I)\geq 3$ and $C_{\min}(I)\geq 2$, and $J_{4}$ of $I_{2}$
is untested by $A$, we have $p_{4}^{A}=\frac{2}{\alpha}$ in both $I_{2}$ and
$I_{3}$ and thus $C^{A}(I_{i})\geq p_{4}^{A}+2=2+\frac{2}{\alpha}$ for both
$i=2,3$. They lead to

$E[C^{A}(I_{r})]\geq
3\beta_{1}+(2+\frac{2}{\alpha})(\beta_{2}+\beta_{3})=\frac{5}{2}+\frac{1}{\alpha}.$

To conclude, by Theorem 3, the expected competitive ratio of any randomized
algorithm for $P2\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$ is at
least

$\inf_{A}\frac{E[C^{A}(I_{r})]}{E[C^{*}(I_{r})]}\geq\frac{\frac{5}{2}+\frac{1}{\alpha}}{4\alpha+\frac{1}{\alpha}-1}=\frac{21+4\sqrt{51}}{30}.$

This completes the proof of the theorem. $\Box$

###  4.2 On deterministic competitive ratios

Recall that besides the lower bound of $2$ on the deterministic competitive
ratio for the uniform testing case $P\mid online,t_{j}=1,0\leq p_{j}\leq
u_{j}\mid C_{\max}$, Albers and Eckl [3] also showed a slightly better lower
bound of $2.0953$ for the two-machine general testing case $P2\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$. We improve the latter lower
bound of $2.0953$ to $2.2117$ in the next theorem. Therefore, for $P2\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$, the expected competitive
ratio of GCL not only beats the best known deterministic competitive ratio of
$2.3019$ [11] for the semi-online variant $P2\mid t_{j},0\leq p_{j}\leq
u_{j}\mid C_{\max}$, but also beats the lower bound of $2.2117$ on the
deterministic competitive ratio for the fully online problem.

###### Theorem 6

The competitive ratio of any deterministic algorithm for $P2\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{max}$ is greater than $2.2117$.

Proof.  Note that we are proving a lower bound on the deterministic
competitive ratio, and we use an adversarial argument to construct a three-job
instance with the job order $\langle J_{1},J_{2},J_{3}\rangle$. Consider a
deterministic algorithm $A$.

The first job $J_{1}$ comes with $u_{1}=\varphi$ and $t_{1}=1$. If $A$ tests
$J_{1}$, then the adversary sets $p_{1}=\varphi$. It follows that
$p_{1}^{A}=\varphi+1$ and $\rho_{1}=\varphi$. If $J_{1}$ is untested, then the
adversary sets $p_{1}=0$ and thus $p_{1}^{A}=\varphi$ and $\rho_{1}=1$. Either
way, we have $\frac{p_{1}^{A}}{\rho_{1}}=\varphi$, and thus we assume below
that $p_{1}^{A}=\varphi$ and $\rho_{1}=1$. (If $p_{1}^{A}=\varphi+1$ and
$\rho_{1}=\varphi$, then the below $u_{j}$\- and $t_{j}$-values associated
with $J_{2}$ and $J_{3}$ are scaled up by multiplying a factor of $\varphi$.)

For any upcoming job $J_{j}$, i.e., $j=2,3$, the adversary always sets
$p_{j}=u_{j}$ if $J_{j}$ is tested by the algorithm, or otherwise sets
$p_{j}=0$.

Let $x_{0}=\frac{3\varphi+1-\sqrt{11\varphi+6}}{2}\approx 0.4878$, which is a
root to the quadratic equation $x^{2}-(3\varphi+1)x+\varphi^{2}=0$. The second
job $J_{2}$ comes with $u_{2}=\varphi-x_{0}$ and $t_{2}=x_{0}$. We distinguish
two cases on whether or not $J_{2}$ is tested by the algorithm.

Case 1: $J_{2}$ is tested by the algorithm. In this case, $p_{2}=u_{2}$ and
thus $p_{2}^{A}=\varphi$ and $\rho_{2}=\varphi-x_{0}$. If $J_{2}$ is scheduled
on the same machine with $J_{1}$, then the third job $J_{3}$ is voided (by
setting $u_{j}=t_{j}=0$) leading to $C^{A}=p_{1}^{A}+p_{2}^{A}=2\varphi$. Note
that $\rho_{2}>1$ and thus $C^{*}=\rho_{2}=\varphi-x_{0}$. It follows that the
competitive ratio is $\frac{2\varphi}{\varphi-x_{0}}$.

Below we assume $J_{j}$ is assigned to the machine $M_{j}$, for $j=1,2$,
respectively, and thus the load of each machine is $\varphi$. The third job
$J_{3}$ comes with $u_{3}=y_{0}$ and $t_{3}=\varphi+1-x_{0}$, where
$y_{0}=\frac{1-x_{0}+\sqrt{(3\varphi-5)x_{0}+15\varphi+8}}{2}\approx 3.0933$
is a root to the quadratic equation
$y^{2}-(1-x_{0})y-(\varphi+1-x_{0})(2\varphi+1-x_{0})=0$.

If $J_{3}$ is untested, then $p_{3}=0$ and thus $p_{3}^{A}=y_{0}$ and
$\rho_{3}=\varphi+1-x_{0}$, leading to $C^{A}=\varphi+y_{0}$. In the optimal
offline schedule, $J_{1}$ and $J_{2}$ are scheduled on one machine while
$J_{3}$ is scheduled on the other, leading to the optimal offline makespan
$C^{*}=\varphi+1-x_{0}$. Therefore,
$\frac{C^{A}}{C^{*}}=\frac{y_{0}+\varphi}{\varphi+1-x_{0}}$.

If $J_{3}$ is tested, then $p_{3}=u_{3}$ and thus
$p_{3}^{A}=t_{3}+u_{3}=\varphi+1-x_{0}+y_{0}$ and $\rho_{3}=y_{0}$, leading to
$C^{A}=2\varphi+1-x_{0}+y_{0}$. In the optimal offline schedule, $J_{1}$ and
$J_{2}$ are scheduled on one machine while $J_{3}$ is scheduled on the other,
leading to $C^{*}=y_{0}$ and subsequently
$\frac{C^{A}}{C^{*}}=\frac{2\varphi+1-x_{0}+y_{0}}{y_{0}}$.

To conclude this case, we have

$\frac{C^{A}}{C^{*}}\geq\min\left\\{\frac{2\varphi}{\varphi-
x_{0}},\frac{y_{0}+\varphi}{\varphi+1-x_{0}},\frac{2\varphi+1-x_{0}+y_{0}}{y_{0}}\right\\}.$

Since $y_{0}$ is a root to the quadratic equation
$y^{2}-(1-x_{0})y-(\varphi+1-x_{0})(2\varphi+1-x_{0})=0$, we have

$y_{0}(y_{0}+\varphi)=(\varphi+1-x_{0})(y_{0}+2\varphi+1-x_{0}),$

that is, the last two quantities in the above are equal and approximately
$2.21172$. The first quantity in the above is about $2.8634$. Therefore,
$\frac{C^{A}}{C^{*}}>2.2117$.

Case 2: $J_{2}$ is untested by the algorithm. In this case, $p_{2}=0$ and thus
$p_{2}^{A}=\varphi-x_{0}$ and $\rho_{2}=x_{0}$. If $J_{2}$ is scheduled on the
same machine with $J_{1}$, then the third job $J_{3}$ is voided (by setting
$u_{j}=t_{j}=0$) leading to $C^{A}=p_{1}^{A}+p_{2}^{A}=2\varphi-x_{0}$. Note
that $\rho_{2}=x_{0}<1$ and thus $C^{*}=1$. It follows that the competitive
ratio is $\frac{C^{A}}{C^{*}}=2\varphi-x_{0}$.

Below we assume $J_{j}$ is assigned to the machine $M_{j}$, for $j=1,2$,
respectively, and thus the loads of the two machines are $\varphi$ and
$\varphi-x_{0}$, respectively. The third job $J_{3}$ comes with
$u_{3}=\frac{(1+\varphi)y_{0}}{2\varphi+1-x_{0}}\approx 2.1606$ and
$t_{3}=1+x_{0}$, where $y_{0}$ is set the same as in Case 1.

If $J_{3}$ is untested, then $p_{3}=0$ and thus
$p_{3}^{A}=u_{3}=\frac{(1+\varphi)y_{0}}{2\varphi+1-x_{0}}$ and
$\rho_{3}=1+x_{0}$, leading to $C^{A}\geq\varphi-
x_{0}+\frac{(1+\varphi)y_{0}}{2\varphi+1-x_{0}}$ no matter which machine
$J_{3}$ is assigned to. In the optimal offline schedule, $J_{1}$ and $J_{2}$
are scheduled on one machine while $J_{3}$ is scheduled on the other, leading
to the optimal offline makespan $C^{*}=1+x_{0}$. Therefore,
$\frac{C^{A}}{C^{*}}\geq\frac{\varphi-
x_{0}+\frac{(1+\varphi)y_{0}}{2\varphi+1-x_{0}}}{1+x_{0}}=\frac{(\varphi-
x_{0})(2\varphi+1-x_{0})+(1+\varphi)y_{0}}{(1+x_{0})(2\varphi+1-x_{0})}$.
Since $x_{0}$ is a root to the quadratic equation
$x^{2}-(3\varphi+1)x+\varphi^{2}=0$, we have

$(\varphi-
x_{0})(2\varphi+1-x_{0})=x_{0}^{2}-(3\varphi+1)x_{0}+\varphi(1+2\varphi)=\varphi(1+\varphi)$

and

$(1+x_{0})(2\varphi+1-x_{0})=-x_{0}^{2}+2\varphi
x_{0}+2\varphi+1=(\varphi+1)(1+\varphi-x_{0}).$

It follows that $\frac{C^{A}}{C^{*}}\geq\frac{y_{0}+\varphi}{1+\varphi-
x_{0}}$.

If $J_{3}$ is tested, then $p_{3}=u_{3}$ and thus
$p_{3}^{A}=t_{3}+u_{3}=1+x_{0}+\frac{(1+\varphi)y_{0}}{2\varphi+1-x_{0}}$ and
$\rho_{3}=\frac{(1+\varphi)y_{0}}{2\varphi+1-x_{0}}$, leading to $C^{A}\geq
1+\varphi+\frac{(1+\varphi)y_{0}}{2\varphi+1-x_{0}}$ no matter which machine
$J_{3}$ is assigned to. Since $\rho_{3}>\rho_{1}+\rho_{2}$, in the optimal
offline schedule, $J_{1}$ and $J_{2}$ are scheduled on one machine while
$J_{3}$ is scheduled on the other, leading to
$C^{*}=\rho_{3}=\frac{(1+\varphi)y_{0}}{2\varphi+1-x_{0}}$ and subsequently
$\frac{C^{A}}{C^{*}}\geq\frac{y_{0}+2\varphi+1-x_{0}}{y_{0}}$.

To conclude this case, we have

$\frac{C^{A}}{C^{*}}\geq\min\left\\{2\varphi-
x_{0},\frac{y_{0}+\varphi}{1+\varphi-
x_{0}},\frac{2\varphi+1-x_{0}+y_{0}}{y_{0}}\right\\}.$

The same as in Case 1, the last two quantities in the above are equal and
approximately $2.21172$. The first quantity in the above is about $2.7482$.
Therefore, $\frac{C^{A}}{C^{*}}>2.2117$.

The above two cases prove that the competitive ratio of any deterministic
algorithm for $P2\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{max}$ is
greater than $2.2117$. $\Box$

##  5 Conclusion

We investigated the fully online multiprocessor scheduling with testing
problem $P\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$, and presented
a randomized algorithm GCL that is a non-uniform distribution of arbitrarily
many deterministic algorithms. To the best of our knowledge, randomized
algorithms as meta algorithms in the literature are mostly uniform
distributions of their component deterministic algorithms, while our GCL is
one to bias towards one component algorithm; also, when there are many
component algorithms, the previous randomized algorithm often involves
bookkeeping all their solutions, while our GCL does not do so since the
component algorithms are independent of each other. We showed that the
expected competitive ratio of our GCL is around $3.1490$. When there are only
two machines, i.e., for $P2\mid online,t_{j},0\leq p_{j}\leq u_{j}\mid
C_{\max}$, using only two component algorithms in the revised GCL algorithm
leads to an expected competitive ratio of $2.1839$.

We also proved three inapproximability results, including a lower bound of
$1.6682$ on the expected competitive ratio of any randomized algorithm at the
presence of at least three machines, a lower bound of $1.6522$ on the expected
competitive ratio of any randomized algorithm for $P2\mid online,t_{j},0\leq
p_{j}\leq u_{j}\mid C_{\max}$, and a lower bound of $2.2117$ on the
competitive ratio of any deterministic algorithm for $P2\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$. By the last lower bound, we
conclude that the algorithm GCL beats any deterministic algorithm for $P2\mid
online,t_{j},0\leq p_{j}\leq u_{j}\mid C_{\max}$, in terms of its expected
competitive ratio. Such an algorithmic result is rarely seen in the
literature.

The expected competitive ratio of the algorithm GCL is far away from the lower
bounds of $1.6522$, $1.6682$ and $2-\frac{1}{m}$ for two, three and $m\geq 4$
machines, respectively, suggesting future research to narrow the gaps, even
for the two-machine case. One sees that the testing probability function in
the job ratio in the algorithm GCL is non-continuous at $\varphi$, suggesting
the existence of a plausible better probability distribution function for
choosing component algorithms.

## Declarations

##### Data availability.

Not applicable.

##### Interests.

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## References

  * [1] S. Albers.  On randomized online scheduling.  In Proceedings of ACM STOC 2002, pages 134–143, 2002.
  * [2] S. Albers and A. Eckl.  Explorable uncertainty in scheduling with non-uniform testing times.  In Proceedings of WAOA 2020, LNCS 12806, pages 127–142, 2020.
  * [3] S. Albers and A. Eckl.  Scheduling with testing on multiple identical parallel machines.  In Proceedings of WADS 2021, LNCS 12808, pages 29–42, 2021.
  * [4] Y. Bartal, M. Chrobak, and L. L. Larmore.  A randomized algorithm for two servers on the line.  Information and Computation, 158:53–69, 2000.
  * [5] Y. Bartal, A. Fiat, H. J. Karloff, and R. Vohra.  New algorithms for an ancient scheduling problem.  Journal of Computer and Systems Science, 51:359–366, 1995.
  * [6] C. Dürr, T. Erlebach, N. Megow, and J. Meißner.  Scheduling with explorable uncertainty.  In Proceedings of ITCS 2018, LIPIcs 94, pages 30:1–30:14, 2018\.
  * [7] C. Dürr, T. Erlebach, N. Megow, and J. Meißner.  An adversarial model for scheduling with testing.  Algorithmica, 82:3630–3675, 2020.
  * [8] R. Fleischer and M. Wahl.  On-line scheduling revisited.  Journal of Scheduling, 3:343–353, 2000.
  * [9] S. Fung, C. Poon, and F. Zheng.  Online interval scheduling: Randomized and multiprocessor cases.  Journal of Combinatorial Optimization, 16:248–262, 2008.
  * [10] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-completeness.  W. H. Freeman and Company, San Francisco, 1979.
  * [11] M. Gong, J. Fan, G. Lin, B. Su, Z. Su, and X. Zhang.  Multiprocessor scheduling with testing: Improved approximation algorithms and numerical experiments.  arXiv, 2204.03299, 2022.
  * [12] M. Gong and G. Lin.  Improved approximation algorithms for multiprocessor scheduling with testing.  In Proceedings of FAW 2021, LNCS 12874, pages 65–77, 2021.
  * [13] R. L. Graham.  Bounds for certain multiprocessing anomalies.  Bell Labs Technical Journal, 45:1563–1581, 1966.
  * [14] N. Reingold, J. R. Westbrook, and D. D. Sleator.  Randomized competitive algorithms for the list update problem.  Algorithmica, 11:15–32, 1994.
  * [15] S. S. Seiden.  Online randomized multiprocessor scheduling.  Algorithmica, 28:173–216, 2000.
  * [16] S. S. Seiden.  Barely random algorithms for multiprocessor scheduling.  Journal of Scheduling, 6:309–334, 2003.
  * [17] A. C. Yao.  Probabilistic computations: Toward a unified measure of complexity.  In Proceedings of IEEE FOCS 1977, pages 222–227, 1977.