Scheduling bidirectional traffic on a path

DOI10.1007/978-3-662-47672-7_33MaRDI QIDQ3448803zbMATH OpenOpenAlexFDO

Authors Y. Disser, Max Klimm, Elisabeth Lübbecke

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.07129

zbMATH Keywords

computational complexityschedulingAPX-hardnessPTASpacket routingbidirectional traffic

Mathematics Subject Classification ID

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

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 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 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.

Recommendations

• On- and offline scheduling of bidirectional traffic
• Train scheduling on a unidirectional path
• scientific article; zbMATH DE number 871903
• Scheduling the two-way traffic on a single-track railway with a siding
• Container vessel scheduling with bi-directional flows

Cites work

• scientific article; zbMATH DE number 1187164 (Why is no real title available?)
• scientific article; zbMATH DE number 3550182 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1754639 (Why is no real title available?)
• scientific article; zbMATH DE number 1445389 (Why is no real title available?)
• A simplified NP-complete satisfiability problem
• Algorithms and Computation
• Complexity results for flow-shop problems with a single server
• Packet forwarding algorithms in a line network
• Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
• Railway track allocation: Models and methods
• Reducibility among combinatorial problems
• Scheduling bidirectional traffic on a path
• Scheduling with batching: A review
• Ship traffic optimization for the Kiel Canal
• The Complexity of Flowshop and Jobshop Scheduling
• Universal packet routing with arbitrary bandwidths and transit times

Cited in

(11)

• Online interval scheduling on two related machines: the power of lookahead
• Complexity, bounds and dynamic programming algorithms for single track train scheduling
• Scheduling bidirectional traffic on a path
• Scheduling of waterways with tide and passing box
• No-wait scheduling for locks
• Traffic-light scheduling on the grid
• Scheduling parallel batching machines in a sequence
• On- and offline scheduling of bidirectional traffic
• Ship traffic optimization for the Kiel Canal
• Minimizing the maximal weighted lateness of delivering orders between two railroad stations
• Two-directional traffic scheduling problem solution for a single-track railway with siding

This page was built for publication: Scheduling bidirectional traffic on a path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448803)