1

我有一个有效的 Miniznic 模型来安排 1 位教授有 n 名学生的个人课程（单节课安排模型的优化问题）。该模型考虑了教授和学生的可用性（硬约束）和时间偏好（目标函数）。

现在，我想扩展模型并优化课程表，以最大限度地减少课程之间的差距。

例子：

  Schedule  : p L p p L L . . p p L L p L L p L p p . L p L L . L p L
  Real Gaps : . L p p L L . . . . L L p L L p L . . . L p L L . L p L

在哪里

 `p` =  0 == Teacher available, but no Lesson
 `L` =  1 == Teacher gives lesson (to student)
 `.` = -1 == Teacher not available

显然，pin slot 1 不能算作间隙。同样，插槽 9 和 10 也没有间隙。消除所有错误间隙， Schedule最终应该看起来像Real Gaps数组（注意：错误间隙用.; 与不可用相同）。

结果将是一个间隙数组[2, 1, 1, 1, 1]（每个间隙显示它持续的插槽数）。然后，基于这样的阵列，人们可以例如制定目标以最小化整体间隙槽。

在ruby我能够制定一个算法来做我想要的：

def gap_array(schedule_arr)
  # initialize variables
  start_search = false              # flag for break start
  break_slots  = 0                  # counter of break slots
  res_arr      = []                 # resulting array
  schedule_arr.each do |slot|
    if slot == 1                    # start watching for break
      start_search = true
    end
    #
    if start_search                 
      if    slot == 0               # == break
        break_slots += 1
      elsif slot == 1               # == consecutive lesson slot
        if break_slots > 0          # number of break_slots > 0
          res_arr.append(break_slots)
          break_slots = 0
        end
      else                          # == not available
        break_slots  = 0            # any break so far is discarded
        start_search = false         
      end
    end
  end
  return res_arr
end

如何在 Minizinc 中制定这样的算法？

谢谢！

4

1 回答 1

2

MiniZinc 中的一种方法是通过以下方式扩展单课调度模型的优化问题中的模型：

最初计算teacher_free为教师不可用的时隙与没有上课的相邻时隙相结合（这分两步完成，分别从左侧teacher_free_left和右侧teacher_free_right开始，然后将结果组合成表格teacher_free）。

在下一步中，real_gap将计算教师不空闲且不上课的时段。

real_gap然后在目标中引入一个惩罚项，例如（k2作为间隙惩罚权重）：

int: k2 = 1;
var int: obj = sum(s in STUDENT, t in TIME)
    (active[s,t] * (prio_time[s,t] + k*prioTeacher_time[t])) - k2*sum(real_gap);

这里是模型的所有其他扩展（还有一些进一步的评论）：

array[DAY,SLOT]           of var 0..1: lesson = array2d(DAY, SLOT, [sum(s in STUDENT)(active[s,time(d,z)]) | d in DAY, z in SLOT]);
array[DAY,SLOT]           of var 0..1: teacher_free_left;
array[DAY,SLOT]           of var 0..1: teacher_free_right;
array[DAY,SLOT]           of var 0..1: teacher_free;
array[DAY,SLOT]           of var 0..1: real_gap;

predicate equals_and(var 0..1: z, var 0..1: x, var 0..1: y) = 
    (z <= x /\ z <= y /\ z >= x + y - 1);

predicate equals_or(var 0..1: z, var 0..1: x, var 0..1: y) = 
    (z >= x /\ z >= y /\ z <= x + y);

% calculate teacher free left
%    first slot -> teacher free = no lesson in the slot
%    other slots -> teacher free = teacher out or (left slot teacher free and no lesson in slot)
array[DAY,SLOT]           of var 0..1: teacher_free_left_temp;

constraint forall(d in DAY)
    (teacher_free_left_temp[d,1]=1-lesson[d,1]);
    
constraint forall(d in DAY, z in 2..maxSlots)
    (equals_and(teacher_free_left_temp[d,z], teacher_free_left[d,z-1], 1-lesson[d,z]));

constraint forall(d in DAY, z in SLOT)
    (equals_or(teacher_free_left[d,z], 1 - bool2int(z in teacher[d]), teacher_free_left_temp[d,z]));
    
% calculate teacher free right
%    last slot -> teacher free = no lesson in the slot
%    other slots -> teacher free = teacher out or (right slot teacher free and no lesson in slot)
array[DAY,SLOT]           of var 0..1: teacher_free_right_temp;

constraint forall(d in DAY)
    (teacher_free_right_temp[d,maxSlots]=1-lesson[d,maxSlots]);
    
constraint forall(d in DAY, z in 1..maxSlots-1)
    (equals_and(teacher_free_right_temp[d,z], teacher_free_right[d,z+1], 1-lesson[d,z]));

constraint forall(d in DAY, z in SLOT)
    (equals_or(teacher_free_right[d,z], 1 - bool2int(z in teacher[d]), teacher_free_right_temp[d,z]));

% teacher free when teacher free left or teacher free right
constraint forall(d in DAY, z in SLOT)
    (equals_or(teacher_free[d,z], teacher_free_left[d,z], teacher_free_right[d,z]));

% real gap when teacher not free and no lesson
constraint forall(d in DAY, z in SLOT)
   (equals_and(real_gap[d,z], 1-teacher_free[d,z], 1-lesson[d,z]));
于 2020-06-22T13:29:46.067 回答