Scheduling with explorable uncertainty for minimising the total weighted completion time

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.