TY - GEN A1 - Disser, Yann A1 - Klimm, Max A1 - Lübbecke, Elisabeth T1 - Bidirectional Scheduling on a Path N2 - 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. Y1 - 2014 UR - https://opus4.kobv.de/opus4-matheon/frontdoor/index/index/docId/1292 UR - https://nbn-resolving.org/urn:nbn:de:0296-matheon-12920 ER -