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.
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Tuesday, August 05, 2008
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.
She _was_ optimizing some objective function -- namely, peace and quiet in the office. Luckily for her, in this case, this optimization was in P! :-)
ReplyDeleteOh well, I'd say this is even an O(1) algorithm ;)
ReplyDeleteActually this can be formulated as a heuristic - the "yelling" is a function of job priority and previous waiting time (most probably their multiplication), and then you have a version of the greedy online algorithm.
ReplyDelete