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. It is a well-known combinatorial optimization problem and was the first to undergo competitive analysis, introduced by Graham in 1966. The best problem instances for a basic model with a 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 " J 3 | p i j | C max {\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.
Problem variations 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. It can also be multi-objective optimization problem. Certain jobs must be completed before others can start (see workflow), and objectives may involve multiple-criteria. Set of jobs can relate to different set of machines. Deterministic (fixed) processing times or probabilistic processing times.
NP-hardness Since the traveling salesman problem is NP-hard, the job-shop problem with sequence-dependent setup is also NP-hard since the TSP is a special case of the JSP with a single job (the salesman in TSP) and the machines (the cities in TSP).
Problem representation The disjunctive graph is one of the popular models used for describing the job-shop scheduling problem instances. A mathematical statement of the problem can be made as follows: Let M = { M 1 , M 2 , … , M m } {\displaystyle M=\{M_{1},M_{2},\dots ,M_{m}\}} and J = { J 1 , J 2 , … , J n } {\displaystyle J=\{J_{1},J_{2},\dots ,J_{n}\}} be two finite sets. On account of the industrial origins of the problem, the M i {\displaystyle \displaystyle M_{i}} are called machines and the J j {\displaystyle \displaystyle J_{j}} are called jobs. Let X {\displaystyle \displaystyle \ {\mathcal {X}}} denote the set of all sequential assignments of jobs to machines, such that every job is done by every machine exactly once; elements x ∈ X {\displaystyle x\in {\mathcal {X}}} may be written as n × m {\displaystyle n\times m} matrices, in which column i {\displaystyle \displaystyle i} lists the jobs that machine M i {\displaystyle \displaystyle M_{i}} will do, in order. For example, the matrix
x = ( 1 2 2 3 3 1 ) {\displaystyle x={\begin{pmatrix}1&2\\2&3\\3&1\end{pmatrix}}}
… excerpt ends here. Continue reading the full article.
