Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875960 | Theoretical Computer Science | 2016 | 21 Pages |
Abstract
In this paper, we consider the two-stage scheduling problem in which n jobs are first processed on m identical machines at a manufacturing facility and then delivered to their customers by one vehicle which can deliver one job at each shipment. In the problem, a set of n delivery times is given in advance, and in a schedule, the n delivery times should be assigned to the n jobs, respectively. The objective is to minimize the maximum delivery completion time, i.e., the time when all jobs are delivered to their respective customers and the vehicle returns to the facility. For this problem, we present a 32-approximation algorithm and a polynomial-time approximation scheme.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Youjun Chen, Lingfa Lu, Jinjiang Yuan,