Document Open Access Logo

Scheduling Problems over Network of Machines

Authors Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour, Yifeng Zhang

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.5.pdf
  • Filesize: 0.54 MB
  • 18 pages

Document Identifiers

Author Details

Zachary Friggstad
Arnoosh Golestanian
Kamyar Khodamoradi
Christopher Martin
Mirmahdi Rahgoshay
Mohsen Rezapour
Mohammad R. Salavatipour
Yifeng Zhang

Cite As Get BibTex

Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad R. Salavatipour, and Yifeng Zhang. Scheduling Problems over Network of Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.5

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.

Subject Classification

Keywords
  • approximation algorithms
  • job-shop scheduling
  • min-sum edge coloring
  • minimum latency

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Antonios Antoniadis, Neal Barcelo, Daniel Cole, Kyle Fox, Benjamin Moseley, Michael Nugent, and Kirk Pruhs. Packet forwarding algorithms in a line network. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings, pages 610-621, 2014. URL: http://dx.doi.org/10.1007/978-3-642-54423-1_53.
  2. Nikhil Bansal, Tracy Kimbrel, and Maxim Sviridenko. Job shop scheduling with unit processing times. Math. Oper. Res., 31(2):381-389, 2006. URL: http://dx.doi.org/10.1287/moor.1060.0189.
  3. Sayan Bhattacharya, Janardhan Kulkarni, and Vahab S. Mirrokni. Coordination mechanisms for selfish routing over time on a tree. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 186-197, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_16.
  4. Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, and Kunal Talwar. Paths, trees, and minimum latency tours. In 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings, pages 36-45, 2003. URL: http://dx.doi.org/10.1109/SFCS.2003.1238179.
  5. William J. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver. Combinatorial Optimization. John Wiley &Sons, Inc., New York, NY, USA, 1998. Google Scholar
  6. Uriel Feige and Christian Scheideler. Improved bounds for acyclic job shop scheduling. Combinatorica, 22(3):361-399, 2002. URL: http://dx.doi.org/10.1007/s004930200018.
  7. Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, and Hadas Shachnai. Improved bounds for scheduling conflicting jobs with minsum criteria. ACM Trans. Algorithms, 4(1):11:1-11:20, 2008. URL: http://dx.doi.org/10.1145/1328911.1328922.
  8. Rajiv Gandhi and Julián Mestre. Combinatorial algorithms for data migration to minimize average completion time. Algorithmica, 54(1):54-71, 2009. URL: http://dx.doi.org/10.1007/s00453-007-9118-2.
  9. Magnús M. Halldórsson, Guy Kortsarz, and Maxim Sviridenko. Sum edge coloring of multigraphs via configuration LP. ACM Trans. Algorithms, 7(2):22:1-22:21, 2011. URL: http://dx.doi.org/10.1145/1921659.1921668.
  10. David G. Harris and Aravind Srinivasan. Constraint satisfaction, packet routing, and the lovasz local lemma. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 685-694, 2013. URL: http://dx.doi.org/10.1145/2488608.2488696.
  11. Sungjin Im and Benjamin Moseley. Scheduling in bandwidth constrained tree networks. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, pages 171-180, 2015. URL: http://dx.doi.org/10.1145/2755573.2755576.
  12. Dariusz R. Kowalski, Eyal Nussbaum, Michael Segal, and Vitaly Milyeykovski. Scheduling problems in transportation networks of line topology. Optimization Letters, 8(2):777-799, 2014. URL: http://dx.doi.org/10.1007/s11590-013-0613-x.
  13. Dariusz R. Kowalski, Zeev Nutov, and Michael Segal. Scheduling of vehicles in transportation networks. In Communication Technologies for Vehicles - 4th International Workshop, Nets4Cars/Nets4Trains 2012, Vilnius, Lithuania, April 25-27, 2012. Proceedings, pages 124-136, 2012. URL: http://dx.doi.org/10.1007/978-3-642-29667-3_11.
  14. Frank Thomson Leighton, Bruce M. Maggs, and Satish Rao. Packet routing and job-shop scheduling in O(congestion + dilation) steps. Combinatorica, 14(2):167-186, 1994. URL: http://dx.doi.org/10.1007/BF01215349.
  15. Frank Thomson Leighton, Bruce M. Maggs, and Andréa W. Richa. Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules. Combinatorica, 19(3):375-401, 1999. URL: http://dx.doi.org/10.1007/s004930050061.
  16. Joseph Y.-T. Leung, Tommy W. Tam, and Gilbert H. Young. On-line routing of real-time messages. J. Parallel Distrib. Comput., 34(2):211-217, 1996. URL: http://dx.doi.org/10.1006/jpdc.1996.0057.
  17. Wenhua Li, Maurice Queyranne, Maxim Sviridenko, and Jinjiang Yuan. Approximation algorithms for shop scheduling problems with minsum objective: A correction. J. Scheduling, 9(6):569-570, 2006. URL: http://dx.doi.org/10.1007/s10951-006-8790-4.
  18. Monaldo Mastrolilli and Ola Svensson. Hardness of approximating flow and job shop scheduling problems. J. ACM, 58(5):20:1-20:32, 2011. URL: http://dx.doi.org/10.1145/2027216.2027218.
  19. Britta Peis, Martin Skutella, and Andreas Wiese. Packet routing: Complexity and algorithms. In Approximation and Online Algorithms, 7th International Workshop, WAOA 2009, Copenhagen, Denmark, September 10-11, 2009. Revised Papers, pages 217-228, 2009. URL: http://dx.doi.org/10.1007/978-3-642-12450-1_20.
  20. Britta Peis, Martin Skutella, and Andreas Wiese. Packet routing on the grid. In LATIN 2010: Theoretical Informatics, 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010. Proceedings, pages 120-130, 2010. URL: http://dx.doi.org/10.1007/978-3-642-12200-2_12.
  21. Julius Petersen. Die theorie der regulären graphs. Acta Math., 15:193-220, 1891. URL: http://dx.doi.org/10.1007/BF02392606.
  22. Maurice Queyranne and Maxim Sviridenko. Approximation algorithms for shop scheduling problems with minsum objective. Journal of Scheduling, 5(4):287-305, 2002. URL: http://dx.doi.org/10.1002/jos.96.
  23. Natalia Shakhlevich, Han Hoogeveen, and Michael Pinedo. Minimizing total weighted completion time in a proportionate flow shop. Journal of Scheduling, 1(3):157-168, 1998. URL: http://dx.doi.org/10.1002/(SICI)1099-1425(1998100)1:3<157::AID-JOS12>3.0.CO;2-Y.
  24. F. Bruce Shepherd and Adrian Vetta. The demand matching problem. In Integer Programming and Combinatorial Optimization, 9th International IPCO Conference, Cambridge, MA, USA, May 27-29, 2002, Proceedings, pages 457-474, 2002. URL: http://dx.doi.org/10.1007/3-540-47867-1_32.
  25. David B. Shmoys, Clifford Stein, and Joel Wein. Improved approximation algorithms for shop scheduling problems. SIAM J. Comput., 23(3):617-632, 1994. URL: http://dx.doi.org/10.1137/S009753979222676X.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact