Classical task-scheduling assignment
- by Bruno
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.
