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.

Babak Takand 2016 - secured.pdf - Published Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (575kB) | Preview


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

Actions (login required)

View Item View Item


Downloads per month over past year

View more statistics