The routing open-shop problem on a network: Complexity and approximation |
| |
| Affiliation: | 1. Neonatology and NICU, S. Anna Hospital, Torino Italy;2. Neonatology, Ca’ Foncello Hospital Treviso Italy;3. Department of Pediatrics, University of Torino Italy;1. KU Leuven Institute for Mobility, Belgium;2. KU Leuven, Center for Economics and Corporate Sustainability, Faculty of Economics and Business, Campus Brussels, Belgium;3. Vrije Universiteit Amsterdam, School of Business and Economics, Department of Operations Analytics, the Netherlands;4. KU Leuven, Group T, Department of Mechanical Engineering, Centre for Industrial Management, Belgium |
| |
| 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: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
