Takand, Babak (2016) Towards power of preemption on parallel machines. MPhil thesis, University of Greenwich.

Preview

PDF Babak Takand 2016 - secured.pdf - Published Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (575kB) | Preview

Abstract

Classical scheduling models typically fall in either of two categories: those that allow interruption of the processing of jobs, and those that do not. In parallel machine environments, scheduling problems for models which allow parallel processing of jobs are typically easier to solve, in terms of computational requirements, while these models are in the majority of cases associated with an improved quality of solutions.

In this thesis, we focus on one of the notion of preemption, a foundational concept in scheduling, which defines the ability to interrupt the processing of a job and resuming it at a later time, or in the case of multiple processors, on a different machine. Preemptive scheduling is limited to the fact that every job in a preemptive schedule may not be processed by more than one machine at a time. Additionally, we consider the closely related notion of splitting jobs, where jobs can be processed at the same time by multiple processors.

We address the issue of power of preemption and power of splitting, defined as the ratio of the cost function of an optimal non-preemptive schedule over the cost function of an optimal preemptive schedule, and schedule with splitting jobs respectively. For several parallel machine scheduling models we provide new results, in addition to a detailed review of the best known results.

Item Type:	Thesis (MPhil)
Uncontrolled Keywords:	Preemption; machine scheduling; parallel machines; mathematics;
Subjects:	Q Science > QA Mathematics
Faculty / School / Research Centre / Research Group:	Faculty of Engineering & Science > School of Computing & Mathematical Sciences (CMS) Faculty of Engineering & Science
Last Modified:	04 Mar 2022 13:07
URI:	http://gala.gre.ac.uk/id/eprint/23603

Actions (login required)

View Item

Downloads