ICS 52, Fall, 2007
Official Requirements Specification -- Oct. 31, 2007
Later clarifications and modifications in blue
1 Introduction
This document specifies the Official Requirements for the
Schocr system, and should serve as the basis for a further
development of the system.
The Schocr system is designed to assist
high schools, colleges, and universities in the task of "time tabling,"
or assigning classes to classrooms and times.
It is designed to create a schedule that takes into account a wide
variety of factors and possibly competing goals.
All information was accurate at the time of writing.
This document details 62 discrete, atomic requirements.
Each is labeled with an identifier in boldface type (e.g. A-1)
for easy reference elsewhere in this document and in subsequent system
development.
In places where the user interface is incompletely specified, the
powers that be are relying on the implementers to devise a user
interface that is both pleasing to use and in accordance with all
listed requirements.
This document contains the following Sections:
2) User Requirements Definition - This section is designed for the
non-technical reader. It describes the major features of the system
and the rational for each one.
3) System Requirements Specification - This section identifies the objects that
make up the system and inter-relationships between them. It has been
written so as to provide enough detail for the technical design to be
produced.
4) Constraints and Non-functional Requirements - This sections
contains the current constraints on the system.
5) Implementation Phases
6) Future Directions and Expected Changes - Although speculative, this
section is a key way of influencing the product currently being
developed so that it can better respond to situations in the future.
7) Acceptance Test Plan
2 User Requirements Definition
A typical large high school, college, or university has
hundreds of courses to schedule into classrooms each
quarter or semester.
The task of doing so can be time consuming and subject to error
if done by hand.
In addition, there are many possibly competing constraints
on a schedule which are difficult for a human to keep in mind
simultaneously, but which are automatically considered by
Schocr.
The primary goal of the Schocr system is to create a schedule
of courses, classrooms (including labs and lecture halls), and
times that satisfies the largest possible number of constraints.
Schocr is designed to operate independently
of other computer information systems at the school.
It operates on the assumption that courses are scheduled into
rooms at particular times of the week, and that this scheduling
is completed before the start of the term.
The key features of the Schocr system are:
- The school administration enters, for an upcoming term,
the courses, classrooms, and available times, along with
additional information such as the teacher(s) assigned to each course.
- A course is characterized primarily by its one or two teachers
and the maximum number of students.
- Each classroom, lab, and lecture hall has a fixed
capacity, as well as other characteristics.
- Teachers can specify, for each course, their time and room preferences.
- Students can specify, for the upcoming term, courses they would
like to take. Schocr will try not to schedule to meet at the same time
courses that many students want to take in the same term.
- Schocr creates a schedule that is based on all the data
that has been entered.
- Schocr can produce a number of statistical and informative reports.
The Schocr system has a standard, easy-to-use graphical user
interface. It stores data on a computer disk, and can convert some data
from a previous database format.
3 System Requirements Specification
3.1 Overall Operation
The Schocr system supports the following typical cycle of events
for each school term.
- Data about courses to be offered, available classrooms,
and available time slots and time periods
are entered in Schocr.
Often most of this information can be carried forward from
the previous term. (Done approximately
10 weeks before the start of the term.)
- Teachers enter time and room preferences. (9 weeks before term start.)
- Students enter courses they plan to take the following term.
(7 weeks before term start.)
- Schocr's Schedule function is run, which creates a tentative
schedule (6 weeks before term start.)
- Further modifications can be made to Schocr's database.
(5 weeks before term start.)
- Schocr's Schedule function creates the final schedule.
(5 weeks before term start.)
- During the term, Schocr can be used to schedule room and
time changes for regular courses, and to schedule special
one time events.
The Schocr system is used by only one user at a
time. It does not handle or have any representation of multiple
terms.
3.2 Courses
Information about courses can be entered into Schocr and
later modified.
Course information is one of the primary sources for creating a schedule.
Schocr stores the following information about each course:
- Number. E.g. "ICS 52" or "English 140BW".
Each course has a unique number. (C-1)
Use of the colloquial term "number" does not
imply that this information is strictly numeric.
- Title, a maximum of 16 characters. E.g. "Sftwr Engneering". (C-2)
- Teacher (refers to lecturer, discussion leader, or lab attendant).
E.g. "Frost, D." or "Pazzani, M.". (C-3)
- Second Teacher. If the course is taught by two teachers, the
name of the second one is also stored. (C-4)
- Course type, one of "Lecture", "Discussion", or "Lab". (C-5)
- Discussion / Lab letter. Each Discussion or Lab is identified
by its lecture course number followed by a single lower case
letter. E.g. "Math 140a".
For each course, no discussion/lab letter is used more than once.
(C-6)
- Number of hours per week that this lecture, discussion, or
lab meets. This is always a whole number
between one and twelve. (C-7)
- Maximum allowed enrollment. This is always a positive whole number.
(C-8)
- Special room requirements. This information is a list of
between zero and five short
text phrases describing characteristics of the room the course
should be scheduled in.
The complete and specific list of possible
text phrases is: "lecture hall," "white board,"
"pc lab," "tech enhanced," "chem lab," "pc projector,"
"high ceilings". (C-9)
3.3 Rooms
Information about rooms can be entered into Schocr and
is one of the primary sources for creating a schedule.
Schocr stores the following information about each room
(R-0):
- Building code. E.g. "ICS", "Bio Sci 2", "Admin". (R-1)
- Room number. E.g. "100", "A". (R-2)
A room is usually identified
by its building code and room number, separated by a dash,
e.g. "ICS-100", "Admin-A".
Each room has a unique combination of
building code and room number. (R-3)
- Room capacity. This is a positive whole number. (R-4)
- Room facilities. This is a list of between zero and
ten short text phrases
(from the list in (C-9))
that will be matched to the phrases used as a course's special
room requirements. (R-5)
3.4 Time Periods and Time Slots
Each class is scheduled to meet during one or more time periods.
A time period has three components:
- Day of the week. (T-1)
- Starting time. Can be any time of the day. (T-2)
- Duration. A positive whole number of minutes. (T-3)
Time periods can be aggregated into time slots by administrators. (T-4)
A time slot is a collection of one or more time periods
with different days of the week, but the same starting times and
durations. For instance, the time periods Tuesday 12:30 p.m. for
90 minutes and Thursday 12:30 p.m. for 90 minutes can be
grouped together to form the time slot Tuesday-Thursday 12:30 p.m.
for 90 minutes.
One time period can be part of zero, one, or several time slots (T-5).
A time slot is assigned by the administration a
desirability level of A (most desirable),
B (medium), or C (least desirable) to indicate the general
priority with which it should be used (T-6) (see SR-2).
Typically, meeting times in the late morning and early afternoon are
most desirable, and courses that meet at early hours such
as 8:00 a.m. are least desirable.
(T-7) Time periods and time slots
are usually displayed in a format indicating the
day or days (abbreviated M for Monday, T for Tuesday, W for
Wednesday, Th for Thursday, F for Friday, Sa for Saturday,
Su for Sunday) with multiple day abbreviations adjacent to each
other; followed by a space; followed by the starting time in
12 hour format and without "am" or "pm"; followed by a dash;
followed by the ending time.
Examples: "M 12:00-2:00", "MWF 8:30-9:30", "TThSa 5:00-6:00",
"MTWThF 9:45-12:15".
Note that although "am" or "pm" does not appear in the
display of a time period or time slot, the
Schocr system does distinguish between a.m. and p.m. times.
3.5 Teachers
Every course is taught by one or two teachers, who may be
faculty, students, researchers, or other personnel.
Each teacher has a unique name (P-1).
For each course that a teacher teaches, he or she can enter
a first, second, and third choice of time slots or time
periods (P-2). Teachers cannot enter time preferences for courses
in which they are the second teacher (P-3).
A teachers can also enter a first, second, and third choice of
room for each course where he or she is the first teacher (P-4).
3.6 Students
Students are inconvenienced when two courses they desire to
take in the same term are scheduled at the same time.
Therefore, students can inform Schocr of a list of courses
they wish to take in the following term (S-1), and that list will be
factored in to the creation of a schedule (see (SR-5)).
Each student can enter at most one list
(this will not be enforced until security is implemented)
which can reference at most five courses.
3.7 Schedules and Evaluating Schedules
A schedule assigns to each course a room and either a time slot
or a time period (SCH-1).
A schedule generated by Schocr follows the "hard" and
"soft" rules listed below. The hard rules cannot be violated. The
soft rules are enforced by assigning to each violated soft rule
a certain number of "penalty points".
The penalty points for all violated soft rules are summed to create
the schedule's penalty rating. The best schedule is the
one with the lowest penalty rating (SCH-2).
Finding the best schedule is potentially a time-consuming task.
Therefore, Schocr has two processes for creating a schedule.
One, called "optimum", uses sophisticated artificial intelligence
techniques to find the best (lowest penalty) possible schedule
(SCH-3).
The other process, called "speedy", uses a much less time-consuming
approach and finds a good (satisfies hard constraints)
but not necessarily optimal schedule (SCH-4).
Sometimes a valid schedule that meets all the hard rules will not
be possible to create.
In this case, Schocr will display an error message identifying
the course that could not be scheduled (SCH-5).
Schocr will then continue with the process of scheduling other
courses.
Hard Rules
- A course can only be scheduled in a room with a capacity greater
than or equal to the course's maximum allowed enrollment. (HR-1)
- Each course must be scheduled to meet in a single room. (HR-2)
- Two courses taught by the same teacher cannot be scheduled
to meet at the same time or at overlapping times. (HR-3)
- A course can only be scheduled to meet at a time represented
by one of Schocr's time slots or time periods. (HR-4)
- Each course must be scheduled in time periods that
add up to the appropriate number of hours per week. (HR-5)
- Two courses cannot be scheduled to meet in the same room at
the same time or for overlapping times. (HR-6)
- A discussion or lab cannot be scheduled at any time that overlaps
the times when the
corresponding lecture is scheduled. (HR-7)
Soft Rules
The following rules may be violated in a schedule, at the cost
of the specified number of penalty points.
- The difference between a course's maximum allowed enrollment
and the capacity of the room in which it is scheduled
should be as small as possible.
(Penalty: difference times 10 points.) (SR-1)
- A course should be scheduled in a preferred time slot, and
in a time slot rather than a time period.
(Penalties: type A time slot, no penalty; type B time slot,
50 points; type C time slot, 100 points; in a time period, 200 points.) (SR-2)
- If the first teacher has entered course time
preferences,
a course should be scheduled in one of its teacher's preferred
time periods or time slots.
(Penalty: first choice: no penalty; second choice: 100 points;
third choice: 200 points; not a preferred time: 700 points.) (SR-3)
- A course should be scheduled in one of its teacher's preferred
rooms.
(Penalty: first choice: no penalty; second choice: 20 points;
third choice: 40 points; not a preferred room: 60 points.) (SR-4)
- Two courses which both appear on a student's list should
not be scheduled at overlapping times.
(Penalty: 2 points for each student list that contains two
or more courses that overlap.) (SR-5)
- A room should have all the special requirements that the
course needs.
(Penalty: 500 points for each course requirement not matched by
the room.) (SR-6)
3.8 User Interface
A graphical user interface (GUI) allows access to and control of
all of Schocr's functions.
The GUI will be based on one or more standard operating system windows
and dialog boxes, utilizing menus, buttons, hot keys, and other
standard user interface elements (UI-1).
It should be organized in an intuitive and easy to use manner.
Where appropriate, the user (administrator, teacher, or student)
has the option to save the current information, including
term, room, time slot, time period, teacher and course information,
teacher and student preferences, and a
schedule, to a disk file, and later to read the information back in
to Schocr from the disk file (UI-2).
The GUI will have the following elements:
- A teacher section that allows teachers to enter and modify their
preferred times and rooms. (UI-3)
- A student section that allows students to enter
their coming term course lists. (UI-4)
- A administration section which allows administrative personnel to
- Enter, modify, and delete course information. (UI-5)
- Enter and modify time slot and time period information
including time slot desirability level. (UI-6)
- Enter, modify and delete room information. (UI-7)
- Initiate the conversion of old data into the Schocr system
(see section 3.9). (UI-8)
- Initiate the generation of a schedule, using either the optimal
or speedy process. (UI-9)
- View the latest schedule produced, in order
by course number. The schedule's
total penalty should display. (UI-10)
- View a report that shows statistics summarizing the number
of courses, teachers, and rooms. (UI-11)
- View reports that list courses, teachers, and rooms. (UI-12)
- Query the latest schedule to find a room and time
for a special event with a specified maximum capacity. (UI-13)
Security
Initially, Schocr will have no security.
However, the functions that apply to students, teachers,
and administrators should be segregated in the user interface. (UI-14)
3.9 Conversion of existing data
Information about courses, rooms, and times currently exists in
a DF-2007 database.
The exact format of this database has not been determined at the
time of writing, but should be available shortly.
Schocr's lists of courses, rooms, and times for the first
term of operation
should be initialized
from this data, in so far as possible (CN-1).
4 Constraints and Non-functional Requirements
-
The software should be written in Java 1.6.
-
The time to generate a schedule with 500 classes, 100 rooms,
and 40 time periods, using a Pentium 4 computer, should be
under 30 seconds with the speedy process, and under 12 hours
with the optimum process
5 Implementation Phases
An operational system is desired before Finals Week, Fall, 2007.
For the first phase, which should be achieved in this time frame,
the following functional requirements may be omitted, if
required to meet the deadline:
(UI-4), (UI-11), (UI-12), (SR-5),
and implementation of the optimum
scheduling process (SCH-3).
6 Future Directions and Expected Changes
- Penalty amounts will be modified and controlled by the administration
through the user interface.
-
Teachers, students, and administrative personnel will use their
employee IDs or student IDs, as appropriate, as a password before
being able to access the Schocr system, and will only be able
to access appropriate functionality within Schocr.
7 Acceptance Test Plan
The complete acceptance test plan will demonstrate that the implemented system
completely fulfills the requirements stated in this document.
Here is one scenario, or test case, for testing the hard rules.
Before the test begins, the following information should have
been entered into Schocr:
- Time Periods:
60 minute time periods starting at 9:00 am, 10:00 am, and 11:00 am
for Monday, Tuesday, Wednesday, Thursday, and Friday (15 time periods
total).
- Time Slots: Three time slots:
MTWThF at 9:00 (desirability level C),
MTWThF at 10:00 (desirability level B),
MTWThF at 11:00 (desirability level A).
- Rooms:
CS-100 (capacity 50, no facilities),
CS-200 (capacity 100, no facilities).
- Courses:
- ICS 1: title "Intro to CS", type lecture, max 95, hours 5,
teacher Washington
- ICS 1a: title "Intro to CS disc", type discussion, max 25, hours 1,
teacher Adams
- ICS 1b: title "Intro to CS disc", type discussion, max 25, hours 1,
teacher Jefferson
- ICS 1c: title "Intro to CS disc", type discussion, max 25, hours 1,
teacher Madison
- ICS 1d: title "Intro to CS disc", type discussion, max 25, hours 1,
teacher Monroe
- ICS 1e: title "Intro to CS disc", type discussion, max 25, hours 1,
teacher Tyler
- ICS 2: title "Fun with CS", type lecture, max 45, hours 5,
teacher Lincoln
- ICS 3: title "Thrills with CS", type lecture, max 45, hours 5,
teacher Washington
- ICS 4: title "Fear of CS", type lecture, max 55, hours 5,
teacher Nixon
- ICS 5: title "Xtreme CS", type lecture, max 75, hours 5,
teacher Ford
No courses have special room requirements.
For the first step of the test, run the speedy scheduler.
It should be able to find a schedule. Note that the five
ICS 1 discussions must all be scheduled at the same time,
on different days, in room CS-100. One correct schedule is
| Time | Monday | Tuesday | Wednesday
| Thursday | Friday
|
| 9:00
| CS-100: ICS-3
CS-200: ICS-4
| CS-100: ICS-3
CS-200: ICS-4
| CS-100: ICS-3
CS-200: ICS-4
| CS-100: ICS-3
CS-200: ICS-4
| CS-100: ICS-3
CS-200: ICS-4
|
| 10:00
| CS-100: ICS-1a
CS-200: ICS-5
| CS-100: ICS-1b
CS-200: ICS-5
| CS-100: ICS-1c
CS-200: ICS-5
| CS-100: ICS-1d
CS-200: ICS-5
| CS-100: ICS-1e
CS-200: ICS-5
|
| 11:00
| CS-100: ICS-2
CS-200: ICS-1
| CS-100: ICS-2
CS-200: ICS-1
| CS-100: ICS-2
CS-200: ICS-1
| CS-100: ICS-2
CS-200: ICS-1
| CS-100: ICS-2
CS-200: ICS-1
|
Also check that Washington's two courses are not scheduled
at the same time.
For the second step, add one more discussion to ICS 1:
ICS 1f: title "Intro to CS disc", type discussion, max 25, hours 1,
teacher Burr
Use the speedy scheduler again.
This should result in one course not being scheduled.