We consider the open shop problem with n jobs, m machines, and the minimum makespan criterion. Let li stand for the load of the ith machine, lmax be the maximum machine load, and pmax be the maximum operation length. Suppose that the machines are numbered in nonincreasing order of their loads and that pmax = 1, while other processing times are numbers in the interval [0, 1]. Then, given an instance of the open shop problem, we define its vector of differences VOD = (Δ(1),…Δ(m)), where Δ(i) = lmax − li. An instance is called normal if its optimal schedule has length lmax. A vector Δ ∈ ℝm is called normalizing if every instance with VOD = Δ is normal. A vector Δ ∈ ℝm is called efficiently normalizing if it is normalizing and there is a polynomial-time algorithm which for any instance with VOD = Δ constructs its optimal schedule. In this paper, a few nontrivial classes of efficiently normalizing vectors are found in ℝm. It is also shown that the vector (0, 0, 2) is the unique minimal normalizing vector in ℝ3, and that there are at least two minimal normalizing vectors in ℝ4.
