• search hit 68 of 1103
Back to Result List

Bidirectional Scheduling on a Path

Please always quote using this URN:urn:nbn:de:0296-matheon-12920
  • We study the fundamental problem of scheduling bidirectional traffic across machines arranged on a path. The main feature of the problem is that jobs traveling in the same direction can be scheduled in quick succession on a machine, while jobs in the other direction have to wait for an additional transit time. We show that this tradeoff makes the problem significantly harder than the related flow shop problem, by showing that it is NP-hard even for jobs with identical processing and transit times. We give polynomial algorithms for a single machine and any constant number of machines. In contrast, we show the problem to be NP-hard on a single machine and with identical processing and transit times if some pairs of jobs in different directions are allowed to run on the machine concurrently. We generalize a PTAS of Afrati et al. [1999] for one direction and a single machine to the bidirectional case on any constant number of machines.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Yann Disser, Max Klimm, Elisabeth Lübbecke
URN:urn:nbn:de:0296-matheon-12920
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2014/05/19
Release Date:2014/05/19
Institute:Research Center Matheon
Technische Universität Berlin
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section {04 in that areag 68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) / 68-06 Proceedings, conferences, collections, etc.
Preprint Number:1060
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.