Разработать программу, реализующий алгоритм
«Распределение работ по взаимозаменяемым исполнителям с целью минимизации суммарного запаздывания».
Нужно разработать алгоритм с хронологическими связями или реализовать по описани. Реализация эвристического алгоритма на Python без хронологических связей уже есть. Цена договорная
Описание:
Есть n работ и m исполнителей. Нужно эти работы распределить так, чтобы их окончание не выходило за рамки директивных сроков - минимизировать суммарное выполнение этих работ.
Исполнители могут браться за любые работы.
У каждой из работ установлены интервалы начала и окончания выполнения. Работы можно назначить разным исполнителям, но нужно сделать так, что время окончания последней работы было наименьшим.
- Должны соблюдаться хронологические связи: очередность реализации операций – задано, что одну работу нужно сделать раньше другой.
1) Формируется фронт операций - множество операций, предыдущие у которых в графике, в расписании. То есть их можно уже ставить в расписание, тк все их хронологические моменты уже известны.
2) Для операций фронта рассчитываются условные директивные сроки (d’), а именно "di’=di-Emin pij " или минус сумма максимумов " - Emax pij ". А можно взять серединку, то есть -0,5 от суммы мин. и минус суммы макс.
3) Далее выбираем работу с минимальным d’ и наибольшей критичностью. Для фронтальных работ есть уже условные директ. сроки
и дальше мы выбираем работу с минимальным сроком, но если их несколько то с наибольшей критичностью.
4) Дальше опять ставим туда, где меньше момент окончания. Значит, делаем пробную подстановку выбранной работы и 5) выбираем вариант с наименьшим моментом окончания в графике.
Дальше пересчитываем фронт, пересчитываем директивные сроки, но для одной работы, ту которую поставили.
Чуть более подробная информация о задаче:
Директивные сроки исполнения фиксированы, но если работы выходят за рамки сроков - ничего страшного, главная задача - минимизировать суммарное запаздывание.
Работы по исполнителям (данные) задаются матрицей: 1-ую работу 1-ый исполнитель может сделать за 5 часов, 2-ой исполнитель ту же работу может выполнить за 7 часов, 3-ий исполнитель сделает за 10 часов.
Директивный срок первой работы установлен, например, 20 ч.
И так далее с остальными работами.
На выходе данные, чтобы по ним можно было построить расписание, наглядно вручную:
Исходные данные:
- i - номер работы,
- j - номер исполнителя,
матрица длительности,
di - директивные сроки - момент времени, к которому желательно завершить обслуживание.
|i1 |i2 |i3|i4 ...| di
j1| pi1j1 | pi2j1 | ... | ... |
j2| pi2j2 |.... |
j3|.... |
А дальше расписание пойдет:
- номер работы,
- номер исполнителя,
- Pij - длительность, чтобы проверить то ли было дано, ту ли длительность работы мы использовали
- Mi - момент начала
- Ci - момент окончания - например, 0 или больше 0 (если запаздывание).
- di - директивные сроки
- хронологически связанные операции
- Ti - запаздывание
- Сумм.Ti - суммарное запаздывание
Эти данные выводим, чтобы потом вручную сделать расписание и убедиться, не получается ли так что работы накладываются (одна работа начинается в одно время, а другая работа как бы начинается раньше, но заканчивается позже первой, что получается накладка).