Classical task-scheduling assignment

Question

I am working on a flight scheduling app (disclaimer: it's for a college project, so no code answers, please). Please read this question w/ a quantum of attention before answering as it has a lot of peculiarities :(

First, some terminology issues:
You have planes and flights, and you have to pair them up. For simplicity's sake, we'll assume that a plane is free as soon as the flight using it prior lands.

Flights are seen as tasks:

• They have a duration
• They have dependencies
• They have an expected date/time for beginning

Planes can be seen as resources to be used by tasks (or flights, in our terminology).

Flights have a specific type of plane needed. e.g. flight 200 needs a plane of type B. Planes obviously are of one and only one specific type, e.g., Plane Airforce One is of type C.

A "project" is the set of all the flights by an airline in a given time period.

The functionality required is:

• Finding the shortest possible duration for a said project

• The earliest and latest possible start for a task (flight)

• The critical tasks, with basis on provided data, complete with identifiers of preceding tasks.

• Automatically pair up flights and planes, so as to get all flights paired up with a plane. (Note: the duration of flights is fixed)

• Get a Gantt diagram with the projects scheduling, in which all flights begin as early as possible, showing all previously referred data graphically (dependencies, time info, etc.)

So the questions is: How in the world do I achieve this? Particularly:

• We are required to use a graph.
  • What do the graph's edges and nodes respectively symbolise?
• Are we required to discard tasks to achieve the critical tasks set?

If you could also recommend some algorithms for us to look up, that'd be great.

Answer 1

Here some suggestions.

In principle you can have a graph where every node is a flight and there is an edge from flight A to flight B if B depends on A, i.e. B can't take off before A has landed. You can use this dependency graph to calculate the shortest possible duration for the project --- find the path through the graph that has maximum duration when you add the durations of all the flights on the path together. This is the "critical path" of your project.

However, the fact that you need to pair with planes makes it more difficult, esp. as I guess it is assumed that the planes are not allowed to fly without passengers, i.e. a plane must take off from the same city where it landed last.

If you have an excessive number of planes, allocating them to the flights can be most likely easily with a combinatorial optimization algorithm like simulated annealing. If the plan is very tight, i.e. you don't have excess planes, it could be a hard problem.

To set the actual take-off times for your flights, you can for example formulate the allowed schedules as a linear programming problem, or as a semi-definite / quadratic programming problem.

Here some references:

• http://en.wikipedia.org/wiki/Simulated_annealing
• http://en.wikipedia.org/wiki/Linear_programming
• http://en.wikipedia.org/wiki/Quadratic_programming
• http://en.wikipedia.org/wiki/Gradient_descent
• http://en.wikipedia.org/wiki/Critical_path_method

Answer 2

Start with drawing out a domain model (class diagram) and make a clear separation in your mind between:

• planning-immutable facts: PlaneType, Plane, Flight, FlightBeforeFlightConstraint, ...
• planning variables: PlaneToFlightAssignment

Wrap all those instances in that Project class (= a Solution). Then define a score function (AKA fitness function) on such a Solution. For example, if there are 2 PlaneToFlightAssignments which are not ok with a FlightBeforeFlightConstraint (= flight dependency), then lower the score.

Then it's just a matter for finding the Solution with the best score, by changing the PlaneToFlightAssignment instances. There are several algorithms you can use to find that best solution. If your data set is really really small (say 10 planes), you might be able to use brute force.