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

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

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

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

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

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

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

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

The functionality required is:

  • Поиск минимально возможной продолжительности указанного проекта

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

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

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

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

Итак, вопрос: как мне этого добиться? Особенно:

  • We are required to use a graph.
    • What do the graph's edges and nodes respectively symbolise?
  • Обязаны ли мы отказываться от задач для достижения поставленных критических задач?

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


graph scheduling algorithm gantt-chart
person Bruno    schedule 21.04.2011    source источник
comment
@TKTS: Привет, я товарищ по команде @ Bruno. Действительно, будут, но мы, к сожалению (никогда не думал, что скажу это :)) в отпуске, и время отклика будет ... меньше звездного :(   -  person F. P.    schedule 22.04.2011
comment
Есть ли у рейсов также пункты отправления и назначения? Так что, если самолет использовался только для полета из пункта А в пункт Б, его нельзя было снова использовать для другого полета из пункта А, пока он не был доставлен обратно в пункт А?   -  person j_random_hacker    schedule 22.04.2011
comment
@j_random_hacker: Да. Если самолет летел из пункта A в пункт B, следующий рейс, который его использует, должен вылететь из пункта B.   -  person F. P.    schedule 22.04.2011

Ответы (2)


arrow_upward
5
arrow_downward

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

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

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

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

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

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

person Antti Huima    schedule 21.04.2011
comment
Ой, извините, я забыл упомянуть, что для каждого рейса нужен определенный тип самолета. Одну секунду. - person F. P.; 22.04.2011
comment
Но вам может потребоваться разрешить либо (1) полеты без пассажиров (2) лишние самолеты, либо (3) что проблема не всегда имеет решение. - person Antti Huima; 22.04.2011
comment
Пассажиров можно не принимать во внимание. У нас 58 самолетов и еще немало рейсов. - person F. P.; 22.04.2011
comment
Забудь об этом. Да, самолет должен взлетать с того места, где он приземлился последним. Если это не слишком сложно. Тогда мы проигнорируем это требование - person F. P.; 22.04.2011

arrow_upward
1
arrow_downward

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

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

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

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

person Geoffrey De Smet    schedule 22.04.2011