Geodesic
Chain structures in schedules tasks
Prikladnaâ diskretnaâ matematika, no. 3 (2016), pp. 67-77.

Voir la notice de l'article provenant de la source Math-Net.Ru

Some algorithms for constructing the following shedules are developed: 1) one-processor schedule with a partial precedence, 2) a multiprocessor schedule without idle time and conditions of partial precedence.
Keywords: schedule, graph, algorithm, colors, complexity. 
@article{PDM_2016_3_a4,
     author = {A. M. Magomedov},
     title = {Chain structures in schedules tasks},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {67--77},
     publisher = {mathdoc},
     number = {3},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2016_3_a4/}
}
TY  - JOUR
AU  - A. M. Magomedov
TI  - Chain structures in schedules tasks
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2016
SP  - 67
EP  - 77
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2016_3_a4/
LA  - ru
ID  - PDM_2016_3_a4
ER  - 
%0 Journal Article
%A A. M. Magomedov
%T Chain structures in schedules tasks
%J Prikladnaâ diskretnaâ matematika
%D 2016
%P 67-77
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2016_3_a4/
%G ru
%F PDM_2016_3_a4
A. M. Magomedov. Chain structures in schedules tasks. Prikladnaâ diskretnaâ matematika, no. 3 (2016), pp. 67-77. http://geodesic.mathdoc.fr/item/PDM_2016_3_a4/

[1] Swamy M. N. S., Thulasiraman K., Graphs, Networks, and Algorithms, Wiley-Inter-Science, 1981 | MR | Zbl

[2] Asratyan A. S. and Kamalyan R. R., “Interval coloring of multigraph edges”, Prikladnaya Matematika, 5, Yerevan SU Publ., 1987, 25–34 (in Russian) | MR

[3] Tanaev V. S., Sotskov Yu. N., Strusevich V. A., Shedules Theory. The Multi-Stage Systems, Nauka Publ., Moscow, 1989 (in Russian) | MR

[4] Magomedov A. M., “On interval $\Delta$-coloring of bipartite graphs”, Avtomatika i Telemekhanika, 2015, no. 1, 101–109 (in Russian) | MR | Zbl

[5] Magomedov A. M., Magomedov T. A., “Edge-vertex incident matchings in scheduling”, Prikladnaya Diskretnaya Matematika, 2015, no. 1(27), 92–95 (in Russian)

[6] Magomedov A. M., Magomedov T. A., “Sequential partitioning of bipartite graph edges on matching”, Diskr. Mat., 28:1 (2016), 78–86 (in Russian) | DOI

[7] Emelichev V. A., Mel'nikov O. I., Sarvanov V. I., Tyshkevich R. I., Sequential Partitioning of Bipartite Graph Edges on matching, Librokom Publ., Moscow, 2009 (in Russian)

[8] Sevast'yanov S. V., “On the interval coloring of edges of a bipartite graph”, Metody Diskretnogo Analiza, 50, 1990, 61–72 (in Russian) | MR | Zbl

[9] Kamalyan R .R., Interval Coloring of Complete Bipartite Graphs and Trees, Preprint, VTs AN ArmSSR, Yerevan, 1989 (in Russian)

[10] Garey M., Johnson D., Computers and Intractability, W. H. Freeman Co, N.Y., USA, 1979 | MR | MR | Zbl

[11] Aho A., Hopcroft J., Ullman J., The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1974 | MR | Zbl

[12] Petersen J., “Die Theorie der regularen Graphs”, Acta Math., 15 (1891), 193–220 | DOI | MR

[13] Tucker A., “Covering Circuits and Graph Colorings”, Appl. Combinat., 5th Ed., John Wiley Sons, Hoboken, 2006, Ch. 2, 49

[14] Lawler E. L., Combinatorial Optimization: Networks and Matroids, Holt, Rinehart and Winston, N.Y., 1976 | MR | Zbl

[15] Giaro K., Compact task scheduling on dedicated processors with no waiting period, PhD thesis, Technical University of Gdansk, IETI Faculty, Gdansk, 1999 (in Polish)