Задача 15.
N pазличных станков один за дpугим объединены в конвейеp. Имеется N pабочих. Задана матpица C[N , N], где C[i,j] пpоизводительность i-ого pабочего на j-ом станке. Опpеделить
а) на каком станке должен pаботать каждый из pабочих, чтобы пpоизводительность была максимальной.
б) то же, но станки pасположены паpаллельно и выполняют одноpодные опеpации.
|
Решение задачи 15.
Производительность конвейера определяется минимальной производительностью рабочего на конвейере. Поэтому для решения задачи нам достаточно определить максимальную производительность Р, при которой возможно распределить по станкам, всех рабочих, когда для каждого рабочего определен набор станков, на которые он может быть поставлен (понятно, что это те станки, производительность на которых у рабочего не ниже производительности Р). Легко понять, что для выбранной производительности Х задача определения, возможно ли распределение по станкам для каждого рабочего, аналогична решению задачи 4. Для определения максимальной производительности Р, при которой возможно распределить по станкам всех рабочих, можно воспользоваться методом дихотомии следующим образом. Отсортируем в одномерном A массиве размера N*N все элементы C[i,j], 1<=i,j<=N. Определим левую границу ЛГ=1 и правую границу ПГ=N.
Для элемента массива А с индексом СГ=(ЛГ+ПГ)/2, рассматриваемого в качестве возможной максимальной производительности Р, определяем, можно ли распределить по станкам всех рабочих. Если да, то величина возможной максимальной производительности Р увеличивается. Для этого пересчитывается значение левой границы по правилу ЛГ:=СГ+1. Если нет, то величина возможной максимальной производительности Р уменьшается. Для этого пересчитывается значение правой границы по правилу ПГ:=СГ-1.
Процесс заканчивается, когда ЛГ>=ПГ. Значение А[ПГ-1] и является максимальной производительностью Р, а конкретное распределение рабочих определяется структурой максимального потока.
|
