Cтраница 3
В предыдущем пункте мы сделали еще один шаг, позволяющий внести существенные упрощения в задачи теории расписаний. Но все же задачи этого типа остаются еще очень сложными и для организации рациональных вычислительных процедур необходимы дальнейшие упрощения. [31]
В этом параграфе мы ограничимся описанием четырех приемов, носящих эвристический характер, которые позволяют качественно упростить задачи теории расписаний. [32]
Материал данного параграфа может быть использован при разработке эффективных алгоритмов решения многих дискретных задач, в том числе задач теории расписаний. [33]
Критериями качества расписания могут быть: суммарное время простоя всех машин, суммарные издержки на обработку серии изделий, число комплектов изделий, обработанных в заданное время, и др. При решении задач теории расписаний применяются самые разнообразные методы - от динамич. [34]
Заметим, что кривая x ( ti) всегда является монотонной. Интерпретация задачи теории расписаний как динамической задачи, разумеется, никак не меняет ее содержания - она продолжает оставаться одной из труднейших задач дискретного программирования. Главная трудность рассматриваемой задачи состоит в отсутствии упорядоченности фазовых состояний. [35]
Согласно сказанному задача теории расписаний сводится к определению управления Ы; ЕЕ. [36]
Задача о коммивояжере описывает класс моделей нахождения маршрутов развозки груза, минимизирующих суммарный пробег. Что же касается задачи теории расписаний, то она является моделью основной массы задач организации производства. [37]
Причем нередко чем более специален такой метод, тем эффективнее задача решается на ЭВМ. Специальными комбинаторными задачами являются задачи теории расписания. [38]
Эта задача решается на стадии организационно-технической подготовки к строительству для обеспечения планомерного развертывания и осуществления строительно-монтажных работ индустриальными поточными методами и выполнения установленных плановых показателей. Она относится к классу задач теории расписаний и является многокритериальной и комбинированной. [39]
В настоящий момент отсутствует исчерпывающее объяснение удач или неудач различных вычислительных экспериментов. Все же для задачи коммивояжера и задачи теории расписаний является правдоподобным следующее соображение. [40]
В третьей главе рассматриваются вопросы минимизации так называемых приоритето-порождающих функционалов на множестве перестановок элементов конечного множества N, сохраняющих заданный на N строгий порядок. В терминах минимизации приоритето-порождающих функционалов естественным образом формулируются многие задачи теории расписаний. Там же вводится понятие приоритето-порождающего функционала. В § 2 описываются преобразования графа G редукции отношения строгого порядка, заданного на N. [41]
К числу NP-полных задач относится много таких, которые используются при анализе экономических процессов математическими методами. Это задачи целочисленного программирования, задачи оптимизации времени выполнения инвестиционных проектов, задачи оптимизации на графах, задачи теории расписаний и многие другие. [42]
Минимизация этой функции производится методом ветвей и границ. Задача составления расписания в наиболее общих случаях относится к числу трудно формализуемых, и обычно расписания составляют, исходя из особенностей конкретной оптимизируемой системы; известную трудность представляет также решение задач теории расписаний. По содержанию эти задачи относятся к классу комбинаторных, для которых существенное значение имеет размерность. Как правило, размерность ладач составления оптимальных расписаний настолько велика, что решать их простым перебором вариантов не представляется возможным даже на современных быстродействующих вычислительных машинах. Часто задачи составления расписаний сводятся к задачам целочисленного линейного программирования ( в том числе многоиндексного), для решения которых используются широко известные методы отсечения или ветвей и границ. Рассмотрим несколько примеров составления оптимальных расписаний. [43]
Но при этом задача перестает быть устойчивой: приходится умножать большие величины на очень малые. Потому, как уже неоднократно отмечалось в данной монографии, метод функций штрафа не дает возможности проводить расчеты с высокой точностью. Но задача теории расписаний, как правило, и не требует высокой точности. По этой причине указанный подход оказывается применимым к широкому классу подобных задач. [44]
Эволюция системы (7.2) стеснена еще условиями подчиненности. Такая переформулировка задачи теории расписаний открывает определенные перспективы для применения итерационных методов, разработанных в теории оптимальных управлений. [45]