×

Scheduling bidirectional traffic on a path. (English) Zbl 1440.90008

Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 406-418 (2015).
Summary: 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.
For the entire collection see [Zbl 1316.68014].

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] 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)
[2] Antoniadis, A.; Barcelo, N.; Cole, D.; Fox, K.; Moseley, B.; Nugent, M.; Pruhs, K.; Pardo, A.; Viola, A., Packet forwarding algorithms in a line network, LATIN 2014: Theoretical Informatics, 610-621 (2014), Heidelberg: Springer, Heidelberg · Zbl 1405.68022 · doi:10.1007/978-3-642-54423-1_53
[3] 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)
[4] Brucker, P.; Knust, S.; Wang, G., Complexity results for flow-shop problems with a single server, European J. Oper. Res., 165, 398-407 (2005) · Zbl 1066.90024 · doi:10.1016/j.ejor.2004.04.010
[5] Bundesamt für Seeschifffahrt und Hydrographie (BSH). German Traffic Regulations for Navigable Maritime Waterways. Hamburg and Rostock, Germany (2013)
[6] Chekuri, C.; Khanna, S.; Orejas, F.; Spirakis, PG; van Leeuwen, J., A PTAS for minimizing weighted completion time on uniformly related machines, Automata, Languages and Programming, 848-861 (2001), Heidelberg: Springer, Heidelberg · Zbl 0986.68503 · doi:10.1007/3-540-48224-5_69
[7] Disser, Y., Klimm, M., Lübbecke, E.: Scheduling bidirectional traffic on a path. arXiv:1504.07129 (2015) · Zbl 1440.90008
[8] Fishkin, AV; Jansen, K.; Mastrolilli, M.; Ibaraki, T.; Katoh, N.; Ono, H., On minimizing average weighted completion time: A PTAS for the job shop problem with release dates, Algorithms and Computation, 319-328 (2003), Heidelberg: Springer, Heidelberg · Zbl 1205.90122 · doi:10.1007/978-3-540-24587-2_34
[9] Garey, MR; Johnson, DS, Computers and intractability: A Guide to the Theory of NP-Completeness (1979), New York: W.H. Freeman & Co., New York · Zbl 0411.68039
[10] Garey, MR; Johnson, DS; Sethi, R., The complexity of flowshop and jobshop scheduling, Math. Oper. Res., 1, 2, 117-129 (1976) · Zbl 0396.90041 · doi:10.1287/moor.1.2.117
[11] Hoogeveen, H.; Schuurman, P.; Woeginger, GJ; Bixby, RE; Boyd, EA; Ríos-Mercado, RZ, Non-approximability results for scheduling problems with minsum criteria, Integer Programming and Combinatorial Optimization, 353-366 (1998), Heidelberg: Springer, Heidelberg · Zbl 0911.90208 · doi:10.1007/3-540-69346-7_27
[12] 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) · Zbl 1467.68065
[13] 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)
[14] 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) · Zbl 0811.68062
[15] Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343-362 (1977) · Zbl 0353.68067
[16] 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) · Zbl 1444.90029
[17] Lusby, RM; Larsen, J.; Ehrgott, M.; Ryan, D., Railway track allocation: models and methods, OR Spectrum, 33, 4, 843-883 (2011) · Zbl 1229.90037 · doi:10.1007/s00291-009-0189-0
[18] Peis, B.; Wiese, A.; Günlük, O.; Woeginger, GJ, Universal packet routing with arbitrary bandwidths and transit times, Integer Programming and Combinatoral Optimization, 362-375 (2011), Heidelberg: Springer, Heidelberg · Zbl 1341.68007 · doi:10.1007/978-3-642-20807-2_29
[19] Potts, CN; Kovalyov, MY, Scheduling with batching: A review, European J. Oper. Res., 120, 2, 228-249 (2000) · Zbl 0953.90028 · doi:10.1016/S0377-2217(99)00153-8
[20] Queyranne, M., Sviridenko, M.: New and improved algorithms for minsum shop scheduling. In: Proc. 11th Symposium on Discrete Algorithms (SODA), pp. 871-878 (2000) · Zbl 0952.90013
[21] Scheideler, C.: Offline routing protocols. In: Universal Routing Strategies for Interconnection Networks, pp. 57-71 (1998)
[22] Tovey, CA, A simplified NP-complete satisfiability problem, Discrete Appl. Math., 8, 1, 85-89 (1984) · Zbl 0534.68028 · doi:10.1016/0166-218X(84)90081-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.