Approximation Techniques for Average Completion Time Scheduling I: Best-α on One Machine with Release DatesResearch Paper
Minimizing the average completion time of jobs that arrive over time is one of the basic objectives of machine scheduling: it measures how long, on average, a job waits in the system. On a single machine with release dates and no preemption (written ), the problem is strongly NP-hard, so research has focused on approximation algorithms whose…