April 1998
Issues in Education:
Not Your Ordinary Scheduling Problem
By Vijay Mehrotra
I recently participated as a judge in an undergraduate mathematical modeling competition - officially titled the Mathematical Competition in Modeling (MCM). MCM is a fairly big deal. This year's competition featured teams from more than 300 institutions worldwide. Over the course of two grueling days, a dozen of us each read approximately 25 student papers that presented solutions to a scheduling problem.
Note: this was no ordinary scheduling problem. Instead, it was a decidedly non-trivial combinatorial optimization problem with several different dimensions: seven different time slots, with multiple concurrent meetings per time slot, three different classes of people and a whole lot of restrictions on how these people were to be scheduled. Moreover, the students were also asked for a solution method that (a) could be run by an individual with no technical knowledge; (b) could be re-run in less than one hour if inputs were changed slightly; and (c) was general enough to tackle a somewhat similar problem with different parameters or more general constraints.
There is a huge amount to learn from this contest.
The ground rules
Students organize themselves into teams of three to four people. Once the contest starts, each team must work independently for four days on the assigned problem, using whatever they can figure out on their own. When the deadline approaches, they can submit whatever they think the judges will think is relevant to the solution of their problem.
This process puts tomorrow's unknown challenges in competition with today's tasks. Though unclear what you should spend your time on beforehand, in retrospect it becomes obvious what you should have done. Once the game begins, you must organize your teams to make the most out of your respective strengths, and you must figure out how to get along with one another while subjected to significant stress. It can be tempting to figure the problem out by yourself; however, that is usually neither feasible or optimal for most problems.
The problem
The specific problem that was used in the MCM is a great one, for a couple of reasons. First, rather than give the contestants a clear definition of what is an optimal schedule, the problem statement simply suggests some desirable characteristics of a good solution. Thus, a significant part of what the contestants were judged on was how well they had defined their objective function and justified their assumptions. This is very appealing to me because it challenges the students to think about the problem holistically - "what are we trying to accomplish, anyway?" - with different assumptions having significant implications for how the problem should be structured and solved.
No matter what the assumptions, there are an infinite number of ways to tackle the problem. Therefore, contestants are not only cast as problem solvers, but as solution synthesizers. Lots of blood, sweat and tears are shed: suppose you fashion a method that is elegant but intractable? Effective but not extendible? Fast but not guaranteed to produce optimality? And how do you know how good your method actually is?
The solutions
We saw all sorts. We saw solutions featuring graph theory, simulated annealing, integer programming and Latin squares. One group provided a sociological theory of "elemental desire" to motivate their model, while another paper exhorted us to think in terms of electrons scheduled around various nuclei. There were greedy algorithms, hill-climbing methods, explicit enumerations and elemental rotations. Some very polished papers, some decidedly ragged ones. Some included too much detail for us to figure out what they were doing, while others left us mystified with their omissions.
Final verdict: the four papers that we judged to be "outstanding" featured different solution techniques, different writing styles, different assumptions and different results. The only constant: each of these winners developed a strong solution methodology, with clear justification for its validity, to a difficult and imprecise problem.
Conclusions
Contests can intimidate us, especially when we don't quite know what we're doing, we've got very little time to do it and we've no choice but to work with other people to get it done. Contests can bring out the best in us, especially when we are trying desperately to do our best, for we can discover a deeper-than-imagined capacity for hypothesizing, learning, assessing, analyzing and cooperating. The MCM is just an extreme case of what OR/MS people struggle with in projects and careers.
In business and in life, we don't have all the information about problems; we don't always know who the judges are; we aren't sure what the best approach is; and we are perpetually constrained by time. Our choices are clear: refuse to participate (or go through the motions half-heartedly) due to all of the uncertainties, or dive in, think hard, work with our teammates, struggle and fall down a few times, take our best shot, clean up our mess, and explain clearly what we did and why we did it.
If we can bring ourselves to do that much with our own challenges, then it doesn't matter how the judges grade us. We've already won.
|
|
OR/MS Today copyright © 1998 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Street, Suite 220, Marietta, GA 30060, USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 1998 by Lionheart Publishing, Inc. All rights reserved.