8135

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

Лекция

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

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

Русский

2015-02-01

45.5 KB

5 чел.

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

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

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

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

Рассмотрим упрощенную задачу сборки автомобиля, предусматривающую две работы: сборка автомобилей 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


 

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

27648. Побег из мест лишения свободы, из-под ареста или из-под стражи (ст. 313 УК), его отличие от уклонения от отбывания лишения свободы (ст. 314 УК) 27 KB
  Побег из мест лишения свободы изпод ареста или изпод стражи ст. 313 УК его отличие от уклонения от отбывания лишения свободы ст. Побег из мест лишения свободы или из под ареста или из при стражи ст.313 его отличие от уклонения отбывания лишения свободы ст.
27650. Подделка, изготовление или сбыт поддельных документов, государственных наград, штампов, печатей, бланков (ст.327 УК). Отличие данного преступления от служебного подлога (ст. 292 УК) 37 KB
  Бланк лист бумаги с оттиском углового или центрального штампа либо с напечатанным любым способом текстом штампа либо иным текстом текстом и рисунком используемый для составления документа бланк лицензии паспорта удостоверения анкеты заявления и т.1 имеет альтернативный характер: подделка удостоверения или иного официального документа предоставляющих права или освобождающих от обязанностей государственной награды штампа печати или бланка в целях использования указанных предметов; сбыт поддельного документа поддельных...
27652. Объект (непосредственный) 290-порядок функционирования гос. органов и органов местного самоуправления и муниципальных учреждений; 204-интересы службы в негосудар. организациях 106.5 KB
  Особо квалифицирующие признаки деяния совершены: группой лиц по предварительному сговору или организованной группой; с вымогательством взятки; в крупном размере. Различия по объекту преступления В коммерческом подкупе преступление против коммерческой организации в получении взятки преступление против гос. Дача взятки состоит в незаконном вручения передаче материальных ценностей или предоставлении выгод имущественного характера должностному лицу лично или через посредника за совершение действий бездействия входящих в служебные...
27653. Понятие вымогательства (ст. 163 УК), его объект и момент окончания. Отличие вымогательства от насильственного грабежа и разбоя. Обстоятельства, отягчающие совершение этого преступления 43.5 KB
  Отличие вымогательства от насильственного грабежа и разбоя. Отличие вымогательства от самоуправства ст. Вымогательство: Объект вымогательства: отношения собственности и личности.
27654. Понятие и виды обстоятельств, исключающих преступность деяния. Их социально-правовая природа и значение 29 KB
  Любое преступление как правило связано с причинением серьезного вреда охраняемым общест. Мера причиненного или грозящего вреда выражает основной признак любого преступления его общественную опасность. Однако в некоторых ситуациях причинение даже существенного вреда по своему социальному содержанию является полезным для личности и общества и в силу этого лишено общественной опасности и угол. Законом и господствующей моралью допускаются необходимая оборона причинение вреда при задержании лица совершившего преступление обоснованный риск...
27655. Понятие и виды преступлений в сфере кредитно-финансовой деятельности 36 KB
  176 УК изготовление или сбыт поддельных денег или ценных бумаг ст. № 2 О судебной практике по делам об изготовлении или сбыте поддельных денег и ценных бумаг. 186 Изготовление или сбыт поддельных денег или ценных бумаг Непосредственный объект общественные отношения обеспечивающие: право на эмиссию денег и ценных бумаг уполномоченным кругом субъектов экономической деятельности в том числе исключительное право РФ на эмиссию национальной валюты; интересы негосударственного финансового объекта а также право собственности потенциальных...
27656. Понятие и виды преступлений против службы в коммерческих и иных организациях. Злоупотребление полномочиями (ст.201 УК РФ). Коммерческий подкуп (ст. 204 УК РФ). Особенности субъекта данных преступлений 38.5 KB
  Коммерческие организации это организации преследующие извлечение прибыли в качестве основной цели своей деятельности в частности хозяйственные товарищества; хозяйственные общества; производственные кооперативы; государственные унитарные предприятия. Действие главы 23 УК РФ распространяется на все коммерческие организации независимо от формы их собственности. Некоммерческие организации это организации не имеющие в качестве основной цели своей деятельности извлечение прибыли и поэтому они могут заниматься предпринимательской...