Uniform-machines scheduling

Last updated July 17, 2024

Uniform machine scheduling (also called uniformly-related machine scheduling or related machine scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We are given n jobs J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on m different machines. The goal is to minimize the makespan - the total time required to execute the schedule. The time that machine i needs in order to process job j is denoted by p_i,j. In the general case, the times p_i,j are unrelated, and any matrix of positive processing times is possible. In the specific variant called uniform machine scheduling, some machines are uniformly faster than others. This means that, for each machine i, there is a speed factor s_i, and the run-time of job j on machine i is p_i,j = p_j / s_i.

In the standard three-field notation for optimal job scheduling problems, the uniform-machine variant is denoted by Q in the first field. For example, the problem denoted by " Q|| $C_{\max }$ " is a uniform machine scheduling problem with no constraints, where the goal is to minimize the maximum completion time. A special case of uniform machine scheduling is identical-machines scheduling, in which all machines have the same speed. This variant is denoted by P in the first field.

In some variants of the problem, instead of minimizing the maximum completion time, it is desired to minimize the average completion time (averaged over all n jobs); it is denoted by Q|| $\sum C_{i}$ . More generally, when some jobs are more important than others, it may be desired to minimize a weighted average of the completion time, where each job has a different weight. This is denoted by Q|| $\sum w_{i}C_{i}$ .

Algorithms

Minimizing the average completion time

Minimizing the average completion time can be done in polynomial time:

The SPT algorithm (Shortest Processing Time First), sorts the jobs by their length, shortest first, and then assigns them to the processor with the earliest end time so far. It runs in time O(n log n), and minimizes the average completion time on identical machines,^[1]P|| $\sum C_{i}$ .
Horowitz and Sahni^[1] present an exact algorithm, with run time O(n log m n), for minimizing the average completion time on uniform machines, Q|| $\sum C_{i}$ .
Bruno, Coffman and Sethi^[2] present an algorithm, running in time $O(\max(mn^{2},n^{3}))$ , for minimizing the average completion time on unrelated machines, R|| $\sum C_{i}$ .

Minimizing the weighted-average completion time

Minimizing the weighted average completion time is NP-hard even on identical machines, by reduction from the knapsack problem.^[1] It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the partition problem.^[3]

Sahni^[3] presents an exponential-time algorithm and a polynomial-time approximation algorithm for identical machines.

Horowitz and Sahni^[1] presented:

Exact dynamic programming algorithms for minimizing the weighted-average completion time on uniform machines. These algorithms run in exponential time.
Polynomial-time approximation schemes, which for any ε>0, attain at most (1+ε)OPT. For minimizing the weighted average completion time on two uniform machines, the run-time is $O(10^{l}n^{2})$ = $O(n^{2}/\epsilon )$ , so it is an FPTAS. They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case. They do not present an algorithm for weighted-average completion time on unrelated machines.

Minimizing the maximum completion time (makespan)

Minimizing the maximum completion time is NP-hard even for identical machines, by reduction from the partition problem.

A constant-factor approximation is attained by the Longest-processing-time-first algorithm (LPT).

Horowitz and Sahni^[1] presented:

Exact dynamic programming algorithms for minimizing the maximum completion time on both uniform and unrelated machines. These algorithms run in exponential time (recall that these problems are all NP-hard).
Polynomial-time approximation schemes, which for any ε>0, attain at most (1+ε)OPT. For minimizing the maximum completion time on two uniform machines, their algorithm runs in time $O(10^{2l}n)$ , where $l$ is the smallest integer for which $\epsilon \geq 2\cdot 10^{-l}$ . Therefore, the run-time is in $O(n/\epsilon ^{2})$ , so it is an FPTAS. For minimizing the maximum completion time on two unrelated machines, the run-time is $O(10^{l}n^{2})$ = $O(n^{2}/\epsilon )$ . They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case.

Hochbaum and Shmoys^[4] presented several approximation algorithms for any number of identical machines. Later,^[5] they developed a PTAS for uniform machines.

Epstein and Sgall^[6] generalized the PTAS for uniform machines to handle more general objective functions. Let C_i (for i between 1 and m) be the makespan of machine i in a given schedule. Instead of minimizing the objective function max(C_i), one can minimize the objective function max(f(C_i)), where f is any fixed function. Similarly, one can minimize the objective function sum(f(C_i)).

Monotonicity and Truthfulness

In some settings, the machine speed is the machine's private information, and we want to incentivize machines to reveal their true speed, that is, we want a truthful mechanism. An important consideration for attaining truthfulness is monotonicity.^[7] It means that, if a machine reports a higher speed, and all other inputs remain the same, then the total processing time allocated to the machine weakly increases. For this problem:

Auletta, De Prisco, Penna and Persiano^[8] presented a 4-approximation monotone algorithm, which runs in polytime when the number of machines is fixed.
Ambrosio and Auletta^[9] proved that the Longest Processing Time algorithm is monotone whenever the machine speeds are powers of some c ≥ 2, but not when c ≤ 1.78. In contrast, List scheduling is not monotone for c > 2.
Andelman, Azar and Sorani^[10] presented a 5-approximation monotone algorithm, which runs in polytime even when the number of machines is variable.
Kovacz^[11] presented a 3-approximation monotone algorithm.

Extensions

Dependent jobs: In some cases, the jobs may be dependent. For example, take the case of reading user credentials from console, then use it to authenticate, then if authentication is successful display some data on the console. Clearly one task is dependent upon another. This is a clear case of where some kind of ordering exists between the tasks. In fact it is clear that it can be modelled with partial ordering. Then, by definition, the set of tasks constitute a lattice structure. This adds further complication to the multiprocessor scheduling problem.

Static versus Dynamic: Machine scheduling algorithms are static or dynamic. A scheduling algorithm is static if the scheduling decisions as to what computational tasks will be allocated to what processors are made before running the program. An algorithm is dynamic if it is taken at run time. For static scheduling algorithms, a typical approach is to rank the tasks according to their precedence relationships and use a list scheduling technique to schedule them onto the processors.^[12]

Multi-stage jobs: In various settings, each job might have several operations that must be executed in parallel. Some such settings are handled by open shop scheduling, flow shop scheduling and job shop scheduling.

External links

Summary of parallel machine problems without preemtion

Related Research Articles

The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has many applications, such as filling up containers, loading trucks with weight capacity constraints, creating file backups in media, splitting a network prefix into multiple subnets, and technology mapping in FPGA semiconductor chip design.

In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines.

A fully polynomial-time approximation scheme (FPTAS) is an algorithm for finding approximate solutions to function problems, especially optimization problems. An FPTAS takes as input an instance of the problem and a parameter ε > 0. It returns as output a value which is at least $times the correct value, and at most times the correct value.$

Single-machine scheduling or single-resource scheduling is an optimization problem in computer science and operations research. We are given n jobs J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on a single machine, in a way that optimizes a certain objective, such as the throughput.

Optimal job scheduling is a class of optimization problems related to scheduling. The inputs to such problems are a list of jobs and a list of machines. The required output is a schedule – an assignment of jobs to machines. The schedule should optimize a certain objective function. In the literature, problems of optimal job scheduling are often called machine scheduling, processor scheduling, multiprocessor scheduling, or just scheduling.

Stochastic approximation methods are a family of iterative methods typically used for root-finding problems or for optimization problems. The recursive update rules of stochastic approximation methods can be used, among other things, for solving linear systems when the collected data is corrupted by noise, or for approximating extreme values of functions which cannot be computed directly, but only estimated via noisy observations.

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 J₁, J₂, ..., J_n 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. In the specific variant known as job-shop scheduling, each job consists of a set of operationsO₁, O₂, ..., O_n which need to be processed in a specific order. 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.

Flow-shop scheduling 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 J₁, J₂, ..., J_n 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. In the specific variant known as flow-shop scheduling, each job contains exactly m operations. The i-th operation of the job must be executed on the i-th machine. No machine can perform more than one operation simultaneously. For each operation of each job, execution time is specified.

In computer science, streaming algorithms are algorithms for processing data streams in which the input is presented as a sequence of items and can be examined in only a few passes, typically just one. These algorithms are designed to operate with limited memory, generally logarithmic in the size of the stream and/or in the maximum value in the stream, and may also have limited processing time per item.

In mathematics, a submodular set function is a set function that, informally, describes the relationship between a set of inputs and an output, where adding more of one input has a decreasing additional benefit. The natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory and electrical networks. Recently, submodular functions have also found utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains.

Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research.

Parallel task scheduling 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 J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on m machines while trying to minimize the makespan - the total length of the schedule. In the specific variant known as parallel-task scheduling, all machines are identical. Each job j has a length parameter p_j and a size parameter q_j, and it must run for exactly p_j time-steps on exactly q_j machines in parallel.

In computer science, multiway number partitioning is the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible. It was first presented by Ronald Graham in 1969 in the context of the identical-machines scheduling problem. The problem is parametrized by a positive integer k, and called k-way number partitioning. The input to the problem is a multiset S of numbers, whose sum is k*T.

Identical-machines scheduling is an optimization problem in computer science and operations research. We are given n jobs J₁, J₂, ..., J_n of varying processing times, which need to be scheduled on m identical machines, such that a certain objective function is optimized, for example, the makespan is minimized.

Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J₁, J₂, ..., J_n on m different machines, such that a certain objective function is optimized. The time that machine i needs in order to process job j is denoted by p_i,j. The term unrelated emphasizes that there is no relation between values of p_i,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which p_i,j = p_i / s_j, and identical-machines scheduling - in which p_i,j = p_i.

Longest-processing-time-first (LPT) is a greedy algorithm for job scheduling. The input to the algorithm is a set of jobs, each of which has a specific processing-time. There is also a number m specifying the number of machines that can process the jobs. The LPT algorithm works as follows:

Order the jobs by descending order of their processing-time, such that the job with the longest processing time is first.
Schedule each job in this sequence into a machine in which the current load is smallest.

Balanced number partitioning is a variant of multiway number partitioning in which there are constraints on the number of items allocated to each set. The input to the problem is a set of n items of different sizes, and two integers m, k. The output is a partition of the items into m subsets, such that the number of items in each subset is at most k. Subject to this, it is required that the sums of sizes in the m subsets are as similar as possible.

The configuration linear program (configuration-LP) is a linear programming technique used for solving combinatorial optimization problems. It was introduced in the context of the cutting stock problem. Later, it has been applied to the bin packing and job scheduling problems. In the configuration-LP, there is a variable for each possible configuration - each possible multiset of items that can fit in a single bin. Usually, the number of configurations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations.

Fractional job scheduling is a variant of optimal job scheduling in which it is allowed to break jobs into parts and process each part separately on the same or a different machine. Breaking jobs into parts may allow for improving the overall performance, for example, decreasing the makespan. Moreover, the computational problem of finding an optimal schedule may become easier, as some of the optimization variables become continuous. On the other hand, breaking jobs apart might be costly.

References

1 2 3 4 5 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.
↑ Bruno, J.; Coffman, E. G.; Sethi, R. (1974-07-01). "Scheduling independent tasks to reduce mean finishing time". Communications of the ACM. 17 (7): 382–387. doi: 10.1145/361011.361064 . ISSN 0001-0782.
1 2 Sahni, Sartaj K. (1976-01-01). "Algorithms for Scheduling Independent Tasks". Journal of the ACM. 23 (1): 116–127. doi: 10.1145/321921.321934 . ISSN 0004-5411.
↑ Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Using dual approximation algorithms for scheduling problems theoretical and practical results". Journal of the ACM. 34 (1): 144–162. doi: 10.1145/7531.7535 . ISSN 0004-5411. S2CID 9739129.
↑ Hochbaum, Dorit S.; Shmoys, David B. (1988-06-01). "A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach". SIAM Journal on Computing. 17 (3): 539–551. doi:10.1137/0217033. ISSN 0097-5397.
↑ Epstein, Leah; Sgall, Jiri (2004-05-01). "Approximation Schemes for Schedulingon Uniformly Related and Identical Parallel Machines". Algorithmica. 39 (1): 43–57. doi:10.1007/s00453-003-1077-7. ISSN 1432-0541. S2CID 12965369.
↑ Archer, A.; Tardos, E. (2001-10-01). "Truthful mechanisms for one-parameter agents". Proceedings 42nd IEEE Symposium on Foundations of Computer Science. pp. 482–491. doi:10.1109/SFCS.2001.959924. ISBN 0-7695-1390-5. S2CID 11377808.
↑ Auletta, Vincenzo; De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004). "Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines". In Diekert, Volker; Habib, Michel (eds.). Stacs 2004. Lecture Notes in Computer Science. Vol. 2996. Berlin, Heidelberg: Springer. pp. 608–619. doi:10.1007/978-3-540-24749-4_53. ISBN 978-3-540-24749-4.
↑ Ambrosio, Pasquale; Auletta, Vincenzo (2005). "Deterministic Monotone Algorithms for Scheduling on Related Machines". In Persiano, Giuseppe; Solis-Oba, Roberto (eds.). Approximation and Online Algorithms. Lecture Notes in Computer Science. Vol. 3351. Berlin, Heidelberg: Springer. pp. 267–280. doi:10.1007/978-3-540-31833-0_22. ISBN 978-3-540-31833-0.
↑ Andelman, Nir; Azar, Yossi; Sorani, Motti (2005). "Truthful Approximation Mechanisms for Scheduling Selfish Related Machines". In Diekert, Volker; Durand, Bruno (eds.). Stacs 2005. Lecture Notes in Computer Science. Vol. 3404. Berlin, Heidelberg: Springer. pp. 69–82. doi:10.1007/978-3-540-31856-9_6. ISBN 978-3-540-31856-9.
↑ Kovács, Annamária (2005). "Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines". In Brodal, Gerth Stølting; Leonardi, Stefano (eds.). Algorithms – ESA 2005. Lecture Notes in Computer Science. Vol. 3669. Berlin, Heidelberg: Springer. pp. 616–627. doi:10.1007/11561071_55. ISBN 978-3-540-31951-1.
↑ Kwok, Yu-Kwong; Ahmad, Ishfaq (1999-12-01). "Static scheduling algorithms for allocating directed task graphs to multiprocessors". ACM Computing Surveys. 31 (4): 406–471. CiteSeerX 10.1.1.322.2295 . doi:10.1145/344588.344618. ISSN 0360-0300. S2CID 207614150.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 3 4 5 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.

[2] Bruno, J.; Coffman, E. G.; Sethi, R. (1974-07-01). "Scheduling independent tasks to reduce mean finishing time". Communications of the ACM. 17 (7): 382–387. doi: 10.1145/361011.361064 . ISSN 0001-0782.

[:3-3] 1 2 Sahni, Sartaj K. (1976-01-01). "Algorithms for Scheduling Independent Tasks". Journal of the ACM. 23 (1): 116–127. doi: 10.1145/321921.321934 . ISSN 0004-5411.

[:02-4] Hochbaum, Dorit S.; Shmoys, David B. (1987-01-01). "Using dual approximation algorithms for scheduling problems theoretical and practical results". Journal of the ACM. 34 (1): 144–162. doi: 10.1145/7531.7535 . ISSN 0004-5411. S2CID 9739129.

[5] Hochbaum, Dorit S.; Shmoys, David B. (1988-06-01). "A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach". SIAM Journal on Computing. 17 (3): 539–551. doi:10.1137/0217033. ISSN 0097-5397.

[6] Epstein, Leah; Sgall, Jiri (2004-05-01). "Approximation Schemes for Schedulingon Uniformly Related and Identical Parallel Machines". Algorithmica. 39 (1): 43–57. doi:10.1007/s00453-003-1077-7. ISSN 1432-0541. S2CID 12965369.

[7] Archer, A.; Tardos, E. (2001-10-01). "Truthful mechanisms for one-parameter agents". Proceedings 42nd IEEE Symposium on Foundations of Computer Science. pp. 482–491. doi:10.1109/SFCS.2001.959924. ISBN 0-7695-1390-5. S2CID 11377808.

[8] Auletta, Vincenzo; De Prisco, Roberto; Penna, Paolo; Persiano, Giuseppe (2004). "Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines". In Diekert, Volker; Habib, Michel (eds.). Stacs 2004. Lecture Notes in Computer Science. Vol. 2996. Berlin, Heidelberg: Springer. pp. 608–619. doi:10.1007/978-3-540-24749-4_53. ISBN 978-3-540-24749-4.

[9] Ambrosio, Pasquale; Auletta, Vincenzo (2005). "Deterministic Monotone Algorithms for Scheduling on Related Machines". In Persiano, Giuseppe; Solis-Oba, Roberto (eds.). Approximation and Online Algorithms. Lecture Notes in Computer Science. Vol. 3351. Berlin, Heidelberg: Springer. pp. 267–280. doi:10.1007/978-3-540-31833-0_22. ISBN 978-3-540-31833-0.

[10] Andelman, Nir; Azar, Yossi; Sorani, Motti (2005). "Truthful Approximation Mechanisms for Scheduling Selfish Related Machines". In Diekert, Volker; Durand, Bruno (eds.). Stacs 2005. Lecture Notes in Computer Science. Vol. 3404. Berlin, Heidelberg: Springer. pp. 69–82. doi:10.1007/978-3-540-31856-9_6. ISBN 978-3-540-31856-9.

[11] Kovács, Annamária (2005). "Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines". In Brodal, Gerth Stølting; Leonardi, Stefano (eds.). Algorithms – ESA 2005. Lecture Notes in Computer Science. Vol. 3669. Berlin, Heidelberg: Springer. pp. 616–627. doi:10.1007/11561071_55. ISBN 978-3-540-31951-1.

[12] Kwok, Yu-Kwong; Ahmad, Ishfaq (1999-12-01). "Static scheduling algorithms for allocating directed task graphs to multiprocessors". ACM Computing Surveys. 31 (4): 406–471. CiteSeerX 10.1.1.322.2295 . doi:10.1145/344588.344618. ISSN 0360-0300. S2CID 207614150.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v t e Optimal job scheduling problems
One-stage jobs	Single machine Identical machines Uniform machines Unrelated machines
Multi-stage jobs	Parallel tasks Open shop Flow shop Job shop
Optimization objectives	Makespan Earliness Lateness Tardiness Throughput
Other requirements	Interval scheduling Truthful job scheduling