Cтраница 3
Минимизация этой функции производится методом ветвей и границ. Задача составления расписания в наиболее общих случаях относится к числу трудно формализуемых, и обычно расписания составляют, исходя из особенностей конкретной оптимизируемой системы; известную трудность представляет также решение задач теории расписаний. По содержанию эти задачи относятся к классу комбинаторных, для которых существенное значение имеет размерность. Как правило, размерность ладач составления оптимальных расписаний настолько велика, что решать их простым перебором вариантов не представляется возможным даже на современных быстродействующих вычислительных машинах. Часто задачи составления расписаний сводятся к задачам целочисленного линейного программирования ( в том числе многоиндексного), для решения которых используются широко известные методы отсечения или ветвей и границ. Рассмотрим несколько примеров составления оптимальных расписаний. [31]
Оценки, для исходной задачи об упаковке в контейнеры асимптотически наилучшие. В терминах задачи составления расписаний при наличии дополнительных ресурсов эти оценки более точно вычисляются как функции наибольшей потребности в ресурсах в предположении, что объем дополнительного ресурса / rtil и что любая его доля может потребоваться при выполнении данного задания. [32]
Связь между методом ветвей и границ и динамическим программированием была продемонстрирована на примере модельной задачи. В общем случае для заданной задачи составления расписания и заданного алгоритма динамического программирования, предназначенного для ее решения, может быть также найден эквивалентный алгоритм ветвей и границ. Эта связь не должна вызывать удивление. В обоих случаях соответствующее пространство решений может быть представлено в виде конечного ориентированного дерева частичных решений, и задача заключается в локализации и извлечении оптимального решения, при этом полный перебор осуществляется лишь в небольшой части полного дерева. [33]
Эти задачи называют также задачами составления расписаний. [34]
Поскольку в последнем случае уже нельзя заранее назначить сроки выполнения всех работ, то и рассчитать заранее критический путь, сроки наиболее раннего завершения проекта и резервы времени, вообще говоря, невозможно. Поэтому вопрос о составлении расписания работ часто решается с помощью других подходов, один из которых мы сейчас кратко изложим. Задача составления расписания осложняется тем, что состояние проекта описывается на языке графов, в то время как ограничения по ресурсам - на языке обыкновенных неравенств. [35]
Однако заметные успехи достигнуты лишь в решении частных задач, в к-рых число машин или число изделий весьма мало. Разработаны алгоритмы составления расписания для случая одной, двух и трех машин и произвольного числа изделии при различных критериях качества решения. Подробно исследована задача составления расписания обработки двух изделий на произвольном числе машин. Для общего случая до сих пор неясно, можно ли получить оптим. Пока не изучены важные для приложений стохастич. [36]
Однако заметные успехи достигнуты лишь в решении частных задач, в к-рых число машин или число изделий весьма мало. Разработаны алгоритмы составления расписания для случая одной, двух и трех машин и произвольного числа изделий при различных критериях качества решения. Подробно исследована задача составления расписания обработки двух изделий на произвольном числе машин. Для общего случая до сих пор неясно, можно ли получить оптим. Пока не изучены важные для приложений стохастич. [37]
Для решения этой задачи используются методы направленного перебора вариантов, позволяющие найти наилучшее расписание без полного перебора всех вариантов. Некоторые другие модели и задачи составления расписаний будут рассмотрены в параграфе, посвященном сетевым методам планирования. [38]
В силу своего переходного характера данные задачи часто включаются в состав подсистем ( систем) оперативного управления АСУП и в ряде случаев доводятся до уровня выполнения функций сменно-суточного планирования. Планирование в разрезе сменно-суточных заданий определяет [6]: необходимость переналаживания оборудования; необходимость временного прекращения выпуска на поточных участках; очередность запуска деталей; размер очередного сменно-суточного задания и другие операции. Опорной задачей оперативного планирования служит задача составления расписания [4,9] работ, рекомендуемых на запуск в производство. Выполнение функций и задач упреждающего контроля обеспечивает организационно-экономический аспект диспетчирования. [39]
В представленной выше общей концепции распределения ресурсов предусматривается, что все программы должны быть обеспечены ресурсами за исключением тех, которые могут быть заменены базовыми разработками. Поскольку ресурсы ограничены во времени, требуется сформулировать и решить задачу их оптимального распределения на заданный период упреждения без распределения программ во времени. Эта задача относится к классу задач составления расписания. [40]
Производственное расписание представляет собой развертку действий, необходимых для выполнения планов, во времени, фиксируя моменты их начала и завершения и определяя порядок их выполнения. Природа проблемы составления расписаний, встающей перед менеджерами, определяется в значительной степени структурой оперирующей системы и целями, которые необходимо достичь. В рамках заданных ограничений ( что-можно сделать в производственной системе и что должно быть сделано) менеджер решает задачу составления расписания. При этом сначала он должен решить, какой принципиальный подход необходимо использовать, разрабатывая расписание, затем определить необходимые процедуры этой деятельности, в первую очередь - процедуру увязки расписаний и производственных мощностей. [41]
Почти все виды прерывного производства имеют одну особенность: начатый на оборудовании период технологического процесса обязательно должен быть закончен. Для случая прерывного производства целесообразно заранее наметить, какой новый период будет начат на этом оборудовании после окон-яания каждого предыдущего периода, учитывая при этом занятость остального оборудования. Таким образом, в дополнение к задаче оперативного управления на интервалах непрерывности в данном случае встает еще задача определения целесообразных моментов перехода оборудования на новую продукцию. Если задача составления расписания становится основной задачей оперативного планирования на верхней ступени, то управление производством на интервале непрерывности переходит, как правило, в задачу оперативного управления следующей нижней ступени. Фактически задачей составления расписания является любая задача оперативного планирования прерывных производств, состоящая в распределении во времени заданной производственной программы, включающей различные виды продукции. Расписание может относиться не только к работе каждой установки или машины, но и к движению отдельных деталей по мере их обработки от одного рабочего места к другому. [42]
Задачи составления оптимального расписания запуска оборудования в схеме в целом и в каждой из ее стадий сложны с вычислительной точки зрения и принадлежат к числу так называемых универсальных дискретных задач. Это означает, что они эквивалентны по сложности, например, общей задаче целочисленного линейного программирования, или задаче о коммивояжере. В настоящее время неизвестны эффективные алгоритмы Для их точного решения. Для приближенного решения задачи составления расписания для ГАПС применяется метод ветвей и границ, который заключается в следующем. [43]
Минимизация этой функции производится методом ветвей и границ. Задача составления расписания в наиболее общих случаях относится к числу трудно формализуемых, и обычно расписания составляют, исходя из особенностей конкретной оптимизируемой системы; известную трудность представляет также решение задач теории расписаний. По содержанию эти задачи относятся к классу комбинаторных, для которых существенное значение имеет размерность. Как правило, размерность ладач составления оптимальных расписаний настолько велика, что решать их простым перебором вариантов не представляется возможным даже на современных быстродействующих вычислительных машинах. Часто задачи составления расписаний сводятся к задачам целочисленного линейного программирования ( в том числе многоиндексного), для решения которых используются широко известные методы отсечения или ветвей и границ. Рассмотрим несколько примеров составления оптимальных расписаний. [44]
Почти все виды прерывного производства имеют одну особенность: начатый на оборудовании период технологического процесса обязательно должен быть закончен. Для случая прерывного производства целесообразно заранее наметить, какой новый период будет начат на этом оборудовании после окон-яания каждого предыдущего периода, учитывая при этом занятость остального оборудования. Таким образом, в дополнение к задаче оперативного управления на интервалах непрерывности в данном случае встает еще задача определения целесообразных моментов перехода оборудования на новую продукцию. Если задача составления расписания становится основной задачей оперативного планирования на верхней ступени, то управление производством на интервале непрерывности переходит, как правило, в задачу оперативного управления следующей нижней ступени. Фактически задачей составления расписания является любая задача оперативного планирования прерывных производств, состоящая в распределении во времени заданной производственной программы, включающей различные виды продукции. Расписание может относиться не только к работе каждой установки или машины, но и к движению отдельных деталей по мере их обработки от одного рабочего места к другому. [45]