Job-shop scheduling

Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. In a general job scheduling problem, we are given n jobs J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on m machines with varying processing power, while trying to minimize the makespan – the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as job-shop scheduling, each job consists of a set of operations O₁, O₂, ..., O_n which need to be processed in a specific order (known as precedence constraints). Each operation has a specific machine that it needs to be processed on and only one operation in a job can be processed at a given time. A common relaxation is the flexible job shop, where each operation can be processed on any machine of a given set (the machines in each set are identical).

The name originally came from the scheduling of jobs in a job shop, but the theme has wide applications beyond that type of instance. It is a well-known combinatorial optimization problem and was the first to undergo competitive analysis, introduced by Graham in 1966.^[1] The best problem instances for a basic model with a makespan objective are due to Taillard.^[2]

In the standard three-field notation for optimal job scheduling problems, the job-shop variant is denoted by J in the first field. For example, the problem denoted by "${\displaystyle J_{3}|p_{ij}|C_{\max }}$" is a 3-machines job-shop problem with unit processing times, where the goal is to minimize the maximum completion time.