White Rose University Consortium logo
University of Leeds logo University of Sheffield logo York University logo

Scheduling Models with Additional Features: Synchronization, Pliability and Resiliency

Weiß, Christian (2016) Scheduling Models with Additional Features: Synchronization, Pliability and Resiliency. PhD thesis, University of Leeds.

[img]
Preview
Text
Weiss_C_Computing_PhD_2016.pdf - Final eThesis - complete (pdf)
Available under License Creative Commons Attribution-Noncommercial-Share Alike 2.0 UK: England & Wales.

Download (1801Kb) | Preview

Abstract

In this thesis we study three new extensions of scheduling models with both practical and theoretical relevance, namely synchronization, pliability and resiliency. Synchronization has previously been studied for flow shop scheduling and we now apply the concept to open shop models for the first time. Here, as opposed to the traditional models, operations that are processed together all have to be started at the same time. Operations that are completed are not removed from the machines until the longest operation in their group is finished. Pliability is a new approach to model flexibility in flow shops and open shops. In scheduling with pliability, parts of the processing load of the jobs can be re-distributed between the machines in order to achieve better schedules. This is applicable, for example, if the machines represent cross-trained workers. Resiliency is a new measure for the quality of a given solution if the input data are uncertain. A resilient solution remains better than some given bound, even if the original input data are changed. The more we can perturb the input data without the solution losing too much quality, the more resilient the solution is. We also consider the assignment problem, as it is the traditional combinatorial optimization problem underlying many scheduling problems. Particularly, we study a version of the assignment problem with a special cost structure derived from the synchronous open shop model and obtain new structural and complexity results. Furthermore we study resiliency for the assignment problem. The main focus of this thesis is the study of structural properties, algorithm development and complexity. For synchronous open shop we show that for a fixed number of machines the makespan can be minimized in polynomial time. All other traditional scheduling objectives are at least as hard to optimize as in the traditional open shop model. Starting out research in pliability we focus on the most general case of the model as well as two relevant special cases. We deliver a fairly complete complexity study for all three versions of the model. Finally, for resiliency, we investigate two different questions: `how to compute the resiliency of a given solution?' and `how to find a most resilient solution?'. We focus on the assignment problem and single machine scheduling to minimize the total sum of completion times and present a number of positive results for both questions. The main goal is to make a case that the concept deserves further study.

Item Type: Thesis (PhD)
Related URLs:
Keywords: Scheduling, Combinatorial Optimization, Algorithms, NP-hardness, Complexity, Synchronization, Pliability, Resiliency, Flow shop, Open shop, Parallel machines, Preemption, Stability, Assignment problem, Monge property, Monge matrix, Monge array
Academic Units: The University of Leeds > Faculty of Engineering (Leeds) > School of Computing (Leeds)
Depositing User: Christian Weiß
Date Deposited: 04 Apr 2017 11:05
Last Modified: 01 Apr 2019 00:18
URI: http://etheses.whiterose.ac.uk/id/eprint/16794

You do not need to contact us to get a copy of this thesis. Please use the 'Download' link(s) above to get a copy.
You can contact us about this thesis. If you need to make a general enquiry, please see the Contact us page.

Actions (repository staff only: login required)