Scheduling

My schedule for this semester was out. Differ from the time table I usually got in my old college, this schedule was arranged by the subject instead of by the day. I needed some adjustments in how to read the schedule but so far, I’m doing fine. The only things that not going well was about the schedule itself.

It is a fact that the schedule at the first week might dissatisfied some people involved. The chance of clash on schedule is pretty high. There were a lot of people involved though. So the first week is usually a mediation term. In the next coming week, the schedule will be re-arranged to meet everyone’s need.

DNA_double_helix_horizontal This scheduling things made me remember about one of my friends thesis. He used genetic algorithm to determine the best schedule possibilities. Given some constraints, the algorithm aimed to find the schedule with lowest violation to the constraints. I’m not the expert about this technique, but I’m trying to explain it to you. You can correct me if I’m wrong.

genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a particular class of evolutionary algorithms (EA) that use techniques inspired by evolutionary biology such as inheritancemutationselection, and crossover. (Wikipedia)

The technique started with creating genetic representations of the problem and the fitness function to determine the optimized solution. Then, a population is generated to cover the entire solutions available. This population the being selected by fitness function to find the best solution. The selected invidual then crossed over to find the next generation. This steps repeated some times until the termination conditions are met.

The common termination conditions are:

  • A solution is found that satisfies minimum criteria
  • Fixed number of generations reached
  • Allocated budget (computation time/money) reached
  • The highest ranking solution’s fitness is reaching or has reached a plateau such that successive iterations no longer produce better results
  • Manual inspection
  • Combinations of the above

(Wikipedia)

Back into the scheduling case. Some of the constraints defined here are the class capacity, the lecturer availability, and the lessons itself. The class must not occupied more than one lesson at a time and must have the right capacity for the students. The lecturer must not teach at more than one place at a time. And the last but not least, the students must not attend more than one classes at a time.

Genetic Algorithm (xkcd.com)
Genetic Algorithm (xkcd.com)

The constraints themselves were very complicated if the schedule used for one campus. Imagine how many places, students, lecturers, and lessons. Because of this massive quantity, this friend of mine take a narrower sample. He used just one major in one year. The results were pretty good, although it couldn’t achieve zero constraint violation.

Now with the experiment is done, is it possible to bring it to the real world? That’s definitely a different case. Right after he started the experiment, the institution already used different system on their education programme. Instead of one single major, now students can choose another minor on the other department. So typically, one student can take one major in one department and take another minor on another department. The combinations of this major-minor programme was gigantic.

The major-minor wasn’t only the problem. There are also some bureaucracy (did I spell it right?) things in the higher tops that hard to deal with. Another problems maybe, the genetic algorithm itself didn’t good enough. Maybe it also can be combined with another technique to have a better optimized solutions.

Anyway, just take the traditional approach. Use one week of adaptation, then re-schedule it again. That always worked.

Credits : Genetic Algorithm, webcomic by Randall Munroe from xkcd.com

2 thoughts on “Scheduling

What's in your mind?