| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427302 | Information Processing Letters | 2011 | 8 Pages |
We study a scheduling problem that integrates parallel-batch production with family jobs and job delivery at the same time. The jobs are first processed on an unbounded parallel-batch machine and then delivered in batches to their specified customers by a transportation vehicle. We assume that jobs from different families (customers) cannot be processed together by the batch machine and also transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We first show that the problem is NPNP-hard, and then propose for it a heuristic algorithm with a worst-case performance ratio of 3/2.
► Parallel-batch production with family jobs and job delivery is considered. ► The problem is proved to be NPNP-hard. ► A 3/2-approximation algorithm is presented. ► The bound 3/2 is shown to be tight.
