Document Open Access Logo

Maximizing Throughput in Flow Shop Real-Time Scheduling

Authors Lior Ben Yamin, Jing Li, Kanthi Sarpatwar , Baruch Schieber, Hadas Shachnai

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.48.pdf
  • Filesize: 0.55 MB
  • 18 pages

Document Identifiers

Author Details

Lior Ben Yamin
  • Computer Science Department, Technion, Haifa, Israel
Jing Li
  • Department of Computer Science, New Jersey Institute of Technology, Newark, NJ, USA
Kanthi Sarpatwar
  • IBM T. J. Watson Research Center, Yorktown Heights, NY, USA
Baruch Schieber
  • Department of Computer Science, New Jersey Institute of Technology, Newark, NJ, USA
Hadas Shachnai
  • Computer Science Department, Technion, Haifa, Israel

Funding

  • Li, Jing: Supported by NSF CNS-1948457.

Cite As Get BibTex

Lior Ben Yamin, Jing Li, Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai. Maximizing Throughput in Flow Shop Real-Time Scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.48

Abstract

We consider scheduling real-time jobs in the classic flow shop model. The input is a set of n jobs, each consisting of m segments to be processed on m machines in the specified order, such that segment I_i of a job can start processing on machine M_i only after segment I_{i-1} of the same job completed processing on machine M_{i-1}, for 2 ≤ i ≤ m. Each job also has a release time, a due date, and a weight. The objective is to maximize the throughput (or, profit) of the n jobs, i.e., to find a subset of the jobs that have the maximum total weight and can complete processing on the m machines within their time windows. This problem has numerous real-life applications ranging from manufacturing to cloud and embedded computing platforms, already in the special case where m = 2. Previous work in the flow shop model has focused on makespan, flow time, or tardiness objectives. However, little is known for the flow shop model in the real-time setting. In this work, we give the first nontrivial results for this problem and present a pseudo-polynomial time (2m+1)-approximation algorithm for the problem on m ≥ 2 machines, where m is a constant. This ratio is essentially tight due to a hardness result of Ω(m/(log m)) for the approximation ratio. We further give a polynomial-time algorithm for the two-machine case, with an approximation ratio of (9+ε) where ε = O(1/n). We obtain better bounds for some restricted subclasses of inputs with two machines. To the best of our knowledge, this fundamental problem of throughput maximization in the flow shop scheduling model is studied here for the first time.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
  • Theory of computation → Scheduling algorithms
Keywords
  • Flow shop
  • real-time scheduling
  • throughput maximization
  • approximation algorithms

Metrics

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

References

  1. Kunal Agrawal, Jing Li, Kefu Lu, and Benjamin Moseley. Scheduling parallelizable jobs online to maximize throughput. In Latin American Symposium on Theoretical Informatics, pages 755-776. Springer, 2018. Google Scholar
  2. Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Baruch Schieber, and Cliff Stein. Non-preemptive min-sum scheduling with resource augmentation. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 614-624. IEEE, 2007. Google Scholar
  3. Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. A unified approach to approximating resource allocation and scheduling. J. ACM, 48(5):1069-1090, 2001. Google Scholar
  4. Amotz Bar-Noy, Sudipto Guha, Joseph Naor, and Baruch Schieber. Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput., 31(2):331-352, 2001. Google Scholar
  5. Reuven Bar-Yehuda, Magnús M Halldórsson, Joseph Naor, Hadas Shachnai, and Irina Shapira. Scheduling split intervals. SIAM Journal on Computing, 36(1):1-15, 2006. Google Scholar
  6. Michael G Bechtel, Elise McEllhiney, Minje Kim, and Heechul Yun. Deeppicar: A low-cost deep neural network-based autonomous car. In RTCSA, pages 11-21, 2018. Google Scholar
  7. Bo Chen, Chris N Potts, and Gerhard J Woeginger. A review of machine scheduling: Complexity, algorithms and approximability. In Handbook of combinatorial optimization, pages 1493-1641. Springer, 1998. Google Scholar
  8. Byung-Cheon Choi and Suk-Hun Yoon. Maximizing the weighted number of just-in-time jobs in flow shop scheduling. Journal of Scheduling, 10(4-5):237-243, 2007. Google Scholar
  9. Julia Chuzhoy, Rafail Ostrovsky, and Yuval Rabani. Approximation algorithms for the job interval selection problem and related scheduling problems. Mathematics of Operations Research, 31(4):730-738, 2006. Google Scholar
  10. Amir Elalouf, Eugene Levner, and Huajun Tang. An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem. Journal of Scheduling, 16(4):429-435, 2013. Google Scholar
  11. Michael R Garey and David S Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  12. Michael R Garey, David S Johnson, and Ravi Sethi. The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 1(2):117-129, 1976. Google Scholar
  13. Leslie A. Hall. Approximability of flow shop scheduling. Math. Program., 82:175-190, 1998. Google Scholar
  14. Elad Hazan, Shmuel Safra, and Oded Schwartz. On the complexity of approximating k-dimensional matching. In Proceedings of APPROX, pages 83-97. Springer, 2003. Google Scholar
  15. Sungjin Im, Shi Li, Benjamin Moseley, and Eric Torng. A dynamic programming framework for non-preemptive scheduling problems on multiple machines. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1070-1086. SIAM, 2014. Google Scholar
  16. Selmer Martin Johnson. Optimal two-and three-stage production schedules with setup times included. Naval research logistics quarterly, 1(1):61-68, 1954. Google Scholar
  17. Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. Journal of the ACM (JACM), 47(4):617-643, 2000. Google Scholar
  18. Monaldo Mastrolilli and Ola Svensson. Hardness of approximating flow and job shop scheduling problems. Journal of the ACM (JACM), 58(5):20, 2011. Google Scholar
  19. J Michael Moore. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management science, 15(1):102-109, 1968. Google Scholar
  20. Viswanath Nagarajan and Maxim Sviridenko. Tight bounds for permutation flow shop scheduling. Mathematics of Operations Research, 34(2):417-427, 2009. Google Scholar
  21. Sartaj K Sahni. Algorithms for scheduling independent tasks. Journal of the ACM (JACM), 23(1):116-127, 1976. Google Scholar
  22. Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM J. Discrete Math., 8(2):223-250, 1995. Google Scholar
  23. Dvir Shabtay and Yaron Bensoussan. Maximizing the weighted number of just-in-time jobs in several two-machine scheduling systems. Journal of Scheduling, 15(1):39-47, 2012. Google Scholar
  24. Maxim Sviridenko. A note on permutation flow shop problem. Annals of Operations Research, 129(1-4):247-252, 2004. Google Scholar
  25. Gerhard J Woeginger. On-line scheduling of jobs with fixed start and end times. Theoretical Computer Science, 130(1):5-16, 1994. Google Scholar
  26. Yiyong Xiao, Siyue Zhang, Pei Yang, Meng You, and Jiaoying Huang. A two-stage flow-shop scheme for the multi-satellite observation and data-downlink scheduling problem considering weather uncertainties. Reliability Engineering & System Safety, 188:263-275, 2019. Google Scholar
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