An Algorithm for the Open-Shop Problem

The open-shop problem is known to be NP-complete. However we give an algorithm, which solves the problem in polynomial time, whenever the sum of execution times for one processor is large enough with respect to the maximal execution time. According to the schedule given by our algorithm one of the processors works without idle time. Construction of this schedule is based on a suitable generalization of several “integer-making” techniques.