3

So.. someone recently asked me to make a timetable for them and I agreed. When I sat down to do it I realized it was harder than I thought. It's just a timetable to give shifts to 4 people for either day or night.

I thought of something like this:

for Monday to Saturday {
  for(i=0;i<people.length;i++){
    if (person[i].available()){
      person.worksDay()
      person is now not available.
    }
  }

  for(i=0;i<people.length;i++){
    if (person[i].available()){
      person[i].worksNight()
      person[i] is now not available.
    }
  }
}

So the idea behind this algorithm is that for each day, a person is assigned to a day or night shift. A person is available if they haven't JUST worked a shift and they aren't on holidays. It's for Monday to Saturday. As you can probably tell, given persons A,B,C,D the assignment would look like this (if no one is on holidays):

Mon A B
Tue C D
Wed A B
Th  C D
Fri A B
Sat C D

This works I guess but it's a bit obvious. The person who asked me wanted to see different options. Is there a better way about doing this to see more than just this option? Or is there even a program that does this for you?

ABCDpeople
  • 31
  • 1
  • 2
  • You're right; it's a much harder problem than it looks. I would start with assigning a priority to some of the combinations. This will shuffle the combinations around. – Robert Harvey Oct 18 '10 at 15:23
  • Hmm.. do you mean assigning a priority to all possible combinations AB, AC .. DB, DC? What could the priority be? random number? – ABCDpeople Oct 18 '10 at 15:39
  • Perhaps you could use graph coloring approach for your scheduling. – thomas1234 Oct 18 '10 at 16:45

3 Answers3

2

I think you should use genetic algorithm because:

  • It is best suited for large problem instances.
  • It yields reduced time complexity on the price of inaccurate answer(Not the ultimate best)
  • You can specify constraints & preferences easily by adjusting fitness punishments for not met ones.
  • You can specify time limit for program execution.

  • The quality of solution depends on how much time you intend to spend solving the program..

    Genetic Algorithms Definition

    Genetic Algorithms Tutorial

    Class scheduling project with GA

Also take a look at :a similar question and another one

Community
  • 1
  • 1
Betamoo
  • 14,964
  • 25
  • 75
  • 109
1

Brute force is pointless.

Use a framework such as Drools Planner, Choco, JGap, cpsolver, ... to solve it for you. Some of those frameworks (including Drools Planner) allow you to easily switch optimization algorithms and include tools to determine the best one to use for your problem.

Geoffrey De Smet
  • 26,223
  • 11
  • 73
  • 120
0

Constraint programming problems are complex and difficult to program in general. Even though your problem is fairly simple you may want to download a tool to do it. The Gnu Linear Programming Kit is probably the best option, it has a solver and a modeling language you can use. I wrote a really long post about scheduling one time.

Community
  • 1
  • 1
fairidox
  • 3,358
  • 2
  • 28
  • 29