Four-parametric complexity analysis for an open shop problem (Q2713932)

The authors study the open shop problem on the minimum of the length of a schedule. A complexity analysis of the problem is carried out in terms of the following four parameters: the number of jobs, maximal number of operations for a job, number of machines, and maximal number of operations for a machine. These parameters are combined in a four-dimensional characteristic vector \(x_I\) of a given entry \(I\). Given a four-dimensional vector \(x\), the authors define classes \(\mathcal J (x)\) of individual open shop problems for which their characteristic vector is at most \(x\). It is shown that, in the infinite set of non-trivial classes \(\mathcal J (x)\) (which admit unlimited number of operations), there exists a finite set of the so-called basic classes which make it possible to determine the complexity of an open shop problem for the entry classes \(\mathcal J (x)\) for every admissible value \(x\).