Return to search

Tractability and approximability for subclasses of the makespan problem on unrelated parallel machines

Let there be m parallel machines and n jobs to be scheduled non-preemptively. A job j scheduled on machine i takes p_{i,j} time units to complete, where 1 ≤ i ≤ m and 1 ≤ j ≤ n. For a given schedule, the makespan is the completion time of a machine that finishes last. The goal is to produce a schedule of all n jobs with minimum makespan. This is known as the makespan problem on unrelated parallel machines (UPMs), denoted as R||C_{max}. In this thesis, we focus on subclasses of R||C_{max}. Our research consists of two components. First, a survey of theoretic results for R||C_{max} with a focus on approximation algorithms is presented. Second, we present exact polynomial-time algorithms and approximation algorithms for some subclasses of R||C_{max}. For instance, we present k-approximation algorithms on par with or better than the best known for certain subclasses of R||C_{max}.

Identiferoai:union.ndltd.org:MANITOBA/oai:mspace.lib.umanitoba.ca:1993/23825
Date19 August 2014
CreatorsPage, Daniel
ContributorsLi, Ben (Computer Science), Durocher, Stephane (Computer Science) Cameron, Helen (Computer Science) Gunderson, David (Mathematics)
Source SetsUniversity of Manitoba Canada
Detected LanguageEnglish

Page generated in 0.0019 seconds