Abstract

Data for the schedule is given in a form of a bipartite graph where the vertices of the two parts of the graph are associated with specialized processors and tasks, and the edges are associated with prescribed operations of single-unit duration for processing by the processors. The schedule is viewed as a mapping from a set of graph edges to the set of positive integers – "colors" of edges (the set of discrete time intervals of single-unit duration assigned to perform a particular operation). Problem of edge interval coloring of a bipartite graph is considered as a theoretical-graph model for schedule of a multiprocessor system without downtime of the processors and job interruptions. Graph structures necessary for subsequent sections are defined in the Introduction. Using those in section 1 a number of properties of interval coloring are defined. Based on the concept of piecewise continuous path in section 2, we developed a heuristic algorithm for interval coloring, effective for both theoretical and practical problems of schedule optimizations. In the Conclusion we discuss the results of the application of software developed on the basis of that heuristic algorithm and future prospects.

Keywords:

schedule, graph, algorithm, colors, complexity

pp. 78-84 

References

1. Swamy, M.N.S. and K. Thulasiraman. Graphs, Networks and Algorithms. — N.Y.: Wiley, 1980. 612 p.
2. Asratjan, A.S., and R.R. Kamaljan. 1987. Interval'nye raskraski reber mul'tigrafa [Interval coloring of the edges of the multigraph]. Prikladnaja matematika. Erevan: Izd-vo Erevanskogo un-ta [Applied mathematics. Yerevan: Publishing house of the Yerevan University] 5: 25-34.
3. Tanaev, V.S., Ju.N. Sotskov, and V.A. Strusevich, eds 1989. Teorija raspisanij. Mnogostadijnye sistemy [The scheduling theory. Multistage system]. Moscow: Science. 328 p.
4. Magomedov, A.M. 2015. K voprosu ob interval'noj Δ -raskraske dvudol'nyh grafov [To the question about the interval Δ-coloring of bipartite graphs]. Avtomatika i telemehanika [Automatics and telemechanics] 1:101-109.
5. Magomedov, A.M., and T.A. Magomedov. 2015. Reberno-vershinnye incidentnye parosochetanija v zadachah raspisanij [The edge-vertex incident matching in the task schedules]. Prikladnaja diskretnaja matematika [Applied discrete mathematics] 1 (27): 92-95.
6. Magomedov, A.M., and T.A. Magomedov. 2016. Posledovatel'noe razbienie reber dvudol'nogo grafa na parosochetanija [Successive splitting of edges on a bipartite graph matching]. Diskretnaja matematika [Discrete mathematics] 1(28): 78-86.
7. Magomedov, A.M. 2016. Cepochechnye struktury v zadachah o raspisanijah [Chain structure in schedule’s tasks]. Prikladnaja diskretnaja matematika [Applied discrete mathematics] 3 (33): 67-77.
8. Sevast'janov, S.V. 1990. Ob interval'noj raskrashivaemosti reber dvudol'nogo grafa [About the interval-coloring of edges of the bipartite graph]. Metody diskretnogo analiza [Discrete analysis methods] 50: 61-72.
9. Emelichev, V.A., O.I. Mel'nikov, V.I. Sarvanov, and R.I. Tyshkevich, eds. 2009. Lekcii po teorii grafov [Lectures on graph theory]. Moscow: Book house «Librokom». 392 p.
10. Swamy, M.N.S. and K. Thulasiraman. Graphs, Networks and Algorithms. — N.Y.: Wiley, 1980. 612 p.
11. Petersen, Julius (1891), Die Theorie der regulären graphs, Acta Mathematica 15: p. 193–220.
12. Kamaljan, R.R. 1989. Interval'nye raskraski polnyh dvudol'nyh grafov i derev'ev [Interval coloring of complete bipartite graphs and trees]. Preprint VC AN Armjanskoj SSR, Erevan [Preprint VTS an Armenian SSR, Yerevan]. 11 p.
13. Tucker, Alan. Chapter 2: Covering Circuits and Graph Colorings // Applied Combinatorics. — 5th. — Hoboken: John Wiley & sons, 2006. P. 49.
14. Lawler, E. L. Combinatorial Optimization: Networks and Matroids. – New York: Holt, Rinehart and Winston, 1976.
15. Giaro, K. Compact task scheduling on dedicated processors with no waiting period (in Polish) // PhD thesis, Technical University of Gdansk, IETI Faculty, Gdansk. – 1999.
16. Magomedov A.M. 2016. Rebernaja raskraska dvudol'nyh grafov [Edge-coloring of bipartite graphs]. Svidetel'stvo № 2016660830 o gosudarstvennoj registracii programmy dlja JeVM [Certificate No. 2016660830 on the state registration of the computer program].
17. Magomedov A.M. 2017. Generacija grafov i ih raskraska metodom zhadnogo algoritma [Generation of graphs and their coloring method, greedy algorithm]. Svidetel'stvo № 2017611516 o gosudarstvennoj registracii programmy dlja JeVM [Certificate No. 2017611516 on the state registration of the computer program].