Mixed graph colouring as scheduling multi-processor tasks with equal processing times

Yu. N. Sotskov

Journal of the Belarusian State University. Mathematics and Informatics, Tome 2 (2021), pp. 67-81.

Résumé

A problem of scheduling partially ordered unit-time tasks processed on dedicated machines is formulated as a mixed graph colouring problem, i. e., as an assignment of integers (colours) ${1, 2, …, t}$ to the vertices (tasks) $V ={v_1, v_2, \ldots, v_n}$ of the mixed graph $G = (V, A, E)$ such that if vertices $v_p$ and $v_q$ are joined by an edge $[v_p, v_q] \in E$, their colours have to be different. Further, if two vertices $v_i$ and $v_j$ are joined by an arc $(v_i, v_j) \in A$ the colour of vertex $v_i$ has to be no greater than the colour of vertex $v_j$. We prove that an optimal colouring of a mixed graph $G = (V, A, E)$ is equivalent to the scheduling problem $GcMPT|p_i = 1|C_{max}$ of finding an optimal schedule for partially ordered multi-processor tasks with unit (equal) processing times. Contrary to classical shop-scheduling problems, several dedicated machines are required to process an individual task in the scheduling problem $GcMPT|p_i = 1|C_{max}$. Moreover, along with precedence constraints given on the set $V ={v_1, v_2, \ldots, v_n}$, it is required that a subset of tasks must be processed simultaneously. Due to the theorems proved in this article, most analytical results that have been proved for the scheduling problems $GcMPT|p_i = 1|C_{max}$ so far, have analogous results for optimal colourings of the mixed graphs $G = (V, A, E)$, and vice versa.

Détail

Keywords: optimisation; unit-time scheduling; makespan; mixed graph; vertex colouring.

Bibliographie

[1] L. Wan, J. Mei, J. Du, “Two-agent scheduling of unit processing time jobs to minimize total weighted completion time and total weighted number of tardy jobs”, European Journal of Operational Research, 290(1) (2021), 26–35 | DOI | MR | Zbl

[2] Y. N. Sotskov, V. S. Tanaev, “A chromatic polynomial of a mixed graph”, Izvestiya Akademii nauk BSSR. Seriya fiziko-matematicheskikh nauk, 6 (1976), 20–23 | MR | Zbl

[3] R. M. Karp, “Reducibility among combinatorial problems. Complexity of computer computations”, Boston: Springer, 1972, 85–103 | DOI | MR | Zbl

[4] Y. N. Sotskov, A. Dolgui, F. Werner, “Mixed graph coloring for unit-time job-shop scheduling”, International Journal of Mathematical Algorithms, 2 (2001), 289–323 | Zbl

[5] Y. N. Sotskov, V. S. Tanaev, F. Werner, “Scheduling problems and mixed graph colorings”, Optimization, 51(3) (2002), 597–624 | DOI | MR | Zbl

[6] F. S. Al-Anzi, Y. N. Sotskov, A. Allahverdi, G. V. Andreev, “Using mixed graph coloring to minimize total completion time in job shop scheduling”, Applied Mathematics and Computation, 182(2) (2006), 1137–1148 | DOI | MR | Zbl

[7] A. Kouider, Haddadene. Ait, S. Ourari, A. Oulamara, “Mixed graph colouring for unit-time scheduling”, International Journal of Production Research, 55(6) (2017), 1720–1729 | DOI | MR

[8] A. Kouider, Haddadene. Ait, A. Oulamara, “On minimization of memory usage in branch-and-bound algorithm for the mixed graph coloring: application to the unit-time job shop scheduling”, Computer and Operations Research, 4967 (2019), 1001–1008 | MR

[9] J. K. Lenstra, Kan. Rinnooy, “Computational complexity of discrete optimization problems”, Annals of Discrete Mathematics, 4 (1979), 121–140 | DOI | MR | Zbl

[10] Y. N. Sotskov, “Complexity of optimal scheduling problems with three jobs”, Cybernetics, 26(5) (1990), 686–692 | DOI | MR | Zbl

[11] Y. N. Sotskov, “The complexity of shop-scheduling problems with two or three jobs”, European Journal of Operational Research, 53(3) (1991), 326–336 | DOI | Zbl

[12] Y. N. Sotskov, N. V. Shakhlevich, “NP-hardness of shop-scheduling problems with three jobs”, Discrete Applied Mathematics, 59(3) (1995), 237–266 | DOI | MR | Zbl

[13] S. A. Kravchenko, Y. N. Sotskov, “Optimal makespan schedule for three jobs on two machines”, Mathematical Methods of Operations Research, 43(2) (1996), 233–238 | DOI | MR | Zbl

[14] T. Gonzalez, “Unit execution time shop problems”, Mathematics of Operations Research, 7(1) (1982), 57–66 | DOI | MR | Zbl

[15] P. Brucker, S. A. Kravchenko, Y. N. Sotskov, “On the complexity of two machine job-shop scheduling with regular objective functions”, OR Spektrum, 19 (1997), 5–10 | DOI | MR | Zbl

[16] N. V. Shakhlevich, Y. N. Sotskov, “Scheduling two jobs with fixed and nonfixed routes”, Computing, 52(1) (1994), 17–30 | DOI | MR | Zbl

[17] N. V. Shakhlevich, Y. N. Sotskov, F. Werner, “Shop-scheduling problems with fixed and non-fixed machine orders of the jobs”, Annals of Operations Research, 92 (1999), 281–304 | DOI | MR | Zbl

[18] P. Damaschke, “Parameterized mixed graph coloring”, Journal of Combinatorial Optimization, 38 (2019), 326–374 | DOI | MR

[19] P. Hansen, J. Kuplinsky, Werra. de, “Mixed graph colorings”, Mathematical Methods of Operations Research, 45 (1997), 145–160 | DOI | MR | Zbl

[20] K. Kruger, Y. N. Sotskov, F. Werner, “Heuristics for generalized shop scheduling problems based on decomposition”, International Journal of Production Research, 36(11) (1998), 3013–3033 | DOI | Zbl

[21] Y. N. Sotskov, “Software for production scheduling based on the mixed (multi)graph approach”, Computing and Control Engineering Journal, 7(5) (1996), 240–246 | DOI

[22] Y. N. Sotskov, “Mixed multigraph approach to scheduling jobs on machines of different types”, Optimization, 42(3) (1997), 245–280 | DOI | MR | Zbl

[23] Werra. de, “Restricted coloring models for timetabling”, Discrete Mathematics, 165–166 (1997), 161–170 | DOI | MR | Zbl

[24] Werra. de, “On a multiconstrained model for chromatic scheduling”, Discrete Applied Mathematics, 94(1–3) (1999), 171–180 | DOI | MR | Zbl

[25] Y. N. Sotskov, “Mixed graph colorings: a historical review”, Mathematics, 8(3) (2020), 385 | DOI

[26] F. Harary, “Graph theory”, Addison-Wesley, Massachusetts, 1969, 274 | MR | Zbl

[27] K. Thulasiraman, MNS. Swamy, “Graphs: theory and algorithms”, John Wiley and Sons, Inc, Canada, 1992, 480 | DOI | MR

[28] V. S. Tanaev, Y. N. Sotskov, V. A. Strusevich, “Scheduling theory. Multi-stage systems”, Kluwer Academic Publishers, Dordrecht, 1994, 406 | DOI | MR

[29] P. Brucker, “Scheduling algorithms”, Springer, Berlin, 1995, 326 | DOI | MR | Zbl

[30] R. L. Graham, E. L. Lawler, J. K. Lenstra, Kan. Rinnooy, “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Annals of Discrete Mathematics, 5 (1979), 287–326 | DOI | MR | Zbl

[31] Y. N. Sotskov, V. S. Tanaev, “Scheduling theory and practice: Minsk group results”, Intelligent Systems Engineering, 3(1) (1994), 1–8 | DOI

[32] B. Sussmann, “Scheduling problems with interval disjunctions”, Mathematical Methods of Operations Research, 16 (1972), 165–178 | MR | Zbl

[33] P. Brucker, A. Kramer, “Shop scheduling problems with multiprocessor tasks on dedicated processors”, Annals of Operations Research, 57(1) (1995), 13–27 | DOI | MR | Zbl

[34] P. Brucker, A. Kramer, “Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems”, European Journal of Operational Research, 90(2) (1996), 214–226 | DOI | Zbl

[35] J. A. Hoogeveen, d. e. van, B. Veltman, “Complexity of scheduling multiprocessor tasks with prespecified processor allocations”, Discrete Applied Mathematics, 55(3) (1994), 259–272 | DOI | MR | Zbl

[36] J. A. Hoogeveen, J. K. Lenstra, B. Veltman, “Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard”, European Journal of Operational Research, 89(1) (1996), 172–175 | DOI | Zbl