МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА
Аннотация
Оптимальная раскраска φ смешанного графа G=(V,A,E) определяет расписание, которое минимизирует среднее время обслуживания n требований в системе job shop с единичными длительностями операций. Подграф (V,A,Æ) смешанного графа G представляет собой объединение путей, а подграф (V,Æ,E) – объединение клик. Разработан метод ветвей и границ для оптимальной раскраски смешанного графа G с критерием минимизации суммы номеров цветов, используемых для n требований. Проведен вычислительный эксперимент на ПЭВМ по построению оптимальной раскраски вершин смешанных графов порядка n £ 200, сгенерированных случайным образом.
Об авторах
Ю. Н. Сотсков
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Г. В. Андреев
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Список литературы
1. Сотсков Ю.Н., Танаев В.С. Хроматический многочлен смешанного графа // Весцi АН БССР. Сер. фiз.-мат. навук. – 1976. – № 6. – С. 20-23.
2. Hansen P., Kuplinsky J., de Werra D. Mixed graph colorings // Mathematical Methods of Operations Research. – 1997. – V. 45. – P. 145-160.
3. Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. – М.: Наука, 1989.
4. Харари Ф. Теория графов. – М.: Мир, 1973.
5. Gonzalez T. Unit execution time shop problems // Mathematical Methods of Operations Research. – 1982. – V. 7. – № 1. – P. 57-66.
6. 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.
7. De Werra D. An introduction to timetabling // European Journal of Operations Re-search. – 1985. – V. 19. – P. 151-162.
8. Sotskov Yu.N., Tanaev V.S, Werner F. Scheduling problems and mixed graph colorings // Optimization. – 2002. – V. 5. – № 3. – P. 597-624.
9. 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.
10. Андреев Г.В., Сотсков Ю.Н. Раскраска вершин смешанного графа методом ветвей и границ // Весцi НАН Беларусi. Сер. фiз.-мат. навук. – 2001. – № 1. – С. 124-129.
11. Сотсков Ю.Н. Оптимальное обслуживание двух требований при регулярном критерии // Автоматизация процессов проектирования. - Мн.: Ин-т техн. кибернетики АН БССР, 1985. – С. 86-95.
12. Сотсков Ю.Н. Сложность задач оптимального обслуживания трех требований // Кибернетика. – 1990. – № 5. – С. 50-54.
13. 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.
Рецензия
Для цитирования:
Сотсков Ю.Н., Андреев Г.В. МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА. Информатика. 2004;(3(03)):5-16.
Просмотров: 470
Послать статью по эл. почте 