Классическое задание для планирования задач - PullRequest
Новая
       58

Классическое задание для планирования задач

8 голосов
/ 22 апреля 2011

Я работаю над приложением для планирования полетов (отказ от ответственности: это для проекта колледжа, поэтому не отвечайте на код, пожалуйста).Пожалуйста, прочитайте этот вопрос, прежде чем отвечать, так как он имеет много особенностей: (* ​​1001 *

Во-первых, некоторые терминологические проблемы:
У вас есть самолеты и полеты, и вы должны объединить их в пару.Для простоты мы будем предполагать, что самолет свободен, как только полет использует его ранее.

Полеты рассматриваются как задачи:

  • Они имеют продолжительность
  • У них есть зависимости
  • У них есть ожидаемая дата / время начала

Самолеты можно рассматривать как ресурсы, которые будут использоваться задачами (или полетами, в нашей терминологии).

Для полетов нужен определенный тип самолета, например, для полета 200 нужен самолет типа B. Самолеты, очевидно, относятся к одному и только одному конкретному типу, например, самолет Airforce One типа C.

«Проект» - это совокупность всех рейсов авиакомпании за определенный период времени.

Требуемая функциональность:

  • Нахождение кратчайшей возможной продолжительностиуказанный проект

  • Самый ранний и самый поздний возможный старт для задачи (полета)

  • Критические задачи, основанные на предоставленных данных, завершеныс идентификаторами предыдущих задач.

  • Автоматически объединяет полеты и самолеты, чтобы все рейсы были в паре с самолетом.(Примечание: продолжительность полетов фиксирована)

  • Получите диаграмму Ганта с расписанием проектов, в которой все полеты начинаются как можно раньше, с графическим отображением всех ранее упомянутых данных (зависимости,информация о времени и т. д.)

Итак, возникает вопрос: как в мире я могу достичь этого?В частности:

  • Мы обязаны использовать график.
    • Что соответственно обозначают ребра и узлы графа?
  • Требуется ли нам отбрасывать задачи для выполнения поставленных критических задач?

Если бы вы могли также порекомендовать нам некоторые алгоритмы, это было бы здорово.

Ответы [ 2 ]

5 голосов
/ 22 апреля 2011

Вот несколько предложений.

В принципе, у вас может быть график, где каждый узел является полетом, и есть перелет от рейса A к рейсу B, если B зависит от A, то есть B не может взлететь до приземления A. Вы можете использовать этот график зависимостей для вычисления кратчайшей возможной продолжительности проекта - найти путь через график, который имеет максимальную продолжительность, когда вы добавляете длительности всех полетов на пути вместе. Это «критический путь» вашего проекта.

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

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

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

Вот несколько ссылок:

1 голос
/ 22 апреля 2011

Начните с рисования модели предметной области (диаграммы классов) и проведите четкое разделение в уме:

  • планирование-неизменное факты : PlaneType, Plane, Flight, FlightBeforeFlightConstraint, ...
  • планирование переменные : PlaneToFlightAssignment

Оберните все эти экземпляры в этот класс Project (= Решение). Затем определите функцию оценки (функция пригодности АКА) для такого решения. Например, если есть 2 PlaneToFlightAssignments, которые не подходят для FlightBeforeFlightConstraint (= зависимость от полета), то уменьшите оценку.

Тогда нужно просто найти решение с лучшим счетом, изменив PlaneToFlightAssignment экземпляров. Есть несколько алгоритмов , которые вы можете использовать, чтобы найти это лучшее решение. Если ваш набор данных действительно очень мал (например, 10 плоскостей), вы можете использовать грубая сила .

...