8135

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

Лекция

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

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

Русский

2015-02-01

45.5 KB

4 чел.

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

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

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

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

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


 

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

27168. DAT-кассета 167.5 KB
  Так же как у видеокассеты рабочая поверхность ленты защищена шарнирной крышкой и доступ к ней обеспечивается только при откидывании этой крышки. Эта панель к тому же застопоривает шарнирную крышку препятствуя доступу к магнитному слою ленты. Таким образом DATкассета хорошо закрыта со всех сторон и магнитный слой находящейся нее ленты надежно защищен от пыли царапин отпечатков пальцев и других внешних воздействий. В дальнейшем при опускании кассеты внутрь транспортного механизма специальный рычаг ЛПМ поднимает шарнирную крышку...
27169. Система автотрекинга 174.5 KB
  Необходимые условия для вхождения в синхронизм обеспечиваются за счет того что перед началом каждого очередного массива данных на дорожке зона ИКМданных или зона данных субкода размещаются вспомогательные последовательности содержащие большое число переходов IBG вводный и выводной сигналы. Уровни сигналов ошибки при точном а и неточном б следовании головки по дорожке IBG4 F4 F4 F3 F1 F4 F3 IBG3 IBG2 В Нечетный кадр F4 F1 IBG1 1 1 1 2 блока 1 2 2 ATF2 ATF1 Направление движения ленты Направление движения головки 2 2 1 2 1 1 1 IBG1...
27170. Цифровое копирование фонограмм с помощью магнитофона R-DAT 119 KB
  Цифровое копирование фонограмм с помощью магнитофона RDAT Непременным свойством любого магнитофона является его способность к записи. DATмагнитофон в этом смысле не исключение. Однако именно по этой причине вопрос цифрового копирования стал больным вопросом формата RDAT с момента его появления. Компаниипроизводители фонограмм посчитали что такие возможности DATмагнитофонов нарушают их права и права авторов записанного материала справедливо наверное.
27171. Формат цифровой звукозаписи «Компакт-диск» 190 KB
  Таблица 1 Технические параметры формата CD Параметры Значения Диаметр диска мм 120 Толщина диска мм 12 Диаметр центрального отверстия мм 15 Материал диска Поликарбонат Способ воспроизведения информации Постоянная линейная скорость 1214 м с Шаг дорожки записи мкм 16 Минимальная длина пита мкм 083 Длина волны лазера нм 780 Частота дискретизации кГц 441 Число разрядов и характеристика квантования 16 линейная Скорость считывания звуковой информации Мбит с 14112 Общая скорость считывания информации Мбит с 19404 Канальная скорость...
27172. Процедура записи информации с целью последующего ее воспроизведения 54 KB
  В зависимости от типа используемого носителя информации и способа формирования на нем сигналограммы различают несколько систем записи информации [1]. Системой записи принято называть совокупность технических средств обеспечивающих процесс формирования сигналограммы на определенном типе носителя и технических средств обеспечивающих воспроизведение этой информации. Можно выделить семь различных систем записи звуковой информации реально существовавших и применявшихся на практике с момента ее возникновения и до наших дней: механическая...
27173. Неолиберализм в политике правящих кругов стран Европы и Америки в 1960-2000 гг. (на примере США и Великобритании) 42 KB
  Неолибералы выступают за либерализацию экономики использование принципов свободного ценообразования ведущую роль в экономике частной собственности и негосударственных хозяйственных структур. Это обусловило и новую трактовку базовых либеральных ценностей свободы и равенства свободы для свободы которая не только дает возможность бороться за свои интересы но и обеспечивает каждому реальные возможности для этого. впервые мирное время пошла на введение косвенного контроля над ценами и заработной платой. помощи: запретил повышение цен в...
27174. Неоконсерватизм в политике правящих кругов Европы и Америки в 1980-2000 гг. (на примере США и Великобритании 43.5 KB
  На примере США и Великобритании. США. проявились и негативные тенденции в экономическом развитии США. В результате рейганомики дефицит государственного бюджета США составил.