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 J1, J2, ..., Jn 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 O1, O2, ..., On 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. This problem is one of the best known combinatorial optimization problems, and was the first problem for which competitive analysis was presented, by Graham in 1966. Best problem instances for basic model with makespan objective are due to Taillard. 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 " J3||" is a 3-machines job-shop problem with unit processing times, where the goal is to minimize the maximum completion time. Many variations of the problem exist, including the following: Machines can have duplicates (flexible job shop with duplicate machines) or belong to groups of identical machines (flexible job shop). Machines can require a certain gap between jobs or no idle-time. Machines can have sequence-dependent setups. Objective function can be to minimize the makespan, the Lp norm, tardiness, maximum lateness etc.