Abstract
Network flows and scheduling have been studied intensely, but mostly separately. In many applications a joint optimization model for routing and scheduling is desireable. Therefore, we study flows over time with a demand split into jobs. Our objective is to minimize the weighted sum of completion times of these jobs. This is closely related to preemptive scheduling on a single machine with a processing speed increasing over time. For both, flow scheduling and increasing speed scheduling, we provide an EPTAS. Without release dates we can prove a tight approximation factor of \((\sqrt{3}+1)/2\) for Smith’s rule, by fully characterizing the worst case instances. We give exact algorithms for some special cases and a dynamic program for speed functions with a constant number of speeds. We can prove a competitive ratio of 2 for the online version. We also study the class of blind algorithms, i.e., those which schedule without knowledge of the speed function.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., Sviridenko, M.: Approximation schemes for minimizing average weighted completion time with release dates. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS 1999), pp. 32–44. IEEE, Los Alamitos (1999)
Baumann, N., Skutella, M.: Earliest arrival flows with multiple sources. Mathematics of Operations Research 34, 499–512 (2009)
Epstein, L., Levin, A., Marchetti-Spaccamela, A., Megow, N., Mestre, J., Skutella, M., Stougie, L.: Universal sequencing on a single machine. In: Eisenbrand, F., Shepherd, F.B. (eds.) Integer Programming and Combinatorial Optimization. LNCS, vol. 6080, pp. 230–243. Springer, Heidelberg (2010)
Fleischer, L.: Faster algorithms for the quickest transshipment problem with zero transit times. In: Proceedings of the 9th Annual Symposium on Discrete Algorithms (SODA 1998), pp. 147–156 (1998)
Gale, D.: Transient flows in networks. Michigan Mathematical Journal 6, 59–63 (1959)
Hall, A., Hippler, S., Skutella, M.: Multicommodity flows over time: Efficient algorithms and complexity. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 397–409. Springer, Heidelberg (2003)
Hall, A., Hippler, S., Skutella, M.: Multicommodity flows over time: Efficient algorithms and complexity. Theoretical Computer Science 379, 387–404 (2007)
Hoogeveen, H., Skutella, M., Woeginger, G.J.: Preemptive scheduling with rejection. In: Paterson, M. (ed.) ESA 2000. LNCS, vol. 1879, pp. 268–277. Springer, Heidelberg (2000)
Hoppe, B., Tardos, É.: Polynomial time algorithms for some evacuation problems. In: Proceedings of the 5th Annual Symposium on Discrete Algorithms (SODA 1994), pp. 433–441 (1994)
Labetoulle, J., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Preemptive scheduling of uniform machines subject to release dates. In: Progress in Combinatorial Optimization, pp. 245–261. Academic Press, London (1984)
Meilijson, I., Tamir, A.: Minimizing flow time on parallel identical processors with variable unit processing time. Operations Research 32(2), 440–448 (1984)
Minieka, E.: Maximal, lexicographic, and dynamic network flows. Operations Research 21, 517–527 (1973)
Queyranne, M., Schulz, A.S.: Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speed. In: Balas, E., Clausen, J. (eds.) IPCO 1995. LNCS, vol. 920, pp. 307–320. Springer, Heidelberg (1995)
Schulz, A.S., Skutella, M.: The power of α-points in preemptive single machine scheduling. Journal of Scheduling, 121–133 (2002)
Smith, W.E.: Various optimizers for single-stage production. Naval Research and Logistics Quarterly, 59–66 (1956)
Stiller, S., Wiese, A.: Increasing speed scheduling and flow scheduling. Technical Report 007-2010, Technische Universität Berlin (February 2010)
Wilkinson, W.L.: An algorithm for universal maximal dynamic flows in a network. Operations Research 19, 1602–1612 (1971)
Zadeh, N.: A bad network problem for the simplex method and other minimum cost flow algorithms (1973)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Stiller, S., Wiese, A. (2010). Increasing Speed Scheduling and Flow Scheduling. In: Cheong, O., Chwa, KY., Park, K. (eds) Algorithms and Computation. ISAAC 2010. Lecture Notes in Computer Science, vol 6507. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17514-5_24
Download citation
DOI: https://doi.org/10.1007/978-3-642-17514-5_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17513-8
Online ISBN: 978-3-642-17514-5
eBook Packages: Computer ScienceComputer Science (R0)