Making a timetable schedule

问题:

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?

回答1:

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

回答2:

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.

回答3:

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.