## 6 Example 4 of General Scheduling Problem with Interruptible Operations
However, the orders for fulfilling the same set of operations are opposite to the linear orders determined in Example 4._  
While the precedence constraints \(v_{i}\to v_{j}\) and \(v_{p}\Rightarrow v_{q}\) are determined between operations different jobs in Example 4, the inverse precedence constraints \(v_{j}\to v_{i}\) and \(v_{q}\Rightarrow v_{p}\) are determined in Example 5 of the scheduling problem \(G_{c}MPT\big{|}[t_{ij}],pmtn,[D_{i}]\big{|}L_{\max}\). Thus, in Example 5, the due dates of the given set of jobs \(J_{i}\in J=\{J_{1},J_{2},J_{3},J_{4}\}\) are defined as follows: \(D_{1}=\max\{r_{j}:J_{i}\in J\}-r_{1}=4-4=0\), \(D_{2}=4-r_{2}=4-3=1\), \(D_{3}=4-r_{3}=4-1=3\), \(D_{4}=4-r_{4}=4-3=1\). The input data for Example 5 are determined by the mixed graph \(G^{\leftarrow}=(V,A^{\leftarrow},E)\) depicted in Figure 5. Set \(V\) of the vertices and set \(E\) of the edges in the mixed graph \(G^{\leftarrow}\) are the same as those in the mixed graph \(G\) presented in Figure 4.  
Compare mixed graph \(G^{\leftarrow}\) depicted in Figure 5 for scheduling problem \(G_{c}MPT\big{|}[t_{ij}],pmtn,[D_{i}]\big{|}L_{\max}\) with mixed graph \(G\) for scheduling problem \(G_{c}MPT\big{|}[r_{i}],[t_{ij}],pmtn\big{|}C_{\max}\) depicted in Figure 4. According to Theorem 9 and Corollary 3, for Example 5 of the scheduling problem \(G_{c}MPT\big{|}[t_{ij}],pmtn,[D_{i}]\big{|}L_{\max}\) on the mixed graph \(G^{\leftarrow}=(V,A^{\leftarrow},E)\), the optimal semiactive schedule \(S\) is determined by the following optimal colouring \(c(G^{\leftarrow})\): \(c(v_{1})=7\), \(c(v_{2})=2\), \(c(v_{3})=1\), \(c(v_{4})=8\), \(c(v_{5})=7\), \(c(v_{6})=6\), \(c(v_{7})=5\), \(c(v_{8})=4\), \(c(v_{9})=3\), \(c(v_{10})=10\), \(c(v_{11})=9\), \(c(v_{12})=8\), \(c(v_{13})=7\), \(c(v_{14})=6\), \(c(v_{15})=5\), \(c(v_{16})=5\), \(c(v_{17})=4\), \(c(v_{18})=3\), \(c(v_{19})=2\). The colouring \(c(G^{\leftarrow})\) determines the optimal semiactive schedule:  
\(C(Q_{1,1})=c(v_{3})=1\), \(C(Q_{1,2})=c(v_{1})=7\), \(C(Q_{2,1})=c(v_{7})=5\), \(C(Q_{2,2})=c(v_{6})=6\), \(C(Q_{2,3})=c(v_{4})=8\), \(C(Q_{3,1})=c(v_{14})=6\), \(C(Q_{3,2})=c(v_{12})=8\), \(C(Q_{3,3})=c(v_{11})=9\), \(C(Q_{4,1})=c(v_{17})=4\), \(C(Q_{4,2})=c(v_{16})=5\). We compute the optimal objective value as follows:  
\(L_{\max}=\chi(G^{\leftarrow})-\max\{r_{i}:Jscheduling problems, it is necessary to construct optimal schedules for fulfilling partially ordered sets of integer-time multi-processor tasks with allowed operation interruptions. Precedence constraints of the two types of completion-start and start-start can be given on the set of integer-time operations. Furthermore, specified subsets of the operations with unit durations must be executed simultaneously. The propositions proved in Sections 4-7 can be used to construct mixed graphs for representing the entire input data of the numerous scheduling problems with interruptible integer-time operations. It is proven that to construct an optimal semiactive schedule for any studied scheduling problem, it is sufficient to determine the optimal colouring of the vertices of the mixed graph representing all input data of the considered scheduling problem. It is also shown that notions of graph theory are quite sufficient for the formulation of the problems \(G_{c}MPT\big{|}[t_{ij}],pmtn,[D_{i}]\big{|}L_{\max}\) and \(G_{c}MPT\big{|}[r_{i}],[t_{ij}],pmtn\big{|}C_{\max}\), and a huge number of their special cases. To illustrate the obvious benefits of using graph theory terminology instead of terminology of scheduling theory, we list the scheduling terms used in Sections 1-7: _processing system (multi-stage); production planning (scheduling); job-shop, general shop; equipment, machine, processor; schedule (semiactive, feasible, optimal); schedule optimality criterion (makespan, maximal lateness.