МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА
Аннотация
Оптимальная раскраска φ смешанного графа G=(V,A,E) определяет расписание, которое минимизирует среднее время обслуживания n требований в системе job shop с единичными длительностями операций. Подграф (V,A,Æ) смешанного графа G представляет собой объединение путей, а подграф (V,Æ,E) – объединение клик. Разработан метод ветвей и границ для оптимальной раскраски смешанного графа G с критерием минимизации суммы номеров цветов, используемых для n требований. Проведен вычислительный эксперимент на ПЭВМ по построению оптимальной раскраски вершин смешанных графов порядка n £ 200, сгенерированных случайным образом.
Для цитирования:
Сотсков Ю.Н., Андреев Г.В. МИНИМИЗАЦИЯ СУММАРНОГО ВРЕМЕНИ ОБСЛУЖИВАНИЯ ТРЕБОВАНИЙ С ЕДИНИЧНЫМИ ДЛИТЕЛЬНОСТЯМИ ОПЕРАЦИЙ НА ОСНОВЕ РАСКРАСКИ СМЕШАННОГО ГРАФА. Информатика. 2004;(3(03)):5-16.