Name
Title | ||
|---|---|---|
Approximation algorithms for the single-machine scheduling with a period of maintenance. |
Abstract | ||
|---|---|---|
We consider a single machine scheduling problem of minimizing total completion time subject to a period of maintenance, and design an \(O(nlogn)\) time algorithm with a tight performance ratio of \(17/15\). Then, we study an integrated production and distribution problem, in which jobs are delivered by one vehicle to a customer after they are completed on a single machine with a period of maintenance. The objective is to minimize total delivery time of the jobs. We develop a \(3/2\)-approximation algorithm with \(O(n^{3})\) time complexity. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s11590-015-0881-8 | Optimization Letters |
Keywords | Field | DocType |
Scheduling, Completion time, Delivery time, Maintenance, Algorithm | Approximation algorithm,Mathematical optimization,Single-machine scheduling,Performance ratio,Scheduling (computing),Computer science,Time complexity | Journal |
Volume | Issue | ISSN |
10 | 3 | 1862-4480 |
Citations | PageRank | References |
0 | 0.34 | 17 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ganggang Li | 1 | 0 | 0.68 |
| Xiwen Lu | 2 | 182 | 21.03 |