JCW2
asked on
Precise Formulation
I'm trying to give a precise formulation for this constraint satisfaction problem:
Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach.
Class scheduling: There is a fixed number of professors and classrooms, a list of classes to be offered, and a list of possible time slots for classes. Each professor has a set of classes that he or she can teach.
My previous posts makes an implicit assumption about the duration of a class. If you wish to add more flexibility on this trait, then some adjustments to the post must be made.
ASKER
Is this valid?:
{CK, TL | K in [ C1.. CK ], where CK can be taught by PI; L in [T1 .. TL ], where CK is taught during TL}
{CK, TL | K in [ C1.. CK ], where CK can be taught by PI; L in [T1 .. TL ], where CK is taught during TL}
Sorry, not familiar with your formal notation.
ASKER
ASKER
"This," referring to the post with the cryptic notation.
For the solution set, don't you need a triplet S = {P_i, T_j, C_k | ... } ?
That is, the i-th professor teaches the k-th class in the j-th timeslot.
Goal: Maximize |S| subject to constraints.
=======
Notation Issues:
You wrote:
C_K where k in [C1 .. C_K]
Shouldn't C_K be C_k (case sensitive?)
And "k in [C1 .. C_K]" - shouldn't it be "k in [1..C]", since k is an index but C1 is a class.
=======
Constraints:
I know it is obvious that a professor cannot teach two different classes in the same time slot; but do you need to state this in your set of constraints?
Defining S_i as above, shouldn't S_i be part of your set of constraints? Using this notation may simplify the construction (but I don't think it is mandatory).
That is, the i-th professor teaches the k-th class in the j-th timeslot.
Goal: Maximize |S| subject to constraints.
=======
Notation Issues:
You wrote:
C_K where k in [C1 .. C_K]
Shouldn't C_K be C_k (case sensitive?)
And "k in [C1 .. C_K]" - shouldn't it be "k in [1..C]", since k is an index but C1 is a class.
=======
Constraints:
I know it is obvious that a professor cannot teach two different classes in the same time slot; but do you need to state this in your set of constraints?
Defining S_i as above, shouldn't S_i be part of your set of constraints? Using this notation may simplify the construction (but I don't think it is mandatory).
I would list every constraint first in simple English including all the obvious constraints (especially uniqueness and mutual exclusion). For example, a class cannot be in two different timeslots, and a class cannot be taught by two different professors.
ASKER
Is this better:
Correction-2.PNG
Correction-2.PNG
Doesn't http:#34117027 allow two classes to be in the same time slot? That would be OK if there were multiple classrooms.
If precision is necessary, then all assumptions (e.g., number of classrooms, fixed duration of classes and timeslots, etc.) probably should be stated as a preface to your set.
You also need to define what S is. Is S "all possible solutions"? If not, do you need to define "all possible solutions"?
In your OP, you use the term "lists". These lists are objects that can have their own symbol. I would think that more succinct notation would refer to these list symbols rather than using phrases like "can be taught by". In set notation, you can say x element of A (where A can be a list).
BTW - I forget notation, but should the triplet by enclosed in parens like:
(Ck, Tl, Pi) ? That way, it looks like a point in the 3d vector space. Then predefine the meaning of (Ck, Tl, Pi) as Pi teaches Ck in timeslot Tl. After defining this vector definition, it is not necessary to repeat it in your constraint definition as it is pre-defined. Then you can focus on just the constraints.
For constraints, you can use indexes like i != j to establish constraint relationships amongst the vectors.
My previous comments about indexing have still not been addressed or commented.
If precision is necessary, then all assumptions (e.g., number of classrooms, fixed duration of classes and timeslots, etc.) probably should be stated as a preface to your set.
You also need to define what S is. Is S "all possible solutions"? If not, do you need to define "all possible solutions"?
In your OP, you use the term "lists". These lists are objects that can have their own symbol. I would think that more succinct notation would refer to these list symbols rather than using phrases like "can be taught by". In set notation, you can say x element of A (where A can be a list).
BTW - I forget notation, but should the triplet by enclosed in parens like:
(Ck, Tl, Pi) ? That way, it looks like a point in the 3d vector space. Then predefine the meaning of (Ck, Tl, Pi) as Pi teaches Ck in timeslot Tl. After defining this vector definition, it is not necessary to repeat it in your constraint definition as it is pre-defined. Then you can focus on just the constraints.
For constraints, you can use indexes like i != j to establish constraint relationships amongst the vectors.
My previous comments about indexing have still not been addressed or commented.
ASKER
Improved:
Solution-3.PNG
Solution-3.PNG
>> "and a Ck occupies 1 Tl slot at a time"
If Ck were to occupy two timeslots at the same time, then that would perhaps be a redundancy (which depending upon notation can occur in schools).
But the issue is whether two different Ck can occupy the same timeslot. Anser is "No", I think. Is that in your set of constraints?
(If I misunderstood your intent here, then either I am being too fussy, or too tired, or the notation needs to follow a formalism that is not subject to misinterpretation, or all of the above. Back in 1-2 hours.)
In the meantime, could you write down the set of assumptions, and a simple set of constraints in layman's terms, and then we can check off the list a little easier.
If Ck were to occupy two timeslots at the same time, then that would perhaps be a redundancy (which depending upon notation can occur in schools).
But the issue is whether two different Ck can occupy the same timeslot. Anser is "No", I think. Is that in your set of constraints?
(If I misunderstood your intent here, then either I am being too fussy, or too tired, or the notation needs to follow a formalism that is not subject to misinterpretation, or all of the above. Back in 1-2 hours.)
In the meantime, could you write down the set of assumptions, and a simple set of constraints in layman's terms, and then we can check off the list a little easier.
ASKER
C: Class; T: Time slot; P: Professor; K: index for Class; L: index for time slot; I: index for professor.
Solution-4.PNG
Solution-4.PNG
ASKER
is this better:
S.PNG
S.PNG
>> Tl teaches 1 Ck at a time
Having some trouble understanding this. Review this and see if you need to rephrase.
What is your precise definition of the set, S? Depending upon your definition, can C3, for example, appear more than once in S?
[C1..Ck] - if you left out this list and the other list, [T1..TL], would anything be missed? "where Ck can be taught by Pi in TL" - would this be a fair replacement?
While I don't agree with all of your notation (see my previous posts), at least I understand what I think you are trying to say; so maybe it is fine for your course.
Having some trouble understanding this. Review this and see if you need to rephrase.
What is your precise definition of the set, S? Depending upon your definition, can C3, for example, appear more than once in S?
[C1..Ck] - if you left out this list and the other list, [T1..TL], would anything be missed? "where Ck can be taught by Pi in TL" - would this be a fair replacement?
While I don't agree with all of your notation (see my previous posts), at least I understand what I think you are trying to say; so maybe it is fine for your course.
ASKER
I've overhauled my response. Is this any better:
ASet.PNG
ASet.PNG
>> list: fixed number of professors, {P}
>> list: fixed number of classrooms, {D} // easier on the eyes to use {R} for the list of available rooms
>> list: fixed number of classes to be offered, {C}
>> list: fixed number of time slots for classes, {T}
From your OP, it seems that there are the four above lists. I think your "There is a finite number..." is saying this, but I'm not sure what the != 0 at the end means. Does it mean that each list is non-empty? IMO, I think your constraints do not need to restate the pre-conditions of the type and fixed-length of each list. But they
>> a list of possible time slots for classes
Is this just a list of time slots, or does each class get its own list of potential timeslots?
>> For 2 different P (professors) ...
I would break this up into two separate constraints. I am not sure what you mean by two different professors do not teach in a conflicting T (timeslot). Please help me understand using simple sentences, and then later formalize it.
On formalization, for your assignement, is it acceptable that your constraints be written in sentences as you have done in your last post, or are you required in the end to use notation such as, for example:
"For 2 different P (professors)" becomes "for Pi, Pj, where i != j"
For your definition of S, could you explain exactly what the set of elements in S represent. As mentioned before, this could be an issue to resolve. Do you need to define a set where each element of the set is one of the many scheduling solultions that satisfy the constraints? If so, do you think S is this set?
p.s. - fyi, my computer has hard disk problems so I'm borrowing another computer as it becomes available, so it may take awhile to get back to your responses. Sorry about that. BTW, if you could type in the answer, it will be easier for me to cutNpaste. For subscripts, you could write, for example, Pi or P_i.
>> list: fixed number of classrooms, {D} // easier on the eyes to use {R} for the list of available rooms
>> list: fixed number of classes to be offered, {C}
>> list: fixed number of time slots for classes, {T}
From your OP, it seems that there are the four above lists. I think your "There is a finite number..." is saying this, but I'm not sure what the != 0 at the end means. Does it mean that each list is non-empty? IMO, I think your constraints do not need to restate the pre-conditions of the type and fixed-length of each list. But they
>> a list of possible time slots for classes
Is this just a list of time slots, or does each class get its own list of potential timeslots?
>> For 2 different P (professors) ...
I would break this up into two separate constraints. I am not sure what you mean by two different professors do not teach in a conflicting T (timeslot). Please help me understand using simple sentences, and then later formalize it.
On formalization, for your assignement, is it acceptable that your constraints be written in sentences as you have done in your last post, or are you required in the end to use notation such as, for example:
"For 2 different P (professors)" becomes "for Pi, Pj, where i != j"
For your definition of S, could you explain exactly what the set of elements in S represent. As mentioned before, this could be an issue to resolve. Do you need to define a set where each element of the set is one of the many scheduling solultions that satisfy the constraints? If so, do you think S is this set?
p.s. - fyi, my computer has hard disk problems so I'm borrowing another computer as it becomes available, so it may take awhile to get back to your responses. Sorry about that. BTW, if you could type in the answer, it will be easier for me to cutNpaste. For subscripts, you could write, for example, Pi or P_i.
Hit submit to soon..
>> IMO, I think your constraints do not need to restate the pre-conditions of the type and fixed-length of each list. But the definitions and pre-conditions should be stated before you write out your constraints.
>> IMO, I think your constraints do not need to restate the pre-conditions of the type and fixed-length of each list. But the definitions and pre-conditions should be stated before you write out your constraints.
ASKER
On English vs. mathematic notation, I think I should use as much notation as is practical.
ASKER
Could you help me with the notation? Another thing; I think it would be good to use two time slot variables:
something like - P_A and P_B are in conflicting time slots if the time from T1_A to T2_A and T1_B to T2_B overlap.
something like - P_A and P_B are in conflicting time slots if the time from T1_A to T2_A and T1_B to T2_B overlap.
On notation, let the set U be the universe of all 4-tuples of {P, C, T, R}, where P, C, T, R are lists of professors, etc. A point in this Universe is (Pi, Cj, Tk, Rm), where i in {1..|P|}, j in {2...}, etc. Then, |U| = i*j*k*m. Obviously, most of these points do not satisfy your constraints.
From this I can think of two sets of interest (but not necessarily both needed). One is the set of all possible scheduling solutions. If you need this, then what would a single point in this set be? Keep in mind that a single point in U is just that a specific prof teaches a specific class in a specific room in a specific timeslot.
Another set is to define a set of points in U such that they satisfy the constraints.
Is it a fair assumption to say that all the courses are of equal length? (If so, this simplifies the problem).
In my previous few posts, I asked some questions; but I didn't get a response for some of them. Could you take the time to copy the question and give me your response. Sometimes a question is guidance; sometimes it is that I don't understand something you wrote. So, it would be useful if I were on the same page as you. Right now, I don't know where you agree or take issue with some of my posts.
From this I can think of two sets of interest (but not necessarily both needed). One is the set of all possible scheduling solutions. If you need this, then what would a single point in this set be? Keep in mind that a single point in U is just that a specific prof teaches a specific class in a specific room in a specific timeslot.
Another set is to define a set of points in U such that they satisfy the constraints.
Is it a fair assumption to say that all the courses are of equal length? (If so, this simplifies the problem).
In my previous few posts, I asked some questions; but I didn't get a response for some of them. Could you take the time to copy the question and give me your response. Sometimes a question is guidance; sometimes it is that I don't understand something you wrote. So, it would be useful if I were on the same page as you. Right now, I don't know where you agree or take issue with some of my posts.
ASKER
On constraint satisfaction, I found the following:
http://4c.ucc.ie/web/outre
According to my text,
"A constraint satisfaction problem consists of three components, X, D, and C:
X is a set of variables, {X_1, ..., X_n}
D is a set of domains, {D_1, ..., D_n}, one for each variable.
C is a set of constraints that specify allowable combinations of values"
I'll be attending to your questions as soon as possible.
http://4c.ucc.ie/web/outre
According to my text,
"A constraint satisfaction problem consists of three components, X, D, and C:
X is a set of variables, {X_1, ..., X_n}
D is a set of domains, {D_1, ..., D_n}, one for each variable.
C is a set of constraints that specify allowable combinations of values"
I'll be attending to your questions as soon as possible.
ASKER
I put in the above comment because I thought it might help things along.
I'm confused as to why S_i should be part of my constraints.
"I know it is obvious that a professor cannot teach two different classes in the same time slot; but do you need to state this in your set of constraints?"
Unless I'm saying they juggle 2 or more classes at once, I think yes.
"You also need to define what S is. Is S 'all possible solutions'? If not, do you need to define 'all possible solutions'?"
Do you think stating "where S = all possible solutions" would work?
"Does it mean that each list is non-empty?"
Yes.
"Is this just a list of time slots, or does each class get its own list of potential timeslots?"
This variable was constrained or was supposed to be constrained by the professors.
"Is it a fair assumption to say that all the courses are of equal length?"
No.
What do you mean by "|U| = i*j*k*m"?
"Depending upon your definition, can C3, for example, appear more than once in S?"
There might be more than one professor teaching math.
I'm confused as to why S_i should be part of my constraints.
"I know it is obvious that a professor cannot teach two different classes in the same time slot; but do you need to state this in your set of constraints?"
Unless I'm saying they juggle 2 or more classes at once, I think yes.
"You also need to define what S is. Is S 'all possible solutions'? If not, do you need to define 'all possible solutions'?"
Do you think stating "where S = all possible solutions" would work?
"Does it mean that each list is non-empty?"
Yes.
"Is this just a list of time slots, or does each class get its own list of potential timeslots?"
This variable was constrained or was supposed to be constrained by the professors.
"Is it a fair assumption to say that all the courses are of equal length?"
No.
What do you mean by "|U| = i*j*k*m"?
"Depending upon your definition, can C3, for example, appear more than once in S?"
There might be more than one professor teaching math.
Then let X = set of variables, {X_1, ..., X_n} == {P, C, T, R}
D_1 = {P1, ... P_np}, where np = # professors
D_2 = {C1, ... C_nc}, where nc = # classes
etc.
The first constraint is explicitly in your OP:
>> Each professor has a set of classes that he or she can teach.
One way to represent this is a matrix, PC, having np rows, nc columns, with cells (PC_ij)being true/false. Another way is to define a class list for each Pi. Your choice. In practice, if the matrix is sparse, then the ragged array approach is used.
The others are known from intuition and experience.
For example, (1) two P will not teach the same C in the same R in the same T. However, this constraint is overly complicated (requiring all four variables). A shorter constraint could be that two P will not teach in the same R in the same T. This latter constraint has only 3 variables; yet it covers (1) as well as other constraints.
D_1 = {P1, ... P_np}, where np = # professors
D_2 = {C1, ... C_nc}, where nc = # classes
etc.
The first constraint is explicitly in your OP:
>> Each professor has a set of classes that he or she can teach.
One way to represent this is a matrix, PC, having np rows, nc columns, with cells (PC_ij)being true/false. Another way is to define a class list for each Pi. Your choice. In practice, if the matrix is sparse, then the ragged array approach is used.
The others are known from intuition and experience.
For example, (1) two P will not teach the same C in the same R in the same T. However, this constraint is overly complicated (requiring all four variables). A shorter constraint could be that two P will not teach in the same R in the same T. This latter constraint has only 3 variables; yet it covers (1) as well as other constraints.
ASKER
I think this problem doesn't mean for us to consider how long courses run, actually.
I'll be back tomorrow, but will try to respond in a few hours if I have a moment. For now, I'd like you to think more about:
>> Do you think stating "where S = all possible solutions" would work?
>> Yes
Looking at the definition of S as a set of point in U subject to constraints, I think the answer may be No.
>> What do you mean by "|U| = i*j*k*m"?
Sorry, with latest notation, |U| = np * nc * nr * nt = # elements in U
>> Do you think stating "where S = all possible solutions" would work?
>> Yes
Looking at the definition of S as a set of point in U subject to constraints, I think the answer may be No.
>> What do you mean by "|U| = i*j*k*m"?
Sorry, with latest notation, |U| = np * nc * nr * nt = # elements in U
>> can C3, for example, appear more than once
>> There might be more than one professor teaching math.
Well, if math-101 is going to be taught twice, then we could define the classes to be unique with a UID for the class; or just names like math-101-class1, math-101-class2 so that every class is distinct. Then we could say that only a class C3 appears only once. Just sound-boarding this if you think this makes the constraints easier to manage. This is your call.
>> There might be more than one professor teaching math.
Well, if math-101 is going to be taught twice, then we could define the classes to be unique with a UID for the class; or just names like math-101-class1, math-101-class2 so that every class is distinct. Then we could say that only a class C3 appears only once. Just sound-boarding this if you think this makes the constraints easier to manage. This is your call.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
>> my computer has hard disk problems
I may be busy on 14-Nov rebuilding my system (and converting RAID 0 to non-RAID). If I cannot give you the assistance you need to finish, it wouldn't be a bad idea to conclude this question after identifying clear definitions of sets and notations, and then ask a related question posting the conclusions here along with the OP in order to continue with the constraints formulation.
I may be busy on 14-Nov rebuilding my system (and converting RAID 0 to non-RAID). If I cannot give you the assistance you need to finish, it wouldn't be a bad idea to conclude this question after identifying clear definitions of sets and notations, and then ask a related question posting the conclusions here along with the OP in order to continue with the constraints formulation.
ASKER
Thank you for your help.
P = number of professors
P_i = the i_th professor, where i=1..P
C = number of classes to be offered
C_j = the j_th class, where j=1..C
S_i = { C_k | k in [1..C], where C_k can be taught by P_i }
============
Unknown:
T_i = The time slot for the i_th class
============
Constraint:
Mutual Exclusion ... to be filled in ...