1 What is Job Shop Scheduling

We assume we have m machines M_{1}, ⋯, M_{m} and n jobs J_{1}, ⋯, J_{n} Each job J_{i} is made up of n_{j} operations O_{ij}(i = 1, ⋯ n_{j}) which have to be processed in the order O1j, O2j, ⋯ On_{j}. Operation O_{ij} has to be processed without preemption on a dedicated machine μ_{ij} ∈ M_{1}, ⋯ M_{m} for timu duration p_{ij}.

Each task must be processed on a single specified machine, and each job visits each machine exactly once. There is a predefined ordering of the tasks within a job. A machine can process only one task at a time. There are no set-up times, no release dates and no due dates. The makespan is the time from the beginning of the first task to start to the end of the last task to finish. The aim is to find start times for each task such that the makespan is minimised.

The operation O_{jr} requires the exclusive use of M_{r} for an uninterrupted period of time p_{jr}