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

Scheduling with due dates and time-lags : new theoretical results and applications

Condotta, Alessandro (2011) Scheduling with due dates and time-lags : new theoretical results and applications. PhD thesis, University of Leeds.

uk_bl_ethos_578623.pdf - Final eThesis - complete (pdf)

Download (7Mb) | Preview


Manufacturing and service environments involve decisions on sequencing activities. Some examples are assembly operations in workshops, the elaboration of data by computer systems and the handling of products by operators in warehouses. Scheduling theory studies the mathematical structures of such problems with the objective of designing theoretical models and solution algorithms that can be used in practice. In this thesis we investigate scheduling models with time-lags and release/due dates inspired by two realworld problems: transportation of goods and appointment scheduling for chemotherapy patients. The first part of this thesis studies the minimisation of the maximum lateness for two batch scheduling problems with release/due dates and equal processing times: one with a single machine and one with parallel machines. These theoretical models represent the problem of scheduling the delivery of goods within given time windows using one or more limited capacity vehicles. We design two enhanced polynomial-time algorithms that, for the single machine case, outperform the best algorithms known in literature, and, for the parallel machine case, establish the first solution algorithm. In the second part we investigate the coupled-operation scheduling model with timelags which characterises some important features of the problem of booking treatment appointments for chemotherapy patients. The objective is to develop a solution algorithm that minimises the maximum completion time (makespan). Initially we investigate a possible compact representation of a solution considering the sub-problem with a fixed sequence of the first operations of the jobs. We prove that this special case of the problem is NP-hard in the strong sense even in the case of unit processing times. Then we adapt a technique used for solving job shop problems with no-wait constraints to our coupled operation problem and develop an efficient tabu-search heuristic that outperforms the algorithms known in literature. In the last part, we introduce the problem of booking appointments for chemotherapy treatments in an outpatient clinic which is an example of real-world scheduling problem with complex time-lags and release/due dates constraints. We design an innovative 4-stage approach based on the concept of a multi-level template schedule which is generated solving a number of multi-objective integer linear programs. The evaluation of our approach using historical data shows that, using available resources, 20% additional appointments could be scheduled in the clinic eliminating peaks of workloads, maintaining short waiting days/times and improving the overall patient and staff experience.

Item Type: Thesis (PhD)
Academic Units: The University of Leeds > Faculty of Engineering (Leeds) > School of Computing (Leeds)
Identification Number/EthosID: uk.bl.ethos.578623
Depositing User: Ethos Import
Date Deposited: 29 Apr 2014 11:05
Last Modified: 03 Sep 2014 10:47
URI: http://etheses.whiterose.ac.uk/id/eprint/5788

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)