Программирование на языке Пролог для искусственного интеллекта




Применение поиска с предпочтением к планированию выполнения задач - часть 2


Coffman/ Denning, Operating Systems Theory, © 1973, p.86. Приведено с разрешения Prentice-Hall, Englewood Cliffs, New Jersey.

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

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

    Теперь нам необходимо принять решение относительно представления проблемных ситуаций, т.е. частичных планов. Нам понадобится следующая информация:

    (1)        список ждущих задач вместе с их временами выполнения;

    (2)        текущая загрузка процессоров задачами.




    Содержание  Назад  Вперед