## 2 Related Works, Definitions, and Preliminaries
### Minimum Length Unit-Time Job-Shop Problems  
We begin by examining the unit-time scheduling problem \(J\big{|}t_{ij}=1\big{|}C_{\max}\) of constructing a makespan-optimal schedule for fulfilling the set \(J=\left\{J_{1},J_{2},\ldots,J_{|J|}\right\}\) of the given jobs by the dedicated processors \(M=\left\{M_{1},M_{2},\ldots,M_{|M|}\right\}\). The execution of the job \(J_{i}\in J\) entails the execution of the ordered set \(Q^{(i)}=\left\{Q_{i1},Q_{i2},\ldots,Q_{i_{|}Q^{(i)}}\right\}\) of operations with unit (equal) durations \(t_{ij}=1\) in the strict linear order \((Q_{i1},Q_{i2},\ldots,Q_{i_{|}Q^{(i)}})\) on the corresponding processors from the set \(M\). The operation \(Q_{ij}\in Q^{(i)}\) is performed by the processor \(M_{\mu(ij)}\in M\).  
This processing system is called a job-shop, denoted \(\alpha=J\) in the three-field notation \(J\big{|}t_{ij}=1\big{|}C_{\max}\) used for this problem. The notation \(C_{\max}\) is used to specify the optimality criterion of minimising the makespan \(C_{\max}=\max\{C_{i}:J_{i}\in J\}\) (the schedule length) in the desired optimal schedule, where \(C_{i}\) denotes the completion time of the job \(J_{i}\in J\). All jobs in the set \(J=\left\{J_{1},J_{2},\ldots,J_{|J|}\right\}\) are ready for processing from the same release date \(r=0\). Interruptions are not allowed during the execution of an operation \(Q_{ij}\in Q^{(i)}\) with \(J_{i}\in J\). A schedule \(S\) for processing the job set \(J=\left\{J_{1},J_{2},\ldots,J_{|J|}\right\}\) is determined either by the start times \(S(Q_{ij})\geq 0=t\) or by the completion times \(C(Q_{ij})=S(Q_{ij})+t_{ij}\) of the operations \(Q_{ij}\in Q:=\cup_{i=1}^{|J|}Q^{(i)}\). The length (makespan) of the schedule \(S\) is equal to \(C_{\max}(S)=\max\{C(Q_{ij}):Q_{ij}\in Q\}\).  
Let the subset \(Q_{k}\) of the set \(Q\) consist of operations to be fulfilled by the processor \(M_{k}\in M\). Given that every pair of operations within the set \(Q_{k}\) must not be executed simultaneously, any schedule that exists for a job-shop problem \(J\big{|}t_{ij}=1\big{|}C_{\max}\) determines \(|M|\) strict linear orders of the operations \(Q_{k}\) fulfilled by the processors \(M_{k}\in M\). An optimal schedule for the problem \(J\big{|}t_{ij}=1\big{|}C_{\max}\).  
\[S=(C(Q_{1,1}),C(Q_{1,2}),\ldots,C(Q_{1,|Q^{(1)}|}),C(Q_{2,1}),C(Q_{2,2}), \ldots,C(Q_{2,|Q^{(2)}|}),\ldots, \tag{1}\]  
\[C(Q_{|J|,1}),C(Q_{|J|,2}),\ldots,C(Q_{|J|,|Q^{(|E|)}|}))\]  
has the minimum length \(C_{\max}(S)\) among all schedules that exist for this problem.  
The objective function for each regular criterion is a non-decreasing function of the arguments \(C_{i}:=C(Q_{i,|Q^{(i)}|})\), where \(J_{i}\in J\). When solving the scheduling problem \(\alpha|\beta|\gamma\) with a regular criterion \(\gamma\), the optimal schedule can be found within the set of semiactive schedules [5].  
Definition 2 ([5]): The schedule \(\mathsf{S}\) for the problem \(\alpha|\beta|\gamma\) is semiactive, if the execution of every operation cannot be processed earlier without violating the operation order in schedule \(\mathsf{S}\) or another operation is processed later than in this schedule.