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

  • Yuri N. Sotskov United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surhanava Street, Minsk 220012, Belarus https://orcid.org/0000-0002-9971-6169
DOI: https://doi.org/10.33581/2520-6508-2021-2-67-81

Abstract

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 {ν1, ν2, …, νn}, of the mixed graph G = (V, A, E) such that if vertices vp and vq are joined by an edge [νp, νq] ∈ E their colours have to be different. Further, if two vertices νp and νq are joined by an arc (νi, νj) ∈ A the colour of vertex νi has to be no greater than the colour of vertex νj. We prove that an optimal colouring of a mixed graph G = (V, A, E) is equivalent to the scheduling problem GcMPT|pi = 1|Cmax 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|pi = 1|Cmax. Moreover, along with precedence constraints given on the set V {ν1, ν2, …, ν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 |pi = 1|Cmax so far, have analogous results for optimal colourings of the mixed graphs G = (V, A, E), and vice versa.

Author Biography

Yuri N. Sotskov, United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surhanava Street, Minsk 220012, Belarus

doctor of science (physics and mathematics), full professor; chief researcher at the laboratory of mathematical cybernetics

References

  1. Wan L, Mei J, Du J. 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. 2021;290(1):26–35. DOI: 10.1016/j.ejor.2020.07.064.
  2. Sotskov YN, Tanaev VS. [A chromatic polynomial of a mixed graph]. Izvestiya Akademii nauk BSSR. Seriya fiziko-matematicheskikh nauk. 1976;6:20–23. Russian.
  3. Karp RM. Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD, editors. Complexity of computer computations. Boston: Springer; 1972. p. 85–103. DOI: 10.1007/978-1-4684-2001-2_9.
  4. Sotskov YN, Dolgui A, Werner F. Mixed graph coloring for unit-time job-shop scheduling. International Journal of Mathematical Algorithms. 2001;2:289–323.
  5. Sotskov YN, Tanaev VS, Werner F. Scheduling problems and mixed graph colorings. Optimization. 2002;51(3):597–624. DOI: 10.1080/0233193021000004994.
  6. Al-Anzi FS, Sotskov YN, Allahverdi A, Andreev GV. Using mixed graph coloring to minimize total completion time in job shop scheduling. Applied Mathematics and Computation. 2006;182(2):1137–1148. DOI: 10.1016/j.amc.2006.04.063.
  7. Kouider A, Ait Haddadène H, Ourari S, Oulamara A. Mixed graph colouring for unit-time scheduling. International Journal of Production Research. 2017;55(6):1720–1729. DOI: 10.1080/00207543.2016.1224950.
  8. Kouider A, Ait Haddadène H, Oulamara A. On minimization of memory usage in branch-and-bound algorithm for the mixed graph coloring: application to the unit-time job shop scheduling. Computer & Operations Research. 2019;4967:1001–1008.
  9. Lenstra JK, Rinnooy Kan AHG. Computational complexity of discrete optimization problems. Annals of Discrete Mathematics. 1979;4:121–140. DOI: 10.1016/S0167-5060(08)70821-5.
  10. Sotskov YN. Complexity of optimal scheduling problems with three jobs. Cybernetics. 1990;26(5):686–692. DOI: 10.1007/ BF01068549.
  11. Sotskov YN. The complexity of shop-scheduling problems with two or three jobs. European Journal of Operational Research. 1991;53(3):326–336. DOI: 10.1016/0377-2217(91)90066-5.
  12. Sotskov YN, Shakhlevich NV. NP-hardness of shop-scheduling problems with three jobs. Discrete Applied Mathematics. 1995; 59(3):237–266. DOI: 10.1016/0166-218X(95)80004-N.
  13. Kravchenko SA, Sotskov YN. Optimal makespan schedule for three jobs on two machines. Mathematical Methods of Operations Research. 1996;43(2):233–238. DOI: 10.1007/BF01680374.
  14. Gonzalez T. Unit execution time shop problems. Mathematics of Operations Research. 1982;7(1):57–66. DOI: 10.1287/ moor.7.1.57.
  15. Brucker P, Kravchenko SA, Sotskov YN. On the complexity of two machine job-shop scheduling with regular objective functions. OR Spektrum. 1997;19:5–10. DOI: 10.1007/BF01539799.
  16. Shakhlevich NV, Sotskov YN. Scheduling two jobs with fixed and nonfixed routes. Computing. 1994;52(1):17–30. DOI: 10.1007/BF02243393.
  17. Shakhlevich NV, Sotskov YN, Werner F. Shop-scheduling problems with fixed and non-fixed machine orders of the jobs. Annals of Operations Research. 1999;92:281–304. DOI: 10.1023/A:1018943016617.
  18. Damaschke P. Parameterized mixed graph coloring. Journal of Combinatorial Optimization. 2019;38:326–374. DOI: 10.1007/ s10878-019-00388-z.
  19. Hansen P, Kuplinsky J, de Werra D. Mixed graph colorings. Mathematical Methods of Operations Research. 1997;45:145–160. DOI: 10.1007/BF01194253.
  20. Kruger K, Sotskov YN, Werner F. Heuristics for generalized shop scheduling problems based on decomposition. International Journal of Production Research. 1998;36(11):3013–3033. DOI: 10.1080/002075498192265.
  21. Sotskov YN. Software for production scheduling based on the mixed (multi)graph approach. Computing & Control Engineering Journal. 1996;7(5):240–246. DOI: 10.1049/CCE:19960509.
  22. Sotskov YN. Mixed multigraph approach to scheduling jobs on machines of different types. Optimization. 1997;42(3):245–280. DOI: 10.1080/02331939708844361.
  23. de Werra D. Restricted coloring models for timetabling. Discrete Mathematics. 1997;165–166:161–170. DOI: 10.1016/S0012 365X(96)00208-7.
  24. de Werra D. On a multiconstrained model for chromatic scheduling. Discrete Applied Mathematics. 1999;94(1–3):171–180. DOI: 10.1016/S0166-218X(99)00019-0.
  25. Sotskov YN. Mixed graph colorings: a historical review. Mathematics. 2020;8(3):385. DOI: 10.3390/math8030385.
  26. Harary F. Graph theory. Massachusetts: Addison-Wesley; 1969. 274 p.
  27. Thulasiraman K, Swamy MNS. Graphs: theory and algorithms. Canada: John Wiley & Sons, Inc.; 1992. 480 p. DOI: 10.1002/ 9781118033104.
  28. Tanaev VS, Sotskov YN, Strusevich VA. Scheduling theory. Multi-stage systems. Dordrecht: Kluwer Academic Publishers; 1994. 406 p. DOI: 10.1007/978-94-011-1192-8.
  29. Brucker P. Scheduling algorithms. Berlin: Springer; 1995. 326 p. DOI: 10.1007/978-3-662-03088-2.
  30. Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics. 1979;5:287–326. DOI: 10.1016/S0167-5060(08)70356-X.
  31. Sotskov YN, Tanaev VS. Scheduling theory and practice: Minsk group results. Intelligent Systems Engineering. 1994;3(1):1–8. DOI: 10.1049/ISE.1994.0001.
  32. Sussmann B. Scheduling problems with interval disjunctions. Mathematical Methods of Operations Research. 1972;16:165–178.
  33. Brucker P, Krämer A. Shop scheduling problems with multiprocessor tasks on dedicated processors. Annals of Operations Research. 1995;57(1):13–27. DOI: 10.1007/BF02099688.
  34. Brucker P, Krämer A. Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems. European Journal of Operational Research. 1996;90(2):214–226. DOI: 10.1016/0377-2217(95)00350-9.
  35. Hoogeveen JA, van de Velde SL, Veltman B. Complexity of scheduling multiprocessor tasks with prespecified processor allocations. Discrete Applied Mathematics. 1994;55(3):259–272. DOI: 10.1016/0166-218X(94)90012-4.
  36. Hoogeveen JA, Lenstra JK, Veltman B. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. European Journal of Operational Research. 1996;89(1):172–175. DOI: 10.1016/S0377-2217(96)90070-3.
Published
2021-08-05
Keywords: optimisation, unit-time scheduling, makespan, mixed graph, vertex colouring
Supporting Agencies This work was partially supported by the Belarusian Republican Foundation for Fundamental Research (project No. Ф21-010).
How to Cite
Sotskov, Y. N. (2021). Mixed graph colouring as scheduling multi-processor tasks with equal processing times. Journal of the Belarusian State University. Mathematics and Informatics, 2, 67-81. https://doi.org/10.33581/2520-6508-2021-2-67-81
Issue
No 2 (2021): Journal of the Belarusian State University. Mathematics and Informatics
Section
Discrete Mathematics and Mathematical Cybernetics

Copyright (c) 2021 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)