I have been working through some CSPs and I have noted that scheduling problems are quite often used with CSPs. I have the following example:

A certain deli prepares the following meals for take-away:

enter image description here

The number of cooks needs to be minimized - each order is prepared by one cook. Meals are prepared so that they are ready exactly at the time the client will collect the order. These are the orders for a specific day:

enter image description here

So now, the questions:

1. Define the variables and domains for each of the variables.

I am pretty comfortable with the variables - I would say they are:

X = {O1, O2, O3, O4, O5, O6, O7}

My problem is with the domains - I know that the domain for each order should be the cook preparing the meal, but I don't know how to specify that, as I haven't determined yet how many cooks are required.

Should it perhaps be something like this?

Dx = {Cn}

2. Define the constraints.

Looking at the start and end times, I would say the constraints are as follows:

O2 ≠ O3

O3 ≠ O4

O3 ≠ O5

O4 ≠ O5

O4 ≠ O6

O5 ≠ O6

O6 ≠ O7

3. Draw the constraint diagram.

enter image description here

4. State the minimum number of cooks required, as well as which order they will each prepare.

I'm not sure if there's some magic method here, but I just looked at the time overlaps and determined the following:

3 cooks are required

Cook 1 will prepare O1, O2, O4 and O7

Cook 2 will prepare O3 and O6

Cook 3 will prepare O5

Can someone please just guide me here, in case I'm not on the right path?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.