Постановка задачи
Рассмотрим задачу:
- Дано [math]n[/math] работ и [math]2[/math] станка.
- Для каждой работы известно её время выполнения на каждом станке.
- Для каждой работы известна последовательность станков - порядок, в котором нужно выполнить работу. [math]1[/math].
- Длина любой последовательности [math]\lt =2[/math].
Требуется минимизировать время окончания выполнения всех работ.
Описание алгоритма
[math]M_{1}[/math] - первый станок. [math]M_{2}[/math] - второй станок.
Разобьем все работы на четыре множества:
- [math]I_{1}[/math] - множество всех работ, которые должны выполнится только на [math]M_{1}[/math].
- [math]I_{2}[/math] - множество всех работ, которые должны выполнится только на [math]M_{2}[/math].
- [math]I_{12}[/math] - множество всех работ, которые должны выполнится сначала на [math]M_{1}[/math] затем на [math]M_{2}[/math].
- [math]I_{21}[/math] - множество всех работ, которые должны выполнится сначала на [math]M_{2}[/math] затем на [math]M_{1}[/math].
Решим задачу [math]F2 \mid \mid C_{max}[/math] для [math]I_{12}[/math] и для [math]I_{21}[/math]. Получим расписание [math]S_{12}[/math] и [math]S_{21}[/math].
Тогда оптимальное расписание для нашей задачи будет следующим:
- Расписание [math]M1[/math] : сначала [math]I_{12}[/math] в соответсвии с расписанием [math]S_{12}[/math]. Затем [math]I_{1}[/math] в произвольном порядке. Затем [math]I_{21}[/math] в соответсвии с [math]S_{21}[/math].
- Расписание [math]M_{2}[/math] : сначала [math]I_{21}[/math] в соответсвии с расписанием [math]S_{21}[/math]. Затем [math]I_{2}[/math] в произвольном порядке. Затем [math]I_{12}[/math] в соответсвии с [math]S_{12}[/math].
Примечание: во время выполнения [math]I_{21}[/math] на [math]M_{1}[/math] или [math]I_{12}[/math] на [math]M_{2}[/math] могут возникнуть простои
из-за того, что работа ещё не выполнилась на предыдущем станке.
Доказательство корректности алгоритма
[math]T_{i}(x)[/math] - время выполнения множества работ [math]x[/math] на станке [math]i[/math].
Лемма: |
Расписание, построенное данным алгоритмом, обладает следующим свойством : один из станков работает без простоев. |
Доказательство: |
[math]\triangleright[/math] |
Рассмотрим 2 варианта:
[math]T_{1}(I_{12}) + T_{1}(I_{1}) \gt = T_{2}(I_{21}) [/math].
Тогда [math]M_{1}[/math] работает без прерываний, т.к к тому моменту завершения выполнения [math]I_{1}[/math] на [math] M_{1} [/math] все работы [math]I_{21}[/math] выполнены на [math]M_{2}[/math].
Иначе [math]T_{1}(I_{12}) + T_{1}(I_{1}) \lt T_{2}(I_{21}) [/math].
Тогда [math]M_{2}[/math] работает без прерываний, т.к к тому моменту завершения выполнения [math]I_{2}[/math] на [math] M_{2} [/math] все работы [math]I_{12}[/math] выполнены на [math]M_{1}[/math]. |
[math]\triangleleft[/math] |
Теорема: |
Расписание, построенное данным алгоритмом, является корректным и оптимальным. |
Доказательство: |
[math]\triangleright[/math] |
Корректность алгоритма очевидна.
Докажем оптимальность.
Рассмотрим станок на котором достигается [math]С_{max}[/math]. Если этот станок работает без прерываний, то оптимальность очевидна([math]C_{max} \gt = \sum Q[/math]) |
[math]\triangleleft[/math] |
Псевдокод
[math] S \leftarrow \{1 \dots n\}[/math]
[math] time \leftarrow 0[/math]
[math] answer \leftarrow 0[/math]
while [math] S \neq \varnothing [/math]
[math] j \leftarrow i : (\max \limits_{i \in S, r_{i} \leq time} w_{i})[/math]
if [math]j \neq null [/math]
[math] S \leftarrow S \setminus j[/math]
[math] Answer \leftarrow Answer + time \cdot w_{j}[/math]
[math] time++[/math]
Сложность алгоритма
Время работы алгоритма равно времени работы алгоритма [math]F2 \mid \mid C_{max}[/math].
Сложность алгоритма [math]O(n\log n)[/math].