Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
482981 | European Journal of Operational Research | 2007 | 16 Pages |
Abstract
This paper examines two scheduling problems with job delivery coordination, in which each job demands different amount of storage space during transportation. For the first problem, in which jobs are processed on a single machine and delivered by one vehicle to a customer, we present a best possible approximation algorithm with a worst-case ratio arbitrarily close to 3/2. For the second problem, which differs from the first problem in that jobs are processed by two parallel machines, we give an improved algorithm with a worst-case ratio 5/3.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Weiya Zhong, György Dósa, Zhiyi Tan,