The authors consider open-shop problems with precedence relations (job-shop problems included) consisting of n operations vi. From preliminary examinations they know time frames [fi, si] for which exist schedules with minimal makespan where all vi are realized in their time frames. Using the branch and bound method frame iteration is a process of gradually reducing the frames up to the fi are optimal starting times of operations. First of all in this article the authors prove results allowing an estimation of the distance of a feasible schedule to the optimum. From this they get bounods and a branching rule. This rule in connection with a simulation allows to t a good initial schedule and the corresponding first frames by expense of O(n2logn).
