8135

Планирование действий в реальном мире. Условное планирование. Непрерывное планирование

Лекция

Информатика, кибернетика и программирование

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

Русский

2015-02-01

45.5 KB

7 чел.

Планирование действий в реальном мире.

Условное планирование. Непрерывное планирование.

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

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

Рассмотрим упрощенную задачу сборки автомобиля, предусматривающую две работы: сборка автомобилей C1 и C2. Каждая работа состоит из трех действий: установка двигателя, установка колес и проверка результатов. Предположим, что двигатель должен устанавливаться в первую очередь, а проверка, безусловно, должна проводиться в последнюю очередь.

В тексте программы на языке CLIPS, приведенном ниже, используются следующие шаблоны для спецификации неупорядоченных фактов:

engine – спецификация факта начала установки двигателя e на шасси c с плановым временем t,

wheels – спецификация факта начала установки колес w на шасси c за время t,

chassis – спецификация факта использования шасси c,

enginein – спецификация факта окончания установки двигателя на шасси c,

wheelson – спецификация факта окончания установки колес на шасси c,

done – спецификация факта окончания поверки автомобиля, собранного на шасси c.

Правила addengine, addwheels и inspect описывают, соответственно, действия по установке двигателя, колес и проверке.

(deftemplate engine

(slot e (type SYMBOL))

(slot c (type SYMBOL))

(slot t (type INTEGER))

)

(deftemplate wheels

(slot w (type SYMBOL))

(slot c (type SYMBOL))

(slot t (type INTEGER))

)

(deftemplate chassis

(slot c (type SYMBOL))

)

(deftemplate enginein

(slot c (type SYMBOL))

)

(deftemplate wheelson

(slot c (type SYMBOL))

)

(deftemplate done

(slot c (type SYMBOL))

)

(deftemplate goal

(slot current-task (type SYMBOL))

)

(deffacts init

(engine (e E1)(c C1)(t 30))

(engine (e E2)(c C2)(t 60))

(wheels (w W1)(c C1)(t 30))

(wheels (w W2)(c C2)(t 15))                

(chassis (c C1))

(chassis (c C2))

)

(defrule init-system

(initial-fact)

=>

(assert (goal(current-task find)))

)

(defrule addengine

(engine (e ?e)(c ?c)(t ?d))

(chassis (c ?c))

(not (enginein (c ?c)))

(goal (current-task find))

=>

(assert (enginein(c ?c)))

(printout t crlf "addengine " ?e " " ?c " " ?d)

)

(defrule addwheels

(enginein (c ?c))

(wheels (w ?w)(c ?c)(t ?d))

(chassis (c ?c))

(goal (current-task find))

=>

(assert (wheelson(c ?c)))

(printout t crlf "addwheels " ?w " " ?c " " ?d)

)

(defrule inspect

(enginein (c ?c))

(wheelson(c ?c))

(chassis (c ?c))

(goal (current-task find))

=>

(assert (done(c ?c)))                      

(printout t crlf "inspect " ?c " 10")

)

(defrule finish-process

(done (c C1))

(done (c C2))

?goal-ptr <- (goal (current-task find))

=>

(retract ?goal-ptr)

(printout t crlf "Solution found" crlf)

)

Далее показан результат выполнения программы в среде CLIPS с использованием стратегии “в глубину” (depth). Так как действия по сборке обоих автомобилей лишь частично упорядочены, то есть действия, относящиеся к разным автомобилям, могут производиться параллельно, то полученный план можно изобразить так, как показано на рисунке 1. Продолжительность каждого действия обозначена в нижней части каждого прямоугольника, а значения самого раннего и самого позднего времени начала, показаны в верхней левой части.

addengine E1 C1 30

addwheels W1 C1 30

inspect C1 10

addengine E2 C2 60

addwheels W2 C2 15

inspect C2 10

Solution found

Рис.1

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


[0,0]

Start

0,15]

addengine1

30

[30,45]

addwheels1

30

[60,75]

inspect1

10

[85,85]

Finish

[0,0]

addengine2

60

[60,60]

addwheels2

15

[75,75]

inspect2

10


 

А также другие работы, которые могут Вас заинтересовать

686. Разработка технологического процесса изготовления детали 100 KB
  Расчет режимов обработки и основного (машинного) времени. Выбор технологического оборудования и технологической оснастки. Определение припусков и операционных размеров. Разработка маршрутно-технологического процесса. Выбор вида заготовки и способа ее получения.
687. Нормализация условий труда при выполнении работы по приготовлению питательных сред для культуры бактерий Gluconacetobacter xylinus и последующий ее посев 74.5 KB
  Источники и причины проявления факторов опасного и вредного воздействия. Приготовление жидкой питательной среды на основе дрожжевого экстракта и глюкозы. Средства труда и технология выполняемой работы. Факторы опасного и вредного действия. Оценка класса и степени вредности условий труда.
688. Полупроводниковый диод 235 KB
  В данной расчетно-графической работе описываются параметры и характеристики диода Д18. В работе представлены характеристики диода, его паспортные параметры, рисунок конструкции, семейство ВАХ. Также имеются расчеты и графики зависимостей некоторых параметров.
689. Финансовый менеджмент, его основы и содержание 117 KB
  Сущность и функции финансов предприятий. Зарождение и эволюция финансового менеджмента. Финансовый механизм предприятия. Сущность, цель и задачи финансового менеджмента. Функциональное содержание финансового менеджмента.
690. Экспрессия гена. Трансляция 114.5 KB
  Регуляция экспрессии генов на уровне транскрипции у прокариот. Основные положения процесса экспрессии генов. Инициация у эукариот. Некоторые общие особенности процесса трансляции. Аппарат экспрессии генов и его логика.
691. Государственные и муниципальные организации. Формы государственного регулирования экономической жизни 115.5 KB
  Конкурсная организация государственной поддержки приоритетных направлений промышленной сферы. Формы государственного регулирования экономической жизни. Государство и рыночная инфраструктура. Два вида муниципальных организаций и их социальных функций.
692. Профілактика наркотичної залежності серед учнів, молоді у роботі соціального педагога 275 KB
  Наркотична залежність – як проблема соціальної педагогіки. Профілактика наркотизму як соціальна технологія. Робота соцального педагога з профілактики наркотичної залежності. Особливості і тенденції підліткової і юнацької наркоманії.
693. Отставание в психическом развитии 126.5 KB
  Оособенности мышления, речевого развития, игровой и учебной деятельности. Коррекционно-развивающее обучение детей с ЗПР. Олигофрения. Причины умственной отсталости. Обучение детей с умственной отсталостью.
694. Решение задачи коммивояжера 163.5 KB
  Описание реализация метода ветвей и границ и метода Монте-Карло при помощи средств объектно-ориентированного языка Java. Задача поиска кратчайшего гамильтонова цикла в полном графе. Процесс разбиения множеств на подмножества.