informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-836Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGМИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФАСотсковЮ. Н.АндреевГ. В.Объединенный институт проблем информатики НАН БеларусиBelarus20041902201903(03)516Copyright © Сотсков Ю.Н., Андреев Г.В., 20192019Сотсков Ю.Н., Андреев Г.В.Сотсков Ю.Н., Андреев Г.В.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/836

Оптимальная раскраска φ смешанного графа G=(V,A,E) определяет расписание, которое минимизирует среднее время обслуживания n требований в системе job shop с единичными длительностями операций. Подграф (V,A,Æ) смешанного графа G представляет собой объединение путей, а подграф (V,Æ,E) – объединение клик. Разработан метод ветвей и границ для оптимальной раскраски смешанного графа G с критерием минимизации суммы номеров цветов, используемых для n требований. Проведен вычислительный эксперимент на ПЭВМ по построению оптимальной раскраски вершин смешанных графов порядка n £ 200, сгенерированных случайным образом.

 

ReferencesСотсков Ю.Н., Танаев В.С. Хроматический многочлен смешанного графа // Весцi АН БССР. Сер. фiз.-мат. навук. – 1976. – № 6. – С. 20-23.Сотсков Ю.Н., Танаев В.С. Хроматический многочлен смешанного графа // Весцi АН БССР. Сер. фiз.-мат. навук. – 1976. – № 6. – С. 20-23.Hansen P., Kuplinsky J., de Werra D. Mixed graph colorings // Mathematical Methods of Operations Research. – 1997. – V. 45. – P. 145-160.Hansen P., Kuplinsky J., de Werra D. Mixed graph colorings // Mathematical Methods of Operations Research. – 1997. – V. 45. – P. 145-160.Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. – М.: Наука, 1989.Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. – М.: Наука, 1989.Харари Ф. Теория графов. – М.: Мир, 1973.Харари Ф. Теория графов. – М.: Мир, 1973.Gonzalez T. Unit execution time shop problems // Mathematical Methods of Operations Research. – 1982. – V. 7. – № 1. – P. 57-66.Gonzalez T. Unit execution time shop problems // Mathematical Methods of Operations Research. – 1982. – V. 7. – № 1. – P. 57-66.Leighton F.T. A graph coloring algorithm for large scheduling problems // Journal of Research of the National Bureau of Standards. – 1979. – V. 84. – P. 489-506.Leighton F.T. A graph coloring algorithm for large scheduling problems // Journal of Research of the National Bureau of Standards. – 1979. – V. 84. – P. 489-506.De Werra D. An introduction to timetabling // European Journal of Operations Re-search. – 1985. – V. 19. – P. 151-162.De Werra D. An introduction to timetabling // European Journal of Operations Re-search. – 1985. – V. 19. – P. 151-162.Sotskov Yu.N., Tanaev V.S, Werner F. Scheduling problems and mixed graph colorings // Optimization. – 2002. – V. 5. – № 3. – P. 597-624.Sotskov Yu.N., Tanaev V.S, Werner F. Scheduling problems and mixed graph colorings // Optimization. – 2002. – V. 5. – № 3. – P. 597-624.Sotskov Yu.N., Dolgui A., Werner F. Mixed graph coloring for unit-time job-shop scheduling // International Journal of Mathematical Algorithms. – 2001. – V. 2. – P. 289-323.Sotskov Yu.N., Dolgui A., Werner F. Mixed graph coloring for unit-time job-shop scheduling // International Journal of Mathematical Algorithms. – 2001. – V. 2. – P. 289-323.Андреев Г.В., Сотсков Ю.Н. Раскраска вершин смешанного графа методом ветвей и границ // Весцi НАН Беларусi. Сер. фiз.-мат. навук. – 2001. – № 1. – С. 124-129.Андреев Г.В., Сотсков Ю.Н. Раскраска вершин смешанного графа методом ветвей и границ // Весцi НАН Беларусi. Сер. фiз.-мат. навук. – 2001. – № 1. – С. 124-129.Сотсков Ю.Н. Оптимальное обслуживание двух требований при регулярном критерии // Автоматизация процессов проектирования. - Мн.: Ин-т техн. кибернетики АН БССР, 1985. – С. 86-95.Сотсков Ю.Н. Оптимальное обслуживание двух требований при регулярном критерии // Автоматизация процессов проектирования. - Мн.: Ин-т техн. кибернетики АН БССР, 1985. – С. 86-95.Сотсков Ю.Н. Сложность задач оптимального обслуживания трех требований // Кибернетика. – 1990. – № 5. – С. 50-54.Сотсков Ю.Н. Сложность задач оптимального обслуживания трех требований // Кибернетика. – 1990. – № 5. – С. 50-54.Brucker P., Kravchenko C.A., Sotskov Yu.N. Preemptive job-shop scheduling problems with a fixed number of jobs // Mathematical Methods of Operations Research. – 1999. – № 49. – P.41-76.Brucker P., Kravchenko C.A., Sotskov Yu.N. Preemptive job-shop scheduling problems with a fixed number of jobs // Mathematical Methods of Operations Research. – 1999. – № 49. – P.41-76.

The authors declare that there are no conflicts of interest present.