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).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 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
Allahverdi, A.: The third comprehensive survey on scheduling problems with setup times/costs. Eur. J. Oper. Res. 246(2), 345–378 (2015)
Allahverdi, A., Gupta, J.N., Aldowaisan, T.: A review of scheduling research involving setup considerations. Omega 27(2), 219–239 (1999)
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)
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)
Bansal, N., Cloostermans, B.: Minimizing maximum flow-time on related machines. Theory Comput. 12(1), 1–14 (2016)
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)
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)
Borodin, A., Nielsen, M.N., Rackoff, C.: (Incremental) priority algorithms. Algorithmica 37(4), 295–326 (2003)
Divakaran, S., Saks, M.: An online scheduling problem with job set-ups. Technical report, DIMACS Technical Report (2000)
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)
Hiller, B., Vredeveld, T.: Probabilistic alternatives for competitive analysis. Comput. Sci. - R&D 27(3), 189–196 (2012)
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)
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
Koutsoupias, E., Papadimitriou, C.H.: Beyond competitive analysis. SIAM J. Comput. 30(1), 300–317 (2000)
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
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
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
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
Monma, C.L., Potts, C.N.: On the complexity of scheduling with batch setup times. Oper. Res. 37(5), 798–804 (1989)
Motwani, R., Phillips, S., Torng, E.: Non-clairvoyant scheduling. Theor. Comput. Sci. 130(1), 17–47 (1994)
Potts, C.N.: Scheduling two job classes on a single machine. Comput. OR 18(5), 411–415 (1991)
Sahney, V.K.: Single-server, two-machine sequencing with switching time. Oper. Res. 20(1), 24–36 (1972)
Schäfer, G., Sivadasan, N.: Topology matters: smoothed competitiveness of metrical task systems. Theor. Comput. Sci. 341(1–3), 216–246 (2005)
Scharbrodt, M., Schickinger, T., Steger, A.: A new average case analysis for completion time scheduling. J. ACM 53(1), 121–146 (2006)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
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)