Rob Kremer
	Exam Scheduling CPSC 433: Artifical Intelligence Fall 2014	Computer Science

• Problem Description
  • Hard Constraints
  • Soft Constraints
• Input/Output Formats
• Parser
• Sample Input

Problem Description

The assignment is based on the university's registrar's office's on-going problem of scheduling final exams.

Each course (eg: CPSC433) has one or more lectures (eg: CPSC433 L01), and each lecture has an exam, which is a specific length in hours. There are pre-allocated rooms and time slots (day, hour, and length in hours) that may be used for writing these exams. While several exams may take place in a single room at the same time, rooms have a limit on the number of students that may write at the same time. The task is to assign each and every exam to a room/time slot (called a session).

To help you with the problem, I have formally codified the rules in the above paragraph has hard constraints in the next section. But there are also a number of other consideration that the registrar's office would like to recognize. For example:

• No student should be scheduled to write more than one exam at the same time (since, obviously, they can't) and that means the student would have to defer one of the exams. Deferrals are a hassle, so we avoid them where possible.
• Despite appearances, the registrar's office doesn't want to stress out students, so no student should have to write more than 5 hours of exams on any one day.

These are codified in the section on soft constraints and, while they may be violated by your solution, each is associated with a specific penalty.

In the formalization that follows we use the the following types and predicates:

Hard Constraints

There are a few mandatory constraints that may not be violated. Any exam schedule that violates these is not considered a solution. These are:

//H1: every lecture is assigned an exam session (completeness)
FORALL c:COURSE, lec:LECTURE | LECTURE(c,lec) . EXISTS ses:SESSION . ASSIGN(c,lec,ses)

//H2: no lecture is assigned more than one exam session
FORALL c:COURSE, lec:LECTURE, ses1,ses2:SESSION | LECTURE(c,lec) .
  (ASSIGN(lec,ses1) /\ ASSIGN(lec,ses2)) => ses1=ses2

//H3: the number of students writing an exam in a particular exam session may not exceed the capacity of the room
FORALL ses:SESSION, r:ROOM | ROOMASSIGN(ses,r) .
  EXITS cap:int | CAPACITY(r,cap) .
    #{s:STUDENT | FORALL c:COURSE, lec: LECTURE | ASSIGN(c,lec,ses) . ENROLLED(s,c,lec)} <= cap

//H4: every lecture's required time must be less than the session length
FORALL ses:SESSION, c:COURSE, lec:LECTURE | ASSIGN(c,lec,ses) .
  EXISTS slen, llen:int | AT(ses,?,?,slen) /\ EXAMLENGTH(c,lec,llen) . llen <= slen

Soft Constraints

There are also several "soft" constraints that may be violated (and since some of these constraints actually conflict with each other, sometimes must be violated). These all have a penalty associated with them (reflecting their importance). Your job is to come up with a solution that maximizes the utility function that naturally arises from these soft constraints and their penalty weightings. I have, of course, written my own version of this utility function that (I believe) precisely conforms to the these constraints, and I will test your program's solutions against my utility function. You will have to write your own utility function to test your program.

// S1: penalty=100/incident. No student writes more than one exam in a timeslot (no direct conflict)
FORALL s:STUDENT, c1,c2:COURSE, lec1,lec2:LECTURE | (lec1 /= lect2 \/ c1 /= c2) /\ ENROLLED(s,c1,lec1) /\ ENROLLED(s,c2,lec2) .
  FORALL ses1,ses2:SESSION | ASSIGN(c1,lec1,ses1) /\ ASSIGN(c2,lect2,ses2) .
    EXISTS d1,d2:DAY, t1,t2,i:int | AT(ses1,d1,t1,?) /\ AT(ses2,d2,t2,?) /\ d1=d2 /\ t1<=t2 /\ EXAMLENGTH(lec1,i) .
      t1+i < t2

//S2: penalty=20/incident. No instructor invigulates in more than one room at the same time (no direct conflict)
FORALL s:INSTRUCTOR, c1,c2:COURSE, lec1,lec2:LECTURE | (lec1 /= lect2 \/ c1 /= c2) /\ INSTRUCTS(s,c1,lec1) /\ INSTRUCTS(s,c2,lec2) .
  FORALL ses1,ses2:SESSION | ASSIGN(c1,lec1,ses1) /\ ASSIGN(c2,lect2,ses2) .
    EXISTS d1,d2:DAY, t1,t2,i:int | AT(ses1,d1,t1,?) /\ AT(ses2,d2,t2,?) /\ d1=d2 /\ t1<=t2 /\ EXAMLENGTH(lec1,i) .
      (t1+i < t2) => ses1=ses2

//S3: penalty=50/incident. Every lecture for the same course should have the same exam timeslot
FORALL c:COURSE .
  EXISTS1 day:Day, time:int .
    FORALL lec:LECTURE, ses:SESSION | LECTURE(c,lec) /\ ASSIGN(c,lec,ses) .
      AT(ses,day,time,?)

//S4: penalty=50/incident. No student writes for longer than 5 hours in a single day
FORALL s:STUDENT .
  FORALL d:DAY .
    (SUM i:int | (FORALL c:COURSE, lec:LECTURE, ses:SESSION | ENROLLED(s,c,lec) /\ ASSIGN(c,lec,ses) .       dayAssign(ses,d)) . EXAMLENGTH(lec,i)) <= 5

//S5: penalty=50/incident. No student should write exams with no break between them
FORALL s:STUDENT, c1,c2:COURSE, lec1,lec2:LECTURE | (lec1 /= lect2 \/ c1 /= c2) /\ ENROLLED(s,c1,lec1) /\ ENROLLED(s,c2,lec2) .
  FORALL ses1,ses2:SESSION | ASSIGN(c1,lec1,ses1) /\ ASSIGN(c2,lect2,ses2) .
    EXISTS d1,d2:DAY, t1,t2,i:int | AT(ses1,d1,t1,?) /\ AT(ses2,d2,t2,?) /\ d1=d2 /\ t1<=t2 /\ EXAMLENGTH(lec1,i) .
      t1+i /= t2

//S6: penalty=20/session. All the exams taking place in a particular session should have the same length
FORALL ses:SESSIONS .
  EXISTS c1,c2: COURSE, lec1,lect1:LECTURE | ASSIGN(c1,lec1,ses) /\ ASSIGN(c2,lec2,ses) .
    EXISTS i:int . EXAMLENGTH(lec1, i) /\ EXAMLENGTH(lect2,i)

//S7: penalty=5/session. Every exam in a session should take up the full time of the session
FORALL ses:SESSIONS .
  EXISTS c: COURSE, lec:LECTURE | ASSIGN(c,lec,ses) .
    EXISTS i:int . EXAMLENGTH(lec, i) /\ AT(ses,?,?,i)

Input/Output Formats

The input and output file formats are the same, namely, a set of ASCII-format predicates, one per line. The BNF for this format is:

Parser

You will be pleased to learn that I have saved you the effort of writing a parser for the file format. See the JavaDoc documentation. You can download the following JAVA classes:

• ExamSchedule: Contains main() method and helper methods. Among other things, the main() method takes an input filename and a time limit. It's all you really need as your main() program.
• Predicate: The class the encapsulates a predicate as a ADT.
• PredicateReader: The class that does most of the work of parsing a file or a predicate string.
• Pair: Simple utility class representing a pair.
• Entity: Basically just a "named thing". The superclass for predicate reader.
• ExamSchedulePredicates: An interface that defines templates for all the predicates needed in the assignment. Your input reader should implement this interface in it's subclass of the PredicateReader class.

(or download them all in a jar file which includes the .class files, .java files, and manifest as well).

It is highly recommended that you use this parser for your assignment, as it will save you a lot of trouble, it works, and might avoid some possible problems with your assessment and demos. These classes make use of the JAVA reflect package, so that you need only define methods a_predicateName() (to assert a predicate as true) and/or e_predicateName() (to evaluate the truth value of a predicate). Your methods must also, of course, support the appropriate parameter list. You may define additional predicates if you wish, but the assessment will only require you to interpret the predicates listed here. Be warned that the only predicate type expected in your output file is the asssign(course-name, lab-name, session-name) predicate (and perhaps comments).

Sample Input/Output

You can use the following sample texts as a test suite for your program. You will be tested on other scenarios.

There is a long case (and a solution), and a trivial case:

When I run my program on the above program, I get the solution shown below. My utility function rates its utility at -100. Note that in this problem, the solution is constrained by there being an assign() predicate in the input data, which the solution has to respect, even though a better solution might be found if that exam were assigned differently. You might also observe that my program can be run in interactive mode (as well as the "batch" mode required by this assignment), and I'm using the PredicateReader class to parse my interactive input and execute appropriate methods -- a big help with debugging!

CPSC 433: Artificial Intelligence

Last updated 2014-09-02

Rob Kremer