[Computational Complexity] A Simple Heuristic
- When I started off as a professor, my wife worked at a company called Teradyne, which makes testing equipment, as a master scheduler. A master scheduler makes the master schedule of what jobs get run on which machines at what time. As you readers already know, almost every interesting variation of job scheduling is NP-complete. As I was teaching intro theory at the time, I thought about bringing her in to give a lecture on how people deal with NP-complete problems in the real world.
So I asked my wife what algorithms she uses to make up the schedule. She had a simple rule:
Whomever yells the loudest gets their job scheduled first.Needless to say I didn't bring her into class.
Posted By Lance to Computational Complexity at 8/05/2008 07:42:00 AM