в случае b1 = prec1 граф обозначается . Если в для двух заданий Ji и Jj имеется путь с Ji в Jj (обозначается Ji®Jj), то выполнение задания Jj не нач­нется, пока задание Ji не будет выполнено на всех машинах;

в случае b1 = prec2 граф обозначается . Если в существует путь из Ji в Jj (JiÞJj), то выполнение задания Jj на некоторой машине может начаться тогда, когда на этой машине будет выполнено задание Ji;

если b1 = °, то для заданий не задано отношение порядка.

С помощью параметра b2 уточняется структура графа отношения по­рядка:

b2 = chain – граф представляет собой цепочку;

b2 = chain-wip – граф состоит из цепочки и множества изолированных вершин (chain with isolated points);

b2 = tree – отношение порядка на множестве заданий имеет структуру дерева. Это означает, что каждая вершина имеет максимум одного предшественника (вхо­дящее дерево) или каждая вершина имеет максимум одного преемника (выходящее дерево). Дальнейшее выполнение задания Ji может осуществляться только после оконча­ния выполнения всех его пред­шественников;

b2 = tree1 (tree2) – на множестве заданий задано отношение порядка, аналогичное prec1 (prec2), имеет структуру дерева.

В случае b2 = ° граф имеет произвольную структуру.

В случае b3 = «tij =1» речь идет об одинаковой (единичной) длительности выполнения каждого задания на каждой машине.

Если b3 = pmtn, то разрешены прерывания выполнения заданий машинами.

НЕ нашли? Не то? Что вы ищете?

Если b3 = «ri ³0», то для каждого задания существует момент готовности к выполнению ri, прежде которого не может начаться выполнение данного задания.

Третья позиция g обозначает критерий, который минимизируется:

: момент окончания выполнения всех заданий;

: взвешенный момент окончания выполнения всех заданий;

: максимальное отклонение от директивного срока, где откло­не­ние  =  – , – директивный срок;

: взвешенное запаздывание, где запаздывание = max{0, };

: взвешенное количество запоздавших заданий, где  = ;

: общие затраты, где , i = – произвольные монотонные неубывающие функции затрат.

Критерии рассматриваются часто без весовых коэффициентов, т .е. при =1, i = .

В некоторых случаях разыскивается только допустимое решение, без необходимости оптимизации критерия. Этот факт обозначается g = °.

Хороший обзор алгоритмов решения задач теории расписаний приведен в [138]. При исследовании задач ТР оказалось, что большинство этих задач при­на­дле­жит к классу труднорешаемых задач комбинаторной оптимизации. Аппара­том для оценки сложности их решения стала теория сложности (Кук [104], Карп [142]), возникшая в начале 70-х годов ХХ столетия. Более полное изложение этой теории было дано Гэри и Джонсоном в [8].

Лейджвег и др. [147, 148] создали компьютерную программу MSPCLASS для автоматической классификации задач ТР. Она базируется на классифи­кационной схеме Грэма/Лоулера/Ленстра/Ринной Кена и определяет задачи, являющиеся минимальными NP-полными, максимальными полиномиально решаемыми, максимальными псевдополиномиально решаемыми, минимально открытыми, максимально открытыми. Приведем некоторые определения [8]:

Определение 8.3. Если задано семейство C подзадач некоторой NP-полной задачи, то задача ПÎC является минимальной NP-полной подзадачей, если известна NP‑полнота задачи П и у нее нет подзадачи П', которая была бы NP‑полной и принадлежала к семейству C.

Определение 8.4. Задача ПÎC является максимальной полиномиально разрешимой подзадачей, если известна ее принадлежность к классу P и в семействе C нет задачи П', которая была бы разрешимой за полиномиальное время и содержала бы П как подзадачу.

Аналогично вводится понятие максимальной псевдополиномиально разреши­мой задачи – т .е. сложнейшей задачи, которая решается псевдополиномиально.

Аналогичным образом определяются минимальная и максимальная открытые подзадачи семейства C. Минимальные открытые – задачи, сложность которых неизвестна, но все более простые случаи являются полиномиально решаемыми. Максимальные открытые – задачи, сложность которых неизвестна, но все более сложные случаи являются NP‑полными.

С целью модификации результатов определения сложности и расширения клас­­­сификации на новые классы задач ТР создана программа CLASS [174]. Точные ме­­то­ды решения задач ТР предложены лишь для некоторых специальных классов за­­дач [24]. Это обусловлено характером ограничений, которые накладываются на спо­со­бы выполнения элементарных операций и на воз­мож­ности использования ре­су­рсов. Поэтому основной подход к их решению состо­ит в при­менении при­бли­жен­ных ме­то­дов, базирующихся на информационном моде­лиро­ва­нии производст­вен­ных про­цессов с широким использованием разнообразных эврис­тик.

Рассмотрим методы, применяющиеся к решению труднорешаемых задач комбинаторной оптимизации. Их обобщенное пред­с­тав­ле­ние с указанием категории (приближенный метод или метод оптимиза­ции), конструктивности (строит решение, исходя из данных задачи, или является итера­ционным, т. е. модифицирует решение при постоянном переупорядочении после­до­вательности заданий) приведено на рис. 8.1 [138].

Можно считать, что одной из первейших работ в теории расписаний была ра­бота Джонсона [141], в которой был предложен оптимальный алгоритм сос­тав­ления рас­писания для случая двух машин. Тогда же были предложены другие эф­фек­тив­ные полиномиальные методы для задач размерностей 2 ´ m [86], n ´ 2 (для слу­чая, где не больше, чем 2 операции для одного задания) [137] и n ´ 2 (где все операции имеют единичное время выполнения) [136]. Вообще, одним из бо­лее продуктивных периодов в управлении и исследовании операций были 1950-е годы. Много задач решено с при­менением приближенных, но эф­фек­тивных эври­с­тик, что создало основу для раз­вития классической ТР.

Главная переборная стратегия – это метод ветвей и границ, при котором выпо­л­ня­ется неявный поиск в динамично конструируемом дереве, представляющем про­странство всех допустимых решений. Этот метод формулирует процедуры и прави­ла, которые позволяют исключать просмотр больших частей дерева, и много лет был популярнейшим методом. Хотя он подходит для случаев, когда размерность за­да­чи N < 250, чрезмерные вычислительные требования не позволяют применять его к задачам большой размерности. Кроме того, его работа очень чувствительна к индивидуальным случаям и начальным значениям верхних границ [151].

Рис. 8.1. Методы решения ТЗКО

На протяжении 1970-х и к середине 1980-х годов акцент был сделан на обо­с­но­ва­ние сложности. Исследования показали, что обоб­ще­ния зада­ч, которые были раз­решимы как частные случаи в 1950-х, как и многие другие задачи, относятся к NP-сложным задачам. Гери и Джонсон [8] при­водят 320 NP-сложных задач.

Благодаря высокой трудоемкости точных переборных методов прибли­женные методы (методы аппроксимации) стали жизнеспособной аль­тер­на­тивой. Хотя эти методы не гарантируют нахождения оптимального решения, они могут исполь­зоваться для решения задач большой размерности с большой скоростью.

Первейшие приближенные алгоритмы – правила приоритетного упорядо­че­ния. Эти методы построения назначают приоритет всем заданиям, которые доступ­ны для упорядочения, а потом выбирают задание с макси­мальным приоритетом. Они очень про­сты в реализации и имеют низкую вычислительную сложность. Было создано ог­ро­мное множество разных правил [170], и исследования, проведен­ные в этой облас­ти, указывают, что наилучшие методы содержат линейную или слу­чай­ную комби­на­цию разных правил приоритетного упорядочения [113, 153, 170]. Новые подходы – нечеткая логика (Фуцзи-логика) [129] и генетический ло­ка­льный поиск [108]. Одна­ко, в [138] констатируется: сильная зависимость правил приоритетного упорядоче­ния от свойств задачи делает невозможным прио­ритетность ни одного из правил; качество решения ухудшается с возрастанием размерности задачи.

В конце 1980-х годов внимание концентрируется на приближен­ны­х методах. Но из-за несовершенства правил приоритетного упорядочения возни­ка­ет потреб­ность в методах, применение которых будет более перс­пек­тивным. Работа над этими проблемами была инициирована Фише­ром и Рин­ной Кеном [115], которые подчеркивали фундаментальные свойства методов генера­ции хороших эвристик: развитие, анализ и реализация. Пригодность этих методов была в дальнейшем освещена Комитетом по исследованию операций (Com­mittee On the Next Decade of Operations Research CONDOR, 1988), который ука­зал на их чрез­вы­чайную перспективность. В то же время в обзоре [179] сде­лан акцент на гибкости и мощности методов эвристического поиска по сравнению с методами оптимизации. Итак, в этом направлении был достигнут значительный прогресс, и за короткий период (1988–1991 гг.) были сформулированы некоторые из новых алгоритмов.

Гловер и Гринберг [126] отмечают появление эвристических стратегий ре­ше­ния сложных задач, возникающих при решении интеллектуальных проблем. Исследова­ния в период бума были главным образом сконцентрированы на при­­ближенных ме­то­дах. Работы велись и в направлении оптимиза­цион­ных методов, но с примене­нием принципов, полученных из новых эвристических стратегий.

В [120, 184] приведены решения производственных задач с использованием ме­то­­дов удовлетворения ограничений, в то же время применение нейронных сетей (1988 – 1991) [116, 117, 118, 206, 207] обеспечивало решение задач размерности 20 ´ 20:

– оптимизация «большого шага» (1989) [158];

– поиск Tabu (1989, 1990) [124, 125, 193];

– моделированный обжиг (1988 – 1991) [84, 160, 199];

– генетические алгоритмы (1991) [111, 164];

– генетический локальный поиск (1989 – 1991) [84, 162].

Главное достоинство этих работ – введение локального поиска для решения труднорешаемых задач комбинаторной оптимизации [140, 204]. В последние годы проводилась значительная исследовательская работа, связанная со сравни­тельным анализом существующих и разработкой новых, усовершенст­во­ванных методов локальной дискретной оптимизации. Предпосылкой такой работы был широкомасштабный эксперимент по решению на ЭВМ оптими­за­ционных дискретных задач разными алгоритмами локальной опти­ми­зации [24]. На­и­­более эффективными оказались алгоритмы, в которых ком­би­нируются разно­об­разные идеи, развиваемые теорией локальной оптимизации. Все локальные методы базируются на едином подходе к ре­шению задачи, который состоит в улучшении некоторого решения путем по­иска среди множества допустимых решений задачи.

Был осуществлен сравнительный анализ таких методов локальной оптимиза­ции [24]: вектора спада, обжига, табу, глобального равновесного поиска. Общей про­б­лемой для этих методов является выбор стратегии поиска, т. е. правильного объ­е­динения процессов расширения и сужения области поиска с целью нахождения глобального оптимума. Задача состоит в том, чтобы после получения некоторого локального оптимума перейти в область тяготения другого локального оптимума, т. е. выйти из области найденного локального оптимума и таким образом расширить район поиска (так называемая диверсификация поиска). С другой стороны, для на­хождения улучшенного решения логично исследовать точки, близкие к полу­чен­но­му локальному оптимуму, т. е. сузить область поиска (интенсификация поиска).

Дальнейший толчок дал метод, который имел сильнейшее влияние на методы при­ближения – процедура сдвига узкого места [85]. Одна из главных причин того, что этот конструктивный алгоритм дает хорошие результаты – развитое алго­ри­тми­че­ское и программное обеспечение решения задач построения расписаний для одной машины. Процедура сдвига узкого места характеризуется следующими зада­чами: определение подзадачи, выбор узкого места, решение подзадачи и повторная оптимизация расписания [107]. Фактически стратегия сводит задачу к m задачам для одной машины и решает каждую из подзадач. Каждое из одномашинных решений срав­­нивается со всеми другими, и машины упорядочиваются по их решениям. Ма­ши­на, которая имеет наибольшую нижнюю границу, обозначается как узкое место. Процедура сдвига узкого места строит расписание сначала для машины, которая яв­ля­ется узким местом, игнорируя остаток машин, для которых расписание не пос­т­ро­е­но и фиксируя загруженные машины. Каждый раз, когда расписание для уз­кого места построено, для каждой из машин, для которых выполнено предшест­вующее упо­рядочение, выполняется локально повторная оптимизация при решении одно­ма­шин­ной задачи. Главный вклад данного подхода – сведение к одномашинной задаче при поиске последовательности машин, для которых строится расписание. Но фун­да­ментальная проблема этой процедуры – сложность выполнения повторной опти­ми­зации и генерация невыполняемых решений. В одной из последних работ [90] объе­ди­няется регулированный переменный поиск с процедурой сдвига узкого места, что создает один из лучших имеющихся подходов к решению труднорешаемой задачи комбинаторной оптимизации «Минимизация максимального момента окончания выполнения заданий m маши­на­ми». Хотя в [90] предлагается несколько сложных схем переоптимизации, пока нет стратегии, позволяющей это сделать. Поэтому эта процедура требует модификации.

Указанная процедура была включена также во много других работ [101, 197, 202], которые улучшали верхние и нижние границы некоторых труднорешаемых задач. Дальнейшее обобщение выполнено Белес с коллегами [89], которые скомбини­ро­вали точный подход к решению задачи выполнения работ одной маши­ной с регули­руемым переменным поиском и применили это к решению задачи job-shop плани­рования с директивными сроками.

Рассмотрим некоторые аппроксимационные методы, созданием и формализа­ци­ей которых завершился период бума. Алгоритм вставки Вернера и Винклера [201] состоит из двух стадий. На первой стадии применяется конструктивная стратегия, со­гласно которой задание позиционируется в расписании таким образом, чтобы ми­ни­мизировать опре­де­лен­ный критерий. На второй стадии применяется стратегия повторной вставки для ите­ра­ционного улучшения начального решения. На этих ста­диях применяется лучевой поиск [161] для улучшения поиска. Лучевой поиск соде­р­жит эвристики, ко­то­рые исключают необходимость отслеживать каждый возмож­ный выбор, начиная с некоторого момента. Поиск выполняется в ширину, но без об­ра­тного шага, что напоминает стратегию списка кандидатов в табу-поиске [127], также позволяющую ограничить количество разыскиваемых параллельно решений.

Фильтрующая лучевая стратегия была наложена на решения, получен­ные набо­ром процедур узкого места, и опыт свидетельствует [182] о том, что этот подход обес­пе­чи­вает существенное улучшение для результатов, полученных исклю­чи­тельно про­це­дурами узкого места.

Методы удовлетворения ограничений – это пример итерационных аппрок­си­ма­ционных методов, применяющих много правил и стратегий, которые исполь­зу­ются в алгоритмах ветвей и границ. Они направлены на уменьшение эффективного размера поискового пространства при применении ограничений на порядок выбора переменных и на последовательности, в которых каждая переменная приобретает необходимое значение. Эти методы сконцентри­рованы на достижении допустимых расписаний, в которых общий дирек­тивный срок не нарушается. Многие из этих ме­тодов имеют сложность в формализации ограничений и требуют чрезмерного пере­бора с возвратом. В ре­зуль­тате констатируется их плохая сходимость. Вообще, с по­мо­щью этих методов были получены незначительные результаты, тогда как тре­бова­ния к вы­чис­ли­тельной трудоемкости – высокие [101, 166, 173].

Подобные выводы были сделаны относительно нейронных сетей, кото­рые обес­пе­чивают возможность выполнения распределенного выполнения с ис­поль­зо­ванием простых, но очень больших взаимосвязанных структур парал­лельно выполняемых единиц, и только работа [183] была успешно примене­на к эталонным задачам.

Другие упомянутые итерационные методы – это методы пространства задач, ко­то­рые, используя быстродействующие, ориентированные на специ­фику задачи, кон­с­труктивные процедуры, генерируют множество разных стар­товых решений, ко­то­рые потом улучшаются локальным поиском. Этот класс методов включает поиск, который базируется на пространстве задач и эв­ристик, и процедуру «жадный случайный адаптивный поиск» (GRASP) [175].

Популярнейшие итерационные методы – пороговые алгоритмы, в процессе ра­боты которых выбирается новая конфигурация, если разность в стоимости между те­ку­щим решением и соседним – ниже данного порога. Представители этой группы – алго­ритмы: итерационного улучшения, пороговой прием­ле­мости и моделиро­ван­ного обжига. Из-за ограниченности первого и относительного несо­вер­шенства второго мо­делированный обжиг – наиболее попу­лярный метод в этой категории.

В моделированном обжиге порог – добавочный и стохастический. Моделиро­ван­ный обжиг – метод случайного ориентированного локального поиска, заимст­во­ван­ный из статистической физики по аналогии с методом компьютерного моде­ли­рования процесса выжигания горячего металла до состояния ми­нимума энергии. К сожалению, расписания обжига, которые обеспе­чивают сходи­мость к глобальному оп­тимуму, на практике применяться не могут, так как требуют огромных затрат машинного времени. Кроме того, асимптотическая сходимость метода обжига хуже, чем в других подобных методах [24]. В настоящее время исследования на­пра­в­ле­ны на его интеграцию с другими методами для улучшения результатов и сокра­ще­ния времени вычисления. Объединение с критической окрестностью и генерацией эффективных расписаний [203, 202], а также с генетическими алгоритмами [145] сде­лало моделированный обжиг конкуренто­способным относительно качества ре­ше­ния, но он все еще требует чрезмер­ных вычислительных усилий.

Генетические алгоритмы – методы поиска, базирующиеся на абс­трак­т­ной мо­де­ли естественного развития. Они не могут генери­ровать подходящие реше­ния без по­тери эффективности. Кроме того, многие из указанных алгоритмов не спо­соб­ны схо­диться к оптимальному решению. Эти недостатки иници­ировали работу над ге­не­ти­че­ским локальным поиском [132, 162, 196, 195], двухуровневым ме­тодом ло­ка­ль­но­го поиска, в котором потомок, полу­ченный генетическим алгорит­мом, используется как начальное решение для дальнейшего локального поиска.

Оптимизация «большого шага», как и генетический локальный поиск, служит примером двухуровневого метода локального поиска. Этот метод двух­этапной опти­ми­зации, созданный Мартином и др. [158, 159], состоит из большого оптими­зи­ру­ю­ще­го перемещения (большой шаг) и даль­нейшего локального поиска (маленький шаг). Маленький шаг обычно осу­ществляется с помощью методов итерационного улу­чшения или модели­рованного обжига. Большой шаг предполагает применение специфических мето­дов, которые позволяют превышать локальный минимум. Это от­но­сительно новый метод, который был применен только к задаче мини­мизации ма­ксимального момента окончания выполнения заданий m машинами [155, 156, 157]. Анализ показывает, что этот метод имеет очень высокие вычислительные тре­бо­вания, но обеспечивает лучшие резуль­таты по сравне­нию с теми, которые полу­че­ны только применением методов локального поиска. Двухуровневая стратегия по­доб­ного типа, использованная Брукером и др. [97, 98], в применении к более ши­ро­кой области задач ТР позволяет получать некоторые перспек­тивные результаты.

Поиск табу предложен Гловером [122, 123, 124, 125]. Отно­ся­щийся к ите­ра­ционным аппроксимационным, этот простой метод интеллектуально направ­ляет процесс по­ис­ка (базируясь на доступной информации) от решений, которые дублируют или похожи на предвари­тельно полученные решения. Основной идеей метода табу является запрет некоторых переходов, которые были использованы раньше, с целью избе­жания повтор­ной посещаемости точек.

Более сложные схемы могут применяться для усиления поиска в облас­тях, которые являются «хорошими» или расширяют поиск в неисследованных областях пространства решений. Метод, который предложен в [165] – сегодня один из мощ­ных подходов табу-поиска, позволяющий быстро получать хорошие решения. Несмотря на его очевидные преимущества, метод не в полной мере использует те­кущие результаты решения задачи: они применяются лишь для того, чтобы из­бежать зацикливания, а не для того, чтобы организовать эффективный поиск гло­бального оптимума [24].

Таким образом, при рассмотрении методов решения труднорешаемых задач комбинаторной оптимизации мы возвратились к понятию эвристики 50-х годов ХХ столетия, но с некоторыми новыми и усовершенствованными модификациями. В настоящее время доминируют методы, которые имеют гибрид­ное строение и переступают границы недостаточных минимумов при интегрирова­нии специфических для задачи локальных эвристик с общим метарешателем.

Усилиями многих ученых разработка алгоритмов была систематизирована, создана система базовых алгоритмов решения многих классов задач, получены оценки алгоритмов. Однако сегодня проблема стоит гораздо шире: для обеспечения эффективности функционирования сложных систем возникла необходимость разработки систем новых высокоэффективных взаимосвязанных алгоритмов, которые бы позволили эффективно решать задачи планирования и управления в комплексе.

Как показывает приведенный выше обзор, ни один из известных методов не может эффективно решать поставленные задачи планирования и управления в современных условиях в соответствии с требованиями, приведенными в п. 8.2. В главе 9 представлено описание эффективного эвристического мега-алгоритма решения многоэтапных задач календарного планирования по семи различным критериям оптимальности с естественным обобщением на 31 критерий. Его эффективность основана на принципе иерархического планирования и комплексе взаимосвязанных математических моделей и методов.

В п. 8.5 приведена иерархическая модель планирования и управления сложными системами с сетевым представлением технологических процессов и ограниченными ресурсами [56], в которой общая математическая модель задачи календарного планирования, являющаяся многостадийной задачей календарного планирования, заменена последовательностью дискретных математических моделей, совместимых с иерархией решений, принимаемых на каждом уровне управления. Создана система новых высокоэффективных взаимосвязанных алгоритмов решения задач планирования в современных условиях и эффективная формальная процедура решения слабоформализованной задачи выбора наилучшего плана из множества планов, построенных по разным критериям оптимальности. В отличие от существующих эвристических алгоритмов решения многостадийных задач календарного планирования, лучшие из которых содержат линейную или случайную комбинацию разных правил предпочтения, не гарантирующих качества полученных решений, в процессе решения задачи планирования определяется стратегия поиска глобального оптимума, что позволяет получать решения, близкие к оптимальным.

В состав алгоритмического обеспечения модели вошли ПДС-алгоритмы задач МСЗ (глава 1), МВМ (глава 2) и МСЗП (глава 3).

Исследована (см. главу 10) возможность применения разработанной иерархической модели планирования и управления сложными системами в следующих прикладных областях:

–  Производства дискретного типа;

–  Производства «на заказ»;

–  Рабочий цех;

–  Производства по изготовлению партий;

–  Строительные производства;

–  Системы планирования и управления проектами.

8.5  Иерархическая модель планирования и управления сложными системами с сетевым представлением технологических процессов и ограниченными ресурсами

Общая постановка задачи планирования. Пусть задано множество n комплексов взаимосвязанных работ J = {J1, J2, …, Jn} (комплекс работ Ji, i = , в дальнейшем называется заданием). На каждом подмножестве Ji частичный порядок задан ориентированным ацикличным графом. Частичная упорядоченность очевидным образом определяется технологией выполнения комплекса работ. Каждая следующая работа может начаться только по завершению предыдущих работ. Вершины графа отвечают работам, связи указывают на отношения предшествования. Конечные вершины отвечают завершению выполнения заданий. Для каждой вершины j графа известна lj – детерминированная продолжительность выполнения (интегрированный показатель, отображающий выделенные ресурсы – материальные, человеческие, производственные; длительность выполнения каждого задания определяется его критическим путем); для каждой работы i Î I (I – множество конечных вершин, идентифицирующихся с множеством заданий) задан вес wi; для отдельных заданий задан директивный срок окончания di. Величина веса определяется потенциальной сложностью, важностью и неоднозначностью (для работ, связанных с необходимостью получения нового научного решения) выполнения тех работ, без которых в целом задание не может быть выполнено. Для выполнения работ применяется множество ограниченных ресурсов. Совокупность ресурсов и исполнителей разделена на отдельные, достаточно автономные модули – мультиресурсы (мультиресурс – устойчивая группа совместно работающих ресурсов – например, бригада, группа однотипного оборудования, однопрофильное подразделение). Мультиресурсы могут находиться как в одной, так и в разных организациях. В общем случае, если это обусловлено производственной необходимостью и позволит более эффективно выполнить заданный объем работ, то в состав мультиресурса может быть включено разнотипное оборудование.

Необходимо построить согласованный план выполнения комплексов работ мультиресурсами и распределение выполнения работ по ресурсам с учетом критериев оптимальности, указанных ниже, и их комбинаций.

Главная цель планирования в условиях рынка – максимизация прибыли предприятия. Поэтому максимизация прибыли является общим критерием оптимальности для всех уровней модели планирования. Прибыль рассчитывается как планируемый доход от реализации всех изделий (выполнения всех заданий) минус затраты З (все издержки), очевидным образом рассчитываемые по оптимальному расписанию в блоке принятия решений. В процедуру принятия решений и максимизацию прибыли оптимизация по З не входит.

В модели рассматриваются следующие критерии оптимальности и их комбинации.

Задача 1. Максимизация суммарной прибыли предпри­ятия в случае отсутствия директивных сроков.

В обеспечении прибыльности предприятия важное значение играет фактор времени. В выигрыше будет тот, кто обеспечивает максимально быстрое выполнение заказов и сокращение времени выхода на рынок новых товаров. При отсутствии директивных сроков прибыль от реализации і-го изделия (выполнения і-го задания) является функцией времени и равна Pi(t) = wi(T)∙(T – Ci), где wi(T) – весовой коэффициент изделия (задания) i, определенный экспериментальным путем; T – плановый период; Cі ≤ T – момент окончания выполнения изделия (задания) i, соответствующий моменту окончания выполнения его конечной вершины. Критерий максимизации суммарной прибыли предприятия в этом случае определяется выражением

, (8.4)

где P – гарантированный минимальный доход от продажи (выполнения) всех n изделий (заданий). Таким образом, максимизируемая функция имеет вид

max,

отсюда критерий оптимальности: (критерий 1).

Итак, критерий F1 эквивалентен критерию минимизации суммарного взвешенного момента окончания выполнения заданий при заданном отношении порядка на множестве работ каждого задания.

Задача 2. Максимизация суммарной прибыли предпри­ятия при условии: для всех заданий i Î I введены директивные сроки di, которые не могут быть нарушены (планирование «точно в срок»):

max – З, где Ui = ,

wi – прибыль от выполнения i-го задания, если оно выполнено точно в срок. Критерий оптимальности: max (критерий 2);

Задача 3. Максимизация суммарной прибыли предпри­ятия при условии: для некоторых заданий i Î  заданы директивные сроки, которые не могут быть нарушены, для остальных заданий di = 0:

max, где Ui = ,

где P – гарантированный минимальный доход от продажи (выполнения) изделий (заданий) ; wi – прибыль от выполнения i-го задания, если оно выполнено точно в срок; wi(T) – весовой коэффициент задания i (имеет тот же смысл, что и в задаче 1). Критерий оптими­зации:

max (критерий 3);

Задача 4. Максимизация суммарной прибыли предпри­ятия при условии: для всех заданий i Î I введены директивные сроки di, необходимо минимизировать суммарное взвешенное запаздывание выполнения заданий относительно директивных сроков:

max ,

где P – гарантированный минимальный доход от продажи (выполнения) всех n изделий (заданий), если все они выполнены без запаздывания; wi – штраф за запаздывание окончания выполнения i-го задания относительно директивного срока на единицу времени. Критерий оптимизации:

min (критерий 4);

Величина – уменьшение дохода P в случае выполнения задания i с запаздыванием Ci – di. Решение по выполнению или отказу от выполнения таких заданий принимается в блоке принятия решений.

Задача 5. Постановка задачи соответствует задаче 4 с дополнительным условием: для некоторых заданий i Î  директивные сроки не могут быть нарушены:

max, где Ui = ,

– прибыль от выполнения i-го задания, если оно выполнено точно в срок; – штраф за запаздывание окончания выполнения i-го задания относительно директивного срока на единицу времени, P – гарантированный минимальный доход от выполнения заданий , если они выполнены в срок. Критерий оптимальности:

max (критерий 5).

Величина – уменьшение дохода P в случае выполнения задания i с запаздыванием Ci – di. Решение по выполнению или отказу от выполнения таких заданий принимается в блоке принятия решений.

Задача 6. Для всех заданий i Î I введены директивные сроки di. Для каждого задания указана величина wi – абсолютная прибыль от выполнения задания, не зависящая от момента окончания выполнения задания в том случае, если задание выполняется без запаздывания относительно директивного срока, иначе прибыль предприятия по этому заданию равна нулю. Задача – максими­зировать суммарную прибыль предприятия:

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3