[gecode-users] Surgery scheduling problem

[Guido Tack]

Hi,

this is more of a modelling question than about Gecode, but here are some ideas.  I'd try to model the ORs as a cumulative resource of capacity 3, and then add fixed dummy tasks during the time slots where not all of them are available.  The surgeries could either become optional tasks, or you let the schedule overflow the time horizon and regard everything after the one week mark as not scheduled.  To schedule the surgeons, you'd probably need to resort to reified constraints (mapping time slots to surgeons) and then constraining the surgeons in one time slot to be all different.

But given the size of the problem, I'm not sure the model is the issue here, perhaps it's more important to find a good branching heuristic.

Cheers,
Guido

-- 
Guido Tack
http://www.csse.monash.edu/~guidot/



On 27/05/2013, at 6:21 PM, Fabrício de Reuter Sperandio <frsperandio at fe.up.pt> wrote:

> 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 _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20130529/639efc78/attachment.html>