Skip to main content
Springer Nature Link
Log in

Non-clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times

  • Conference paper
  • First Online:
Approximation and Online Algorithms (WAOA 2017)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 10787))

Included in the following conference series:

Abstract

Consider a problem in which n jobs that are classified into k types arrive over time at their release times and are to be scheduled on a single machine so as to minimize the maximum flow time. The machine requires a setup taking s time units whenever it switches from processing jobs of one type to jobs of a different type. We consider the problem as an online problem where each job is only known to the scheduler as soon as it arrives and where the processing time of a job only becomes known upon its completion (non-clairvoyance).

We are interested in the potential of simple “greedy-like” algorithms. We analyze a modification of the FIFO strategy and show its competitiveness to be \(\varTheta (\sqrt{n})\), which is optimal for the considered class of algorithms. For \(k=2\) types it achieves a constant competitiveness. Our main insight is obtained by an analysis of the smoothed competitiveness. If processing times \(p_j\) are independently perturbed to \(\hat{p}_j = (1+X_j)p_j\), we obtain a competitiveness of \(O(\sigma ^{-2} \log ^2 n)\) when \(X_j\) is drawn from a uniform or a (truncated) normal distribution with standard deviation \(\sigma \). The result proves that bad instances are fragile and “practically” one might expect a much better performance than given by the \(\varOmega (\sqrt{n})\)-bound.

This work was partially supported by the German Research Foundation (DFG) within the Collaborative Research Centre “On-The-Fly Computing” (SFB 901).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 39.99
Price excludes VAT (USA)
Softcover Book
USD 54.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    A variant of this algorithm with a fixed \(\lambda \) and hence without Step (3) has been previously mentioned in [10] as an algorithm with \(\varOmega (n)\)-competitiveness for the clairvoyant variant of our problem.

References

  1. Allahverdi, A.: The third comprehensive survey on scheduling problems with setup times/costs. Eur. J. Oper. Res. 246(2), 345–378 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  2. Allahverdi, A., Gupta, J.N., Aldowaisan, T.: A review of scheduling research involving setup considerations. Omega 27(2), 219–239 (1999)

    Article  Google Scholar 

  3. Allahverdi, A., Ng, C.T., Cheng, T.C.E., Kovalyov, M.Y.: A survey of scheduling problems with setup times or costs. Eur. J. Oper. Res. 187(3), 985–1032 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  4. Anand, S., Bringmann, K., Friedrich, T., Garg, N., Kumar, A.: Minimizing maximum (weighted) flow-time on related and unrelated machines. Algorithmica 77(2), 515–536 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bansal, N., Cloostermans, B.: Minimizing maximum flow-time on related machines. Theory Comput. 12(1), 1–14 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  6. Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Schäfer, G., Vredeveld, T.: Average-case and smoothed competitive analysis of the multilevel feedback algorithm. Math. Oper. Res. 31(1), 85–108 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bender, M.A., Chakrabarti, S., Muthukrishnan, S.: Flow and stretch metrics for scheduling continuous job streams. In: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1998), pp. 270–279. ACM/SIAM (1998)

    Google Scholar 

  8. Borodin, A., Nielsen, M.N., Rackoff, C.: (Incremental) priority algorithms. Algorithmica 37(4), 295–326 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  9. Divakaran, S., Saks, M.: An online scheduling problem with job set-ups. Technical report, DIMACS Technical Report (2000)

    Google Scholar 

  10. Divakaran, S., Saks, M.E.: An online algorithm for a problem in scheduling with set-ups and release times. Algorithmica 60(2), 301–315 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  11. Hiller, B., Vredeveld, T.: Probabilistic alternatives for competitive analysis. Comput. Sci. - R&D 27(3), 189–196 (2012)

    Google Scholar 

  12. Hofri, M., Ross, K.W.: On the optimal control of two queues with server setup times and its analysis. SIAM J. Comput. 16(2), 399–420 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  13. Jansen, K., Land, F.: Non-preemptive scheduling with setup times: a PTAS. In: Dutot, P.-F., Trystram, D. (eds.) Euro-Par 2016. LNCS, vol. 9833, pp. 159–170. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-43659-3_12

    Google Scholar 

  14. Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM J. Comput. 30(1), 300–317 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  15. López-Ortiz, A.: Alternative performance measures in online algorithms. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms, pp. 67–72. Springer, Heidelberg (2016). https://doi.org/10.1007/978-1-4939-2864-4_13

    Chapter  Google Scholar 

  16. Mäcker, A., Malatyali, M., Meyer auf der Heide, F., Riechers, S.: Non-preemptive scheduling on machines with setup times. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 542–553. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21840-3_45

    Chapter  Google Scholar 

  17. Mäcker, A., Malatyali, M., Meyer auf der Heide, F., Riechers, S.: Non-clairvoyant scheduling to minimize max flow time on a machine with setup times. CoRR (2017). 1709.05896

  18. Mastrolilli, M.: Scheduling to minimize max flow time: offline and online algorithms. In: Lingas, A., Nilsson, B.J. (eds.) FCT 2003. LNCS, vol. 2751, pp. 49–60. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45077-1_6

    Chapter  Google Scholar 

  19. Monma, C.L., Potts, C.N.: On the complexity of scheduling with batch setup times. Oper. Res. 37(5), 798–804 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  20. Motwani, R., Phillips, S., Torng, E.: Non-clairvoyant scheduling. Theor. Comput. Sci. 130(1), 17–47 (1994)

    Article  MATH  Google Scholar 

  21. Potts, C.N.: Scheduling two job classes on a single machine. Comput. OR 18(5), 411–415 (1991)

    Article  MATH  Google Scholar 

  22. Sahney, V.K.: Single-server, two-machine sequencing with switching time. Oper. Res. 20(1), 24–36 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  23. Schäfer, G., Sivadasan, N.: Topology matters: smoothed competitiveness of metrical task systems. Theor. Comput. Sci. 341(1–3), 216–246 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  24. Scharbrodt, M., Schickinger, T., Steger, A.: A new average case analysis for completion time scheduling. J. ACM 53(1), 121–146 (2006)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Heinz Nixdorf Institute, Paderborn University, Paderborn, Germany

    Alexander Mäcker, Manuel Malatyali, Friedhelm Meyer auf der Heide & Sören Riechers

Authors
  1. Alexander Mäcker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Manuel Malatyali
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Friedhelm Meyer auf der Heide
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sören Riechers
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alexander Mäcker .

Editor information

Editors and Affiliations

  1. The University of Western Ontario, London, Ontario, Canada

    Roberto Solis-Oba

  2. German University of Technology in Oman, Muscat, Oman

    Rudolf Fleischer

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG, part of Springer Nature

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Mäcker, A., Malatyali, M., Meyer auf der Heide, F., Riechers, S. (2018). Non-clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times. In: Solis-Oba, R., Fleischer, R. (eds) Approximation and Online Algorithms. WAOA 2017. Lecture Notes in Computer Science(), vol 10787. Springer, Cham. https://doi.org/10.1007/978-3-319-89441-6_16

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-89441-6_16

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-89440-9

  • Online ISBN: 978-3-319-89441-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation