Nonpreemptive open shop with restricted processing times

A polynomial time algorithm was given by Fiala for the nonpreemptive m-processor open shop problem whenever the sum of processing times for one processor is large enough with respect to the maximal processing time. Here a special case where all processing times are from a bounded cardinality set of nonnegative integers is studied. For such a situation the authors give an O(nm) algorithm while the algorithm of Fiala works in O(n²m³) where n is the number of jobs.