Complexity of Machine Scheduling Problems 4: KNAPSACK Reduces to Single-Machine Total Completion Time with One Release DateResearch Paper
Minimizing the total completion time of jobs on a single machine is one of the oldest problems in scheduling theory. When every job is available at time , processing the jobs in order of nondecreasing processing time is optimal (the shortest-processing-time rule), so the problem is solved by sorting. Release dates, times before which a job may…