• Advertisement
Sign in to follow this  

Flight Scheduling

This topic is 4414 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

For a school project, my team is creating a web application which will automate the process of scheduling when aeronautical flight students will fly throughout the semester. Right now, the flight department does this all with pencil and paper. In the scheduling process, there are 3 variables - student class schedules, plane availability, and instructor schedules. The students have to fly about 3 hours/week, and certain groups of students have higher priority than others. It does not really matter which instructor they fly with, but it does matter which type (not specifically which plane though) they fly in. We are trying to come up with an algorithm for handling this. Do you think a neural network could do this, maybe a self-organizing Kohonen neural net?

Share this post


Link to post
Share on other sites
Advertisement
I've always thought of scheduling problems as Constraint Satisfaction Problems (CSP). I'm not sure if you've had experience with them, but they're apparently quite good for applying to scheduling problems. Here's a good link:

http://aima.cs.berkeley.edu/

not to mention the pdf which explains the algorithms:

http://aima.cs.berkeley.edu/newchap05.pdf

So, you've got your variables, student class schedules, plane availability, instructor schedules. You'll probably have to break down the schedules into days, hours, minutes, depending on the sort of granularity you want. The CSP attacks the problem in a "brute force" sort of way, by applying values to variables and seeing whether or not this breaks the constraints which you impose on the problem. Since all you want is a schedule, and which students fly on which days with which instructor, you should have no trouble creating the constraints.

Now, be warned: this can get pretty hairy. I had a project a long time back scheduling round robin basketball tournaments for class, and the program took a long time to come back with an acceptable schedule.

And even if you do find an acceptable schedule, you might want to try applying Simulated Annealing to it. I don't have a good link for that, but you should be able to Google it anyway.

Hope that was helpful.

Share this post


Link to post
Share on other sites
There are plenty of online resources for solving constraint satisfaction problems. Try looking at Mixed Integer Linear Programming. You should be able to find free software for it.

Having said that, this sort of schedulin problem is the bread and butter of Operations Research, from which inumerable scheduling algorithms and implementations have been produced. You should have no problem finding a tonne of literature through Google that should enable you to solve your problem.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
I had very similar problems to solve in a class and variations of the network flow algorithm were good for finding optimal solutions. Just google "network flow" and you'll find tons of references.

Share this post


Link to post
Share on other sites
I agree with what Timkin said, and I'ld like to add, please see Neural Networks as your last resort, not your first option. People in Numerical Methods and Operations Research are bleeding to provide you with optimal solutions!

Share this post


Link to post
Share on other sites
For a typical size flight school, a greedy allocator with some degree of backtracking might brute-force the problem in reasonable time.

What you'll end up finding, on the requirements part, is that some people can't do certain hours (i e, students, planes, instructors are not interchangeable for all time slots), and certain preferences/dislikes may come into play as well. Scheduling people is never as easy as scheduling packets.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement