3.08.3. Задача о распределении оборудования

Пусть V ={1,2 ,… , N} – множество работ, которые необходимо выполнить. Предположим, что для выполнения каждой работы требуется одинаковое время t и некоторые механизмы из множества механизмов М = {M1, M2, … , MS}. Никакие механизмы не могут быть использованы одновременно для выполнения двух и более работ.

Требуется распределить механизмы так, чтобы выполнить все работы и чтобы затраченное на это время T было минимальным.

Построим граф, соответствующий данной задаче, выбрав в качестве множества вершин V – множество работ. Если какие-то две работы требуют для их выполнения один и тот же механизм или механизмы, то соответствующие им вершины, соединим ребром, в противном случае – нет. Найдем какую-нибудь правильную раскраску полученного графа G. Тогда видно, что работы "раскрашенные в один и тот же цвет" могут выполняться одновременно. Значит минимальное время выполнения всех работ T = t χ(G).

Аналогичным образом формулируется и интерпретируется задача о составлении расписания занятий ( в школе, ВУЗе и т. д. ).

< Предыдущая		Следующая >