- 171 views
- 229 downloads
Scheduing problems on Stars and Paths
-
- Author / Creator
- Golestanian, Arnoosh
-
In this thesis, we consider scheduling problems in which jobs need to be processed through a (shared) network of machines according to their given paths. Formally, we are given a graph $G(V, E)$ where the edges $E$ represent the machines. We are also given a set of jobs $J$ and a path of edges for each of them showing that the job needs to be processed on those edges in that order. Each job can be moved to the next machine only if it has been fully processed by all the previous machines in the path. Moreover, each job takes $1$ unit of time to be processed on each machine and once a machine starts processing a job, it cannot process any other jobs. Our goal is to find a schedule with minimum total completion time. We consider two closely related scheduling problems, Star Scheduling with Unit Processing time (SSUP) and Generalized Path scheduling with Unit processing time (GPUP). As it is clear from their terminology, in SSUP the network of machines is a star and in GPUP it is a path. The most important contribution of this thesis is a $1.796$-approximation for the SSUP problem, described in Chapter 2. To achieve this we partition jobs into smaller subsets, in each subset, the number of jobs that share a machine is less than a specific number which is increasing geometrically. We also prove that for the case that jobs cannot have a delay in the middle of their processing, the problem is APX-hard. In Chapter 3, we consider GPUP problem and prove that in polynomial time one can find a schedule which minimizes the total completion time. Our analysis for the algorithm is new and is much simpler than the previous analysis.
-
- Subjects / Keywords
-
- Graduation date
- Fall 2017
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.