On the complexity of scheduling to optimize average response time

Process and job scheduling is one of the most widely studied problems in operations research, computer science, and combinatorial optimization. Unfortunately, many common and interesting scheduling problems are known to be NP-hard. In modern, interactive computer systems it is desirable to minimize the response time of each process competing for the system’s resources. In this short note, we prove that approximating an optimal solution to the problem of scheduling processes to minimize the average response time to the processes at least as hard as the well-known difficult problem of finding an approximate graph coloring.