## 1 Introduction  
For optimal production planning and scheduling, it is required to construct an optimal schedule for processing a set of tasks (jobs) using existing equipment (processors). Optimisation of a schedule is a key factor in improving efficiency, as it allows a scheduler to reduce production costs, the time of the execution of incoming customer orders and the timely supply of production processes with raw materials and other components that are required for the manufacture of final products. Practical production scheduling (planning) problems are diverse in terms of conditions, restrictions and the objectives to be achieved by optimal schedules. To solve a large number of scheduling problems, special models and algorithms have been developed that take into account the specific conditions and objectives of concrete production planning. An extension of the application areas of scheduling algorithms can be based on a generalisation of scheduling models for complicated multi-stage systems in order to present different problem sets and to develop universal methods for constructing optimal schedules on the basis of the generalised scheduling models. It is well known that the construction of the makespan-optimal schedule for fulfilling operations of equal duration reduces the construction of the optimal colouring of vertices of the graph. If it is required to consider precedence constraints specified on the operation set and the impossibility of processing two or more tasks simultaneously on the same processor, then, to determine the makespan-optimal schedule for fulfilling the unit-time operations, one can use the optimal colouring of the mixed graph [1, 2]. In this paper, we focus on scheduling problems with integer operation durations and job release dates to minimize the makespan \(C_{\max}\) or maximal lateness \(L_{\max}\) of the given jobs with integer due dates. Let \(G=(V,A,E)\) be a mixed graph with the set \(V=\left\{v_{1},v_{2},\ldots,v_{|V|}\right\}\
eq\varnothing\) of vertices, the set \(A\) of arcs and the set \(E\) of edges. Each arc determines an ordered pair of vertices from the set \(V\). Each edge determines an unordered pair of vertices. The mixed graph \(G\) considered in this paper does not contain loops, multiple arcs and multiple edges. For the empty set of arcs, we obtain the graph \(G=(V,\varnothing,E)\). For the empty set of edges, we obtain the directed graph \(G=(V,A,\varnothing)\) (the digraph for short). In [3], a colouring of the mixed graph was defined. Definition 1 ([3]): A function \(c:V\to\{1,2,\ldots,t\}\) is called a colouring \(c(G)\) of a mixed graph \(G=(V,A,E)\) if the inequalities \(c(v_{i})\leq c(v_{j})\) hold for all arcs \((v_{i},v_{j})\in A\) and the relations \(c(v_{p})\
eq c(v_{q})\) hold for all edges \([v_{p},v_{q}]\in E\). A colouring \(c(G)\) is optimal if this colouring uses a minimal number \(\chi(G)\) of colours \(c(v_{i})\in\{1,2,\ldots,t\}\). The minimal number \(\chi(G)\) is called a chromatic number of the mixed graph \(G\). If the equality \(A=\varnothing\) holds, then the colouring \(c(G)\) is an ordinary colouring of the graph \(G=(V,\varnothing,E)\). The mixed graph \((V,A,E)\) with the non-empty set of arcs and the non-empty set of edges may not be colourable [3]. Theorem 1 ([3]): _A colouring \(c(G)\) of vertices of mixed graph \(G=(V,A,E)\) exists if and only if the directed graph \((V,A,\varnothing)\) has no circuit containing the adjacent vertices in the graph \((V,\varnothing,E)\)._  
Finding an optimal colouring of the vertices of the mixed graph \(G=(V,A,E)\) is an NP-hard problem, even if \(A=\varnothing\); see [4]. The NP-hardness of the optimisation problem means that it is unlikely that there exists a polynomial algorithm for solving this problem, since there is a polynomial reduction to this problem from a huge number of NP-hard problems, while there is no polynomial algorithm for each of them yet.