Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Job-shop scheduling
open-in-new
<p>Job-shop scheduling, the job-shop problem (JSP) or job-shop scheduling problem (JSSP) is an <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a> in <a href="/facts/Computer_science/lN3pEyPz">computer science</a> and <a href="/facts/Operations_Research/H5yJkV5n">operations research</a>. It is a variant of <a href="/facts/Optimal_job_scheduling/XyUejB6y">optimal job scheduling</a>. In a general job scheduling problem, we are given <i>n</i> jobs <i>J</i>1, <i>J</i>2, ..., <i>Jn</i> of varying processing times, which need to be scheduled on <i>m</i> machines with varying processing power, while trying to minimize the <a href="/facts/Makespan/w1HEjJaQ">makespan</a> – the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as <i>job-shop scheduling</i>, each job consists of a set of <i>operations</i> <i>O</i>1, <i>O</i>2, ..., <i>On</i> which need to be processed in a specific order (known as <i>precedence constraints</i>). Each operation has a <i>specific machine</i> 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 <i>set</i> (the machines in each set are identical). </p><p>The name originally came from the scheduling of jobs in a <a href="/facts/Job_shop/aduc4C5n">job shop</a>, but the theme has wide applications beyond that type of instance. It is a well-known <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial optimization</a> problem and was the first to undergo <a href="/facts/Competitive_analysis_(online_algorithm)/ocEpTvXG">competitive analysis</a>, introduced by Graham in 1966. The best problem instances for a basic model with a makespan objective are due to Taillard. </p><p>In the standard <a href="/facts/Optimal_job_scheduling/XyUejB6y">three-field notation for optimal job scheduling problems</a>, the job-shop variant is denoted by <i>J</i> 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. </p>