Uniform-machines scheduling

Key takeaways

Uniform-machines scheduling belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Uniform-machines scheduling to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Uniform-machines scheduling from memory before moving on to harder problems.

Reference excerpt

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. 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 {\displaystyle 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|| ∑ C i {\displaystyle \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|| ∑ w i C i {\displaystyle \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, P|| ∑ C i {\displaystyle \sum C_{i}} . Horowitz and Sahni present an exact algorithm, with run time O(n log m n), for minimizing the average completion time on uniform machines, Q|| ∑ C i {\displaystyle \sum C_{i}} . Bruno, Coffman and Sethi present an algorithm, running in time O ( max ( m n 2 , n 3 ) ) {\displaystyle O(\max(mn^{2},n^{3}))} , for minimizing the average completion time on unrelated machines, R|| ∑ C i {\displaystyle \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. It is NP-hard even if the number of machines is fixed and at least 2, by reduction from the partition problem. Sahni presents an exponential-time algorithm and a polynomial-time approximation algorithm for identical machines. Horowitz and Sahni 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 ) {\displaystyle O(10^{l}n^{2})} = O ( n 2 / ϵ ) {\displaystyle 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 presented:

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Uniform-machines scheduling

Start with the simplest possible case. Write down what Uniform-machines scheduling claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Uniform-machines scheduling before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Uniform-machines scheduling ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Uniform-machines scheduling

In research: Uniform-machines scheduling appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Uniform-machines scheduling in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Uniform-machines scheduling is common in secondary-school and first-year university syllabi. It links to neighbouring topics NP-complete problems, Optimal scheduling, so understanding it makes those chapters shorter.
In everyday life: Look for Uniform-machines scheduling outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

How to study Uniform-machines scheduling in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Uniform-machines scheduling means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Uniform-machines scheduling out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Uniform-machines scheduling in simple terms?

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.

Why does Uniform-machines scheduling matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Uniform-machines scheduling?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Uniform-machines scheduling.