Towards power of preemption on parallel machines

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.

Level dc:type.qualificationlevel

mphil

Grantor dc:publisher.institution

University of Greenwich

Year dc:date.issued

2016

Author dc:creator

• Takand, Babak

Advisors dc:contributor.advisor

• Strusevich, Vitaly
• Soper, Alan

• QA Mathematics

Language dc:language

en