调度算法Maintining二维约束 [英] Scheduling Algorithm for Maintining Two Dimensional Constraint
问题描述
我的职责在我公司做一个调度程序。基本上指定N员工，你应该安排他们转变为一个月。我试图通过暴力来做到这一点，并下令限制的优先级。但是，我想保持垂直和水平的限制，当有问题。
垂直约束，所有的人都应该有同等数量的每月转变。 （例如，他们应该是白班，夜班，休息日，早班的平均数量之内），但也有一日水平约束，每天轮班的数量应该是相等日。
我试着在网上搜索，我经常读答案使用遗传算法。在我的遗传算法的研究，似乎该算法是不是适合我的情况。有谁知道如何解决这个问题？
根据Enigmativity的评论附加说明： 基本上有4班，
在Y的是员工转变为总需要被均匀地分布每名雇员的一个月。 （即每个员工都应该有一个平等的（或只是差）月量偏移型的） - 垂直约束
的X的是每日总量为所有雇员，基本上每个移位也应均匀分布于weedays和周末。 - 水平constaint
另外，还有一些其他的约束像期望的移位和相邻的移位。但我试着与这甚至退出规则，简化它了。
-------------------------------------- ------------------------------------------
|员工| 1 | 2 | 3 | 4 | +++ | 28 | 29 | 30 | 31 | S1 | S2 | S3 | S4 |
-------------------------------------------------- ------------------------------
| EMPA | S3 | S4 | S1 | S2 | +++ | S3 | S4 | S1 | S2 | Y | Y | Y | Y |
-------------------------------------------------- ------------------------------
| EmpB | S1 | S3 | S4 | S1 | +++ | S2 | S3 | S4 | S1 | Y | Y | Y | Y |
-------------------------------------------------- ------------------------------
| EMPC | S2 | S1 | S3 | S4 | +++ | S1 | S2 | S3 | S4 | Y | Y | Y | Y |
-------------------------------------------------- ------------------------------
| EMPD | S2 | S2 | S2 | S3 | +++ | S4 | S1 | S2 | S3 | Y | Y | Y | Y |
-------------------------------------------------- ------------------------------
| S1 | X | X | X | X | +++ | X | X | X | X | | | | |
-------------------------------------------------- ------------------------------
| S2 | X | X | X | X | +++ | X | X | X | X | | | | |
-------------------------------------------------- -----------------------------
| S3 | X | X | X | X | +++ | X | X | X | X | | | | |
-------------------------------------------------- ------------------------------
| S4 | X | X | X | X | +++ | X | X | X | X | | | | |
-------------------------------------------------- ------------------------------
我目前工作的一个听起来非常相似，你的护士调度问题。目的是安排为每个护士移位（或休息日）上的每一天，以便它们都工作权移位数（40HR工作周），并满足每天的基线偏移的要求（3护士星期一，2星期二，等）。这是一个众所周知的问题，就像任何其他的调度问题，它是一个NP难。
我同意你的意见，遗传算法不适合这项任务（或任何任务IMO）。有解决这个问题的更好的方法和他们进行了研究，有据可查的在约束编程和操作的研究领域。
我的建议是把数学的编程语言，您的问题和连接code其建模为约束规划问题或混合整数线性规划（MILP）。有一些可以让你连接$ C C这些问题在高位$语言中，最有名的一个很可能是AMPL。您可以搜索一个护士安排的例子的那种语言的版本，将可能有很大的帮助。 AMPL的语言可以很容易地编译成，然后可以传递给求解器如 GLPK 一个MILP或CPLEX。另外，如果你是在学术界还是有一个相当不错的预算，这个问题你应该考虑让IBM的ILOG CPLEX包和编码的问题，在他们的支持优化编程语言（OPL）。这是我使用的语言/解算器，我感到非常高兴。
请记住，这是和非常很难从计算的观点来看问题，我会确保你所熟悉的困难，你把之前的任何费用概算的项目。
编辑： 既然你升级你的问题让我升级我的答案，这里正在OPL code来解决你的问题。我将使用OPL，因为我不知道AMPL但两种语言非常相似，你可以很容易地转换。
使用CPLEX;
INT nbShifts = ...;
INT nbDays = ...;
INT nbEmpl = ...;
范围sRng = 1..nbShifts; //索引
范围DRNG = 1..nbDays;
范围eRng = 1..nbEmpl;
INT shiftsWorked [eRng] = ...; //将每个雇员的作品数量
INT shiftsRequired [DRNG] [sRng] = ...; //移位数s要求在d天
DVAR INT分配在0..1 [eRng] [DRNG] [sRng] //布尔矩阵，1 =工作0 =不工作
受{
//工作至多每天轮班
FORALL（E在eRng，D在DRNG）
（SUM（S在sRng）分配[E] [D] [S]）＆LT; = 1;
//垂直约束
FORALL（D在DRNG，S中sRng）
shiftsRequired [D]。[S] ==（总和（E在eRng）分配[E] [D] [S]）;
//水平约束
FORALL（E在eRng）
（总和（D在DRNG，S在sRng）分配[E] [D] [S]）== shiftsWorked [E]
}
//打印出，以更好的格式
执行 {
写（\ N）;
VAR标志;
对于（VAR E = 1; e控制= nbEmpl，E ++）{
对于（VAR D = 1; D＆LT; = nbDays; d ++）{
标志= 0;
对于（VAR S = 1; S＆LT; = nbShifts; S ++）{
如果（分配[E] [D] [S] == 1）{
标志= 1;
写（S，多个）;
}
如果（S == nbShifts和放大器;＆安培;标志== 0）写（__）;
}
}
写（\ N）;
}
}
您可以用.dat文件像这样运行此code：
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
我希望有人能告诉我这个当我开始我的问题;）
I have been tasked to do a scheduling program in my company. Basically given N employee you should schedule them shift for the month. I tried to do this via brute force and ordered priority of constraint. However, I am having problem when trying to maintain vertical and horizontal constraints.
Vertical constraints, all person should have equal number of shift per month. (e.g. They should be within the average number of day shift, night shift, rest day, early shift) However, there is also a day horizontal constraint that the number of shift per day should be equal daily.
I tried searching the internet and I usually read answer on using Genetic Algorithm. In my study of Genetic Algorithm, it seems the algorithm is not that suitable in my case. Does anybody know how to solve such problem?
Additional Illustration based on Enigmativity's comment: Basically there are 4 shifts,
The Y's are the employee shift total for the month which needs to be evenly distributed per employee. (ie each employee should have equal (or just difference by one) amount of shift type for the month) - Vertical constraint.
The X's are the daily total for all employee, basically each shift should also be evenly distributed for weedays and for weekends. - Horizontal constaint
Also, there are other constraint like desired shifts and adjacent shifts. But I tried to simplify it with just these even out rules for now.
--------------------------------------------------------------------------------
| Employee | 1 | 2 | 3 | 4 | + + + | 28 | 29 | 30 | 31 | S1 | S2 | S3 | S4 |
--------------------------------------------------------------------------------
| EmpA | S3 | S4 | S1 | S2 | + + + | S3 | S4 | S1 | S2 | Y | Y | Y | Y |
--------------------------------------------------------------------------------
| EmpB | S1 | S3 | S4 | S1 | + + + | S2 | S3 | S4 | S1 | Y | Y | Y | Y |
--------------------------------------------------------------------------------
| EmpC | S2 | S1 | S3 | S4 | + + + | S1 | S2 | S3 | S4 | Y | Y | Y | Y |
--------------------------------------------------------------------------------
| EmpD | S2 | S2 | S2 | S3 | + + + | S4 | S1 | S2 | S3 | Y | Y | Y | Y |
--------------------------------------------------------------------------------
| S1 | X | X | X | X | + + + | X | X | X | X | | | | |
--------------------------------------------------------------------------------
| S2 | X | X | X | X | + + + | X | X | X | X | | | | |
-------------------------------------------------------------------------------
| S3 | X | X | X | X | + + + | X | X | X | X | | | | |
--------------------------------------------------------------------------------
| S4 | X | X | X | X | + + + | X | X | X | X | | | | |
--------------------------------------------------------------------------------
I am currently working on a nurse scheduling problem that sounds very similar to yours. The objective is to schedule a shift (or day off) for each nurse on each day so that they both work the right number shifts (40hr work week) and meet the baseline shift requirements per day (3 nurses monday, 2 tuesday, etc.). This is a well know problem and, like any other scheduling problems, it is NP-Hard.
I agree with your comment that genetic algorithms are not well suited for this task (or for any task imo). There are far better approaches to solving this problem and they have been studied and well documented in the constraint programming and operation research fields.
My advice would be to take a mathematical programming language to model your problem and encode it as a constraint programming problem or a mixed integer linear program (MILP). There are a number of languages that let you encode these problems at a high level, the best known one would probably be AMPL. You can search for a nurse scheduling example's for that language that would probably help a lot. The AMPL language can compile easily into a MILP which can then be passed off to a solver like GLPK or CPLEX. Also, if you are in academia or have a fairly decent budget for this problem you should consider getting IBM's ILOG CPLEX package and coding your problem in their supported Optimization Programming Language (OPL). This is the language/solver that I am using and I am very happy with it.
Keep in mind this is and extremely difficult problem from a computational standpoint and I would make sure you are familiar with the difficulty before you put out any cost estimates for the project.
Edit: Since you upgraded your question let me upgrade my answer, here is working OPL code to solve your problem. I'll use OPL because I don't know AMPL but the two languages are very similar, you could easily translate.
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");
}
}
You could run this code with a .dat file like this:
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]];
And get the following output in less than a second:
S1 __ S3 S4 __ S4 S3
S1 __ S4 S3 __ S4 S3
S1 S2 __ S2 __ S4 S2
S4 S1 __ S1 __ S1 S2
I wish someone would have told me this when I started my problem ;)
这篇关于调度算法Maintining二维约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
