betaFeedback

WorksComputer Science

The Power of Migration on Identical Machines is Two

Abstract

We study the power of migration in preemptive scheduling on identical parallel machines with time windows. If an instance admits a migratory schedule on mm machines, how many machines are needed to schedule it without migration? Kalyanasundaram and Pruhs (2001) showed that 6m−56m-5 machines suffice and gave a polynomial-time construction using 12m−512m-5 machines, whereas 2m−12m-1 machines may be necessary. We close this gap, which has been open for more than 25 years: 2m−12m-1 machines always suffice, and a corresponding non-migratory schedule can be computed in strongly polynomial time. Our proof has two main technical ingredients. First, we introduce supercanonical schedules and prove that the conflict graph of every such schedule on mm machines is (2m−1)(2m-1)-colorable. The key property is that whenever a job pauses, the jobs running alongside it just before and just after the pause separate the jobs processed entirely during the pause from the rest of the conflict graph. We use these separators and Kempe exchanges to compute a coloring in polynomial time. Second, we construct a supercanonical schedule with polynomially many processing blocks by shrinking job windows as far as possible while preserving feasibility and solving a min-cost flow problem.

Introduction

In preemptive scheduling on parallel machines, a natural source of flexibility is migration: an interrupted job may resume on a different machine. Migration can make it easier to meet deadlines, but in practice it incurs communication and synchronization overhead. This raises a question: how much does migration actually help?

We study this question for scheduling jobs with time windows on identical parallel machines, in the offline setting where all jobs are known in advance. Each job has a processing time and must be processed entirely within its time window, given by a release date and a deadline. Jobs may be preempted, that is, their processing may be interrupted and resumed later, but no job may run on two machines simultaneously. A schedule is migratory if a preempted job may resume processing on a different machine, whereas in a non-migratory schedule each job is processed entirely on one machine. The power of migration measures how much the number of machines needed for a feasible schedule can increase when migration is disallowed. More precisely, for a given mm, we ask for the smallest number of machines sufficient to schedule without migration any job set that admits a feasible migratory schedule on mm machines.

Kalyanasundaram and Pruhs [13] showed that the power of migration is constant: every instance feasible with migration on mm machines admits a non-migratory schedule on 6m−56m - 5 machines. Their constructive proof yields a pseudopolynomial-time algorithm, and they also give a polynomial-time algorithm using 12m−512m - 5 machines. Conversely, a simple instance with identical release dates and deadlines shows that 2m−12m - 1 machines may be necessary [16].

In this paper, we close this gap, which has been open for more than 25 years, by proving that 2m−12m - 1 machines always suffice and constructing such a non-migratory schedule in strongly polynomial time.

Our Results and Techniques

Our main result is a sharp worst-case bound on the number of machines needed to eliminate migration.

Theorem 1. Every instance admitting a feasible migratory schedule on mm identical machines admits a feasible non-migratory schedule on 2m−12m - 1 identical machines. Such a schedule can be computed in strongly polynomial time.

The bound is tight for every mm [16]. Consider 2m−12m - 1 jobs with common window [0,1)[0,1) and processing time m/(2m−1)m/(2m - 1). McNaughton’s wrap-around rule [17] schedules them migratorily on mm machines. Since each job requires more than half the window, a non-migratory schedule needs one machine per job.

We follow the conflict-graph approach of Kalyanasundaram and Pruhs [13]. The vertices of the conflict graph are the jobs, and two jobs are adjacent whenever they are processed simultaneously. A proper coloring assigns each job to one machine and therefore gives a non-migratory realization of the schedule. The task is to construct a feasible schedule on mm machines whose conflict graph can be colored with 2m−12m - 1 colors.

Kalyanasundaram and Pruhs [13] use canonical schedules, in which jobs that complete earlier receive priority. Their density argument guarantees a vertex of low degree in every induced subgraph, yielding a coloring bound via the Szekeres–Wilf theorem [21]. We show that the conflict graph of every canonical schedule is (3m−2)(3m - 2)-colorable and that this bound is tight (Appendix § 8). Thus, canonicity alone does not suffice for the desired coloring bound.

We strengthen canonicity by excluding a second type of swap, which delays the start of a job, and call the resulting schedules supercanonical. Even for these schedules, the minimum degree of the conflict graph may exceed 2m−22m - 2, e.g., for m=2m = 2 (Appendix § 9). Thus, this minimum-degree approach does not suffice for our target bound, and we need a different coloring argument.

We show that the conflict graph of every supercanonical schedule on mm machines can be (2m−1)(2m - 1)-colored in time polynomial in the number of jobs and processing blocks (§ 3). Our key structural insight concerns pauses: whenever a job pauses, the jobs running alongside it immediately before and after the pause separate jobs processed entirely during the pause from the remaining conflict graph. We color inductively: we remove an earliest-completing job, color the rest, and reinsert the job via Kempe exchanges [15] across pause separators. Each exchange either frees a color in the neighborhood of the inserted job or decreases a potential based on the last blocks in which colors meet this job.

Our second ingredient is a strongly polynomial-time construction of a supercanonical schedule with O(n2)O(n^2) processing blocks on the original mm machines, where nn is the number of jobs (§ 4). We first shrink the job windows while preserving feasibility until no single window can be shrunk further. This excludes delay swaps and fixes the order of completion times independently of the schedule. We then optimize a min-cost flow objective that favors earlier processing of jobs that complete earlier. Together with a greedy realization of the resulting allocation, this excludes priority swaps.

Consequences and extensions Our migration-elimination theorem also has consequences for other scheduling problems. It determines the exact worst-case loss in optimal weighted throughput when migration is forbidden. On the same mm machines, a non-migratory schedule can always retain at least an m/(2m−1)m/(2m-1) fraction of the migratory optimum (§ 5.1). This guarantee is tight even for weights proportional to processing times, as shown by an example of Koren, Dar, and Amir. For feasibility, doubling the speed of the original mm machines suffices to eliminate migration, and this speedup is asymptotically optimal (§ 5.2). Under restricted assignment, however, even two eligible machines per job can force an Ω(log⁡m)\Omega(\log m) factor increase in the number of machines (§ 5.3).

Further Related Work

The migration-elimination bound of [13] is used to derive approximation and competitive guarantees for throughput maximization against a migratory optimum, both offline [14] and online [7, 8, 18].

An alternative to additional machines is speed augmentation. Chan, Lam, and To [3] give a non-migratory online algorithm on mm machines of speed 3+223+2\sqrt{2} for instances feasible migratorily on mm unit-speed machines, and show that speed 2m/(m+1)2m/(m+1) may be necessary. Devanur and Kulkarni [6] give a polynomial-time algorithm for non-migratory deadline scheduling on unrelated machines with speed augmentation 16. On identical machines, the non-migratory feasibility condition of Baruah and Fisher [1] implies a speedup bound of 4−1/m4-1/m; see § 5.2 for the derivation and comparison with our bound.

In the online setting, migration can have a much stronger effect. Chen et al. [4] show that no deterministic non-migratory online algorithm can bound its machine requirement solely by a function of the migratory offline optimum.

A related line of work studies the power of preemption, measured by the ratio between optimal non-preemptive and preemptive makespans. For jobs available at time zero, this ratio is tightly bounded by 2m/(m+1)2m/(m+1) on mm identical machines [2] and by 4 on unrelated machines [5].

Preliminaries and Coloring Tools

Let JJ be a set of nn jobs such that each job j∈Jj \in J has a processing time pj∈R>0p_j \in\mathbb{R}_{>0}, a release date rj∈R≥0r_j \in\mathbb{R}_{\ge0} and a deadline dj∈R≥0d_j \in\mathbb{R}_{\ge0}. For algorithmic statements, we assume that all numerical input data are rational and encoded in binary. Structural statements also hold for arbitrary real input data. A schedule SS of jobs JJ consists of a sequence of breakpoints b1<b2<⋯<bT+1b_1 < b_2 < \cdots< b_{T+1} and processing sets S1,…,ST⊆JS_1,\ldots,S_T \subseteq J. For each t∈[T]:={1,…,T}t \in[T] := \{1,\ldots,T\}, precisely the jobs in StS_t are processed throughout the block Bt:=[bt,bt+1)B_t := [b_t,b_{t+1}). The schedule is feasible on mm identical unit-speed machines if

∣St∣≤mfor every t∈[T],(1)|S_t| \le m \quad\text{for every } t \in[T], \tag*{(1)}
j∈St implies Bt⊆[rj,dj] for every j∈J,t∈[T], and(2)j \in S_t \text{ implies } B_t \subseteq[r_j,d_j] \text{ for every } j \in J, t \in[T], \text{ and} \tag*{(2)}
∑t∈[T]j∈St(bt+1−bt)=pjfor every job j∈J.(3)\sum_{\substack{t \in[T]\\ j \in S_t}} (b_{t+1}-b_t)=p_j \quad\text{for every job } j \in J. \tag*{(3)}

A machine realization of SS on mm machines consists of an injective assignment μt:St→{1,…,m}\mu_t:S_t\to\{1,\ldots,m\} for every t∈[T]t \in[T]. Such an assignment exists whenever ∣St∣≤m|S_t| \le m. A job may change machines between blocks, which is called migration. The realization is non-migratory if there exists a single assignment c:J→{1,…,m}c:J\to\{1,\ldots,m\} such that μt(j)=c(j)\mu_t(j)=c(j) for all t∈[T]t \in[T] and j∈Stj \in S_t.

Canonical and Supercanonical Schedules

Let SS be a feasible schedule of JJ on mm machines. For each job jj, let ρj\rho_j and δj\delta_j denote its first and last processing blocks, that is, ρj:=min⁡{t∈[T]∣j∈St}\rho_j := \min\{t \in[T] \mid j \in S_t\} and δj:=max⁡{t∈[T]∣j∈St}\delta_j := \max\{t \in[T] \mid j \in S_t\}. Let ≺\prec order the jobs by nondecreasing δj\delta_j-value, with ties broken by job index. Kalyanasundaram and Pruhs [13] introduced canonical schedules, in which jobs that complete earlier receive priority.

Definition 2. A priority swap exists for jobs j1≺j2j_1 \prec j_2 and blocks t1<t2t_1 < t_2 if ρj1≤t1\rho_{j_1} \le t_1, j2∈St1∖St2j_2 \in S_{t_1} \setminus S_{t_2}, and j1∈St2∖St1j_1 \in S_{t_2} \setminus S_{t_1}. Schedule SS is canonical if it admits no priority swap. We then call ≺\prec its canonical ordering.

Suppose there exists a priority swap for jobs j1≺j2j_1 \prec j_2 at blocks t1<t2t_1 < t_2, as in Figure 1. For small ε>0\varepsilon> 0, there is a swap, where we process j1j_1 instead of j2j_2 during [bt1,bt1+ε)[b_{t_1}, b_{t_1} + \varepsilon) and j2j_2 instead of j1j_1 during [bt2,bt2+ε)[b_{t_2}, b_{t_2} + \varepsilon). The result is again a feasible schedule (with different breakpoints). We strengthen canonicity by excluding a second configuration, which postpones the start of a job.

The configurations excluded in a supercanonical schedule

Figure 1. The configurations excluded in a supercanonical schedule. Time runs horizontally, and each job has a row, ordered by ≺\prec from bottom to top, colored whenever the job is processed. Machine assignments are not shown. Left: A priority swap for j1≺j2j_1 \prec j_2 at blocks t1<t2t_1 < t_2. Right: A delay swap for j1,j2j_1, j_2 at blocks ρj2<t\rho_{j_2} < t.

Definition 3. A delay swap exists for distinct jobs j1j_1 and j2j_2 at blocks ρj2<t\rho_{j_2} < t if ρj1<ρj2<t<δj2\rho_{j_1} < \rho_{j_2} < t < \delta_{j_2}, j1∈St∖Sρj2j_1 \in S_t \setminus S_{\rho_{j_2}}, and j2∈Sρj2∖Stj_2 \in S_{\rho_{j_2}} \setminus S_t. Schedule SS is supercanonical if it is canonical and admits no delay swap.

Thus, in a supercanonical schedule, if j1j_1 starts before j2j_2 but is not processed in Bρj2B_{\rho_{j_2}}, then it can run in a block BtB_t with t∈(ρj2,δj2)t \in(\rho_{j_2}, \delta_{j_2}) only if j2j_2 also runs in that block (Figure 1). Both canonicity and supercanonicity are preserved under deleting jobs while retaining the block partition. The remaining jobs keep their first and last processing blocks and their relative order in ≺\prec, so any swap in the restricted schedule would already exist in the original schedule. In § 4, we construct a supercanonical schedule with O(n2)O(n^2) blocks in polynomial time.

The Conflict Graph

Definition 4. The conflict graph of a schedule SS of jobs JJ is the simple undirected graph GS=(J,ES)G^S = (J, E^S), where two distinct jobs j,k∈Jj, k \in J are adjacent if there exists t∈[T]t \in[T] such that j,k∈Stj, k \in S_t, that is, both are processed in block tt.

A qq-coloring of a graph H=(V,E)H = (V, E) is a map c:V→[q]c : V \to[q] such that c(u)≠c(v)c(u) \ne c(v) for every edge {u,v}∈E\{u, v\} \in E. The smallest such qq is the chromatic number χ(H)\chi(H). Assigning jobs of each color to one machine gives a non-migratory realization, since jobs of the same color never run simultaneously. Conversely, each non-migratory realization defines a coloring. Thus, χ(GS)\chi(G^S) is the minimum number of machines needed for a non-migratory realization of SS.

For a graph H=(V,E)H = (V, E) and a vertex v∈Vv \in V, we denote the neighborhood of vv by NH(v):={u∈V∣{u,v}∈E}N_H(v) := \{u \in V \mid\{u, v\} \in E\} and its degree by dH(v):=∣NH(v)∣d_H(v) := |N_H(v)|. Moreover, for a subset of vertices U⊆VU \subseteq V, let H[U]H[U] denote the subgraph induced by UU. Our coloring argument uses Kempe exchanges [15].

References

  1. [1]Sanjay Baruah and Nathan Fisher. Non-migratory feasibility and migratory schedulability analysis of multiprocessor real-time systems. Real-Time Systems, 39(1–3):97–122, 2008.
  2. [2]Oliver Braun and Günter Schmidt. Parallel processor scheduling with limited number of preemptions. SIAM J. Comput., 32(3):671–680, 2003.DOI
  3. [3]Ho-Leung Chan, Tak Wah Lam, and Kar-Keung To. Nonmigratory online deadline scheduling on multiprocessors. SIAM J. Comput., 34(3):669–682, 2005.DOI
  4. [4]Lin Chen, Nicole Megow, and Kevin Schewior. The power of migration in online machine minimization. In SPAA, pages 175–184. ACM, 2016.DOI
  5. [5]José R. Correa, Martin Skutella, and José Verschae. The power of preemption on unrelated machines and applications to scheduling orders. Math. Oper. Res., 37(2):379–398, 2012.
  6. [6]Nikhil R. Devanur and Janardhan Kulkarni. A unified rounding algorithm for unrelated machines scheduling problems. In SPAA, pages 283–290. ACM, 2018.DOI
  7. [7]Franziska Eberle. O(1/ε) is the answer in online weighted throughput maximization. In STACS, volume 289 of LIPIcs, pages 32:1–32:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.DOI
  8. [8]Franziska Eberle, Nicole Megow, and Kevin Schewior. Online throughput maximization on unrelated machines: Commitment is no burden. ACM Trans. Algorithms, 19(1):10:1–10:25, 2023.arxiv.org/abs/1912.10769
  9. [9]Pontus Ekberg and Sanjoy K. Baruah. Partitioned scheduling of recurrent real-time tasks. In RTSS, pages 356–367. IEEE, 2021.
  10. [10]Joël Goossens, Pascal Richard, Markus Lindström, Irina Julia Lupu, and Frédéric Ridouard. Job partitioning strategies for multiprocessor scheduling of real-time periodic tasks with restricted migrations. In RTNS, pages 141–150. ACM, 2012.DOI
  11. [11]W. A. Horn. Some simple scheduling algorithms. Naval Research Logistics Quarterly, 21(1):177–185, 1974.DOI
  12. [12]Sungjin Im and Benjamin Moseley. General profit scheduling and the power of migration on heterogeneous machines. In SPAA, pages 165–173. ACM, 2016.DOI
  13. [13]Bala Kalyanasundaram and Kirk Pruhs. Eliminating migration in multi-processor scheduling. J. Algorithms, 38(1):2–24, 2001.DOI
  14. [14]George Karakostas and Stavros G. Kolliopoulos. Approximation algorithms for maximum weighted throughput on unrelated machines. Theor. Comput. Sci., 1043:115258, 2025.DOI
  15. [15]Alfred B Kempe. On the geographical problem of the four colours. American journal of mathematics, 2(3):193–200, 1879.DOI
  16. [16]Gilad Koren, Emanuel Dar, and Amihod Amir. The power of migration in multiprocessor scheduling of real-time systems. SIAM J. Comput., 30(2):511–527, 2000.DOI
  17. [17]Robert McNaughton. Scheduling with deadlines and loss functions. Management Science, 6(1):1–12, 1959.DOI
  18. [18]Benjamin Moseley, Kirk Pruhs, Clifford Stein, and Rudy Zhou. A competitive algorithm for throughput maximization on identical machines. Math. Program., 206(1–2):497–514, 2024.
  19. [19]James B. Orlin. A faster strongly polynomial minimum cost flow algorithm. Oper. Res., 41(2):338–350, 1993.
  20. [20]Kirk Pruhs and Gerhard J. Woeginger. Approximation schemes for a class of subset selection problems. Theor. Comput. Sci., 382(2):151–156, 2007.
  21. [21]George Szekeres and Herbert S Wilf. An inequality for the chromatic number of a graph. Journal of Combinatorial Theory, 4(1):1–3, 1968.DOI

Paper details

vlnc:W_qdechkvy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

ChatGPT-6 Astra, Claude Opus 5.5

View statement
Looking for related papers…
Contents