Job shop scheduling is a problem in which jobs are assigned to workstations at particular times. The goal is to find a shortest spanning schedule such that each workstation can work on one job at a time. A real life example would be a machine shop with multiple operations (welding, lathing, drilling, cutting) where jobs require a different order of processing. Scheduling is incredibly important in the semiconductor industry since the machines used to build the products are very expensive and therefore, getting the most out of them is necessary for generating profits. Scheduling problems can be extended in many ways, for example to consider precedence constraints (i.e. welding must be completed before painting), machine-dependent task times (some machines/workers are faster than others) or stochastic (random) task durations.
A good solution to this problem ensures that resources are used efficiently:

  • workstation downtime reduces
  • customer receive their orders faster
  • total capacity increases
  • fewer worker-hours are needed to complete the same amount of work
Below is a demo where you can choose the number of jobs to be routed through a plant with 6 workstations. I set the maximum number of jobs to 20 as the problem of this size can still be solved to optimality within ~1 second. Note that there are a total of 10111 solutions so finding the best one in a second is a feat. Once solved, a schedule will be displayed, where each row is a workstation and each color is a job.