Scheduling tasks with preemptions and precedence constraints on identical parallel machines to minimise the maximum lateness

Walker, Samuel James

Scheduling tasks with preemptions and precedence constraints on identical parallel machines to minimise the maximum lateness

Walker, Samuel James

Permalink

Publication Type:: Thesis
Issue Date:: 2016

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download contents and abstractAdobe PDF (78.76 kB)

Adobe PDF

Download thesisAdobe PDF (1.22 MB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Walker, Samuel James
dc.date.accessioned	2016-09-21T01:27:24Z
dc.date.available	2016-09-21T01:27:24Z
dc.date.issued	2016
dc.identifier.uri	http://hdl.handle.net/10453/52943
dc.description	University of Technology Sydney. Faculty of Science.	en_AU
dc.description.abstract	This work examines in depth a collection of related scheduling problems. The problems considered all relate to the processing of tasks on machines over time, with the goal of minimising some function of the tasks’ completion times. The tasks being scheduled are subject to preemptions, that is they may be interrupted during their processing and resumed later on the same or a different set of machines. The tasks are subject to precedence constraints, meaning some tasks cannot be processed until others have been completed. The machines on which the tasks are processed are identical, meaning they have the same speed and functionality, and parallel, in contrast to scheduling models where tasks must be processed on multiple machines sequentially. This is a thoroughly investigated area of research in the literature. Due to the computational complexity of the problems considered, approximation algorithms for these problems are presented and are analysed in several ways. Several well known results are expanded to apply to more general scheduling problems, and a completely new class of results is described. In particular, the solvable cases of some approximation algorithms – i.e. the situations under which the algorithms provide an optimal solution to the considered problem – are examined in more detail than heretofore. Bounds on the worst case of the considered algorithms are also presented, as are results regarding the computational complexity of certain subproblems. The goal of this work is to advance the understanding of this focused but significant area of research, and present a wide variety of results relating to it.	en_AU
dc.format	Thesis (PhD)
dc.language.iso	en_AU	en_AU
dc.relation	https://opus.lib.uts.edu.au/bitstream/10453/52943/2/02whole.pdf
dc.rights	The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
dc.rights	au.edu.uts.lib/ppc
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Related scheduling problems.	en
dc.subject	Identical parallel machines.	en
dc.subject	Scheduling tasks.	en
dc.subject	Subject to preemptions tasks.	en
dc.subject	Precedence constraints tasks.	en
dc.subject	Approximation algorithms.	en
dc.title	Scheduling tasks with preemptions and precedence constraints on identical parallel machines to minimise the maximum lateness	en_AU
dc.type	Thesis	en_AU
utslib.copyright.status	open_access

Abstract:

This work examines in depth a collection of related scheduling problems. The problems considered all relate to the processing of tasks on machines over time, with the goal of minimising some function of the tasks’ completion times. The tasks being scheduled are subject to preemptions, that is they may be interrupted during their processing and resumed later on the same or a different set of machines. The tasks are subject to precedence constraints, meaning some tasks cannot be processed until others have been completed. The machines on which the tasks are processed are identical, meaning they have the same speed and functionality, and parallel, in contrast to scheduling models where tasks must be processed on multiple machines sequentially. This is a thoroughly investigated area of research in the literature. Due to the computational complexity of the problems considered, approximation algorithms for these problems are presented and are analysed in several ways. Several well known results are expanded to apply to more general scheduling problems, and a completely new class of results is described. In particular, the solvable cases of some approximation algorithms – i.e. the situations under which the algorithms provide an optimal solution to the considered problem – are examined in more detail than heretofore. Bounds on the worst case of the considered algorithms are also presented, as are results regarding the computational complexity of certain subproblems. The goal of this work is to advance the understanding of this focused but significant area of research, and present a wide variety of results relating to it.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/52943