Skip navigation

Towards power of preemption on parallel machines

Towards power of preemption on parallel machines

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

[img]
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 / Department / Research Group: Faculty of Architecture, Computing & Humanities
Faculty of Architecture, Computing & Humanities > Department of Mathematical Sciences
Last Modified: 16 Apr 2019 10:35
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
Selected for GREAT 2019: None
URI: http://gala.gre.ac.uk/id/eprint/23603

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics