IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v22y2019i2d10.1007_s10951-018-0591-z.html
   My bibliography  Save this article

Scheduling problems over a network of machines

Author

Listed:
  • 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)

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.

Suggested Citation

  • Zachary Friggstad & Arnoosh Golestanian & Kamyar Khodamoradi & Christopher Martin & Mirmahdi Rahgoshay & Mohsen Rezapour & Mohammad R. Salavatipour & Yifeng Zhang, 2019. "Scheduling problems over a network of machines," Journal of Scheduling, Springer, vol. 22(2), pages 239-253, April.
    • Handle: RePEc:spr:jsched:v:22:y:2019:i:2:d:10.1007_s10951-018-0591-z
    DOI: 10.1007/s10951-018-0591-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-018-0591-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10951-018-0591-z?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Nikhil Bansal & Tracy Kimbrel & Maxim Sviridenko, 2006. "Job Shop Scheduling with Unit Processing Times," Mathematics of Operations Research, INFORMS, vol. 31(2), pages 381-389, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Klaus Heeger & Danny Hermelin & George B. Mertzios & Hendrik Molter & Rolf Niedermeier & Dvir Shabtay, 2023. "Equitable scheduling on a single machine," Journal of Scheduling, Springer, vol. 26(2), pages 209-225, April.
    2. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.
    3. S. Sevastyanov & D. Chemisova & I. Chernykh, 2014. "On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion," Annals of Operations Research, Springer, vol. 213(1), pages 253-270, February.
    4. Oron, Daniel & Shabtay, Dvir & Steiner, George, 2015. "Single machine scheduling with two competing agents and equal job processing times," European Journal of Operational Research, Elsevier, vol. 244(1), pages 86-99.
    5. Omri Dover & Dvir Shabtay, 2016. "Single machine scheduling with two competing agents, arbitrary release dates and unit processing times," Annals of Operations Research, Springer, vol. 238(1), pages 145-178, March.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jsched:v:22:y:2019:i:2:d:10.1007_s10951-018-0591-z. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.