Scheduling the Open Shop to Minimize Mean Flow Time

Abstract

It is shown that the problem of scheduling a two-processor n-job open shop nonpreemptively in order to minimize mean flow time is NP-complete even if input length is measured by the sum of the task lengths. The proof is similar in approach to that used by Garey, Johnson and Sethi to show NP-completeness of the two-processor flow shop mean flow problem. We assume previous results from their paper where possible and concentrate on those elements of the proof that are distinct from theirs. In addition, bounds are derived for the mean flow times of arbitrary and shortest processing time (SPT) first schedules for m-processor n-job systems in terms of the mean flow time of an optimal schedule.