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