Материал из Викиконспекты
|
|
| (не показано 10 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | ==Постановка задачи==
| |
| − | Рассмотрим задачу:
| |
| − | <ol>
| |
| − | <li>Дано <tex>n</tex> работ и один станок.</li>
| |
| − | <li>Для каждой работы известно её время появления <tex>r_{i}</tex> и вес <tex>w_{i}</tex>. Время выполнения всех работ <tex>p_i</tex> равно <tex>1</tex>.</li>
| |
| − | </ol>
| |
| − | Требуется выполнить все работы, чтобы значение <tex>\sum w_{i}(c_{i} - p_{i} - r_{i})</tex> было минимальным.
| |
| | | | |
| − | ==Описание алгоритма==
| |
| − | Пусть <tex>time</tex> {{---}} текущий момент времени.<br/>
| |
| − | Для каждого очередного значения <tex>time</tex>, которое изменяется от <tex>0</tex> до времени окончания последний работы, будем:
| |
| − | <ol>
| |
| − | <li> Выбирать работу <tex>j</tex> из множества невыполненных работ, у которой <tex>r_{i} \le time</tex> и значение <tex>w_{i}(time - r{i})</tex> максимально.</li>
| |
| − | <li> Выполняем <tex>j</tex> в момент времени <tex>time</tex> и увеличиваем <tex>time</tex> на один.
| |
| − | </ol>
| |
| − |
| |
| − | ==Доказательство корректности алгоритма==
| |
Текущая версия на 19:23, 4 сентября 2022
