Составление расписания

Question

Итак ... кто-то недавно попросил меня составить расписание для них, и я согласился.Когда я сел, чтобы сделать это, я понял, что это сложнее, чем я думал.Это просто расписание для смены 4 человек на день или ночь.

Я думал о чем-то вроде этого:

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.
    }
  }
}

Так что идея этого алгоритма заключается в том, что для каждого дня,человек назначен на дневную или ночную смену.Человек доступен, если он просто не работал в смену и не в отпуске.Это с понедельника по субботу.Как вы, вероятно, можете сказать, для заданных лиц A, B, C, D задание будет выглядеть так (если никто не будет в выходных):

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

Это работает, я думаю, но это немного очевидно.Человек, который спросил меня, хотел увидеть разные варианты.Есть ли лучший способ сделать это, чтобы увидеть больше, чем просто этот вариант?Или есть даже программа, которая делает это для вас?

Answer 1

Я думаю, вам следует использовать генетический алгоритм, потому что:

• Лучше всего подходит для больших проблемных случаев.
• Это снижает сложность времени по цене неточного ответа (неНаилучшее)
• Вы можете легко указать ограничения и предпочтения, отрегулировав физические наказания за невыполнение.
• Вы можете указать ограничение по времени для выполнения программы.

• Качество решения зависит от того, сколько времени вы собираетесь потратить на решение программы.

  Определение генетических алгоритмов

  Учебное пособие по генетическим алгоритмам

  Проект планирования классов с GA

Также взгляните на: аналогичный вопрос и еще один

Answer 2

Грубая сила равна бессмысленно .

Используйте рамки, такие как Drools Planner , Choco, JGap, cpsolver, ..., чтобы решить это за вас.Некоторые из этих сред (в том числе Drools Planner) позволяют легко переключать алгоритмы оптимизации и включают инструменты для определения наиболее подходящего для вашей задачи решения.

Answer 3

Проблемы программирования с ограничениями сложны и трудны для программирования в целом.Даже если ваша проблема довольно проста, вы можете скачать инструмент для этого.Gnu Linear Programming Kit, вероятно, лучший вариант, он имеет решатель и язык моделирования, который вы можете использовать.Я написал очень длинный пост о планировании один раз .