Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] A Simple Heuristic

Expand Messages
  • Lance
    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
    Message 1 of 1 , Aug 5, 2008
    • 0 Attachment
      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
    Your message has been successfully submitted and would be delivered to recipients shortly.