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

        On Machine Scheduling with Exponentially Distributed Processing Times

        Thumbnail
        View/Open
        JagtenbergCarolineMA2011.pdf (433.6Kb)
        Publication date
        2011
        Author
        Jagtenberg, C.J.
        Metadata
        Show full item record
        Summary
        We address the problem to minimize the weighted sum of completion times in nonpreemptive parallel machine scheduling. We consider the stochastic variant of this problem in which the processing times are exponentially distributed random variables. We discuss the phenomenon of deliberate idleness. For some cases we prove that optimal policies are idle time free, but the general question remains unanswered. We extensively study the WSEPT list scheduling policy, and show that its perfomance guarantee is not better than 1.243. This constitutes the first lower bound for WSEPT in this setting. In particular, this bound is larger than the (tight) bound for WSPT for deterministic scheduling, which is ...... Furthermore, we show that for any list scheduling policy, the objective value of the deterministic counterpart is an upper bound for the objective value of the stochastic instance. This result holds for arbitrarily distributed processing times. For a WSEPT policy, we show that the expected objective value for an instance with exponentially distributed processing times is at least ..... times the the objective value of the deterministic couterpart, where m denotes the number of machines. Finally, we conclude with some consideratons about the computational complexity of finding an optimal policy, and of calculating the objective value corresponding to a given policy.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/9359
        Collections
        • Theses
        Utrecht university logo