The job shop scheduling problem: Conventional and new solution techniques

A job shop consists of a set of different machines (like lathes, milling machines, drills, etc.) that perform operations on jobs. Each job has a specified processing order through the machines, i.e. a job is composed of an ordered list of operations each of which is determined by the machine required and the processing time on it. There are several constraints on jobs and machines: (i) There are no precedence constraints among operations of different jobs; (ii) operations cannot be interrupted (non-preemption) and each machine can handle only one job at a time; (iii) each job can be performed only on one machine at a time. While the machine sequence of the jobs is fixed, the problem is to find the job sequences on the machines which minimize the makespan, i.e. the maximum of the completion times of all operations. It is well known that the problem is NP-hard and belongs to the most intractable problems considered. A huge amount of literature on machine scheduling, including scheduling of job shops, has been published within the last 30 years. A variety of scheduling rules for certain types of job shops have been considered in an enormous number of publications, also covering complexity issues and mathematical programming formulations. This survey is devoted to an overview of the solution techniques available for solving the job shop problem.