Solved

Precise Formulation

Posted on 2010-11-10
30
675 Views
Last Modified: 2012-05-10
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.
0
Comment
Question by:JCW2
  • 16
  • 14
30 Comments
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
Givens:

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 ...
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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.
0
 

Author Comment

by:JCW2
Comment Utility
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}
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
Sorry, not familiar with your formal notation.
0
 

Author Comment

by:JCW2
Comment Utility
I was about to correct this, and had to perform some task.


Subs.PNG
0
 

Author Comment

by:JCW2
Comment Utility
"This," referring to the post with the cryptic notation.
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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).
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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.
0
 

Author Comment

by:JCW2
Comment Utility
Is this better:
Correction-2.PNG
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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.
0
 

Author Comment

by:JCW2
Comment Utility
Improved:
Solution-3.PNG
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
>> "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.
0
 

Author Comment

by:JCW2
Comment Utility
C: Class; T: Time slot; P: Professor; K: index for Class; L: index for time slot; I: index for professor.
Solution-4.PNG
0
 

Author Comment

by:JCW2
Comment Utility
is this better:
S.PNG
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
>> 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.
0
Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

 

Author Comment

by:JCW2
Comment Utility
I've overhauled my response. Is this any better:
ASet.PNG
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
>> 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.
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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.
0
 

Author Comment

by:JCW2
Comment Utility
On English vs. mathematic notation, I think I should use as much notation as is practical.
0
 

Author Comment

by:JCW2
Comment Utility
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.
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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.
0
 

Author Comment

by:JCW2
Comment Utility
On constraint satisfaction, I found the following:

http://4c.ucc.ie/web/outreach/tutorial.html

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.
0
 

Author Comment

by:JCW2
Comment Utility
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.

0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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.
0
 

Author Comment

by:JCW2
Comment Utility
I think this problem doesn't mean for us to consider how long courses run, actually.
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
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
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
>> 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.
0
 
LVL 32

Accepted Solution

by:
phoffric earned 500 total points
Comment Utility
>> 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

From OP:
>> a list of possible time slots
D_3 = {T1, ... T_nt}, where nt = # timeslots
A timeslot needs to have an attribute of Start_Time. A second attribute could be either Stop_time or Duration. In either case, I am not understanding the need for two time slot variables, since from the values in D_3, one can compute whether two values overlap.

Also, should we assume that a class attribute to be included is number hours per week, and that all that is necessary is to assure that a class gets the proper number of hours in the set of timeslots allocated to the class?
0
 
LVL 32

Expert Comment

by:phoffric
Comment Utility
>> 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.
0
 

Author Closing Comment

by:JCW2
Comment Utility
Thank you for your help.
0

Featured Post

6 Surprising Benefits of Threat Intelligence

All sorts of threat intelligence is available on the web. Intelligence you can learn from, and use to anticipate and prepare for future attacks.

Join & Write a Comment

This is about my first experience with programming Arduino.
If you’re thinking to yourself “That description sounds a lot like two people doing the work that one could accomplish,” you’re not alone.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

743 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now