| Article ID: | iaor20163737 |
| Volume: | 10 |
| Issue: | 8 |
| Start Page Number: | 1645 |
| End Page Number: | 1656 |
| Publication Date: | Dec 2016 |
| Journal: | Optimization Letters |
| Authors: | Xu Yinfeng, Lin Guohui, Hu Jueliang, Dong Jianming, Luo Taibo, Su Xiaotong, Tong Weitian, Goebel Randy |
| Keywords: | production, scheduling, combinatorial optimization, maintenance, repair & replacement, vehicle routing & scheduling |
We investigate a scheduling problem with job delivery coordination in which the machine has a maintenance time interval. The goal is to minimize the makespan. In the problem, each job needs to be processed on the machine non‐preemptively for a certain time, and then transported to a distribution center, by one vehicle with a limited physical capacity. We present a 2‐approximation algorithm for the problem, and show that the performance ratio is tight.