The Complexity of Mean Flow Time Scheduling Problems with Release Times

Philippe Baptiste, Peter Brucker, Marek Chrobak +3

We study the problem of preemptive scheduling n jobs with given release times on m identical parallel machines. The objective is to minimize the average flow time. We show that whe…