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


 

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

20471. Безпека програмного забезпечення 16.55 KB
  Проблеми хто потенційно може здійснити практичне впровадження програмних дефектів деструктивного впливу в програмний код які можливі мотиви дій суб'єкта що здійснює розробку таких дефектів як можна ідентифікувати наявність програмного дефекту як можна відрізнити навмисний програмний дефект від програмної помилки які найбільш імовірні наслідки активізації деструктивних програмних засобів при експлуатації комп'ютерних систем Меоди та концепції захисту Для захисту програм від дослідження необхідно застосовувати методи захисту від...
20472. Методологiя структурного програмування 17.08 KB
  Метою структурного програмування є створення ієрархічно впорядкованих модульних програм в яких застосовуються стандартні керуючі конструкції. Одним із шляхів вдосконалення структурного програмування є введення стандартів що регламентують процес програмування. Необхідність стандартизації програмування обумовлена: необхідністю підвищення експлуатаційних характеристик програм що створюються; прагненням зробити систему достатньо простою доступною для сприйняття програмістом який знайомий з відповідними стандартами; вимогою зробити систему...
20473. Клієнт-сервер (англ. Client-server) 16.26 KB
  Clientserver обчислювальна або мережева архітектура в якій завдання або мережева навантаження розподілені між постачальниками послуг сервісів званими серверами і замовниками послуг званими клієнтами. Нерідко клієнти і сервери взаємодіють через комп'ютерну мережу і можуть бути як різними фізичними пристроями так і програмним забезпеченням.Багаторівнева архітектура клієнтсерверБагаторівнева архітектура клієнтсервер різновид архітектури клієнтсервер в якій функція обробки даних винесена на один або декілька окремих серверів. Це...
20474. Ефективність програмного забезпечення та її оцінка 36 KB
  Оптимізація це покращення характеристик програмної системи або просто програми. Отже перший етап програмування створення правильної програми і лише другий її оптимізація. Але перед тим як починати покращувати ефективність програми слід перевірити наскільки це покращення буде корисним і точно визначити місце яке слід переробити. Справа у тому що існує правило 20 80: 20 обєктного коду тексту програми виконується 80 часу роботи всієї програми.
20475. Абсолютна величина і норма матриці 139 KB
  За абсолютну величину модуль матриці будемо вважати матрицю де модулі елементів матриці . Якщо і матриці для яких операції і мають сенс то: а б в число. За норму матриці вважаємо дійсне число що задовольняє умови: а причому тоді і тільки тоді коли =0; б число і зокрема ; в ; г і матриці для яких відповідні операції мають сенс.
20476. Біном Ньютона 31 KB
  Запишемо його у вигляді добутку пронумерувавши дужки: Кожний доданок містить n множників: k множників a і nk множників b тобто має вигляд akbnk де k≤n k≥0.
20477. Візуальні мови проектування специфікацій 36 KB
  Складність сучасних обчислювальних систем а також висока вартість створення якісного та надійного програмного забезпечення ЕОМ стимулюють розвиток теоретично обгрунтованих методів та засобів розробки програмних систем. Особливо актуальним є застосування таких методів та засобів при об'єктноорієнтованому підході до створення програмних систем. Формалізовані візуальні мови набули широкого використання при проектуванні та розробці складних програмних систем. Об'єктноорієнтовані методи розробки програмного забезпечення широко застосовують...
20478. Властивості сполучень (Трикутник Паскаля) 25.5 KB
  Ряди трикутника Паскаля умовно пронумеровані згори починаючи з нульового й числа в нижньому ряді відносно чисел у попередньому ряді завжди розміщені ступінчасто й навскіс. Кожне число в кожному ряді одержуємо додавши два числа розміщені вгорі зліва і справа. Наприклад перше число в першому ряді 0 1 = 1 тоді як числа 1 і 3 в третьому ряді утворюють число 4 в четвертому ряді: 1 3 = 4. Правило Паскаля стверджує: якщо kй біноміальний коефіцієнт в біноміальному ряді для x yn тоді для будьякого додатного цілого n і будьякого...
20479. Графічний метод відокремлення коренів 39.5 KB
  Найчастіше в додатках використовуються трансцендентні рівняння. Для відокремлення коренів можна ефективно використати ЕОМ. Проте слід памятати що дане твердження справедливе лише за умов монотонності на заданому відрізку і виборі достатньо малого кроку приросту аргументу з врахуванням характеристик. Слід аналізувати три можливості що можуть виникнути а саме: Якщо рис.