J2ni2Cmax — различия между версиями
(→Доказательство корректности алгоритма) |
(→Доказательство корректности алгоритма) |
||
Строка 32: | Строка 32: | ||
==Доказательство корректности алгоритма== | ==Доказательство корректности алгоритма== | ||
<tex>T_{i}(x)</tex> - время выполнения множества работ <tex>x</tex> на станке <tex>i</tex>. | <tex>T_{i}(x)</tex> - время выполнения множества работ <tex>x</tex> на станке <tex>i</tex>. | ||
− | + | <tex>G_{i}</tex> - множество всех работ, которые нужно сделать на i-м станке.(Формально <tex>G_{1} = I_{1} /cup I_{12} /cup I_{21}</tex>) | |
{{Лемма | {{Лемма | ||
|id=lemma1 | |id=lemma1 |
Версия 17:11, 22 июня 2013
Содержание
Постановка задачи
Рассмотрим задачу:
- Дано работ и станка.
- Для каждой работы известно её время выполнения на каждом станке .
- Для каждой работы известна последовательность станков - порядок, в котором нужно выполнить работу. .
- Длина любой последовательности .
Требуется минимизировать время окончания выполнения всех работ.
Описание алгоритма
- первый станок. - второй станок.
Разобьем все работы на четыре множества:
- - множество всех работ, которые должны выполнится только на .
- - множество всех работ, которые должны выполнится только на .
- - множество всех работ, которые должны выполнится сначала на затем на .
- - множество всех работ, которые должны выполнится сначала на затем на .
Решим задачу для и для . Получим расписание и .
Тогда оптимальное расписание для нашей задачи будет следующим:
- Расписание : сначала в соответсвии с расписанием . Затем в произвольном порядке. Затем в соответсвии с .
- Расписание : сначала в соответсвии с расписанием . Затем в произвольном порядке. Затем в соответсвии с .
Примечание: во время выполнения
на или на могут возникнуть простои из-за того, что работа ещё не выполнилась на предыдущем станке.Доказательство корректности алгоритма
- время выполнения множества работ на станке . - множество всех работ, которые нужно сделать на i-м станке.(Формально )
Лемма: |
Расписание, построенное данным алгоритмом, обладает следующим свойством : один из станков работает без простоев. |
Доказательство: |
Рассмотрим 2 варианта: |
Сложность алгоритма
Время работы алгоритма равно времени работы алгоритма .
Сложность алгоритма
.