Tractability and approximability for subclasses of the makespan problem on unrelated parallel machines
| dc.contributor.author | Page, Daniel | |
| dc.contributor.examiningcommittee | Durocher, Stephane (Computer Science) Cameron, Helen (Computer Science) Gunderson, David (Mathematics) | en_US |
| dc.contributor.supervisor | Li, Ben (Computer Science) | en_US |
| dc.date.accessioned | 2014-08-19T17:29:03Z | |
| dc.date.available | 2014-08-19T17:29:03Z | |
| dc.date.issued | 2014-08-19 | |
| dc.degree.discipline | Computer Science | en_US |
| dc.degree.level | Master of Science (M.Sc.) | en_US |
| 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.description.note | October 2014 | en_US |
| dc.identifier.uri | http://hdl.handle.net/1993/23825 | |
| dc.language.iso | eng | en_US |
| dc.rights | open access | 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.type | master thesis | en_US |