| dc.description.abstract | This thesis addresses the problem of scheduling with explorable uncertainty on a single machine. We
consider the scenario where n jobs have a uniform upper limit on the processing time ̄u, a uniform
testing time of 1 and a true processing time pj (0 ≤ pj ≤ ̄u), which is only revealed after testing.
Moreover, each job j has a weight wj ∈ N. The machine can either test a job or execute a job.
The duration of executing any job j is either ̄u or pj , depending on whether the job was tested
or not. Since decisions, regarding testing and execution, are irrevocable and the true processing
time is initially hidden, this problem can be viewed as an online problem. The objective is to
schedule all jobs to minimise the total weighted completion time. We present two deterministic
algorithms, Delay-All (DA) and L-Delay-All (L-DA), and analyse their competitive ratios. For
the special case with two weights (1 and α), DA achieves a competitive ratio of 3 + 1
2 × α, while L-DA achieves a ratio of 3 + 1
2 × ̄u. For the more general case with multiple weights, DA and L-DA
achieve a competitive ratios of 1 + 2 × wmax and 3 + 5
3 × ̄u, respectively. We also introduce an
algorithm called Unified-Delay-All (U-DA) which combines DA and L-DA. For the case with two
weights U-DA is 3-competitive when α ≥ ̄u. Moreover, we present a modified version of L-DA, called
Postpone-L-Delay-All (PL-DA), which achieves a 3-competitive ratio for the case with two weights
when the number of α-weighted jobs is at least n
̄u . Furthermore, we show that for DA and L-DA
there exists an instance where the competitive ratio is at least 2.4-competitive and 3.4-competitive,
respectively. | |
