# Regarding a constraint satisfaction problem.

This topic is 5228 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633734
• Total Posts
3013590
×