Минимизация суммарного времени обслуживания с единичным длительностями операций на основе раскраски смешанного графа'
Сотсков Ю. Н.
1
,
Андреев Г. В.
1
- Объединенный институт проблем информатики Минск, Сурганова, 6
УДК: 519.8
Статья поступила: 14.04.2004
Реферат:
Оптимальная раскраска ? смешанного графа G = (V, A, E) определяет расписание, которое минимизирует среднее время обслуживания n требований в системе job shop с единичными длительностями операций. Подграф (V, A, O) смешанного графа G представляет собой объединение путей, а подграф (V, O, Е) – объединение клик. Разработан метод ветвей и границ для оптимальной раскраски смешанного графа G с критерием минимизации суммы номеров цветов, используемых для n требований. Проведен вычислительный эксперимент на ПЭВМ по построению оптимальной раскраски вершин смешанных графов порядка n ? 200, сгенерированных случайным образом.
|