License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.5
URN: urn:nbn:de:0030-drops-75547
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7554/
Friggstad, Zachary ;
Golestanian, Arnoosh ;
Khodamoradi, Kamyar ;
Martin, Christopher ;
Rahgoshay, Mirmahdi ;
Rezapour, Mohsen ;
Salavatipour, Mohammad R. ;
Zhang, Yifeng
Scheduling Problems over Network of Machines
Abstract
We consider scheduling problems in which jobs need to be processed through a (shared) network of machines. The network is given in the form of a graph the edges of which represent the machines. We are also given a set of jobs, each specified by its processing time and a path in the graph. Every job needs to be processed in the order of edges specified by its path. We assume that jobs can wait between machines and preemption is not allowed; that is, once a job is started being processed on a machine, it must be completed without interruption. Every machine can only process one job at a time.
The makespan of a schedule is the earliest time by which all the jobs have finished processing. The flow time (a.k.a. the completion time) of a job in a schedule is the difference in time between when it finishes processing on its last machine and when the it begins processing on its first machine. The total flow time (or the sum of completion times) is the sum of flow times (or completion times) of all jobs. Our focus is on finding schedules with the minimum sum of completion times or minimum makespan.
In this paper, we develop several algorithms (both approximate and exact) for the problem both on general graphs and when the underlying graph of machines is a tree. Even in the very special case when the underlying network is a simple star, the problem is very interesting as it models a biprocessor scheduling with applications to data migration.
BibTeX - Entry
@InProceedings{friggstad_et_al:LIPIcs:2017:7554,
author = {Zachary Friggstad and Arnoosh Golestanian and Kamyar Khodamoradi and Christopher Martin and Mirmahdi Rahgoshay and Mohsen Rezapour and Mohammad R. Salavatipour and Yifeng Zhang},
title = {{Scheduling Problems over Network of Machines}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
pages = {5:1--5:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-044-6},
ISSN = {1868-8969},
year = {2017},
volume = {81},
editor = {Klaus Jansen and Jos{\'e} D. P. Rolim and David Williamson and Santosh S. Vempala},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7554},
URN = {urn:nbn:de:0030-drops-75547},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.5},
annote = {Keywords: approximation algorithms, job-shop scheduling, min-sum edge coloring, minimum latency}
}
|
Keywords: |
|
approximation algorithms, job-shop scheduling, min-sum edge coloring, minimum latency |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
11.08.2017 |
