کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1141710 | 957085 | 2008 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Approximation algorithm for minimizing total latency in machine scheduling with deliveries Approximation algorithm for minimizing total latency in machine scheduling with deliveries](/preview/png/1141710.png)
We study the problem of minimizing total latency in machine scheduling with deliveries, which is defined as follows. There is a set of nn jobs to be processed by a single machine at a plant, where job JiJi is associated with its processing time and a customer ii located at location ii to which the job is to be delivered. In addition, there is a single uncapacitated delivery vehicle available. All jobs (vehicle) are available for processing (delivery) at time 0. Our aim is to determine the sequence in which the jobs should be processed in the plant, the departure times of the vehicle from the plant, and the routing of the vehicle, so as to minimize the total latency (job delivery time). We present a 6e∼16.309691-approximation algorithm for the problem.
Journal: Discrete Optimization - Volume 5, Issue 1, February 2008, Pages 97–107