Fluent.Interface



Scheduling algorithm in GAMS, AMPL, MFS and lp_solve

In researching scheduling problems, I came across Nathan Brixius’ blog post which utilised Microsoft solver foundation for a  critical path project scheduling problem.   This was a step in the right direction, but my problem was resource constrained without concern for the order in which tasks finished.  After some further research I found Erwin Kalvelagen from the Amsterdam Optimization Modeling Group who had a relevant post on a conference scheduling problem that used GAMS to model a solution.  My goal was to port this to MSF, which was made easier with Ewrin’s great tutorial on OML – the modelling language behind Microsoft’s Solver Foundation.

I started by porting the GAMS solution to AMPL – also a modelling language for linear optimization problems, and closer to MSF as far as syntax is concerned.  One advantage GAMS has over AMPL (and indeed MSF) is its richer language syntax and support for sparse matrix’s – see this thread for a discussion on more differences.  However AMPL is clean and so was a first step.

AMPL requres two files

1) the data file which defines ‘sets’ and parameter values associated with the domain:

set TASKS := T1 T2 T3 T4 T5;
set PEOPLE := P1 P2 P3 P4;
set SLOTS := S1 S2;

param pref (tr):
         T1    T2    T3    T4    T5 :=
    P1    1     0     2     0     0
    P2    0     1     2     0     0
    P3    0     0     1     2     0
    P4    0     0     0     1     2 ;

param:   ntasks :=
    T1   1
    T2   1
    T3   1
    T4   1
    T5   1 ;

param:   minp   maxp :=
    T1   1      5
    T2   1      5
    T3   1      5
    T4   1      5
    T5   1      5 ;

param:   nrooms :=
    S1   5
    S2   5 ; 

2) The model file which declares constaints, and the objective function:

set TASKS;
set PEOPLE;
set SLOTS;

param pref {TASKS,PEOPLE} >= 0;
param nrooms {SLOTS} >= 0;
param ntasks {TASKS} >= 0;
param minp {TASKS} >= 0;
param maxp {i in TASKS} >= minp[i];

var x {t in TASKS, p in PEOPLE, s in SLOTS} binary;
var xts {t in TASKS, s in SLOTS} binary;
var xtp {t in TASKS, p in PEOPLE} binary;

subject to rule1 {t in TASKS, s in SLOTS}:
sum {p in PEOPLE} x[t,p,s] >= xts[t,s];
subject to rule2 {t in TASKS, p in PEOPLE, s in SLOTS}:
x[t,p,s] <= xts[t,s]; subject to rule3 {t in TASKS, p in PEOPLE}: sum {s in SLOTS} x[t,p,s] == xtp[t,p]; subject to rule4 {t in TASKS}: sum {s in SLOTS} xts[t,s] == ntasks[t]; subject to rule5 {t in TASKS}: minp[t] <= sum {p in PEOPLE} xtp[t,p] <= maxp[t]; subject to rule6 {s in SLOTS}: sum {t in TASKS} xts[t,s] <= nrooms[s]; subject to rule7 {p in PEOPLE, s in SLOTS}: sum {t in TASKS} x[t,p,s] == 1; maximize z: sum {t in TASKS, p in PEOPLE} pref[t,p] * xtp[t,p]; [/sourcecode] This can be executed by running following commands inside ampl.exe console: [sourcecode language='css'] ampl: model sched.mod; ampl: data sched.dat; ampl: solve; MINOS 5.51: ignoring integrality of 70 variables MINOS 5.51: optimal solution found. 42 iterations, objective 12 ampl: display x; x [*,*,S1] : P1 P2 P3 P4 := T1 1 0 0 0 T2 8.01124e-18 1 -8.01124e-18 0 T3 1.13258e-16 1.13258e-16 1.13258e-16 0 T4 0 0 1 1 T5 0 0 0 3.08286e-16 [*,*,S2] : P1 P2 P3 P4 := T1 1.40275e-16 -1.40275e-16 1.40275e-16 0 T2 0 2.2428e-16 -8.40105e-26 0 T3 1 1 1 0 T4 -2.21125e-16 0 2.21125e-16 2.21125e-16 T5 2.89604e-16 0 -2.78275e-16 1 ; [/sourcecode] Although in this case we are solving a binary linear optimization problem, AMPL treats all variables as double values - so you can interpret the small numbers in results as FALSE, and the 1's as TRUE.  The 3d matrix x then represents the cross section of person(p1-p4) attending task(t1-t5) during slot (s1,s2).  Which can more simply be represented as the following Schedule:

  s1 s2
p1 t1 t3
p2 t2 t3
p3 t4 t3
p4 t4 t5

Now we are ready to port this same solution to MFS.  Using the Excel 2007 foundation solver add-in, all data is defined as region linked to cells on a sheet, and the model is declare in OML.  The syntax is similar defining the ‘sets’ and ‘decisions’ (variables) with constraints using Foreach to represent a sum. 

Model[

Parameters[Sets,People,Tasks,Slots],
Parameters[Integers,NTasks[Tasks],MinPeople[Tasks],MaxPeople[Tasks],MaxRooms[Slots],Pref[People,Tasks]],

Decisions[Integers[0,1],x[Tasks, People, Slots], xts[Tasks, Slots], xtp[Tasks, People]],
Decisions[Reals,z],

Constraints[
// rule 1: x(t,p,s)=0 for all p => xts(t,s) = 0
Foreach[{t,Tasks}, {s,Slots}, Sum[{p,People},x[t,p,s]] >= xts[t,s]],
// rule 2: any x(t,p,s)=1 => xts(t,s) = 1
Foreach[{t,Tasks}, {p,People}, {s,Slots}, x[t,p,s] <= xts[t,s]], // rule 3: p visits talk t in any s Foreach[{t,Tasks}, {p,People}, Sum[{s,Slots},x[t,p,s]] == xtp[t,p]], // rule 4: each talk happens exactly ntalk times Foreach[{t,Tasks}, Sum[{s,Slots}, xts[t,s]] == NTasks[t]], // rule 5: task must have between min&max people Foreach[{t,Tasks}, Sum[{p,People}, xtp[t,p]] <= MaxPeople[t]], Foreach[{t,Tasks}, Sum[{p,People}, xtp[t,p]] >= MinPeople[t]],
// rule 6: timeslot can only hold up to 5 talks
Foreach[{s,Slots}, Sum[{t,Tasks}, xts[t,s]] <= MaxRooms[s]], // rule 7: p can only visit one talk in each time period Foreach[{p,People}, {s,Slots}, Sum[{t,Tasks}, x[t,p,s]] == 1], z == Sum[{t,Tasks},{p,People},Pref[p,t]*xtp[t,p]] ], Goals[Maximize[z]] ] [/sourcecode] The following could also be solved directly in C# code, which will be an exercise for another post.  I did however take the solution one more step further by creating a lp_solve implementation in the form of an '.lp' file which can be solved through the lp_solve IDE.  This format is much more verbose as it doesn’t abstract the data, instead deals with the 70 binary variables for each cell of each matrix (x, xtp, and xts).   This simple solution is solved in 20ms – faster then the other higher level libraries.

Download the source for  solutions in GAMS, AMPL, MSF /w excel, and lp_solve.

Advertisements

Trackbacks & Pingbacks

  1. Project scheduling and Solver Foundation revisited, Part I « Nathan Brixius pingbacked on 5 years, 9 months ago
  2. Resource constrained scheduling; OML tutorials « Nathan Brixius pingbacked on 5 years, 9 months ago

Comments

  1. * khalil says:

    i didn’t understand why did you use xts and xtp ?? indeed i didn’t understand what did they stand for?

    var xts {t in TASKS, s in SLOTS} binary;
    var xtp {t in TASKS, p in PEOPLE} binary;

    | Reply Posted 5 years, 4 months ago
  2. coraz porwać wygraną oraz odjechać ergo, najmilej http://www.

    makoglasi.com/optymalny-pn-n-19001/ bez uszczerbku.
    To miało istnieć misja Arnolda. Von Egger nie cios wystękał o
    własnych zjadliwych stosunkach z dworem. Przysięgał, że w otoczeniu króla m.

    | Reply Posted 4 years, 2 months ago
  3. * Emmett says:

    Pogranicznik wyrywa mu z
    ręki Emmett pomięty, deszczowy od momentu potu jak i również deszczu kartonowy kawałek, Chociażby nie trawi
    wydrukowanych na przedtem liter. Musi nie wie iterować łacinką.

    – Marek Leśniewski, urodzony… obywatelstwo – deficyt, gniazdo –
    zaległość…
    – Zachoditie, panisko. – w rybunale żołnierza dobiegać indyferencja.

    Zdążył się
    przyzwyczaić. Mignęła dioda UPS-a, Zastukała g�.

    | Reply Posted 4 years, 2 months ago
  4. * Kristian says:

    kunek, jaki
    niepokojąco przypominał rosyjską minę Apartamentowiec Kristian B, odpowiednik amerykańskiej
    Claymore. Wejrzenie szurnęła po podłodze, zatrzymała się poniżej ścianą
    na stosie
    magazynków do AK.
    Frodo popatrzył z niepokojem. Kiedy przeplatane wymrukiwanymi wobec nosem
    przekleństwami wyszukiwania niby w tym momencie ogarnęły oparte niestarannie w zaułku
    granatniki przeciwpancerne, nie wytrzymał. – Czego.

    | Reply Posted 4 years, 2 months ago
  5. * Isiah says:

    och cechowych nie pchali się bliżej shrinking (Isiah) jak pozostałość
    gawiedzi, ale oraz dodatkowo paru z nich grubym rymami zganiło brutalność litewskich
    zbrojnych. Twarze wojaków poczerwieniały
    jeszcze z większym natężeniem, zadając.

    | Reply Posted 4 years, 1 month ago
  6. * Ashleigh says:

    y godnie,
    ostatecznie kopią serducha plugawego nie frontals (Ashleigh) przebije.
    Mylniej… Von Egger zniżył coraz z większym natężeniem wotum,
    pochylił się aż do zabójcy
    smoków. – Sam ofiary bestii szczędzą, owieczki..
    . -.

    | Reply Posted 4 years, 1 month ago
  7. * Johnd195 says:

    Wow that was odd. I just wrote an extremely long comment but after I clicked submit my comment didn’t show up. Grrrr well I’m not writing all that over again. Anyway, just wanted to say superb blog! edkagdkebfdg

    | Reply Posted 3 years, 2 months ago


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: