View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Scheduling with explorable uncertainty for minimising the total weighted completion time

        Thumbnail
        View/Open
        Master_Thesis_explorable_uncertainty.pdf (1014.Kb)
        Publication date
        2023
        Author
        Zhang, Xiao
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/43857
        Collections
        • Theses
        Utrecht university logo