二维约束维护的调度算法

Question

我的任务是在我公司做一个调度计划.基本上给N员工你应该安排他们转移这个月.我试图通过蛮力和有序的约束优先权来做到这一点.但是,我在尝试维护垂直和水平约束时遇到问题.

纵向约束,所有人每月应该有相同的班次.(例如,他们应该在白班,夜班,休息日,提前班次的平均数量之内)但是,还有一天水平约束,即每天的班次数应该相等.

我试着在互联网上搜索,我经常阅读使用遗传算法的答案.在我对遗传算法的研究中,似乎算法并不适用于我的情况.有谁知道如何解决这个问题？

基于Enigmativity评论的附加插图:基本上有4个班次,

Y是本月的员工轮班总额,需要按员工平均分配.(即每个员工本月的班次类型应该相等(或只差一个) - 垂直约束.

X是所有员工的每日总数,基本上每个班次也应平均分配给休息和周末. - 水平构造

此外,还存在其他约束,例如期望的移位和相邻移位.但我现在尝试用这些均匀的规则来简化它.

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

Answer 1

我目前正在研究一个听起来非常类似于你的护士安排问题.目标是为每位护士安排每天轮班(或休假),以便他们都能正常轮班(每周工作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

我希望当我开始我的问题时,有人会告诉我这个;)