When difference in machine loads leadsto efficient scheduling in open shops

We consider the open shop problem with n jobs, mmachines, and the minimum makespan criterion. Let l i stand for the loadof the ith machine, l max be the maximum machine load,and p max be the maximum operation length. Suppose that the machines arenumbered in nonincreasing order of their loads and that p max =1, whileother processing times are numbers in the interval [0,1]. Then, given aninstance of the open shop problem, we define its vector of differences $$VOD=\left( {\Delta \left( 1 \right), \ldots ,\Delta \left( m \right)} \right)$$ , where $$\Delta \left( i \right)=l_{\max } - l_i $$ .An instance is called normal if its optimal schedule has length l max .A vector Δ ∈ ℝ m is called normalizing if every instancewith VOD=Δ is normal. A vector Δ ∈ ℝ m is called efficiently normalizing if it is normalizing and there is a polynomial‐timealgorithm which for any instance with VOD=Δ constructs itsoptimal schedule. In this paper, a few nontrivial classes of efficiently normalizingvectors are found in ℝ m . It is also shown that the vector $$\left( {0,0,2} \right)$$ is the unique minimal normalizingvector in ℝ m , and that there are at least two minimal normalizingvectors in ℝ m . Copyright Kluwer Academic Publishers 1999