Optimal'noe po bystrodeystviyu raspisanie obsluzhivaniya trebovaniy s preryvaniyami operatsiy kak optimal'naya raskraska smeshannogo grafa

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription or Fee Access

Abstract

Установлена взаимосвязь задач теории расписаний с критерием минимизации длины расписания и задач поиска оптимальных (строгих) раскрасок вершин смешанного графа, т.е. назначений минимального множества упорядоченных цветов вершинам V = {v1, . . . , v|V |} смешанного графа G = (V,A,E), для которых вершинам vi и vj , инцидентным ребру [vi, vj ] ∈ E, назначаются разные цвета, а для дуги (vk, vl) ∈ A цвет вершины vk не больше (меньше) цвета вершины vl. Показано, что любая задача поиска оптимальной раскраски вершин смешанного графа G может быть представлена как задача GcMPT |[pij], pmtn|Cmax построения оптимального по быстродействию расписания обслуживания частично упорядоченного множества требований с целочисленными длительностями pij операций при допустимости прерываний их выполнения. В отличие от классических задач теории расписаний, в задаче GcMPT |[pij], pmtn|Cmax для выполнения операции может требоваться несколько приборов и помимо двух типов отношений предшествования, заданных на множестве операций, необходимо, чтобы единичные операции заданного подмножества выполнялись одновременно. Задача GcMPT |[pij], pmtn|Cmax псевдополиномиально сводится к задаче поиска оптимальной раскраски вершин смешанного графа G, который определяет исходные данные задачи. В силу доказанных утверждений для результатов, полученных для задачи GcMPT |[pij], pmtn|Cmax, имеются аналоги для соответствующих задач оптимальных раскрасок вершин смешанных графов G, и наоборот.

About the authors

Yu. N Sotskov

Объединенный институт проблем информатики НАН Беларуси

Email: sotskov48@mail.ru

References

  1. Sotskov Y.N., Tanaev V.S. Хроматический многочлен смешаннoго графа // Изв. АН БССР. Сер. физ.-мат. наук. 1976. № 6. С. 20-23.
  2. Hansen P., Kuplinsky J., de Werra D. Mixed graph colorings // Math. Methods Oper. Res. 1997. V. 45. P. 145-160.
  3. Karp R.M. Reducibility among combinatorial problems / In Complexity of Computer Computations, R.E. Miller, J.W. Thatcher (Editors.) // New York, USA: Plenum Press. 1972. P. 85-103.
  4. Sotskov Y.N., Dolgui A., Werner F. Mixed graph coloring for unit-time job-shop scheduling // Int. J. of Math. Algorithms. 2001. V. 2. P. 289-323.
  5. Sotskov Y.N., Tanaev V.S., Werner F. Scheduling problems and mixed graph colorings // Optimization. 2002. V. 51. No. 3. P. 597-624.
  6. Al-Anzi F.S., Sotskov Y.N., Allahverdi A., Andreev G.V. Using mixed graph coloring to minimize total completion time in job shop scheduling // Appl. Math.Comput. 2006. V. 182. P. 1137-1148.
  7. Kouider A., Ait Haddadene H., Ourari S., Oulamara A. Mixed graph coloring for unit-time scheduling // Int. J. Product. Res. 2017. V. 55. No. 6. P. 1720-1729.
  8. Kouider A., Ait Haddadene H., Oulamara A. On minimization of memory usage in branch-and-bound algorithm for the mixed graph coloring: application to the unittime job shop scheduling // Comput. Oper. Res. 2019. V. 4967. P. 1001-1008.
  9. Sotskov Y.N. Mixed graph colorings: A historical review // Mathematics. 2020. V. 8. P. 1-24.
  10. Harary F. Graph Theory. MA, USA: Addison-Wesley, Reading, 1969.
  11. Thulasiraman K., Swamy M.N.S. Graphs: Theory and Algorithms. Toronto, Canada: John Wiley & Sons, Inc. 1992.
  12. Tanaev V.S., Sotskov Y.N., Strusevich V.A. Scheduling Theory: Multi-Stage Systems. Dordrecht, The Netherlands: Kluwer Academic Publishers, 1994.
  13. Brucker P. Scheduling Algorithms, Berlin, Germany: Springer, 1995.
  14. Graham R.E., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. Optimization and approximation in deterministic sequencing and scheduling: a survey // Ann. Discret. Math. 1979. V. 5. P. 287-326.
  15. Hoogeveen J.A., van de Velde S.L., Veltman B.Complexity of scheduling multiprocessor tasks with prespecified processor allocations // Discret. Appl. Math. 1994. V. 55. P. 259-272.
  16. Brucker P., Kramer A. Shop scheduling problems with multiprocessor tasks on dedicated processors // Ann. Oper. Res. 1995. V. 57. P. 13-27.
  17. Chou F.D. Particle swarm optimization with cocktail decoding method for hybrid flow shop scheduling problems with multiprocessor tasks // Int. J. Prod. Econom. 2013. V. 141. P. 137-145.
  18. Kurdi M. Ant colony system with a novel Non-Daemon Actions procedure for multiprocessor task scheduling in multistage hybrid flow shop // Swarm Evol. Comput. 2019. V. 44. P. 987-1002.
  19. Drozdowski M. Scheduling multiprocessor - an overview // Eur. J. Oper. Res. 1996. V. 94. P. 215-230.
  20. Baptiste P. A note on scheduling multiprocessor tasks with identical processing times // Comput. Oper. Res. 2003. V. 30. P. 2071-2078.
  21. Zinder Y., Dob V.H., Oguz C.Computational complexity of some scheduling problems with multiprocessor tasks // Discret. Optimization. 2005. V. 2. P. 391-408.
  22. Kis T. Scheduling multiprocessor UET tasks of two sizes // Theor.Comput. Sci. 2009. V. 410. P. 4864-4873.
  23. Giaro K., Kubale M., Obszarski P. A graph coloring approach to scheduling of multiprocessor tasks on dedicated machines with availability constraints // Discret. Appl. Math. 2009. V. 157. P. 3625-3630.
  24. Sotskov Y.N. Mixed graph coloring as scheduling multi-processor tasks with equal processing times //j. Belarusian State Univ. Math. Inform. 2021. V. 2. P. 67-81.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2023 The Russian Academy of Sciences