Backward Scheduling to Minimize the Actual Mean Flow Time with Dependent and Independent Setup Times

The present paper deals with a new perfomance measure, the actual mean flow time, defined as a mean of the elapsed time of each job counted from the start time on a schedule to the corresponding due date. For the one machine backward scheduling model with a common due date and independent setup times, LPT schedule is shown as the optimal solution for the proposed measure. An optimal algorithm is presented for the case with dependent setup times on the basis of the algorithm by Arcelus and Chandra for a n / 1 / F forward scheduling problem. The proposed algorithm is coded in C-language and a computational experience is reported through a 16-bit computer.