Print Email Facebook Twitter The Complexity of Stability Title The Complexity of Stability: In Parallel Processor Scheduling Author van Elsas, Maarten (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Algorithmics; TU Delft Software Technology) Contributor de Weerdt, Mathijs (mentor) Yorke-Smith, Neil (graduation committee) Atasoy, Bilge (graduation committee) Degree granting institution Delft University of Technology Date 2019-06-25 Abstract In dynamic scheduling, some of the information about the scheduling problem is learnt during the execution of the schedule. Because of this, creating a low cost schedule that does not have to be changed is impossible in most cases. When changes are made during the execution, focussing solely on the performance of the schedule may result in very large differences between the original schedule and the realised schedule. These differences are undesirable particularly if tasks or resources are human. In order to quantify them, several stability metrics are considered, as well as the performance objective makespan. The complexity of computing these metrics when a single disruption to the duration of one of the tasks occurred is considered. For single machine scheduling problems and constraint programming the complexity of several stability metrics is known. For parallel processor scheduling, very little has been investigated. Optimizing just the stability metrics turns out to be possible in polynomial time. We further show that many of the multi objective optimizations problems that consider both a stability metric and the makespan are strongly NP-complete. For the instances that are not, an algorithm is given. In order to reduce the complexity, reducing the search space to a partial order schedule is investigated. This is a promising method as optimizing the makespan in this reduced search space can be done in polynomial time. Surprisingly, the resulting complexities are the same as those of the original problems. Subject Planning under UncertaintyStabilityScheduling RepairComplexityPartial Order Schedules To reference this document use: http://resolver.tudelft.nl/uuid:d5db27f8-75c1-4633-ae95-4404a42e03de Part of collection Student theses Document type master thesis Rights © 2019 Maarten van Elsas Files PDF mvanelsas_final.pdf 508.17 KB Close viewer /islandora/object/uuid%3Ad5db27f8-75c1-4633-ae95-4404a42e03de/datastream/OBJ/view