The Variable Length Scheduling Problem has been studied in the context of web searching, where the execution time for a task depends on the start time for the task. The objective is to minimize the total completion time of all the tasks. It is known that the problem is NP-Hard to approximate within a factor of n~(O(1)). For the case when the execution times are from the set {1, 2}, the optimal execution sequence can be determined in polynomial time. Also, when the execution times are from the set {k_1, k_2} the problem is NP-complete and can be approximated within a ratio of 2 + k_2/2k_1. Here we note that the approximation ratio for the case when the execution times are from the set {k_1, k_2} can be improved to 2 + 2k_2/5k_1.
展开▼
