Scheduling bidirectional traffic on a path

DOI10.1007/978-3-662-47672-7_33zbMATH Open1440.90008arXiv1504.07129OpenAlexW2249768568MaRDI QIDQ3448803FDOQ3448803

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

Publication date: 27 October 2015

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

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.

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

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

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)

Cites Work

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

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)