An improved lower bound for a bi-criteria scheduling problem |
| |
Authors: | Jin Yan |
| |
Affiliation: | School of Mathematics and Systems Sciences, Shandong University, Jinan 250100, China |
| |
Abstract: | For the bi-criteria scheduling problem of minimizing the sum of completion times and the sum of weighted completion times, min-sum of weighted completion times, we prove that there exists no constant β>1 such that (1+1/γ,β)-approximate schedules can be found for any γ>0. This result confirms a recently published conjecture. |
| |
Keywords: | Scheduling Completion time Weighted completion time Lower bound |
本文献已被 ScienceDirect 等数据库收录! |
|