A Time-Optimal Schedule for Processing Jobs with Possible Operation Preemptions as an Optimal Mixed Graph Coloring
| Autor: | Sotskov, Y.N. |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: | |
| DOI: | 10.25728/arcras.2023.29.68.001 |
| Popis: | This paper establishes a relationship between optimal scheduling problems with the minimum schedule length and the problems of finding optimal (strict) colorings of mixed graph vertices, i.e., assigning a minimal set of ordered colors to the vertices V = {v1, . . . , v|V |} of a mixed graph G = (V,A,E) so that the vertices vi and vj incident to an edge [vi, vj ] ∈ E will have different colors and the color of the vertex vk in an arc (vk, vl) ∈ A will be not greater (smaller) than that of the vertex vl. As shown below, any optimal coloring problem for the vertices of a mixed graph G can be represented as the problem GcMPT |[pij], pmtn|Cmax of constructing a time-optimal schedule for processing a partially ordered set of jobs with integer durations pij of their operations with possible preemptions. In contrast to classical scheduling problems, executing an operation in the problem GcMPT |[pij], pmtn|Cmax may require several machines and, besides the two types of precedence relations defined on the set of operations, unit-time operations of a given subset must be executed simultaneously. The problem GcMPT |[pij], pmtn|Cmax is pseudopolynomially reduced to the problem of finding an optimal coloring of the vertices of a mixed graph G (the initial conditions of the problem). Due to the assertions proved, the results obtained for the problem GcMPT |[pij], pmtn|Cmax have analogs for the corresponding optimal coloring problems for the vertices of a mixed graph G, and vice versa. Automation and Remote Control, Выпуск 2 2023 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|