Scheduing problems on Stars and Paths Open Access
- Other title
approximation algorithms, flow-shop scheduling, min-sum edge colouring
- Type of item
- Degree grantor
University of Alberta
- Author or creator
- Supervisor and department
Salavatipour, Mohammad R (Computing Science)
- Examining committee member and department
Friggstad, Zachary (Computing Science)
Lin, Guohui (Computing Science)
Department of Computing Science
- Date accepted
- Graduation date
Master of Science
- Degree level
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.
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. 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.
- Citation for previous publication
Friggstad, Zachary, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour, and Yifeng Zhang. ``Scheduling problems over network of machines." APPROX 2017.
- Date Uploaded
- Date Modified
- Audit Status
- Audits have not yet been run on this file.
File format: pdf (PDF/A)
Mime type: application/pdf
File size: 686658
Last modified: 2017:11:08 17:49:50-07:00
Original checksum: 5d817d6a9418a7d8571be61e4d6bde81
Activity of users you follow