[gecode-users] Surgery scheduling problem

[Fabrício de Reuter Sperandio]

Dear members of the GECODE mailing list,

I am trying to model a surgery scheduling problem as a constraint
programming model. The problem consists in scheduling a set of surgeries to
operating rooms across a one week planning horizon. My testing instance
contains 316 surgeries to be scheduled into 10 timeblocks (OR/shift) of 3
operating rooms. Each surgery has a determined surgeon and estimated
duration. In some days of the week the 3 ORs are working in parallel and we
have to schedule the surgeons among them. The goal is to maximize the
number of surgeries scheduled.

I have tried to model the problem using the binpacking constraint, however
it is different from a binpacking problem as the number of bins is fixed
and I have to select a subset of items, it is more like a knapsack problem,
more specifically a multiple knapsack problem. Does anyone know if I can
use the binpacking constraint limiting the number of bins and not packing
some items?

I have also tried to model the problem using the cumulatives constraint,
however I have multiple resources of two types, more specificaly 3 ORs and
10 surgeons. I was trying to use cumulatives to deal with the multiple ORs
using limit 1, but I am not sure if I can use cumulatives at the same time
to schedule the surgeons, also limited to one.

The problems is like a multiple knapsack problem with parallel resources.
Could you point me to the more efficient way to model this problem?

I have modeled the problem in a naive way, but it is not efficient, so I
would like to use different constraints to improve performance.

Best regards,

Fabrício Sperandio
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20130527/fb9850b8/attachment.html>