USA

Westside 2009 (US-WS-09)

USA Westside 2009

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