В настоящее время я работаю над проблемой планирования медсестры, которая звучит очень похоже на вашу.Цель состоит в том, чтобы запланировать смену (или выходной день) для каждой медсестры на каждый день, чтобы они оба работали с правильными сменами чисел (40 часов рабочей недели) и соответствовали требованиям базовой смены в день (3 медсестры в понедельник, 2 вторника и т. Д.).).Это хорошо известная проблема, и, как и любые другие проблемы с расписанием, это NP-Hard.
Я согласен с вашим комментарием, что генетические алгоритмы не очень подходят для этой задачи (или для любой задачи imo).Существуют гораздо лучшие подходы к решению этой проблемы, и они были изучены и хорошо документированы в областях программирования ограничений и исследования операций.
Мой совет - взять математический язык программирования для моделирования вашей проблемы и кодировать его как задачу программирования с ограничениями или смешанную целочисленную линейную программу (MILP).Существует ряд языков, позволяющих кодировать эти проблемы на высоком уровне, наиболее известным из которых, вероятно, будет AMPL.Вы можете найти пример расписания медсестры для этого языка, который, вероятно, очень поможет.Язык AMPL может легко компилироваться в MILP, который затем может быть передан в решатель, такой как GLPK или CPLEX.Кроме того, если вы работаете в академической среде или у вас достаточно приличный бюджет для решения этой проблемы, вам следует рассмотреть возможность приобретения пакета IBM ILOG CPLEX и кодирования вашей проблемы на их поддерживаемом языке программирования оптимизации (OPL).Это язык / решатель, который я использую, и я очень доволен им.
Имейте в виду, что это и чрезвычайно трудная проблема с вычислительной точки зрения, и я хотел бы убедиться, что вы знакомы с этой трудностью, прежде чем выдавать какие-либо сметы расходов на проект.
Редактировать: Поскольку вы обновили свой вопрос, позвольте мне обновить мой ответ, здесь работает код OPL для решения вашей проблемы.Я буду использовать OPL, потому что я не знаю AMPL, но два языка очень похожи, вы можете легко перевести.
using CPLEX;
int nbShifts = ...;
int nbDays = ...;
int nbEmpl = ...;
range sRng = 1..nbShifts; // for indexing
range dRng = 1..nbDays;
range eRng = 1..nbEmpl;
int shiftsWorked[eRng] = ...; // number of shifts each employee works
int shiftsRequired[dRng][sRng] = ...; // number of shift s required on day d
dvar int Assignments[eRng][dRng][sRng] in 0..1; // boolean matrix, 1=working 0=not working
subject to {
// work at most 1 shift per day
forall(e in eRng, d in dRng)
(sum(s in sRng) Assignments[e][d][s]) <= 1;
// "vertical" constraint
forall(d in dRng, s in sRng)
shiftsRequired[d][s] == (sum(e in eRng) Assignments[e][d][s]);
// "horizontal" constraint
forall(e in eRng)
(sum(d in dRng, s in sRng) Assignments[e][d][s]) == shiftsWorked[e];
}
// to print out A, in nicer format
execute {
write("\n");
var flag;
for (var e=1; e <= nbEmpl; e++) {
for (var d=1; d <= nbDays; d++) {
flag=0;
for (var s=1; s <= nbShifts; s++) {
if (Assignments[e][d][s] == 1) {
flag=1;
write(" S",s);
}
if (s == nbShifts && flag==0) write(" __");
}
}
write("\n");
}
}
Вы можете запустить этот код с файлом .dat, например так:
nbShifts = 4;
nbDays = 7;
nbEmpl = 4;
shiftsWorked = [ 5 5 5 5 ];
shiftsRequired = [[3 0 0 1] [1 1 0 0] [0 0 1 1] [1 1 1 1] [0 0 0 0] [1 0 0 3] [0 2 2 0]];
И получите следующий вывод менее чем за секунду:
S1 __ S3 S4 __ S4 S3
S1 __ S4 S3 __ S4 S3
S1 S2 __ S2 __ S4 S2
S4 S1 __ S1 __ S1 S2
Хотелось бы, чтобы кто-нибудь сказал мне это, когда я начал свою проблему;)