Задача - составление - расписание
Cтраница 1
Задача составления расписания заключается в таком структурировании времени работы коллектива предприятия, которое было бы максимально удобно для всех его сотрудников и клиентов. [1]
Эти задачи составления расписаний попадают в категорию больших комбинаторных оптимизационных задач, многие из которых являются ЛГР-полными и считаются традиционно трудноразрешимыми. Главное внимание в этой главе было уделено получению при заданном количестве вычислительных ресурсов наиболее полезной информации, необходимой для осуществления упорядочения заданий либо в виде оптимального расписания ( когда это возможно), либо в виде расписания с обеспечением заданной точности относительно оптимального. [2]
Теорема 4.3. Задача составления расписаний является NP-полной. [3]
Следствие 4.4. Задача составления расписаний с прерываниями является NP-полной. [4]
Говоря о задачах составления расписаний, следует подчеркнуть еще одно обстоятельство. Ввиду неточности исходных посылок, неточности нормативной базы, наличия неизбежных помех и многих других факторов, нами не учтенных следует признать, что в реальных задачах проектирования ( где требуется определить срок окончания проекта или его стоимость) особая точность, как правило, и не требуется. Кроме того, найденный вариант распределения ресурсов всегда может быть использован в качестве первого приближения для более точного расчета, а уточнение может быть сделано с помощью значительно менее трудоемких методов теории возмущений. [5]
Говоря о задачах составления расписаний, следует подчеркнуть еще одно обстоятельство. Ввиду неточности исходных посылок, неточности нормативной базы, наличия неизбежных помех и многих других факторов, нами не учтенных, следует признать, что в реальных задачах проектирования ( где требуется определить срок окончания проекта или его стоимость) особая точность, как правило, и не требуется. Кроме того, найденный вариант распределения ресурсов всегда может быть использован в качестве первого приближения для более точного расчета, а уточнение может быть сделано с помощью значительно менее трудоемких методов теории возмущений. [6]
Пусть 5s - задача составления расписания такая, что является входящим лесом. С помощью леммы 3.2 и определения р-максимального множества можно показать, что для нахождения р-максимального множества относительно 3 нет необходимости рассматривать все начальные множества 53; в действительности нам нужно рассмотреть только п из них, где п есть число заданий. [7]
 |
Основные компоненты моделей составления расписаний. [8] |
Таким образом, задачи составления расписаний решаются в условиях определенной архитектуры или заданной математической модели вычислительной системы. [9]
Метод используется для задач составления расписаний. [10]
Вход: Р - задача составления расписания для выходящего леса. [11]
К счастью, для задач составления расписаний мы можем показать, что и в частном случае, когда времена выполнения равны 2 или даже 1 ( но при наличии ограничений предшествования), они все еще остаются yVP - полными. Следовательно, в некотором смысле структура ограничений предшествования вбирает в себя всю комбинаторную сложность, которая содержалась в больших временах выполнения. [12]
Дополнительные сведения о свойствах задач составления расписаний могут быть получены при исследовании более сложных моделей оптимального планирования, в которых полнее отражены связи между отдельными операциями, производственными участками, способами организации работ. [13]
В наиболее общей формулировке задачи составления расписаний, изучаемые в этой книге, состоят в следующем. [14]
Следующая лемма показывает, что задачи составления расписаний для выходящих лесов являются двойственными по отношению к задачам для входящих лесов. [15]
Страницы: 1 2 3 4