Name
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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.ejor.2005.01.034 | European Journal of Operational Research |
Keywords | Field | DocType |
Heuristics,Scheduling,Approximation | Open shop,Flow network,Mathematical optimization,Job shop scheduling,Network complexity,Scheduling (computing),Job shop,Heuristics,Time complexity,Mathematics,Operations management | Journal |
Volume | Issue | ISSN |
173 | 2 | 0377-2217 |
Citations | PageRank | References |
9 | 0.70 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Igor Averbakh | 1 | 699 | 54.76 |
| O. Berman | 2 | 1604 | 231.36 |
| Ilya Chernykh | 3 | 21 | 4.68 |