Scheduling problems over a network of machines

Zachary Friggstad (), Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour and Yifeng Zhang
Additional contact information
Zachary Friggstad: University of Alberta
Arnoosh Golestanian: University of Alberta
Kamyar Khodamoradi: University of Alberta
Christopher Martin: University of Alberta
Mirmahdi Rahgoshay: University of Alberta
Mohsen Rezapour: K. N. Toosi University of Technology
Mohammad R. Salavatipour: University of Alberta
Yifeng Zhang: University of Alberta

Journal of Scheduling, 2019, vol. 22, issue 2, No 8, 239-253

Abstract: Abstract We consider scheduling problems in which jobs must 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 must 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 starts processing 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 completion time of a job in a schedule is defined as the time it finishes processing on its last machine. The total completion time refers to the sum of completion times of all the 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.

Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-018-0591-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:22:y:2019:i:2:d:10.1007_s10951-018-0591-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-018-0591-z

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().