Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Optimal job scheduling
open-in-new
<h2 id="single-stage-jobs-vs-multi-stage-jobs">Single-stage jobs vs. multi-stage jobs</h2> <p>In the simpler optimal job scheduling problems, each job <i>j</i> consists of a single execution phase, with a given processing time <i>pj</i>. In more complex variants, each job consists of several execution phases, which may be executed in sequence or in parallel. </p> <h2 id="machine-environments">Machine environments</h2> <p>In single-stage job scheduling problems, there are four main categories of machine environments: </p> <ul><li>1: <a href="/facts/Single-machine_scheduling/d0jkcNrh">Single-machine scheduling</a>. There is a single machine.</li> <li>P: <a href="/facts/Identical-machines_scheduling/lwNSXMs6">Identical-machines scheduling</a>. There are m {\displaystyle m} parallel machines, and they are identical. Job j {\displaystyle j} takes time p j {\displaystyle p_{j}} on any machine it is scheduled to.</li> <li>Q: <a href="/facts/Uniform-machines_scheduling/LFDtRUfD">Uniform-machines scheduling</a>. There are m {\displaystyle m} parallel machines, and they have different given speeds. Job j {\displaystyle j} on machine i {\displaystyle i} takes time p j / s i {\displaystyle p_{j}/s_{i}} .</li> <li>R: <a href="/facts/Unrelated-machines_scheduling/V3cIylxs">Unrelated-machines scheduling</a>. There are m {\displaystyle m} parallel machines, and they are unrelated – Job j {\displaystyle j} on machine i {\displaystyle i} takes time p i j {\displaystyle p_{ij}} .</li></ul> <p>These letters might be followed by the number of machines, which is then fixed. For example, P2 indicates that there are two parallel identical machines. Pm indicates that there are <i>m</i> parallel identical machines, where <i>m</i> is a fixed parameter. In contrast, P indicates that there are <i>m</i> parallel identical machines, but <i>m</i> is not fixed (it is part of the input). </p><p>In multi-stage job scheduling problems, there are other options for the machine environments: </p> <ul><li>O: <a href="/facts/Open-shop_scheduling/Y3cImTY8">Open-shop problem</a>. Every job j {\displaystyle j} consists of m {\displaystyle m} operations O i j {\displaystyle O_{ij}} for i = 1 , … , m {\displaystyle i=1,\ldots ,m} . The operations can be scheduled in <i>any</i> order. Operation O i j {\displaystyle O_{ij}} must be processed for p i j {\displaystyle p_{ij}} units on machine i {\displaystyle i} .</li> <li>F: <a href="/facts/Flow-shop_scheduling/9XLuvp5b">Flow-shop problem</a>. Every job j {\displaystyle j} consists of m {\displaystyle m} operations O i j {\displaystyle O_{ij}} for i = 1 , … , m {\displaystyle i=1,\ldots ,m} , to be scheduled in <i>the given</i> order. Operation O i j {\displaystyle O_{ij}} must be processed for p i j {\displaystyle p_{ij}} units on machine i {\displaystyle i} .</li> <li>J: <a href="/facts/Job-shop_scheduling/1JjAvD3m">Job-shop problem</a>. Every job j {\displaystyle j} consists of n j {\displaystyle n_{j}} operations O k j {\displaystyle O_{kj}} for k = 1 , … , n j {\displaystyle k=1,\ldots ,n_{j}} , to be scheduled in that order. Operation O k j {\displaystyle O_{kj}} must be processed for p k j {\displaystyle p_{kj}} units on a <i>dedicated</i> machine μ k j {\displaystyle \mu _{kj}} with μ k j ≠ μ k ′ j {\displaystyle \mu _{kj}\neq \mu _{k'j}} for k ≠ k ′ {\displaystyle k\neq k'} .</li></ul> <h2 id="job-characteristics">Job characteristics</h2> <p>All processing times are assumed to be integers. In some older research papers however they are assumed to be rationals. </p> <ul><li> p i = p {\displaystyle p_{i}=p} , or p i j = p {\displaystyle p_{ij}=p} : the processing time is equal for all jobs.</li> <li> p i = 1 {\displaystyle p_{i}=1} , or p i j = 1 {\displaystyle p_{ij}=1} : the processing time is equal to 1 time-unit for all jobs.</li> <li> r j {\displaystyle r_{j}} : for each job a release time is given before which it cannot be scheduled, default is 0.</li> <li> online- r j {\displaystyle {\text{online-}}r_{j}} : an online problem. Jobs are revealed at their release times. In this context the performance of an algorithm is measured by its <a href="/facts/Competitive_analysis_(online_algorithm)/ocEpTvXG">competitive ratio</a>.</li> <li> d j {\displaystyle d_{j}} : for each job a due date is given. The idea is that every job should complete before its due date and there is some penalty for jobs that complete late. This penalty is denoted in the objective value. The presence of the job characteristic d j {\displaystyle d_{j}} is implicitly assumed and not denoted in the problem name, unless there are some restrictions as for example d j = d {\displaystyle d_{j}=d} , assuming that all due dates are equal to some given date.</li> <li> d ¯ j {\displaystyle {\bar {d}}_{j}} : for each job a strict deadline is given. Every job must complete before its deadline.</li> <li>pmtn: Jobs can be preempted and resumed possibly on another machine. Sometimes also denoted by 'prmp'.</li> <li> size j {\displaystyle {\text{size}}_{j}} : Each job comes with a number of machines on which it must be scheduled at the same time. The default is 1. This is an important parameter in the variant called <a href="/facts/Parallel_task_scheduling/KUBSl2qj">parallel task scheduling</a>.</li></ul> <h3>Precedence relations</h3> <p>Each pair of two jobs may or may not have a precedence relation. A precedence relation between two jobs means that one job must be finished before the other job. For example, if job i is a predecessor of job j in that order, job j can only start once job i is completed. </p> <ul><li>prec: There are no restrictions placed on the precedence relations.</li> <li>chains: Each job is the predecessor of at most one other job and is preceded by at most one other job.</li> <li>tree: The precedence relations must satisfy one of the two restrictions. <ul><li>intree: Each node is the predecessor of at most one other job.</li> <li>outtree: Each node is preceded by at most one other job.</li></ul></li> <li>opposing forest: If the graph of precedence relations is split into <a href="/facts/Component_(graph_theory)/5owVSXtY">connected components</a>, then each connected component is either an intree or outtree.</li> <li>sp-graph: The graph of precedence relations is a <a href="/facts/Series%25E2%2580%2593parallel_graph/XdfWgomL">series parallel graph</a>.</li> <li>bounded height: The length of the longest directed path is capped at a fixed value. (A directed path is a sequence of jobs where each job except the last is a predecessor of the next job in the sequence.)</li> <li>level order: Each job has a level, which is the length of the longest directed path starting from that job. Each job with level k {\displaystyle k} is a predecessor of every job with level k − 1 {\displaystyle k-1} .</li> <li>interval order: Each job x {\displaystyle x} has an interval [<i>s</i><i>x</i>,<i>e</i><i>x</i>) and job x {\displaystyle x} is a predecessor of y {\displaystyle y} if and only if the end of the interval of x {\displaystyle x} is strictly less than the start of the interval for y {\displaystyle y} .=</li></ul> <p>In the presence of a precedence relation one might in addition assume <i>time lags</i>. The time lag between two jobs is the amount of time that must be waited after the first job is complete before the second job to begin. Formally, if job i precedes job j, then C i + ℓ i j ≤ S j {\displaystyle C_{i}+\ell _{ij}\leq S_{j}} must be true. If no time lag ℓ i j {\displaystyle \ell _{ij}} is specified then it is assumed to be zero. Time lags can also be negative. A negative time lag means that the second job can begin a fixed time before the first job finishes. </p> <ul><li><i>ℓ</i>: The time lag is the same for each pair of jobs.</li> <li> ℓ i j {\displaystyle \ell _{ij}} : Different pairs of jobs can have different time lags.</li></ul> <h3>Transportation delays</h3> <ul><li> t j k {\displaystyle t_{jk}} : Between the completion of operation O k j {\displaystyle O_{kj}} of job j {\displaystyle j} on machine k {\displaystyle k} and the start of operation O k + 1 , j {\displaystyle O_{k+1,j}} of job j {\displaystyle j} on machine k + 1 {\displaystyle k+1} , there is a transportation delay of at least t j k {\displaystyle t_{jk}} units.</li> <li> t j k l {\displaystyle t_{jkl}} : Between the completion of operation O k j {\displaystyle O_{kj}} of job j {\displaystyle j} on machine k {\displaystyle k} and the start of operation O l , j {\displaystyle O_{l,j}} of job j {\displaystyle j} on machine l {\displaystyle l} , there is a transportation delay of at least t j k l {\displaystyle t_{jkl}} units.</li> <li> t k {\displaystyle t_{k}} : Machine dependent transportation delay. Between the completion of operation O k j {\displaystyle O_{kj}} of job j {\displaystyle j} on machine k {\displaystyle k} and the start of operation O k + 1 , j {\displaystyle O_{k+1,j}} of job j {\displaystyle j} on machine k + 1 {\displaystyle k+1} , there is a transportation delay of at least t k {\displaystyle t_{k}} units.</li> <li> t k l {\displaystyle t_{kl}} : Machine pair dependent transportation delay. Between the completion of operation O k j {\displaystyle O_{kj}} of job j {\displaystyle j} on machine k {\displaystyle k} and the start of operation O l , j {\displaystyle O_{l,j}} of job j {\displaystyle j} on machine l {\displaystyle l} , there is a transportation delay of at least t k l {\displaystyle t_{kl}} units.</li> <li> t j {\displaystyle t_{j}} : Job dependent transportation delay. Between the completion of operation O k j {\displaystyle O_{kj}} of job j {\displaystyle j} on machine k {\displaystyle k} and the start of operation O l , j {\displaystyle O_{l,j}} of job j {\displaystyle j} on machine l {\displaystyle l} , there is a transportation delay of at least t j {\displaystyle t_{j}} units.</li></ul> <h3>Various constraints</h3> <ul><li>rcrc: Also known as Recirculation or flexible job shop. The promise on μ {\displaystyle \mu } is lifted and for some pairs k ≠ k ′ {\displaystyle k\neq k'} we might have μ k j = μ k ′ j {\displaystyle \mu _{kj}=\mu _{k'j}} . In other words, it is possible for different operations of the same job to be assigned to the same machine.</li> <li>no-wait: The operation O k + 1 , i {\displaystyle O_{k+1,i}} must start exactly when operation O k , i {\displaystyle O_{k,i}} completes. In other words, once one operation of a job finishes, the next operation must begin immediately. Sometimes also denoted as 'nwt'.</li> <li>no-idle: No machine may ever be idle between the start of its first execution to the end of its last execution.</li> <li> size j {\displaystyle {\text{size}}_{j}} : Multiprocessor tasks on identical parallel machines. The execution of job j {\displaystyle j} is done simultaneously on size j {\displaystyle {\text{size}}_{j}} parallel machines.</li> <li> fix j {\displaystyle {\text{fix}}_{j}} : Multiprocessor tasks. Every job j {\displaystyle j} is given with a set of machines fix j ⊆ { 1 , … , m } {\displaystyle {\text{fix}}_{j}\subseteq \{1,\ldots ,m\}} , and needs simultaneously all these machines for execution. Sometimes also denoted by 'MPT'.</li> <li> M j {\displaystyle M_{j}} : Multipurpose machines. Every job j {\displaystyle j} needs to be scheduled on one machine out of a given set M j ⊆ { 1 , … , m } {\displaystyle M_{j}\subseteq \{1,\ldots ,m\}} . Sometimes also denoted by <i>M</i><i>j</i>.</li></ul> <h2 id="objective-functions">Objective functions</h2> <p>Usually the goal is to minimize some objective value. One difference is the notation ∑ U j {\displaystyle \sum U_{j}} where the goal is to maximize the number of jobs that complete before their deadline. This is also called the <i>throughput</i>. The objective value can be sum, possibly weighted by some given priority weights w j {\displaystyle w_{j}} per job. </p> <ul><li>-: The absence of an objective value is denoted by a single dash. This means that the problem consists simply in producing a feasible scheduling, satisfying all given constraints.</li> <li> C j {\displaystyle C_{j}} : the <i>completion time</i> of job j {\displaystyle j} . C max {\displaystyle C_{\max }} is the maximum completion time; also known as the <a href="/facts/Makespan/w1HEjJaQ">makespan</a>. Sometimes we are interested in the <i>mean</i> completion time (the average of C j {\displaystyle C_{j}} over all <i>j</i>), which is sometimes denoted by mft (mean finish time).<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a></li> <li> F j {\displaystyle F_{j}} : The <i>flow time</i> of a job is the difference between its completion time and its release time, i.e. F j = C j − r j {\displaystyle F_{j}=C_{j}-r_{j}} .</li> <li> L j {\displaystyle L_{j}} : <a href="/facts/Lateness_(scheduling)/aqEhb7Mk">Lateness</a>. Every job j {\displaystyle j} is given a due date d j {\displaystyle d_{j}} . The lateness of job j {\displaystyle j} is defined as C j − d j {\displaystyle C_{j}-d_{j}} . Sometimes L max {\displaystyle L_{\max }} is used to denote feasibility for a problem with deadlines. Indeed using binary search, the complexity of the feasibility version is equivalent to the minimization of L max {\displaystyle L_{\max }} .</li> <li> U j {\displaystyle U_{j}} : <a href="/facts/Throughput/6zAUsXqw">Throughput</a>. Every job is given a due date d j {\displaystyle d_{j}} . There is a unit profit for jobs that complete on time, i.e. U j = 1 {\displaystyle U_{j}=1} if C j ≤ d j {\displaystyle C_{j}\leq d_{j}} and U j = 0 {\displaystyle U_{j}=0} otherwise. Sometimes the meaning of U j {\displaystyle U_{j}} is inverted in the literature, which is equivalent when considering the decision version of the problem, but which makes a huge difference for approximations.</li> <li> T j {\displaystyle T_{j}} : <a href="/facts/Tardiness_(scheduling)/aqEhb7Mk">Tardiness</a>. Every job j {\displaystyle j} is given a due date d j {\displaystyle d_{j}} . The tardiness of job j {\displaystyle j} is defined as T j = max { 0 , C j − d j } {\displaystyle T_{j}=\max\{0,C_{j}-d_{j}\}} .</li> <li> E j {\displaystyle E_{j}} : <a href="/facts/Earliness_(scheduling)/aqEhb7Mk">Earliness</a>. Every job j {\displaystyle j} is given a due date d j {\displaystyle d_{j}} . The earliness of job j {\displaystyle j} is defined as E j = max { 0 , d j − C j } {\displaystyle E_{j}=\max\{0,d_{j}-C_{j}\}} . This objective is important for <i>just-in-time scheduling.</i></li></ul> <p>There are also variants with <a href="/facts/Multi-objective_optimization/1Hb4gjGJ">multiple objectives</a>, but they are much less studied.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p> <h2 id="examples">Examples</h2> <p>Here are some examples for problems defined using the above notation.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <ul><li> P 2 ∥ C max {\displaystyle P_{2}\parallel C_{\max }} – assigning each of n {\displaystyle n} given jobs to one of the two identical machines so to minimize the maximum total processing time over the machines. This is an optimization version of the <a href="/facts/Partition_problem/LcSBAcmu">partition problem</a></li> <li>1|prec| L max {\displaystyle L_{\max }} – assigning to a single machine, processes with general precedence constraint, minimizing maximum lateness.</li> <li>R|pmtn| ∑ C i {\displaystyle \sum C_{i}} – assigning tasks to a variable number of unrelated parallel machines, allowing preemption, minimizing total completion time.</li> <li>J3| p i j = 1 {\displaystyle p_{ij}=1} | C max {\displaystyle C_{\max }} – a 3-machine job shop problem with unit processing times, where the goal is to minimize the maximum completion time.</li> <li> P ∣ size j ∣ C max {\displaystyle P\mid {\text{size}}_{j}\mid C_{\max }} – assigning jobs to m {\displaystyle m} parallel identical machines, where each job comes with a number of machines on which it must be scheduled at the same time, minimizing maximum completion time. See <a href="/facts/Parallel_task_scheduling/KUBSl2qj">parallel task scheduling</a>.</li></ul> <h2 id="other-variants">Other variants</h2> <ul><li>All variants surveyed above are <i>deterministic</i> in that all data is known to the planner. There are also <i>stochastic</i> variants, in which the data is not known in advance, or can perturb randomly.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a></li> <li>In a <i>load balancing game</i>, each job belongs to a strategic agent, who can decide where to schedule his job. The <a href="/facts/Nash_equilibrium/l74xzIHd">Nash equilibrium</a> in this game may not be optimal. Aumann and Dombb<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> assess the inefficiency of equilibrium in several load-balancing games.</li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Fractional_job_scheduling/ICy8zG03">Fractional job scheduling</a></li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://schedulingzoo.lip6.fr/">Scheduling zoo</a> (by Christoph Dürr, Sigrid Knust, Damien Prot, Óscar C. Vásquez): an online tool for searching an optimal scheduling problem using the notation.</li> <li><a href="http://www.informatik.uni-osnabrueck.de/knust/class/">Complexity results for scheduling problems</a> (by Peter Brucker, Sigrid Knust): a classification of optimal scheduling problems by what is known on their runtime complexity.</li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Graham, R. L.; Lawler, E. L.; Lenstra, J.K.; Rinnooy Kan, A.H.G. (1979). "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey" (PDF). Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium. Elsevier. pp. (5) 287–326. <a href="http://mat.uab.es/~alseda/MasterOpt/79_03_scheduling_survey.pdf" target="_blank">http://mat.uab.es/~alseda/MasterOpt/79_03_scheduling_survey.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys (1993-01-01). "Chapter 9 Sequencing and scheduling: Algorithms and complexity". Handbooks in Operations Research and Management Science. 4: 445–522. doi:10.1016/S0927-0507(05)80189-6. ISBN 9780444874726. ISSN 0927-0507.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="9780444874726" target="_blank">9780444874726</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>B. Chen, C.N. Potts and G.J. Woeginger. "A review of machine scheduling: Complexity, algorithms and approximability". Handbook of Combinatorial Optimization (Volume 3) (Editors: D.-Z. Du and P. Pardalos), 1998, Kluwer Academic Publishers. 21-169. ISBN 0-7923-5285-8 (HB) 0-7923-5019-7 (Set) <a href="/wiki/Gerhard_J._Woeginger" target="_blank">/wiki/Gerhard_J._Woeginger</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Horowitz, Ellis; Sahni, Sartaj (1976-04-01). "Exact and Approximate Algorithms for Scheduling Nonidentical Processors". Journal of the ACM. 23 (2): 317–327. doi:10.1145/321941.321951. ISSN 0004-5411. S2CID 18693114. <a href="https://doi.org/10.1145%2F321941.321951" target="_blank">https://doi.org/10.1145%2F321941.321951</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys (1993-01-01). "Chapter 9 Sequencing and scheduling: Algorithms and complexity". Handbooks in Operations Research and Management Science. 4: 445–522. doi:10.1016/S0927-0507(05)80189-6. ISBN 9780444874726. ISSN 0927-0507.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="9780444874726" target="_blank">9780444874726</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Graham, R. L.; Lawler, E. L.; Lenstra, J.K.; Rinnooy Kan, A.H.G. (1979). "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey" (PDF). Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium. Elsevier. pp. (5) 287–326. <a href="http://mat.uab.es/~alseda/MasterOpt/79_03_scheduling_survey.pdf" target="_blank">http://mat.uab.es/~alseda/MasterOpt/79_03_scheduling_survey.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys (1993-01-01). "Chapter 9 Sequencing and scheduling: Algorithms and complexity". Handbooks in Operations Research and Management Science. 4: 445–522. doi:10.1016/S0927-0507(05)80189-6. ISBN 9780444874726. ISSN 0927-0507.{{cite journal}}: CS1 maint: multiple names: authors list (link) <a href="9780444874726" target="_blank">9780444874726</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Aumann, Yonatan; Dombb, Yair (2010). "Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games". In Kontogiannis, Spyros; Koutsoupias, Elias; Spirakis, Paul G. (eds.). Algorithmic Game Theory. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. pp. 66–77. doi:10.1007/978-3-642-16170-4_7. ISBN 978-3-642-16170-4. <a href="978-3-642-16170-4" target="_blank">978-3-642-16170-4</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> </ol>