## 2 Related Works, Definitions, and Preliminaries
### General Shop Minimum-Length Unit-Time Scheduling Problems  
The general shop scheduling problem \(\,G_{c}|t_{ij}=1|C_{\max}\) is a generalisation of the job-shop scheduling problem \(\,J\big{|}t_{ij}=1|C_{\max}\). In the former problem \(\,G_{c}|t_{ij}=1|C_{\max}\), in addition to the strict order that is determined on the set of operations \(Q^{(i)}\) of the same job \(\,J_{i}\in J\), precedence constraints can be defined between operations of different jobs. Moreover, indicated unit-time operations must be processed simultaneously. In [9], completion-start precedence constraints and start-start precedence constraints between operations of different jobs were also considered. The processing job \(\,J_{k}\in J\) consists of the set \(V^{(k)}\) of linearly ordered operations. The duration \(\,t_{i}\) of every operation \(\,v_{i}\) of the set \(\,V=\cup_{k=1}^{|J|}V^{(k)}\) equals one; \(\,t_{i}=1\). We represent the job \(\,J_{k}\in J\) as a union of the path \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{k_{j}}})\) in the directed graph \((V,A,\varnothing)\) and the chain \((v_{k_{1}},v_{k_{2}},\ldots,v_{k_{j_{k}}})\) in the graph \((V,\varnothing,E)\), which are subgraphs of the mixed graph \(G=(V,A,E)\) determining input data of the problem \(\,G_{c}\big{|}t_{ij}=1|C_{\max}\). Thus, we obtain the vertex set \(\,V=\cup_{k=1}^{|J|}V^{(k)}\) of the desired mixed graph \(G=(V,A,E)\), the subset \(\,E^{*}=\cup_{k=1}^{|J|}\Big{\{}[v_{k_{1}},v_{k_{2}}],[v_{k_{2}},v_{k_{3}}], \ldots,[v_{k_{j_{k}}-1},v_{k_{j_{k}}}]\Big{\}}\) of edges \(\,E\supseteq E^{*}\) and the subset \(A^{*}\) of arcs \(\,A\) such that the implication (3) holds:  
\[[v_{i},v_{j}]\in E^{*}\Rightarrow\ (v_{i},v_{j})\in A^{*} \tag{3}\]  
In the general shop unit-time scheduling problem \(\,G_{c}\big{|}t_{ij}=1|C_{\max}\), along with a linear strict order given on the set \(V^{(k)}\) of all operations of the job \(\,J_{k}\in J\), there are given precedence constraints between operations belonging to different jobs in the set \(J\) Let \(A\setminus A^{*}\) denote a subset of the set \(A\) such that the implication (2) does not hold for each arc \(\,(v_{i},v_{j})\in A\setminus A^{*}\). In the unit-time scheduling problem \(\,G_{c}\big{|}t_{ij}=1\big{|}C_{\max}\), one processor of the set \(M\) is needed to process an operation \(\,v_{i}\in V=\cup_{k=1}^{|J|}V^{(k)}\). Let the set \(\,V_{i}=\Big{\{}v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|V_{i}|}}\Big{\}}\subseteq V\) be a set of operations, which must be processed on the processor \(\,M_{i}\in M\). A pair of operations processed on the processor \(\,M_{i}\in M\) cannot be processed simultaneously. Such a capacity constraint for processing operations \(\,V_{i}\subseteq V\) on the processor \(\,M_{i}\in M\) is represented by the clique \(\,\Big{\{}v_{i_{1}},v_{i_{2}},\ldots,v_{i_{|V_{i}|}}\Big{\}}\) in the subgraph \(\,(V,\varnothing,E\setminus E^{*})\) of the desired mixed graph \(\,G=(V,A,E)\). The general shop unit-time scheduling problem \(\,G_{c}\big{|}t_{ij}=1\big{|}C_{\max}\) is to find a schedule \(\,S\) for processing the set \(\,V=\cup_{i=1}^{|M|}V_{i}=\cup_{k=1}^{|J|}V^{(k)}\) of partially ordered operations, whose length \(\,C_{\max}(S)\) is minimal among the lengths of all semiactive schedules existing for the general shop scheduling problem \(\,G_{c}\big{|}t_{ij}=1\big{|}C_{\max}\). The input data for the general shop unit-time scheduling problem \(\,G_{c}\big{|}t_{ij}=1\big{|}C_{\max}\) are determined by the mixed graph \(\,G=(V,A,E)\), where the vertex set \(V\) is a set of operations, the arc set \(A\) determines precedence constraints and the edge set \(E\) determines capacity constraints. The union \(\,A^{*}\cup E^{*}\) of the arc set \(\,A^{*}\) and the edge set \(\,E^{*}\) determines \(\,|J|\,\) subsets \(\,V^{(k)}\) of the linearly ordered operations of the jobs \(\,J_{k}\in J\).