Задача оптимизации модели планирования одиночных занятий - PullRequest
Новая
       36

Задача оптимизации модели планирования одиночных занятий

0 голосов
/ 17 декабря 2018

Я написал Миницинк-модель, которая позволяет учителю планировать отдельные занятия своих учеников.Учитель и ученики могут расставить приоритеты для своих доступных временных интервалов (prioTeacher, соответственно prio).

Модель отлично работает для простых и небольших входных наборов, но с реалистичным набором входных данных, т.е. 3 дня,каждый из них имеет 44 временных интервала (== 15 минут) и 11 студентов, но не нашел оптимального решения после более чем 24 часов.

Модель (stupla-prio.mzn) 

% enum of presence days
enum DAY;
int: num_days = card(DAY);
% maximal duration of a lessons
int: maxDur;
% maximal numbers of slots per Day;
int: maxSlots;
set of int: SLOT  = 1..maxSlots;
set of int: SLOTx = 0..maxSlots;
% number of students
int: n;
set of int: STUDENT = 1..n;
%
array[DAY]         of set of SLOT: teacher;
array[STUDENT,DAY] of set of SLOT: feasible;
array[STUDENT]       of 1..maxDur: lessonDuration;
array[STUDENT,DAY,SLOT]   of 0..3: prio;
array[DAY,SLOT]           of 0..3: prioTeacher;
% Factor for weighting: obj = obj_stud + k * obj_teacher
int: k;
%
% decision VARIABLES
% array[STUDENT,DAY] of var 0..maxSlots: start_slot;
array[STUDENT,DAY] of var SLOTx: start_slot;
array[STUDENT,DAY] of var SLOTx: end_slot;

% 2d-array that stores for each d (in DAYS) and each SLOT 
%    the STUDENT or 
%    0  if it is not allocated or
%    -1 the teacher is available neither
array[SLOT,DAY] of var -1..n: schedule;

% -----------------------------------------------------------
% CONSTRAINTS 
% 1. For each student 'start_slot' must be in 'feasible'
constraint forall(s in STUDENT, d in DAY where start_slot[s,d] > 0)(
  start_slot[s,d] in feasible[s,d] );

% 2. For each student 'end_slot' = 'start_slot' + lessonDuration - 1
constraint forall(s in STUDENT, d in DAY)(
  if start_slot[s,d] > 0 then
    end_slot[s,d] = start_slot[s,d] + lessonDuration[s] - 1
  else
    end_slot[s,d] = 0
  endif);
% 3. All slot between 'start_slot' and 'end_slot' must be in 'feasible' 
constraint forall(s in STUDENT, d in DAY where start_slot[s,d] > 0)( 
  forall(j in 1..lessonDuration[s]-1) ( start_slot[s,d] + j in feasible[s,d] )
  ); 
% 4. make sure each student has exactly 1 lesson
constraint forall(s in STUDENT)( sum([start_slot[s,d] > 0| d in DAY]) = 1);
% 5. link 'schedule' to 'start_slot' and 'end_slot'
constraint forall(s in STUDENT, d in DAY, z in SLOT) (
  (z in feasible[s,d] /\ z >= start_slot[s,d] /\ z <= end_slot[s,d]) 
     <-> schedule[z,d] = s
  );
% 6. mark empty slots for teacher
constraint forall(d in DAY, z in SLOT)(
  (z in teacher[d] /\ schedule[z,d] = -1) -> schedule[z,d] = 0 );
% objective function students
var int: obj_stud;
constraint obj_stud = sum([prio[schedule[z,d],d,z]|
  d in DAY, z in SLOT where schedule[z,d] > 0]);
% objective function teacher
var int: obj_teacher;
constraint obj_teacher = sum([prioTeacher[d,z]|
  d in DAY, z in SLOT where schedule[z,d] > 0]);

%solve satisfy;
solve :: int_search( [start_slot[s,d] |s in STUDENT, d in DAY], first_fail, indomain, complete) maximize (obj_stud + k * obj_teacher);

output [ 
% "start_slot =\n" ++ show2d(start_slot) ++ "\n" ++
% "end_slot   = " ++ show2d(end_slot) ++ "\n" ++
% " teacher   = " ++ show(teacher) ++ ";\n" ++
% " feasible  = " ++ show2d(feasible) ++ "\n" ++
% "schedule   = \n" ++ show2d(schedule) ++ ";\n"  ++
% " - "
  "  Slot# ||"] ++
  [ "  \(d)  |" | d in DAY ] ++
 [
  "|  obj = " ++ show(obj_stud + k * obj_teacher) ++ 
  "   [teacher=\(obj_teacher), " ++
  "stud=\(obj_stud), k=\(k)]" ] ++
[ "\n -------++"] ++ 
[ "-------+" | d in DAY ] ++ 
["+\n"] ++
[
  if d = 1 then show_int(5,z) ++ "   ||" else "" endif ++
  show_int(4,schedule[z,d]) ++ "   |" ++
  if d = num_days then "|\n" else "" endif | z in SLOT, d in DAY
] ++ [ " -------++"] ++
  [ "-------+" | d in DAY ]  
  ++ ["+\n"]
;

Данные

пример 1 (работает нормально) 

    DAY = {Mon, Wed};
maxSlots = 14;                % == 30 minutes slot duration
teacher = [ {1,2,3,4,5,6},    
            {6,11,12,13,14}];

n = 4;
lessonDuration = [2,1,1,3];
maxDur = 3;

feasible = array2d(1..n, DAY, [
  {1,2,3,4,5,6}, {6}, 
  {1,2,3},       {},               % Stud2: Day1, Day2
  {1},           {13,14},          % Stud3: Day1, Day2
  {3,4,5},       {11,12,13,14}]);

prio = array3d(1..n,DAY,1..maxSlots, [
    % Stud1
    1,1,1,2,2,2,0,0,0,0,0,0,0,0,
    0,0,0,0,0,2,0,0,0,0,0,0,0,0,
    % Stud2
    1,3,3,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    % Stud3
    3,0,0,0,0,0,0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,0,0,0,0,2,2,
    % Stud4
    0,0,1,2,2,0,0,0,0,0,0,0,0,0 ,
    0,0,0,0,0,0,0,0,0,0,3,3,1,1]); 
%
k = 10;
prioTeacher = array2d(DAY,1..maxSlots, [
    % Example 1:
    % morning muffel, and break
    % 1,1,1,2,2,2,3,1,1,3,3,3,3,3,
    % 1,1,1,2,2,2,3,1,1,3,3,3,3,3,]);
    % Example 2:
    % early bird
    3,3,3,3,3,3,1,1,1,1,1,1,1,1,
    3,3,3,3,3,3,1,1,1,1,1,1,1,1]);

Пример 2 (занимает много времени ...) 

% Datafile
% Available week days
DAY      = {Mon, Tue, Wed};
% Number of maximal slots per day, == 15 minutes slots
maxSlots = 44;
% Number of students
n        = 11;
% Weighting factor
k        = 1;
lessonDuration = [3,3,2,3,3,3,3,3,6,4,2];
maxDur   = 6;
teacher = [ {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44},
  {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44},
  {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44}];
% feasible time slots (teacher and students intersected)
feasible = array2d(1..n, DAY, [
  % IH
  {1,2,3,4,5,6,7,8}, {}, {1,2,3,4,37,38,39,40,41,42,43},
  % MM
  {11,12,13,14,15,16,28,29,30,31}, {7,8,9,10,11}, {},
  % NW
  {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42}, {}, {1,2,3,4,5,6,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42},
  % RD
  {7,8,9,10,11,12,40,41,42}, {13,14,15,16,17,18,19,20,21,22,23,34,35,36,37,38}, {},
  % MS
  {7,8,9,10,11,12,34,35,36,37,38,39,40,41,42}, {35,36,37,38,39,40}, {},
  % SB
  {}, {1,2,3,4,5,6}, {8,9,10,11,12},
  % SO
  {}, {}, {6,7,8,9,10,11,12,36,37,38,39,40,41,42},
  % CT
  {}, {}, {1,2,3,4,5,6,7,8,9,10,11,12},
  % AG
  {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44}, {9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28}, {},
  % SS
  {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44}, {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44}, {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44},
  % RF
  {25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42}, {}, {33,34,35,36,37,38,39,40,41,42}
]);
% Prioririties of Teacher
prioTeacher = array2d(DAY,1..maxSlots, [
  3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2]);
% Priorities of Students
prio  = array3d(1..n,DAY,1..maxSlots, [
  %  1. IH
  2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,0,
  %  2. MM
  0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  %  3. NW
  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  1,1,1,1,1,1,0,0,0,0,0,0,0,0,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,0,0,
  %  4. RD
  0,0,0,0,0,0,3,3,3,3,3,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  %  5. MS
  0,0,0,0,0,0,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  %  6. SB
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  %  7. SO
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,3,3,3,3,3,3,0,0,
  %  8. CT
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  %  9. AG
  1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
  0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  % 10. SS
  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
  3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
  % 11. RF
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,2,0,0]);

(Вы можете получить доступ к файлам здесь: https://gitlab.com/andibachmann/stupla_mzn/tree/master/mzn/t3)

Я провел расчеты с помощью mzn-gecode (оценочный драйвер G12 MiniZinc, версия 2.0.2).

Любые советы и / или указания по дальнейшим улучшениям приветствуются!

С уважением, Анди

1 Ответ

0 голосов
/ 28 декабря 2018

Я внес следующие изменения в модель:

  • объединил измерения DAY и SLOT в одно измерение TIME (параметры преобразованы соответствующим образом), поэтому соблюдайте осторожность, чтобыуроки не продолжаются в течение нескольких дней.
  • удалено явное schedule представление решения - теперь оно вычисляется на лету в секции вывода.
  • предварительно рассчитано выполнимовремя начала занятий для учащихся - таким образом, в модели должны быть ограничены только времена начала.
  • изменено для использования бинарных переменных start и active, которые показывают, начинается ли урок ученика в данное время и является ли он активнымв определенный момент времени соответственно.
  • сделал все ограничения линейными в переменных start и active.

Используя модифицированную модель, решатель OSICBC решает больший экземпляр для оптимального в пределахсекунду. 

% enum of presence days
enum DAY;
int: num_days = card(DAY);
% maximal duration of a lessons
int: maxDur;
% maximal numbers of slots per Day;
int: maxSlots;
set of int: SLOT  = 1..maxSlots;
set of int: SLOTx = 0..maxSlots;
% number of students
int: n;
set of int: STUDENT = 1..n;
%
array[DAY]         of set of SLOT: teacher;
array[STUDENT,DAY] of set of SLOT: feasible;
array[STUDENT]       of 1..maxDur: lessonDuration;
array[STUDENT,DAY,SLOT]   of 0..3: prio;
array[DAY,SLOT]           of 0..3: prioTeacher;
% Factor for weighting: obj = obj_stud + k * obj_teacher
int: k;

% Make the time axis one-dimensional and convert all data accordingly.
set of int: TIME = 1..maxSlots*num_days;

function int: time(int: d, int: z) = (d-1)*maxSlots + z;

set of TIME: teacher_time = {time(d, z) | d in DAY, z in teacher[d]};
array[STUDENT] of set of TIME: feasible_time = [{time(d, z) | d in DAY, z in feasible[s,d]} | s in STUDENT];
array[STUDENT] of set of TIME: feasible_start_time = 
    [{time(d,z) | d in DAY, z in 1..maxSlots-lessonDuration[s]+1 where forall(u in time(d,z)..time(d,z)+lessonDuration[s]-1)(u in feasible_time[s] intersect teacher_time)} | s in STUDENT];

array[STUDENT,TIME] of 0..3: prio_time = array2d(STUDENT, TIME,  [prio[s,d,z] | s in STUDENT, d in DAY, z in SLOT]);
array[TIME] of 0..3: prioTeacher_time = [prioTeacher[d,z] | d in DAY, z in SLOT]; 

%
% decision VARIABLES
array[STUDENT,TIME] of var 0..1: start;
array[STUDENT,TIME] of var 0..1: active;

% -----------------------------------------------------------
% CONSTRAINTS
% 1. a lesson can only start at a feasible time
constraint forall(s in STUDENT, t in TIME)
    (start[s,t] <= bool2int(t in feasible_start_time[s]));

% 2. each lesson must have a start time
constraint forall(s in STUDENT)
    (sum(t in TIME)(start[s,t]) = 1);

% 3. maximum one lesson active at any time         
constraint forall(t in TIME)
    (sum(s in STUDENT)(active[s,t]) <= 1);

% 4&5. constraints defining if lesson active
constraint forall(s in STUDENT, d in 1..num_days)
  (active[s,time(d,1)] = start[s,time(d,1)]);

constraint forall(s in STUDENT, d in 1..num_days, z in 2..maxSlots)  
  (active[s,time(d,z)] <= active[s,time(d,z-1)] + start[s,time(d,z)]);

% 6. ensure duration of lesson is fulfilled
constraint forall(s in STUDENT)
    (sum(t in TIME)(active[s,t]) = lessonDuration[s]);   

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

solve maximize obj;

output [ 
  "  Slot# ||"] ++
  [ "  \(d)  |" | d in DAY ] ++
 [
  "|  obj = " ++ show(obj) ++ 
  "   [teacher=\(sum(s in STUDENT, t in TIME)(active[s,t] * k*prioTeacher_time[t])), " ++
  "stud=\(sum(s in STUDENT, t in TIME)(active[s,t] * prio_time[s,t])), k=\(k)]" ] ++
[ "\n -------++"] ++ 
[ "-------+" | d in DAY ] ++ 
["+\n"] ++
[
  if d = 1 then show_int(5,z) ++ "   ||" else "" endif ++
  show_int(4,let {var int: student = sum(s in STUDENT)(s*active[s,time(d,z)])} in if student > 0 then student else bool2int(z in teacher[d]) - 1 endif) ++ "   |" ++
  if d = num_days then "|\n" else "" endif | z in SLOT, d in DAY
] ++ [ " -------++"] ++
  [ "-------+" | d in DAY ]  
  ++ ["+\n"]
;

Другой вариант (придерживающийся оригинальной модели и более легкий для чтения) будет: 

...
array[STUDENT] of var TIME: start_time;

include "disjunctive.mzn";
constraint disjunctive(start_time, lessonDuration);

constraint forall(s in STUDENT)
    (start_time[s] in feasible_start_time[s]);

var int: obj = sum(s in STUDENT, t in TIME where t >= start_time[s] /\ t <= start_time[s] + lessonDuration[s] - 1)(prio_time[s,t] + k*prioTeacher_time[t]); 

solve maximize obj;
...
...