Job-shop scheduling

<h2 id="problem-variations">Problem variations</h2>
Many variations of the problem exist, including the following:

<ul><li>Machines can have duplicates (flexible job shop with duplicate machines) or belong to groups of identical machines (flexible job shop).<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a></li>
<li>Machines can require a certain gap between jobs or no idle-time.</li>
<li>Machines can have sequence-dependent setups.</li>
<li><a href="/facts/Objective_function/xv5ozuhl">Objective function</a> can be to minimize the makespan, the <a href="/facts/Lp_space/gbad0Rv1">Lp</a> norm, tardiness, <a href="/facts/Latency_(engineering)/6Bjhn30H">maximum lateness</a> etc. It can also be multi-objective optimization problem.</li>
<li>Certain jobs must be completed before others can start (see <a href="/facts/Workflow/Ig8zvxF2">workflow</a>), and objectives may involve multiple-criteria.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li>Set of jobs can relate to different set of machines.</li>
<li>Deterministic (fixed) processing times or probabilistic processing times.</li></ul>
<h2 id="np-hardness">NP-hardness</h2>
Since the <a href="/facts/Traveling_salesman_problem/2WEKVLnV">traveling salesman problem</a> is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>, 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).<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h2 id="problem-representation">Problem representation</h2>
The <a href="/facts/Disjunctive_graph/uu5Lojpm">disjunctive graph</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> is one of the popular models used for describing the job-shop scheduling problem instances.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
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 <a href="/facts/Finite_set/za1newlP">finite</a> <a href="/facts/Set_(mathematics)/BfucfHMq">sets</a>. 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}}}

means that machine 
 
 
 
 
 
 M
 
 1
 
 
 
 
 
 {\displaystyle \displaystyle M_{1}}
 
 will do the three jobs 
 
 
 
 
 
 J
 
 1
 
 
 ,
 
 J
 
 2
 
 
 ,
 
 J
 
 3
 
 
 
 
 
 {\displaystyle \displaystyle J_{1},J_{2},J_{3}}
 
 in the order 
 
 
 
 
 
 J
 
 1
 
 
 ,
 
 J
 
 2
 
 
 ,
 
 J
 
 3
 
 
 
 
 
 {\displaystyle \displaystyle J_{1},J_{2},J_{3}}
 
, while machine 
 
 
 
 
 
 M
 
 2
 
 
 
 
 
 {\displaystyle \displaystyle M_{2}}
 
 will do the jobs in the order 
 
 
 
 
 
 J
 
 2
 
 
 ,
 
 J
 
 3
 
 
 ,
 
 J
 
 1
 
 
 
 
 
 {\displaystyle \displaystyle J_{2},J_{3},J_{1}}
 
.
Suppose also that there is some cost function 
 
 
 
 C
 :
 
 
 X
 
 
 →
 [
 0
 ,
 +
 ∞
 ]
 
 
 {\displaystyle C:{\mathcal {X}}\to [0,+\infty ]}
 
. The cost function may be interpreted as a "total processing time", and may have some expression in terms of times 
 
 
 
 
 C
 
 i
 j
 
 
 :
 M
 ×
 J
 →
 [
 0
 ,
 +
 ∞
 ]
 
 
 {\displaystyle C_{ij}:M\times J\to [0,+\infty ]}
 
, the cost/time for machine 
 
 
 
 
 
 M
 
 i
 
 
 
 
 
 {\displaystyle \displaystyle M_{i}}
 
 to do job 
 
 
 
 
 
 J
 
 j
 
 
 
 
 
 {\displaystyle \displaystyle J_{j}}
 
.
The job-shop problem is to find an assignment of jobs 
 
 
 
 x
 ∈
 
 
 X
 
 
 
 
 {\displaystyle x\in {\mathcal {X}}}
 
 such that 
 
 
 
 
 C
 (
 x
 )
 
 
 
 {\displaystyle \displaystyle C(x)}
 
 is a minimum, that is, there is no 
 
 
 
 y
 ∈
 
 
 X
 
 
 
 
 {\displaystyle y\in {\mathcal {X}}}
 
 such that 
 
 
 
 
 C
 (
 x
 )
 >
 C
 (
 y
 )
 
 
 
 {\displaystyle \displaystyle C(x)>C(y)}
 
.

<h2 id="scheduling-efficiency">Scheduling efficiency</h2>
Scheduling efficiency can be defined for a schedule through the ratio of total machine idle time to the total processing time as below:

 
 
 
 
 C
 ′
 
 =
 1
 +
 
 
 
 
 ∑
 
 i
 
 
 
 l
 
 i
 
 
 
 
 
 ∑
 
 j
 ,
 k
 
 
 
 p
 
 j
 k
 
 
 
 
 
 =
 
 
 
 C
 .
 m
 
 
 
 ∑
 
 j
 ,
 k
 
 
 
 p
 
 j
 k
 
 
 
 
 
 
 
 {\displaystyle C'=1+{\sum _{i}l_{i} \over \sum _{j,k}p_{jk}}={C.m \over \sum _{j,k}p_{jk}}}

Where 
 
 
 
 
 l
 
 i
 
 
 
 
 {\displaystyle l_{i}}
 
 represents the idle time of machine i, C is the makespan, and m is the number of machines. This formulation normalizes the makespan by the number of machines and total processing time, allowing for the comparison of resource utilization across job-shop scheduling (JSP) instances of varying sizes.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="the-problem-of-infinite-cost">The problem of infinite cost</h2>
One of the first problems that must be dealt with in the JSP is that many proposed solutions have infinite cost: i.e., there exists 
 
 
 
 
 x
 
 ∞
 
 
 ∈
 
 
 X
 
 
 
 
 {\displaystyle x_{\infty }\in {\mathcal {X}}}
 
 such that 
 
 
 
 C
 (
 
 x
 
 ∞
 
 
 )
 =
 +
 ∞
 
 
 {\displaystyle C(x_{\infty })=+\infty }
 
. In fact, it is quite simple to concoct examples of such 
 
 
 
 
 x
 
 ∞
 
 
 
 
 {\displaystyle x_{\infty }}
 
 by ensuring that two machines will <a href="/facts/Deadlock_(computer_science)/YDpdfnPP">deadlock</a>, so that each waits for the output of the other's next step.

<h2 id="major-results">Major results</h2>
Graham introduced the List scheduling algorithm in 1966, which is (2 − 1/m)-competitive, where m is the number of machines.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> It was later proven to be the optimal online algorithm for two and three machines. The <a href="/facts/Coffman%25E2%2580%2593Graham_algorithm/eKCds1Dk">Coffman–Graham algorithm</a> (1972) for uniform-length jobs is also optimal for two machines and (2 − 2/m)-competitive.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a><a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
In 1992, Bartal, Fiat, Karloff, and Vohra presented a 1.986-competitive algorithm,<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> followed by a 1.945-competitive algorithm by Karger, Philips, and Torng in 1994.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> That same year, Albers introduced a different 1.923-competitive algorithm.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> The best known result is by Fleischer and Wahl, achieving a 1.9201 competitive ratio.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>
Albers also established a lower bound of 1.852.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> Taillard instances play a key role in developing job-shop scheduling with a makespan objective.
In 1976, Garey proved that this problem is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> for m > 2, meaning no optimal solution can be computed in polynomial time unless <a href="/facts/P%253DNP/xoC7Ruda">P=NP</a>.<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>
In 2011, Xin Chen et al. provided optimal algorithms for online scheduling on two related machines, improving previous results.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a><a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>

<h2 id="offline-makespan-minimization">Offline makespan minimization</h2>
<h3>Atomic jobs</h3>
See also: <a href="/facts/Multiprocessor_scheduling/LFDtRUfD">Multiprocessor scheduling</a>
The simplest form of the offline makespan minimisation problem deals with atomic jobs, that is, jobs that are not subdivided into multiple operations. It is equivalent to packing a number of items of various different sizes into a fixed number of bins, such that the maximum bin size needed is as small as possible. (If instead the number of bins is to be minimised, and the bin size is fixed, the problem becomes a different problem, known as the <a href="/facts/Bin_packing_problem/T67Qe934">bin packing problem</a>.)
<a href="/facts/Dorit_S._Hochbaum/oTG3BBDt">Dorit S. Hochbaum</a> and <a href="/facts/David_Shmoys/v3hDFWn1">David Shmoys</a> presented a <a href="/facts/Polynomial-time_approximation_scheme/52Chjx9y">polynomial-time approximation scheme</a> in 1987 that finds an approximate solution to the offline makespan minimisation problem with atomic jobs to any desired degree of accuracy.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a>

<h3>Jobs consisting of multiple operations</h3>
The basic form of the problem of scheduling jobs with multiple (M) operations, over M machines, such that all of the first operations must be done on the first machine, all of the second operations on the second, etc., and a single job cannot be performed in parallel, is known as the <a href="/facts/Flow-shop_scheduling/9XLuvp5b">flow-shop scheduling</a> problem. Various algorithms exist, including <a href="/facts/Genetic_algorithm/WP2AFWuW">genetic algorithms</a>.<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>

<h4>Johnson's algorithm</h4>
See also: <a href="/facts/Johnson%2527s_rule/9LttC20c">Johnson's rule</a>
A heuristic algorithm by S. M. Johnson can be used to solve the case of a 2 machine N job problem when all jobs are to be processed in the same order.<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a> The steps of algorithm are as follows:
Job Pi has two operations, of duration Pi1, Pi2, to be done on Machine M1, M2 in that sequence.

<ul><li>Step 1. List A = { 1, 2, …, N }, List L1 = {}, List L2 = {}.</li>
<li>Step 2. From all available operation durations, pick the minimum.</li></ul>
If the minimum belongs to Pk1,
Remove K from list A; Add K to end of List L1.
If minimum belongs to Pk2,
Remove K from list A; Add K to beginning of List L2.

<ul><li>Step 3. Repeat Step 2 until List A is empty.</li>
<li>Step 4. Join List L1, List L2. This is the optimum sequence.</li></ul>
Johnson's method only works optimally for two machines. However, since it is optimal, and easy to compute, some researchers have tried to adopt it for M machines, (M > 2.)
The idea is as follows: Imagine that each job requires m operations in sequence, on M1, M2 … Mm. We combine the first m/2 machines into an (imaginary) Machining center, MC1, and the remaining Machines into a Machining Center MC2. Then the total processing time for a Job P on MC1 = sum (operation times on first m/2 machines), and processing time for Job P on MC2 = sum(operation times on last m/2 machines).
By doing so, we have reduced the m-Machine problem into a Two Machining center scheduling problem. We can solve this using Johnson's method.

<h2 id="makespan-prediction">Makespan prediction</h2>
Machine learning has been recently used to predict the optimal makespan of a JSP instance without actually producing the optimal schedule.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a> Preliminary results show around 80% accuracy in classifying small randomly generated JSP instances by optimal scheduling efficiency using supervised learning.

<h2 id="example">Example</h2>
Here is an example of a job-shop scheduling problem formulated in <a href="/facts/AMPL/pzceW9mH">AMPL</a> as a <a href="/facts/Linear_programming/GduXFQxT">mixed-integer programming</a> problem with indicator constraints:

param N_JOBS;
param N_MACHINES;

set JOBS ordered = 1..N_JOBS;
set MACHINES ordered = 1..N_MACHINES;

param ProcessingTime{JOBS, MACHINES} > 0;

param CumulativeTime{i in JOBS, j in MACHINES} =
 sum {jj in MACHINES: ord(jj) <= ord(j)} ProcessingTime[i,jj];

param TimeOffset{i1 in JOBS, i2 in JOBS: i1 <> i2} =
 max {j in MACHINES}
 (CumulativeTime[i1,j] - CumulativeTime[i2,j] + ProcessingTime[i2,j]);

var end >= 0;
var start{JOBS} >= 0;
var precedes{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)} binary;

minimize makespan: end;

subj to makespan_def{i in JOBS}:
   end >= start[i] + sum{j in MACHINES} ProcessingTime[i,j];

subj to no12_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
 precedes[i1,i2] ==> start[i2] >= start[i1] + TimeOffset[i1,i2];

subj to no21_conflict{i1 in JOBS, i2 in JOBS: ord(i1) < ord(i2)}:
 !precedes[i1,i2] ==> start[i1] >= start[i2] + TimeOffset[i2,i1];

data;

param N_JOBS := 4;
param N_MACHINES := 4;

param ProcessingTime:
   1 2 3 4 :=
1  5 4 2 1
2  8 3 6 2
3  9 7 2 3
4  3 1 5 8;

<h2 id="related-problems">Related problems</h2>
<ul><li><a href="/facts/Flow-shop_scheduling/9XLuvp5b">Flow-shop scheduling</a> is a similar problem but without the constraint that each operation must be done on a specific machine (only the order constraint is kept).</li>
<li><a href="/facts/Open-shop_scheduling/Y3cImTY8">Open-shop scheduling</a> is a similar problem but also without the order constraint.</li></ul>
<h2 id="see-also">See also</h2>

<ul><li><a href="/facts/Disjunctive_graph/uu5Lojpm">Disjunctive graph</a></li>
<li><a href="/facts/Dynamic_programming/CLcabtmk">Dynamic programming</a></li>
<li><a href="/facts/Genetic_algorithm_scheduling/pXlA7MkG">Genetic algorithm scheduling</a></li>
<li><a href="/facts/List_of_NP-complete_problems/pmR9Dlym">List of NP-complete problems</a></li>
<li><a href="/facts/Optimal_control/9SmcQHjJ">Optimal control</a></li>
<li><a href="/facts/Scheduling_(production_processes)/ChBw19Kb">Scheduling (production processes)</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.mat.univie.ac.at/~neum/glopt/software_g.html">University of Vienna</a> Directory of methodologies, systems and software for dynamic optimization.</li>
<li><a href="http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/jobshop.dir/best_lb_up.txt">Taillard instances</a></li>
<li>Brucker P. <a href="https://link.springer.com/content/pdf/bfm%3A978-3-540-24804-0%2F1.pdf">Scheduling Algorithms</a>. Heidelberg, Springer. Fifth ed. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-24804-0</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Graham, R. (1966). "Bounds for certain multiprocessing anomalies" (PDF). Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x. <a href="http://www.math.ucsd.edu/~ronspubs/66_04_multiprocessing.pdf" target="_blank">http://www.math.ucsd.edu/~ronspubs/66_04_multiprocessing.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">"Taillard Instances". mistic.heig-vd.ch. Retrieved 2025-03-17. <a href="http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html" target="_blank">http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/ordonnancement.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Maccarthy (1993). "Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling". <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Malakooti, B (2013). Operations and Production Systems with Multiple Objectives. John Wiley & Sons. ISBN 978-1-118-58537-5. <a href="978-1-118-58537-5" target="_blank">978-1-118-58537-5</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Sharma, P. (March 2016). "A review on job shop scheduling with setup times". Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture. 230 (3): 517–533. doi:10.1177/0954405414560617. ISSN 0954-4054. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">B. Roy, B. Sussmann, Les problèmes d’ordonnancement avec constraintes disjonctives, SEMA, Note D.S., No. 9, Paris, 1964. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Błażewicz, Jacek (December 2000). "The disjunctive graph machine representation of the job shop scheduling problem". European Journal of Operational Research. 127 (2): 317–331. doi:10.1016/S0377-2217(99)00486-5. ISSN 0377-2217. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Mirshekarian, Sadegh; Šormaz, Dušan N. (9 June 2016). "Correlation of job-shop scheduling problem features with scheduling efficiency" (PDF). Expert Systems with Applications. 62: 131–147. doi:10.1016/j.eswa.2016.06.014. Archived from the original on 2018-04-17. <a href="https://web.archive.org/web/20180417034243/http://mirshekarian.me/files/corrJSSP.pdf" target="_blank">https://web.archive.org/web/20180417034243/http://mirshekarian.me/files/corrJSSP.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Graham, R. (1966). "Bounds for certain multiprocessing anomalies" (PDF). Bell System Technical Journal. 45 (9): 1563–1581. doi:10.1002/j.1538-7305.1966.tb01709.x. <a href="http://www.math.ucsd.edu/~ronspubs/66_04_multiprocessing.pdf" target="_blank">http://www.math.ucsd.edu/~ronspubs/66_04_multiprocessing.pdf</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Coffman, E. G. Jr.; Graham, R. L. (1972), "Optimal scheduling for two-processor systems" (PDF), Acta Informatica, 1 (3): 200–213, doi:10.1007/bf00288685, MR 0334913, S2CID 40603807. <a href="/wiki/Edward_G._Coffman_Jr." target="_blank">/wiki/Edward_G._Coffman_Jr.</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Lam, Shui; Sethi, Ravi (1977), "Worst case analysis of two scheduling algorithms", SIAM Journal on Computing, 6 (3): 518–536, doi:10.1137/0206037, MR 0496614. <a href="/wiki/Ravi_Sethi" target="_blank">/wiki/Ravi_Sethi</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Bartal, Y.; A. Fiat; H. Karloff; R. Vohra (1992). "New Algorithms for an Ancient Scheduling Problem". Proc. 24th ACM Symp. Theory of Computing. pp. 51–58. doi:10.1145/129712.129718. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Karger, D.; S. Phillips; E. Torng (1994). "A Better Algorithm for an Ancient Scheduling Problem". Proc. Fifth ACM Symp. Discrete Algorithms. <a href="/wiki/David_Karger" target="_blank">/wiki/David_Karger</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Albers, Susanne; Torben Hagerup (1992). "Improved parallel integer sorting without concurrent writing". Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms. Symposium on Discrete Algorithms archive. pp. 463–472. <a href="/wiki/Susanne_Albers" target="_blank">/wiki/Susanne_Albers</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Fleischer, Rudolf (2000). Algorithms – ESA 2000. Berlin / Heidelberg: Springer. pp. 202–210. doi:10.1007/3-540-45253-2_19. ISBN 978-3-540-41004-1. <a href="978-3-540-41004-1" target="_blank">978-3-540-41004-1</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Albers, Susanne (1999). "Better bounds for online scheduling". SIAM Journal on Computing. 29 (2): 459–473. CiteSeerX 10.1.1.685.8756. doi:10.1137/S0097539797324874. <a href="/wiki/Susanne_Albers" target="_blank">/wiki/Susanne_Albers</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Garey, M. R.; Johnson, D. S.; Sethi, Ravi (1976). "The Complexity of Flowshop and Jobshop Scheduling". Mathematics of Operations Research. 1 (2): 117–129. doi:10.1287/moor.1.2.117. JSTOR 3689278. <a href="/wiki/Mathematics_of_Operations_Research" target="_blank">/wiki/Mathematics_of_Operations_Research</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Chen, Xin; Lan, Yan; Benkő, Attila; Dósa, György; Han, Xin (2011). "Optimal algorithms for online scheduling with bounded rearrangement at the end". Theoretical Computer Science. 412 (45): 6269–6278. doi:10.1016/j.tcs.2011.07.014. <a href="https://doi.org/10.1016%2Fj.tcs.2011.07.014" target="_blank">https://doi.org/10.1016%2Fj.tcs.2011.07.014</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Liu, M.; Xu, Y.; Chu, C.; Zheng, F. (2009). "Online scheduling on two uniform machines to minimize the makespan". Theoret. Comput. Sci. 410 (21–23): 2099–2109. doi:10.1016/j.tcs.2009.01.007. <a href="https://doi.org/10.1016%2Fj.tcs.2009.01.007" target="_blank">https://doi.org/10.1016%2Fj.tcs.2009.01.007</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Hochbaum, Dorit; Shmoys, David (1987). "Using dual approximation algorithms for scheduling problems: theoretical and practical results" (PDF). Journal of the ACM. 34 (1): 144–162. CiteSeerX 10.1.1.125.5753. doi:10.1145/7531.7535. S2CID 9739129. <a href="/wiki/Dorit_S._Hochbaum" target="_blank">/wiki/Dorit_S._Hochbaum</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Khuri, Sami; Miryala, Sowmya Rao (1999). "Genetic Algorithms for Solving Open Shop Scheduling Problems". Proceedings of the 9th Portuguese Conference on Artificial Intelligence: Progress in Artificial Intelligence. London: Springer Verlag. CiteSeerX 10.1.1.29.4699. <a href="/wiki/Springer_Verlag" target="_blank">/wiki/Springer_Verlag</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68. <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Mirshekarian, Sadegh; Šormaz, Dušan N. (9 June 2016). "Correlation of job-shop scheduling problem features with scheduling efficiency" (PDF). Expert Systems with Applications. 62: 131–147. doi:10.1016/j.eswa.2016.06.014. Archived from the original on 2018-04-17. <a href="https://web.archive.org/web/20180417034243/http://mirshekarian.me/files/corrJSSP.pdf" target="_blank">https://web.archive.org/web/20180417034243/http://mirshekarian.me/files/corrJSSP.pdf</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
</ol>

Job-shop scheduling open-in-new

Job-shop scheduling