Uniform-machines scheduling

Last updated

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 J1, J2, ..., Jn 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 pi,j. In the general case, the times pi,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 si, and the run-time of job j on machine i is pi,j = pj / si.

Contents

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||" 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||. 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||.

Algorithms

Minimizing the average completion time

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

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:

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:

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 Ci (for i between 1 and m) be the makespan of machine i in a given schedule. Instead of minimizing the objective function max(Ci), one can minimize the objective function max(f(Ci)), where f is any fixed function. Similarly, one can minimize the objective function sum(f(Ci)).

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:

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.

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.

<span class="mw-page-title-main">Time complexity</span> Estimate of time taken for running an algorithm

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 J1, J2, ..., Jn 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 J1J2, ..., 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. In the specific variant known as job-shop scheduling, each job consists of a set of operationsO1O2, ..., On 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 J1J2, ..., 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. 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 J1J2, ..., Jn 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 pj and a size parameter qj, and it must run for exactly pj time-steps on exactly qj 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 J1, J2, ..., Jn 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 J1, J2, ..., Jn 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 pi,j. The term unrelated emphasizes that there is no relation between values of pi,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj, and identical-machines scheduling - in which pi,j = pi.

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:

  1. Order the jobs by descending order of their processing-time, such that the job with the longest processing time is first.
  2. 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 mk. 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. 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. 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.
  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.