JOB SCHEDULING PROBLEM

I have a number of jobs that each take a certain fixed amount of time (not necessarily the same amount of time as each other).  I also have a certain amount of "workers" (traditionally worded as "processors").  Jobs cannot be shared between workers.  Once a worker starts the job, it has to work on the same job until the job is done.  A worker can only work on one job at a time.

The job scheduling problem is given the number of workers and the time each job takes, split the tasks up between the workers, so that the workers working simultaneously will collectively complete all the jobs in the smallest possible amount of time.

This problem is NP-Hard.

CRUDE OVERSIMPLIFICATION:  There is no known way to solve the problem in polynomial time, but it can be done with trial and error, but very slowly, more like exponential time.  However, it's not been proven that polynomial time way doesn't exist.  Were a polynomial time way discovered that solves this problem, that would also solve a huge class of problems and demonstratively show that P=NP.

NP-Hard is different from NP-Complete since NP-Completeness only refers to YES/NO questions.  "Can we schedule the jobs so that all jobs can be completed in under eight hours?"  NP-Hard problem ("How do we schedule the jobs so that the total runtime is as small as possible?")

SIMULATED ANNEALING.

Imagine you have a function (possibly over multiple variables) which returns a specific numeric value.  You want to maximize value, but there could any number of peaks and valleys and ridges in this function.  You want to the find the absolute maximum, not just some local hilltop.

From any given node in our graph, we try a neighbor at random.  If that neighbor gives us a higher point in our function than we presently have, we move to that node.

If the neighbor is lower than we are, we use a random number generator to decide whether we take the lower value or stick where we are.  The probability that we will take value decreases (gradually) over time.

With job scheduling, the "neighbors" of a certain state are those states with a difference of one job.  One job moved from one processor to another.