Decision Optimization

Originally posted by: Gerard75

I am making a schedule of meetings. I use the language OPL and I have to think about several models of data. And we proceed stages time of inactivity of the collaborators. I work with this file :

meeting id_meeting | duration | set of employees

m1 | 4 | e1 e3 e4

 m2 | 3 | e2 e4 e5

 m3 | 1 | e1 e3 e5

m4 | 2 | e2 e3 e4

 m5 | 3 | e1 e2 e3 e4 e5

 m6 | 3 | e1 e2 e4 e5

m7 | 5 | e1 e2 e3

How can I modeling this problem ??

Hi,

let me share a model you could start with:

.mod

using CP;

tuple meeting
{
   int id;
   int duration;
   {int} employees;
}

{meeting} meetings=...;

int totalDuration=sum(m in meetings) m.duration;

tuple incompatibleMeeting
{
meeting m1;
meeting m2;
}

{incompatibleMeeting} incompatibleMeetings={<m1,m2> | ordered m1,m2 in meetings: 0!=card(m1.employees inter m2.employees)};

 

dvar interval itvs_meeting[m in meetings] in 0..totalDuration size m.duration;

minimize max(m in meetings) endOf(itvs_meeting[m]);

subject to
{
forall(<m1,m2> in incompatibleMeetings) overlapLength(itvs_meeting[m1],itvs_meeting[m2])==0;

}

.dat

meetings={<1,4,{1,3,4}>,<2,3,{2,4,5}>,<3,1,{1,3,5}>,<4,2,{2,3,4}>,<5,3,{1,2,3,4,5}>,
<6,3,{1,2,4,5}>,<7,5,{1,2,3}>};

This could be a starting point

regards

Originally posted by: Gerard75

Thank you so much ! But why employees is not {string} employees ?

Hi,

because I wanted to help quickly but of course that would be possible:

.mod

using CP;

tuple meeting
{
   int id;
   int duration;
   {string} employees;
}

{meeting} meetings=...;

int totalDuration=sum(m in meetings) m.duration;

tuple incompatibleMeeting
{
meeting m1;
meeting m2;
}

{incompatibleMeeting} incompatibleMeetings={<m1,m2> | ordered m1,m2 in meetings: 0!=card(m1.employees inter m2.employees)};

 

dvar interval itvs_meeting[m in meetings] in 0..totalDuration size m.duration;

minimize max(m in meetings) endOf(itvs_meeting[m]);

subject to
{
forall(<m1,m2> in incompatibleMeetings) overlapLength(itvs_meeting[m1],itvs_meeting[m2])==0;

}

.dat

meetings={<1,4,{"1","3","4"}>,<2,3,{"2","4","5"}>,<3,1,{"1","3","5"}>,<4,2,{"2","3","4"}>,
<5,3,{"1","2","3","4","5"}>,
<6,3,{"1","2","4","5"}>,<7,5,{"1","2","3"}>};

regards

Originally posted by: Gerard75

Hi, when I run my code meetings "is not define". I don't understand why ? 

Hi,

I guess you have not added the .dat to the run configuration you run.

Or if you use command line , you should not forget the .dat : oplrun f.mod f.dat

regards

Originally posted by: Gerard75

Ok, it's runnable, but now how can I interpret the solution ?

// solution with objective 21
itvs_meeting = [
        <1 3 7 4> <1 7 10 3> <1 2 3 1> <1 0 2 2>
         <1 10 13 3> <1 18 21 3> <1 13 18 5>]

Because meetings aren't ordered, "13" or "18" items are the optimum interval between meetings ? (I'm not sure)

But I would like ordered meetings seeing to optimize the global waiting of each employees.

If you click on itvs you will see

which will show you the meetings in a gantt view

regards

PS:

Some useful links at

Originally posted by: Gerard75

Hi Alex, I don't know how can I implement noOverLap on my code to otpimize global duration of inactivity for each employees ?? I think that we should think of employees duration rather than meetings duration no ?

p.s : sorry for the trouble.

Hi,

if you have a look at the size of

{incompatibleMeeting} incompatibleMeetings={<m1,m2> | ordered m1,m2 in meetings: 0!=card(m1.employees inter m2.employees)};

you get 21 which means no 2 meeting should happen at the same time.

When you say "global duration of inactivity", you mean the holes between starts and ends ?

regards

Originally posted by: Gerard75

No,  for example  in this following case , employees e1 has no wait. Because meeting after meeting e1 is here, meeting noOverlaps. But we're trying to optimize the waiting  for each employee, the global waiting by a new order of meetings. This case is optimize for e1 only.

m2 | 3 | e2 e4 e5

m4 | 2 | e2 e3 e4

m1 | 4 | e1 e3 e4

m3 | 1 | e1 e3 e5

 m5 | 3 | e1 e2 e3 e4 e5

 m6 | 3 | e1 e2 e4 e5

m7  | 5 | e1 e2 e3

Hi

then you should change

minimize max(m in meetings) endOf(itvs_meeting[m]);

into

{string} employees=union (m in meetings ) m.employees ;

minimize sum(e in employees) (max(m in meetings:e in m.employees)endOf(itvs_meeting[m])-min(m in meetings:e in m.employees)startOf(itvs_meeting[m]));       

Originally posted by: Gerard75

// solution with objective 80
itvs_meeting = [
        <1 12 16 4> <1 0 3 3> <1 6 7 1> <1 10 12 2>
         <1 7 10 3> <1 3 6 3> <1 16 21 5>];

How can I display the new meetings order ? I think it's more useful.

Best regards

Hi,

if you click on itvs_meeting you will see

regards