Cтраница 4
Формально рассматриваемая задача может быть представлена как задача теории расписаний. Задачи календарного планирования имеют комбинаторный характер. Обычный подход к решению таких задач состоит в построении математической модели и разработке для нее оптимизационных алгоритмов. Отметим, что ближе всего к рассматриваемой в данной работе задаче подходит модель системы независимых машин с общими ресурсами. В [10] показано, что уже при одном ресурсе и трех машинах составление кратчайшего расписания для такой системы является NP-трудной задачей. Это практически исключает надежду на то, что когда-нибудь удастся построить алгоритмы оптимизации для таких моделей. Кроме того, такой подход, как правило, не позволяет учесть особенности конкретного производства. [46]
Методы приближенного решения задач календарного планирования достаточно быстры и эффектны. [47]
Хотя полученная модель и может принципиально служить для решения задачи методами целочисленного программирования, но практически расчеты оказываются чрезвычайно громоздкими. Поэтому для решения задач календарного планирования используются иные, так называемые комбинаторные методы. [48]
В других случаях задержка в течение некоторого времени может не приводить ни к каким потерям, но по прошествии этого времени потери резко возрастают. Например, решение задачи календарного планирования цеха на очередной отрезок времени может понадобиться только к началу этого отрезка. Если же к началу этого отрезка времени задача не будет решена, то надобность в ее решении может пропасть вовсе. [49]
Отметим, что уже при т 3 рассмотренный алгоритм не может быть исполюован. Рассмотрим теперь общую схему формализации задач календарного планирования и алгоритмы их решения, использующие правила предпочтения. [50]
Весьма важной в прикладном отношении является так называемая общая задача теории расписаний. В отечественной литературе эту задачу обычно называют задачей календарного планирования. [51]
Пусть, например, имеется п деталей, которые должны быть обработаны на т станках. Вследствие этого метод прямого перебора вариантов в задачах календарного планирования неприменим. [52]
Своевременная подготовка материалов и деталей, выполненная на этапе планирования материально-технического снабжения, создает предпосылки для беспрепятственного выполнения заказа. Установление сроков и контроль за их соблюдением является задачей календарного планирования и управления. [53]
Поэтому в отечественной науке общую задачу теории расписаний часто называют задачей календарного планирования. [54]