Integrated scheduling of production and delivery on a single machine with availability constraint

We study the problem of integrated scheduling of production and delivery on a single machine. Because of the availability constraint of the machine, jobs in processing may be interrupted. When the machine becomes available again, the job interrupted can resume or restart processing. The completed jobs are delivered in batches to one customer by vehicles without capacity constraint. The goal is to minimize the sum of total delivery time and total delivery cost. If the interrupted job is resumable, we provide an optimal algorithm with polynomial time. If the interrupted job is non-resumable, we propose an algorithm with the worst-case performance ratio 3/2. Moreover, we show that the problem has a polynomial time approximation scheme (PTAS). (C) 2014 Elsevier B.V. All rights reserved.