2

I was wondering if anyone could please point me the right direction on how to approach the scheduling problem.

I have a teacher/student timetable problem, where I have teachers that teach certain subject at certain times and students that have preferences as of which class they want to take an when. The goal is to create a timetable not necessarily optimal solution.

I looked around here and there is a great number of discussions here on this website on this topic and the ones that I found go from super general to excessively difficult and I am currently unable to understand which programming/logic concepts to use to at least conceptualize the program work-flow.

Could anyone that dealt with similar problems explain how these types of problems are dealt with. I do not need the code (although pseudo-code would be awesome), but some guidelines ie step#1 - do this, step#2 - do that, step#3 - do etc....

Also, are there any libraries that are available that can do scheduling with preferences effectively and that have fairly straightforward inputs?

Many thanks!!

here is the outline of a problem that I have.

Let's say I have a group of salespeople:

enter image description here

The goal is to create a schedule that pairs buyer and seller subject to time availability and preferences.

This is a course time-tabling problem, right?

Can I accomplish with Drool Planner?

mostar
  • 4,723
  • 2
  • 28
  • 45
JavaFan
  • 1,295
  • 3
  • 19
  • 28
  • Can you describe the problem a bit more? "Teachers teach certain subject at certain times" so you have to create a timetable based only on this? – Rafi Kamal Aug 31 '12 at 05:27
  • Maybe you can find it useful: http://stackoverflow.com/questions/7705782/class-scheduling-algorithm-to-show-best-match-with-criteria?rq=1 – Rafi Kamal Aug 31 '12 at 05:35
  • hi, I updated my problem in the original description. Looking forward to hearing from you! – JavaFan Aug 31 '12 at 21:32

3 Answers3

1

Take a look at the curriculum course scheduling problem which schedules lectures of teacher and students into timeslots and rooms. Take a look at my open source implementation in Java or just download and run the example.

I 've configured the construction heuristic First Fit Decreasing with the metaheuristic Tabu Search. I tried other configurations too, see my benchmarker config.

Geoffrey De Smet
  • 26,223
  • 11
  • 73
  • 120
  • Geoffrey, thanks a lot!! How do I learn how to use Drools? Your examples are awesome. Is there any way to give me some pointers how to create a basic optimization problem in Drools Planner? I understand what it does and the logic, but where do I start writing the code and how do i know what classes to use and what to write? Thanks, – JavaFan Sep 04 '12 at 01:34
  • See question [how do I use planner](http://stackoverflow.com/questions/12254350/how-do-i-use-drools-planner) – Geoffrey De Smet Sep 05 '12 at 06:21
  • 1
    The "my open source implementation..." link is broken. – Ricidleiv Tondatto Oct 02 '15 at 21:38
  • fixed that broken link – Geoffrey De Smet Oct 04 '15 at 08:30
0

First you should make a list of resources for your problem. Then you should write down the constraints and set up a mathematical model. Finally you can use some optimization tool to generate solutions.

Of course this is not as easy as it seems to be. This page may give you some insight about possible solutions.

mostar
  • 4,723
  • 2
  • 28
  • 45
0

Matlab has a Global Optimization toolbox which lets you do genetic algorithm optimization with a very simple, point-and-click GUI that has helpful documentation. From what wikipedia says, your problem is just the kind to solve with a GA.

If you don't have access to the toolbox, you should be able to find genetic algorithm libraries for java, or worst comes to worst you can write your own. It won't be as extensive and it will take some work, but it shouldn't be terribly hard to make a simple one.

Superbest
  • 25,318
  • 14
  • 62
  • 134