Sign in to follow this  
Joss

Regarding a constraint satisfaction problem.

Recommended Posts

Hi. I've never posted on this forum, I usually just read the posts, but I've come across a constraint satisfaction problem which I can't figure out, and I thought I'd post it in this forum so I could get some help. Constraint satisfaction problems are not my favorite kind, and the only ones I am able to solve are the easy ones (the n-queen problem, map coloring...). But when I face a harder one, I fint it hard to choose the variables, domains and constraints... This is the problem I told you about: The doctors in a clinic need to schedule the operations arranged for a month. They have a number of surgery rooms, days (with 3 shifts per day, each lasting 8 hours), and a list of operations to carry out. Each operation is assigned to only one surgery team. We need to schedule the operations in a month, taking into account the following facts: a) Two operations can't be carried out simultaneously in the same surgery room. b) The operations assigned to a surgery team must be carried out with a separation of at least 4 shifts. *** That's it. Neither my wife not me can find a proper assignation of variables to the problem. Our constraint satisfaction notes from the AI classes we took are no use. We are already giving up. Could you help us discussing this problem, and finding the variables and domains? Thank you. Let the discussion begin. ------------------------------------------

Share this post


Link to post
Share on other sites
Do you have any constraints on the number of rooms, number of teams, number of operations per team, etc? It could be done with dynamic programming if you had some reasonable upper bounds.

Share this post


Link to post
Share on other sites
It must be more complex than what is laid out, because the maximum number of operations you can schedule is given by :

max operations = min((floor(Days*3)/5) * Teams) , (Rooms*Days*3))

ie. limited by both number of operations that the teams are able to perform OR limited room space.

And if the number of operations to schedule is less than this, the problem is easy to solve, since the 4 shift gap constraint still guarantees that the rooms can be filled eg. 123451234512345

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this