Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Шаг 0. Фиксируем матрицу производительностей и любое назначение на рабочие места. Пусть s - минимальная производительность при этом назначении. Построим рабочую таблицу тех же размеров, что и матрица C; в клетку с номером (ij) в этой таблице проставим символ «´», если ; в противном случае эту клетку оставим пустой.
Шаг 1. Рассматривая рабочую таблицу, построенную на предыдущем шагу, как рабочую таблицу в алгоритме для выбора наибольшего паросочетания в двудольном графе, найдем соответствующее наибольшее паросочетание. Если в нем окажется n ребер, то по ним восстанавливается новое назначение на рабочие места и с новой, более высокой, минимальной производительностью. Обозначим ее снова через s и вернемся к Шагу 0. Если же число ребер окажется меньше n, то имеющееся назначение на рабочие места уже оптимально.
Дата публикования: 2014-11-02; Прочитано: 1027 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!