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