Flight scheduling algorithm?

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. What do you think the best approach would be? Do you think this could be in the realm of A.I. (e.g., a Kohonen self-organizing neural net perhaps?), or does it seem more like a normal algorithm (complex, of course)? And do you think this should incorporate the use of graphs?

Without regard to the language - let's suppose this was in C++ or Java - how would you do this?

Doesn't sound like anything more than a matrix of the 3 variables you brought up. A set of interlinked LinkedLists could handle this problem with ease.

If it's a web application then I'd do it with PHP/MySQL or ASP.NET/(MySQL/MS SQL).

The variables are not sufficiently described, so the following table schema is just a main idea.

Instructor table: instructor, schedule
Student table: student, priority, schedule
Plane table: plane type, availability
Plane_Student table: plane type, student

Then you'll just have queries (e.g. For certain time, get available instructor, plane type, student...bla...bla)

Quote:

---

Originally Posted by CompiledMonkey

Doesn't sound like anything more than a matrix of the 3 variables you brought up. A set of interlinked LinkedLists could handle this problem with ease.

---

Could you expand on this?

Since its for a web application I'd go with the solution alphaoide suggested php/mySql would do the trick...

Especially since you can work with concurrent operations in mysql which you will need probably.

Quote:

---

Originally Posted by ChadJohnson

Could you expand on this?

---

If we're talking about 3 variables or sets of objects to keep track of, you have 3 Linked Lists. Each of which has an object of a specific type that has it's own properties, etc. You can keep them sorted to the priority like you mentioned.

Now, you want to link a student to a flight and a flight to an instructor, so find that student node in your student linked list and point him to a node in your flight linked list. Do the same for the flight and instructor. This way you basically have a ton of nodes out there linked to each other via pointers and related to each other based on students, flights, and instructors. Think of how easy it would be to print the data (student, flight, and instructor) for a student by just following the pointers until the next is null.

Sounds like a great idea, CompiledMonkey.

Do you think it's still possible if, for instance, a student needs to fly in a specific type of airplane with a specific instructor on Monday, Wednesday, and Friday at 2:30 - 4:00?

Also, what are concurrent operations with MySQL?

Quote:

---

Originally Posted by ChadJohnson

Also, what are concurrent operations with MySQL?

---

I dont know how you are going to implement this whole thing but basically what I mean is:

example just to show what im talking about:

suppose i have a web application to book a flight on a commercial plane.

Theres only one seat left , keeping in mind that its a web application so more then one person can book seats at the same time. Now personA and personB do a query on the database at the same time to check how many seats are left. Both see that one seat is left, so both proceed to book the seat ...

Bam , personA or personB just got himself a virtual seat.

For this kind of situation mysql has some built in functionality -> concurrent transaction.

Basically you use BEGIN WORK or START TRANSACTION, to flag the end of a transaction you can then use COMMIT , to undo the changes from where you stated BEGIN WORK theres the command ROLLBACK.

Using these things ( + setting transaction isolation levels etc ) a situation like i described above will no longer be possible.

More info about concurrent transaction using Mysql can be found at http://dev.mysql.com/doc/refman/5.0/...nsactions.html

ps: i meant concurrent transactions ( instead of operations )

Very good point, GanglyLamb. I had have forgotten entirely about transactions. This will make it so that if two users try to schedule themselves for a plane at the same time only one will get it.

After talking to some professors and staff members, my team has decided to first focus on making the system an electronic scheduler so that they no longer have to rely on paper schedules. After this is taken care of we will then focus on the automatic scheduling.

Thanks for the input everyone. I'm still curious as to how, using CompiledMonkey's idea of the linked lists to, for instance, do the auto scheduling if a student needs to fly in a specific type of airplane with a specific instructor on Monday, Wednesday, and Friday at 2:30 - 4:00.

If anyone else has any other suggestions, feel free to post.

I appreciate this!

Quote:

---

Originally Posted by ChadJohnson

Do you think it's still possible if, for instance, a student needs to fly in a specific type of airplane with a specific instructor on Monday, Wednesday, and Friday at 2:30 - 4:00?

---

Sure. The type element can be the criteria you search for as you decide which flight to put a student on. The date/time can be random as well. If you need to see whether a flight is already scheduled for a date/time for an instructor, just travel the instructor or flight list and check for it. It's a lot quicker to travel through considering they're linked lists compared with arrays.

I doubt if the idea of "booking" seats is appropriate. It's not like they're flying United or something. Probably an administrator is going to build a flight chart for the week. Each instructor gives his schedule in advance. Each student gives available hours in advance. Maybe the students give preferred hours. You get your preferred hours if you are the highest priority student that requested those hours. Or, you might not get flight time at all, if you are low priority and you don't provide enough available hours on your schedule.

There are problems that may come up. Consider the situation where there are enough instructors at a given time, but not enough planes to go around. You would have to choose based on priority there.

Also, can a student give a constraint such as, "I'm available 8-12AM MWF, but I can only fly for one hour on each of those days." That would complicate things a bit.

Also, there are weird sort of ordering issues. Consider the case where you start with the student with the highest priority, and he needs something like M2-5pm or something. So there are 2 instructors available at that time: A has M2-7pm available, and B has 2-5pm available. Since it doesn't matter which, you choose the first one that you come across in your list, which is A. Later, a lower priority student needs lets say M4-7pm. Now there are no instructors available from those times, but there would have been if you would have chosen B instead of A earlier for your higher priority student.

I don't know exactly what the solution is, but I don't think it's as easy as some here are leading us to believe.

Quote:

---

Originally Posted by IfYouSaySo

I don't know exactly what the solution is, but I don't think it's as easy as some here are leading us to believe.

---

Or, you're thinking about it too much. We don't know whether this is a class assignment or a prototype for American Airlines. My experience has taught me to break a problem down and begin to solve pieces of it. As you do, and design an algorithm, you'll discover more problems that will shape your overall design. Hopefully my suggestions can act as the platform to solve the problem.

Actually, we do know that it's for a school project (first thing he told us). And it's flight scheduling for flight school, not for passengers making reservations on a commercial jetliner--he told us that also.

Quote:

---

Originally Posted by IfYouSaySo

Actually, we do know that it's for a school project (first thing he told us). And it's flight scheduling for flight school, not for passengers making reservations on a commercial jetliner--he told us that also.

---

Ok, good. Doesn't change my approach.

AI might be interesting as an exercise but seems like overkill.

You've instructors, students, and aircraft.
Each has a number of hours of availability per week. Students may have a priority level and a requirement for a specific aircraft.
Aircraft may require a specific instructor (maybe not now, but keep in mind things like typeratings, dual engine and IFR instruction, which no doubt will at some point need to be pulled in).

Match up students with instructors first. That way all students always get the same instructor.
Then match up those pairs with specific aircraft based on availability (keep in mind that aircraft may have downtime, so each aircraft would need to have a table maintaining their availability as well), starting with the highest priority students and moving down the line from there.

Essentially you're building a small expert system here. If it grows more complex a full AI might become a good idea.
Do keep in mind that students, pilots, and aircraft can become non-available at any time. What are you going to do for rescheduling flights? Likely you're going to want some spare aircraft and instructors but that's a business decision and not yours to make, but you should keep such capabilities in mind when designing your system.

Servlet/JSP based solution would work fine. No need for messy php based stuff.
Database is largely immaterial, employ something like Hibernate to separate the database from the application itself and it becomes a matter of changing some config files if you design your database structure with portability in mind.
My personal preference in the free market is Firebird. Higher performance, easier to set up and maintain, and smaller footprint than mySQL while offering more functionality too.
But likely the school already has a database engine in use which you're going to be expected to ride with, so find out what that is and use it.