Проблема планирования

Проблема планирования и планирования

Автоматизированное планирование и планирование связаны с выполнением стратегий или последовательностей действий. Современное планирование, даже в рамках ИИ, все больше отражает интеграцию теории и высокопроизводительных алгоритмических методов из исследования операций, по крайней мере, с 1950-х годов.

Введение в проблемы планирования

Планирование — это организация достижения целей в конкретной области с использованием различных средств и в течение периода/иерархии. Результатом этой задачи является «план», подробно отвечающий на вопросы типа QQOQCC: кто, что, где, когда, как и сколько.

Задача планирования позволяет в зависимости от условий и информации ответить на следующие вопросы:

  • Как управлять логической последовательностью задач и распределять их по времени?
  • Как анализировать рабочие нагрузки, запрашиваемые из ресурсов или средств, если они ограничены?
  • Как выразить потребность в ресурсах или средствах, если они не ограничены?
  • Как учесть внешние по отношению к проекту ограничения (заказ клиента, доставка поставщиком и т. д.)?
  • Как анализировать последствия разрыва между реальными и прогнозируемыми событиями?
  • Как определить самые поздние даты начала или самые ранние даты окончания действий?
  • Как моделировать оптимистичные, пессимистические или наиболее вероятные гипотезы?
  • Как проанализировать влияние опасности или риска, если он превращается в проблему?
  • Как расставлять приоритеты в задачах?

Проблема назначения связана со многими другими проблемами исследования операций (редукция задач в 21 проблемы с карпом Например). Здесь мы увидим две подзадачи, часто встречающиеся в задачах о присваиваниях.

Подзадача: планирование

Проблема планирования — это проблема планирования задач, в которой необходимо определить порядок, в котором задачи должны выполняться. Эта задача является Np-трудной, учитывая разнообразие и сложность своих ограничений.

Различные методы, представленные в этом курсе, позволяют четко и быстро отображать данные, связанные с реализацией плана, такие как:

  • время, сроки
  • средства или ресурсы
  • Расходы.

Классическая задача планирования:

Пусть N задач Tя требующий периодая данные и дата начала tя быть определенным. На задачу накладываются два типа ограничений: временные ограничения – продолжительность и приоритет задачи; ограничения ресурсов – дизъюнктивные: если задачи i и j выполняются на машине k, то они должны выполняться именно в таком порядке; или кумулятивно: задача i потребляетик ресурса k. Ресурс ка имеет способность Ак. В любой момент времени сумма расходов на машине k должна быть меньше ее мощности.

Подзадача: задание

Эта проблема состоит в лучшем назначении задач агентам. Каждый агент может выполнять одну задачу за определенную стоимость, и каждая задача должна выполняться одним агентом. Все назначения (т. е. пары агент-задача) имеют определенную стоимость, цель состоит в том, чтобы минимизировать общую стоимость назначений для выполнения всех задач. Эта задача решается за полиномиальное время.

Учитывая набор агентов С и набор задач Т, можно смоделировать задачу график двухпартийный Г=((С,Т),Е), с весовой функцией против на гребнях. Таким образом, задача о назначении состоит в том, чтобы найти идеальная связь F⊂E, минимизирующий сумму ∑e∈F c(e) весов ребер Ф.

Подзадача: транспорт

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

Либоя количество товара, доступного в месте происхождения i; бя — количество продукта, необходимое в пункте назначения j; противij стоимость перевозки единицы товара из пункта отправления i в пункт назначения j; и хij количество, перевезенное из пункта отправления i в пункт назначения j.

Вот проблема:

планирование графика перевозки

 

Если сумма источников равна сумме требований, говорят, что проблема уравновешена, и в этом случае ограничения становятся равными. В противном случае создается виртуальная точка спроса (фиктивная), соответствующая избыточному предложению и с нулевой транспортной стоимостью.

планирование графика перевозки

Транспортную задачу часто представляют в виде двудольного графа с задачей потока (сцепления). Здесь мы покажем другие варианты решения этой проблемы.

Делиться
ru_RURU
%d такие блоггеры, как: