## 5 An Optimal Schedule of Interruptible Operations with Integer Processing Times
### Partitions of the Interruptible Operations with Integer Duration into Unit-Time Operations  
If interruptions of the operation are allowed, then a set of schedules is usually larger than a set of schedules of non-interruptible operations of the set \(Q\). The larger set of schedules may complicate optimal scheduling [11]. Obviously, allowing interruptions of the operations from the set \(Q\) may decrease an optimal value of the objective function. Thus, for most scheduling problems, it is desirable to reduce the number of allowed interruptions of the operations \(Q\) without losing an optimal semiactive schedule. Lemma 2: _If the release dates \(r_{i}\) of the jobs \(J_{i}\in J\) are non-negative integers and the operations \(Q_{ij}\in Q\) have positive integer durations \(t_{ij}>0\), then there exists an optimal semiactive schedule such that interruptions in processing operations occur only at the integer times._  
Proof: The interruption of the operation \(Q_{ij}\in Q\) can reduce the value of a regular objective function in the semiactive schedule without interruptions only if the interruption is at a completion time of at least one operation \(Q_{ij}\in Q\). In fact, due to such interruption of the operation \(Q_{ij}\in Q\) processed on the processor \(M_{\mu(i,j)}\in M\), another operation \(Q_{uv}\in Q\) with \(u\
eq i\) can start its processing on the same processor \(M_{\mu(i,j)}=M_{\mu(u,v)}\), since this processor becomes free. Since the release dates \(r_{i}\) of the given jobs \(J_{i}\in\left\{J_{1},J_{2},\ldots,J_{|J|}\right\}\) are non-negative integers and operations have positive integer durations, in any semiactive schedule without operation interruptions, the realisation of each operation can be completed only at integer times. Lemma is proven. Due to Lemma 2, operations \(Q_{1,1}\in Q^{(1)}\) with positive integer durations can be partitioned into \(t_{1,1}\) unit-time operations. We denote these unit-time operations as follows: \(\{v_{1},v_{2},\ldots,v_{t_{1,1}}\}\). Let \(\left\{v_{t_{1,1}+1},v_{t_{1,1}+2},\ldots,v_{t_{1,1}+t_{1,2}}\right\}\) be a set of all unit-time operations generated by similar partitioning the operation \(Q_{1,2}\in Q^{(1)}\). Similarly, we partition operations \(Q^{(1)}\backslash\{Q_{1,1},Q_{1,2}\}\) into unit-time operations and assign sequential indexes to the generated unit-time operations. Continuing the above partitioning procedure of operations from set \(Q^{(1)}\) with integer durations, we generate the following set of unit-time operations:  
\[W_{1}=\left\{v_{1},v_{2},\ldots,v_{|W_{1}|}\right\},\text{ where }|W_{1}|=\sum_{j=1}^{|Q^{(1)}|}t_{1,j}. \tag{5}\]The generated unit-time operations will be ordered as follows: \((v_{1},v_{2},\ldots,v_{|W_{1}|})\) within any feasible schedule; see Lemma 2. Remark 2: _We represent all unit-time operations generated by the above partition of operations \(Q\) as vertices in the mixed graph \(G=(V,A,E)\). Here and elsewhere, the generated unit-time operations are linearly ordered in the ascending order of their indexes. For each job \(J_{i}\in J\), the unit-time operations generated by the above partitioning procedure of the integer-time operations \(Q^{(i)}\) will be fulfilled in the ascending order of their indexes in any semiactive schedule._  
We continue with the generated unit-time operation \(v_{|W_{1}|+1}\) by sequentially indexing the generated unit-time operations into which integer-time operations from set \(Q^{(2)}=\left\{Q_{2,1},Q_{2,2},\ldots,Q_{2,|Q^{(2)}|}\right\}\) contained in the job \(J_{2}\in J\) are partitioned. Thus, we obtain the following set of the unit-time operations:  
\[W_{2}=\left\{v_{|W_{1}|+1},v_{|W_{1}|+2},\ldots,v_{|W_{2}|}\right\}\text{, where }|W_{2}|=|W_{1}|+\sum_{j=1}^{|Q^{(2)}|}t_{2,j}, \tag{6}\]  
of the linearly ordered unit-time operations generated from integer-time operations of job \(J_{2}\); see Remark 2.