I wonder if it is possible to use Mathematica for helping myself to create school timetable. I have a feeling that it requires quite simple optimization algorithm, but I have never been into optimization, so I don't really know where to start.

The task looks like that:

  1. I have a given free class rooms at certain time points.
  2. I have an information about how much time and places require certain lessons
  3. Also I do have some teacher preferences - some would prefer mornings, some evenings etc.

Is there any function that would help solve that matter?

  • $\begingroup$ Related question: mathematica.stackexchange.com/q/5181/5 $\endgroup$ – rm -rf Sep 30 '12 at 16:40
  • $\begingroup$ It is not related to the mentioned question. I have here some kind of optimization question, not visualizing the tabular data. $\endgroup$ – Misery Sep 30 '12 at 16:42
  • 7
    $\begingroup$ More importantly, have you tried formulating this as an optimization problem? Have you written down what the objective function should be and what the constraints are? If not, then Mathematica won't automatically divine that for you. I suggest you formulate the question mathematically first and then show us where you're getting stuck in Mathematica $\endgroup$ – rm -rf Sep 30 '12 at 16:42
  • 2
    $\begingroup$ Yes, I understand your question... my followup question was: Have you thought about where to begin and how to formulate it mathematically? If you have, share it with us and then it is easier to help you with the Mathematica aspect of it. $\endgroup$ – rm -rf Sep 30 '12 at 16:45
  • 3
    $\begingroup$ This sounds like a painful Integer Programming question. NP-Hard. en.wikipedia.org/wiki/Integer_programming $\endgroup$ – Amatya Sep 30 '12 at 19:37

I'd try this with some sort of genetic algorithm. Motivation: It suffices to find a reasonably good schedule, not THE best schedule, since the function you're maximizing is not canonical, (optimize to use the least number of rooms, best room preference or something in between?). Also, the search space is huge, and finding an exact solution is most likely NP-hard (time slots in rooms -> knapsack problem).

Thus, randomly generate a schedule, then make a bunch of random modifications, select a few that are "better" according to your fitness function, and repeat until you have a decent schedule.

  • $\begingroup$ thanks :) now I'll manage to at least properly formulate my problem. Does Mathematica have any genetic algorithms built in? $\endgroup$ – Misery Oct 1 '12 at 5:37
  • 1
    $\begingroup$ Look up "DifferentialEvolution". $\endgroup$ – J. M. will be back soon Oct 1 '12 at 8:45
  • $\begingroup$ @J.M. This seemed interesting, I didn't find any details on the algorithm being implemented for DifferentialEvolution, is there a more detailed reference I've missed ? $\endgroup$ – image_doctor Oct 1 '12 at 12:08
  • 1
    $\begingroup$ @image_doctor: OP was asking about genetic algorithms, and that's why I brought up the particular example that is built into Mathematica. In any event, see this paper, among many other papers on the use of differential evolution in task scheduling. $\endgroup$ – J. M. will be back soon Oct 1 '12 at 12:16
  • $\begingroup$ @J.M. Thanks very much for the link, but sadly I don't have access to IEEE papers. My query was more motivated out of an interest of the particulars of the algorithm in Mathematica, rather than GAs for Scheduling problems in general. $\endgroup$ – image_doctor Oct 1 '12 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.