Show simple item record

dc.contributor.supervisor Li, Ben (Computer Science) en_US
dc.contributor.author Page, Daniel
dc.date.accessioned 2014-08-19T17:29:03Z
dc.date.available 2014-08-19T17:29:03Z
dc.date.issued 2014-08-19
dc.identifier.uri http://hdl.handle.net/1993/23825
dc.description.abstract 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}. en_US
dc.subject theoretical computer science en_US
dc.subject approximation algorithms en_US
dc.subject algorithms en_US
dc.subject combinatorial optimization en_US
dc.subject computational complexity theory en_US
dc.subject makespan problem en_US
dc.subject scheduling en_US
dc.subject unrelated parallel machines en_US
dc.title Tractability and approximability for subclasses of the makespan problem on unrelated parallel machines en_US
dc.degree.discipline Computer Science en_US
dc.contributor.examiningcommittee Durocher, Stephane (Computer Science) Cameron, Helen (Computer Science) Gunderson, David (Mathematics) en_US
dc.degree.level Master of Science (M.Sc.) en_US
dc.description.note October 2014 en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

View Statistics