Cтраница 4
Отношение предшествования называется входящим лесом, если каждая вершина в графе предшествования имеет не более одного непосредственного преемника. Аналогично, является выходящим лесом, если каждая вершина в графе предшествования имеет не более одного непосредственного предшественника. В данном параграфе мы рассмотрим эффективные алгоритмы отыскания оптимальных расписаний для задач, в которых ограничения предшествования являются входящими либо выходящими лесами. Вначале рассматривается задача с входящим лесом, а затем для получения алгоритмов составления расписаний в случае выходящего леса используются соображения двойственности. Мы также представим алгоритм для случая, когда задача составления расписания может быть разделена на две или более независимых задачи. [46]
Необходимость выбора метода решения задачи определяется тем, что для многих задач он оказывается неоднозначным. Поэтому появляется необходимость в выборе такого метода, который обеспечивает оптимальное решение задачи при принятом критерии оптимизации. Например, ту же норму времени можно рассчитать, используя опытно-статистический метод нормирования или расчетно-технический. Для конкретных условий решения задачи выбирается наиболее рациональный метод. Для формирования расписаний работы рабочих разработано множество методов. При решении на ЭВМ задачи составления расписаний работы рабочих мест необходимо выбрать такой метод, который наиболее приемлем в данных условиях производства и обеспечивает максимально возможный экономический эффект. [47]
К каждой ВР в действующей АСУ предъявляются те или иные требования по срочности выполнения после наступления момента готовности определенных информационных массивов. Обычно количество ЭВМ ( или УМ) меньше количества ожидающих выполнения ВР. По этой причине не все требования, связанные с выполнением работ в определенное время, можно удовлетворить. Возникает задача оптимального согласования таких требований. Ввиду того, что все необходимые данные для определения расписания известны до внедрения АСУ, оно может быть составлено в процессе проектирования. Для решения задачи составления расписания по каждой ВР задаются: время, затрачиваемое на выполнение ВР, момент готовности исходных данных и требования по срочности, выражаемые функцией стоимостных или других потерь от момента окончания работы. Кроме того, задается интегральный критерий оценки оптимальности согласования требований по срочности для различных ВР, выражаемый как функционал, аргументами которого являются индивидуальные функции потерь. В качестве интегрального критерия могут фигурировать среднее, средневзвешенное или максимальное ожидание ( запаздывание) по всему комплексу ВР, а также аналогичные стоимостные или вероятностные характеристики. [48]
Для г-й операции задается длительность TIJ 0 ее исполнения на J - M типе ресурса, причем TIJ ос, если г-я операция не может использовать j - й тип ресурса. Удельная стоимость ( или вес) Wi операции чаще всего полагается постоянной. Тогда стоимость завершения операции равна W fi и представляет собой неубывающую от срока завершения операции функцию. По сути т, т и w образуют вектор параметров операции, а совокупность таких векторов параметрически описывает систему операций и соответствующую графовую модель. Эти параметры могут фиксироваться или полагаться случайными. Однако числовые характеристики случайных величин считаются известными либо значения случайных величин формируются до решения задачи упорядочения. Поэтому и такие задачи также относятся к задачам составления детерминированных расписаний: вся информация для принятия решения об упорядочении известна заранее. [49]