USA Westside 2009 (US-WS-09) was collected from an American high school in Omaha, Nebraska and converted to XHSTT by Luke Muggy and Todd Easton.
Westside implements a university-style system where students of all levels may enroll in a course as long as they have fulfilled prerequisites.
For this reason, the “Class” resource group is omitted.
The solution submitted by Martin Klemsa is optimal, following the analysis below, also provided by Martin:
- Timetable for Room_47 is completely filled, so to satisfy any of the remaining PreferResourceConstraint_Room_47 breaks in the solution would introduce infeasibility, leading to the inevitable cost of 59.
- Same holds for Room_65 and constraint PreferResourceConstraint_Room_65 (cost 38).
- Event ELLIntensive_0_1 must be split into two events of duration four to satisfy SplitEventsConstraint_2_4 and prevent infeasibility. These instances should be both placed on Day_0 to satisfy SpreadEventsConstraint_ELLIntensive_0_1 ("Spread") (weight 1). However, they should also not be placed on Day_0 to satisfy PreferTimesConstraint_Stday_1_endday_4_Stmod_10_endmod_14_duration_4 ("PreferredTimes") (weight 4). Missing two Day_0 allocations (thus breaking Spread) and satisfying PreferredTimes has a total cost of 4. Any other placement of ELLIntensive_0_1 has higher cost: Either breaking PreferredTimes once and still not satisfying Spread for a cost of 5, or breaking PreferredTimes twice for a cost of 8. Thus the minimum cost of placing ELLIntensive_0_1 is 4, as in the solution.
A summary of the data can be found in the following table:
|
Assets |
Times |
Teachers |
Rooms |
Students |
Classes |
# events |
Total duration |
|
value |
100 |
134 |
108 |
- |
- |
628 |
6354 |
The following constraints are present:
- Scheduling constraints: AssignResourceConstraint, AssignTimeConstraint, and SplitEventsConstraint.
- Event constraints: PreferResourcesConstraint, PreferTimesConstraint, and SpreadEventsConstraint.
- Resource constraints: AvoidClashesConstraint.
The following feasible solutions are submitted for this instance:
|
SolutionGroup |
Objective value |
Lowerbound |
Submitted by |
Received |
|
MuggyEaston_WHS_2009 |
1531 |
Luke Muggy and Todd Easton |
January 21, 2014 |
|
|
KHE14x8 |
697 |
Jeffrey H. Kingston |
August 22, 2014 |
|
|
GOAL team - Feb 12, 2015 |
111 |
UFOP-GOAL team: Fonseca G.H.G. Santos H.G. and Carrano E.G. |
February 23, 2015 |
|
|
GOAL team - Dec 8, 2016 |
103 |
UFOP-GOAL team: Fonseca G.H.G. Santos H.G. and Carrano E.G. |
April 17, 2017 |
|
|
Skolaris |
101 |
101 |
Martin Klemsa |
September 13, 2017 |
XML file
USAWestside2009.xml (instance and solutions)
previous versions:
[Update Ocober 15, 2014: the spread events constraints were improved.]
USAWestside2009.xml (XHSTT2013)
[Update to 2014: cost function simplified, PreferTimesConstraint added.]