Scheduling Intervals Using Independent Sets in Claw-Free Graphs

摘要

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).