Abstract
We study the fundamental problem of scheduling bidirectional traffic along a path composed of multiple segments. The main feature of the problem is that jobs traveling in the same direction can be scheduled in quick succession on a segment, while jobs in opposing directions cannot cross a segment at the same time. We show that this tradeoff makes the problem significantly harder than the related flow shop problem, by proving that it is \(\mathsf {NP}\)-hard even for identical jobs. We complement this result with a PTAS for a single segment and non-identical jobs. If we allow some pairs of jobs traveling in different directions to cross a segment concurrently, the problem becomes \(\mathsf {APX}\)-hard even on a single segment and with identical jobs. We give polynomial algorithms for the setting with restricted compatibilities between jobs on a single and any constant number of segments, respectively.
M. Klimm and E. Lübbecke—This research was carried out in the framework of Matheon supported by Einstein Foundation Berlin.
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: Proc. 40th Symposium on Foundations of Computer Science (FOCS), pp. 32–43 (1999)
Antoniadis, A., Barcelo, N., Cole, D., Fox, K., Moseley, B., Nugent, M., Pruhs, K.: Packet forwarding algorithms in a line network. In: Pardo, A., Viola, A. (eds.) LATIN 2014. LNCS, vol. 8392, pp. 610–621. Springer, Heidelberg (2014)
Berman, P., Karpinski, M., Scott, A.D.: Approximation hardness of short symmetric instances of MAX-3SAT. Electronic Colloquium on Computational Complexity (ECCC) 10(49) (2003)
Brucker, P., Knust, S., Wang, G.: Complexity results for flow-shop problems with a single server. European J. Oper. Res. 165, 398–407 (2005)
Bundesamt für Seeschifffahrt und Hydrographie (BSH). German Traffic Regulations for Navigable Maritime Waterways. Hamburg and Rostock, Germany (2013)
Chekuri, C., Khanna, S.: A PTAS for minimizing weighted completion time on uniformly related machines. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 848–861. Springer, Heidelberg (2001)
Disser, Y., Klimm, M., Lübbecke, E.: Scheduling bidirectional traffic on a path. arXiv:1504.07129 (2015)
Fishkin, A.V., Jansen, K., Mastrolilli, M.: On minimizing average weighted completion time: A PTAS for the job shop problem with release dates. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 319–328. Springer, Heidelberg (2003)
Garey, M.R., Johnson, D.S.: Computers and intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)
Garey, M.R., Johnson, D.S., Sethi, R.: The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1(2), 117–129 (1976)
Hoogeveen, H., Schuurman, P., Woeginger, G.J.: Non-approximability results for scheduling problems with minsum criteria. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 353–366. Springer, Heidelberg (1998)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations. The IBM Research Symposia Series, pp. 85–103 (1972)
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity. In: Handbooks in Operations Research and Management Science, vol. 4, pp. 445–522 (1993)
Leighton, F.T., Maggs, B.M., Rao, S.B.: Packet routing and job-shop scheduling in \(o\)(congestion+dilation) steps. Combinatorica 14(2), 167–186 (1994)
Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343–362 (1977)
Lübbecke, E., Lübbecke, M.E., Möhring, R.H.: Ship traffic optimization for the Kiel Canal. Technical Report 4681, Optimization. Online 12 (2014)
Lusby, R.M., Larsen, J., Ehrgott, M., Ryan, D.: Railway track allocation: models and methods. OR Spectrum 33(4), 843–883 (2011)
Peis, B., Wiese, A.: Universal packet routing with arbitrary bandwidths and transit times. In: Günlük, O., Woeginger, G.J. (eds.) IPCO 2011. LNCS, vol. 6655, pp. 362–375. Springer, Heidelberg (2011)
Potts, C.N., Kovalyov, M.Y.: Scheduling with batching: A review. European J. Oper. Res. 120(2), 228–249 (2000)
Queyranne, M., Sviridenko, M.: New and improved algorithms for minsum shop scheduling. In: Proc. 11th Symposium on Discrete Algorithms (SODA), pp. 871–878 (2000)
Scheideler, C.: Offline routing protocols. In: Universal Routing Strategies for Interconnection Networks, pp. 57–71 (1998)
Tovey, C.A.: A simplified NP-complete satisfiability problem. Discrete Appl. Math. 8(1), 85–89 (1984)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Disser, Y., Klimm, M., Lübbecke, E. (2015). Scheduling Bidirectional Traffic on a Path. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_33
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)