Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
482754 | European Journal of Operational Research | 2006 | 9 Pages |
Abstract
In the routing open-shop problem, jobs are located at nodes of an undirected transportation network, and the machines travel on the network to execute jobs in the open-shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a nonpreemptive schedule that minimizes the makespan. We prove that the problem is NP-hard even on a two-node network with two machines, and even on a two-node network with two jobs and m machines. We develop polynomial-time approximation heuristics and obtain bounds on their approximation performance.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Igor Averbakh, Oded Berman, Ilya Chernykh,