Decision Support Puzzles for Applied Mathematicians
April 2009 - Dance Scheduling
Dance-pair Student Teacher Skill
1 Daniel Mr. Brown 2
2 Camila Mr. Davis 4
3 Brianna Ms. Evans 2
4 Eve Ms. Clark 3
5 Ava Ms. Anderson 1
6 Camila Ms. Clark 5
7 Ava Mr. Davis 3
8 Eve Ms. Evans 1
9 Camila Ms. Anderson 4
10 Brianna Mr. Davis 3
A popular dance studio in New York City holds ballroom dancing showcases twice a year to provide its students with an environment for socializing, practice, and improvement. A showcase consists of several heats in which multiple dance-pairs dance at the same time. Because multiple objectives are desired to maximize the quality of the showcase, scheduling the dance-pairs becomes a complex problem that requires OR techniques to solve.
The objectives, when scheduling a showcase, are to minimize the number of heats (in order to minimize the overall duration of the showcase), group similarly skilled dance-pairs in the same heat, and minimize the number of heats that have only one dance-pair.
Table 1 shows the dance-pairs that must be scheduled for the showcase. For example, dance-pair 1 shows student Daniel will dance with teacher Mr. Brown. Their Skill level is an indicator of how well this dance-pair performs together. Each dance-pair must be assigned to one heat. You may schedule as many heats as you like in order to fulfill this requirement but you cannot schedule students or teachers twice to the same heat. For example, you cannot assign dance-pairs 6 and 9 to heat 1 because it would require Camila to dance with both Ms. Clark and Ms. Anderson at the same time.
The quality of the showcase is based on a points system. A dance-pair arrangement requiring 3 total heats is worth 110 points, 4 heats are worth 100 points, 5 heats are worth 90, 6 heats are worth 80, 7 heats are worth 70, etc. For every heat with a standard deviation over 1 there is a 25 point penalty. For every heat with only one dance-pair there is a 10 point penalty.
Question: What is the optimal way to assign the dance-pairs to heats in order to maximize the quality of the showcase?