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 m m m , we ask for the smallest number of machines sufficient to schedule without migration any job set that admits a feasible migratory schedule on m m m machines.
Kalyanasundaram and Pruhs [13 ] showed that the power of migration is constant: every instance feasible with migration on m m m machines admits a non-migratory schedule on 6 m − 5 6m - 5 6 m − 5 machines. Their constructive proof yields a pseudopolynomial-time algorithm, and they also give a polynomial-time algorithm using 12 m − 5 12m - 5 12 m − 5 machines. Conversely, a simple instance with identical release dates and deadlines shows that 2 m − 1 2m - 1 2 m − 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 2 m − 1 2m - 1 2 m − 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 m m m identical machines admits a feasible non-migratory schedule on 2 m − 1 2m - 1 2 m − 1 identical machines. Such a schedule can be computed in strongly polynomial time.
The bound is tight for every m m m [16 ] . Consider 2 m − 1 2m - 1 2 m − 1 jobs with common window [ 0 , 1 ) [0,1) [ 0 , 1 ) and processing time m / ( 2 m − 1 ) m/(2m - 1) m / ( 2 m − 1 ) . McNaughton’s wrap-around rule [17 ] schedules them migratorily on m m m 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 m m m machines whose conflict graph can be colored with 2 m − 1 2m - 1 2 m − 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 ( 3 m − 2 ) (3m - 2) ( 3 m − 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 2 m − 2 2m - 2 2 m − 2 , e.g., for m = 2 m = 2 m = 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 m m m machines can be ( 2 m − 1 ) (2m - 1) ( 2 m − 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 ( n 2 ) O(n^2) O ( n 2 ) processing blocks on the original m m m machines, where n n n 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 m m m machines, a non-migratory schedule can always retain at least an m / ( 2 m − 1 ) m/(2m-1) m / ( 2 m − 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 m m m 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) Ω ( 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 m m m machines of speed 3 + 2 2 3+2\sqrt{2} 3 + 2 2 for instances feasible migratorily on m m m unit-speed machines, and show that speed 2 m / ( m + 1 ) 2m/(m+1) 2 m / ( 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 / m 4-1/m 4 − 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 2 m / ( m + 1 ) 2m/(m+1) 2 m / ( m + 1 ) on m m m identical machines [2 ] and by 4 on unrelated machines [5 ] .
Preliminaries and Coloring Tools
Let J J J be a set of n n n jobs such that each job j ∈ J j \in J j ∈ J has a processing time p j ∈ R > 0 p_j \in\mathbb{R}_{>0} p j ∈ R > 0 , a release date r j ∈ R ≥ 0 r_j \in\mathbb{R}_{\ge0} r j ∈ R ≥ 0 and a deadline d j ∈ R ≥ 0 d_j \in\mathbb{R}_{\ge0} d j ∈ R ≥ 0 . 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 S S S of jobs J J J consists of a sequence of breakpoints b 1 < b 2 < ⋯ < b T + 1 b_1 < b_2 < \cdots< b_{T+1} b 1 < b 2 < ⋯ < b T + 1 and processing sets S 1 , … , S T ⊆ J S_1,\ldots,S_T \subseteq J S 1 , … , S T ⊆ J . For each t ∈ [ T ] : = { 1 , … , T } t \in[T] := \{1,\ldots,T\} t ∈ [ T ] := { 1 , … , T } , precisely the jobs in S t S_t S t are processed throughout the block B t : = [ b t , b t + 1 ) B_t := [b_t,b_{t+1}) B t := [ b t , b t + 1 ) . The schedule is feasible on m m m identical unit-speed machines if
∣ S t ∣ ≤ m for every t ∈ [ T ] , (1) |S_t| \le m \quad\text{for every } t \in[T], \tag*{(1)} ∣ S t ∣ ≤ m for every t ∈ [ T ] , (1)
j ∈ S t implies B t ⊆ [ r j , d j ] 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)} j ∈ S t implies B t ⊆ [ r j , d j ] for every j ∈ J , t ∈ [ T ] , and (2)
∑ t ∈ [ T ] j ∈ S t ( b t + 1 − b t ) = p j for 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)} t ∈ [ T ] j ∈ S t ∑ ( b t + 1 − b t ) = p j for every job j ∈ J . (3)
A machine realization of S S S on m m m machines consists of an injective assignment μ t : S t → { 1 , … , m } \mu_t:S_t\to\{1,\ldots,m\} μ t : S t → { 1 , … , m } for every t ∈ [ T ] t \in[T] t ∈ [ T ] . Such an assignment exists whenever ∣ S t ∣ ≤ m |S_t| \le m ∣ S t ∣ ≤ 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\} c : J → { 1 , … , m } such that μ t ( j ) = c ( j ) \mu_t(j)=c(j) μ t ( j ) = c ( j ) for all t ∈ [ T ] t \in[T] t ∈ [ T ] and j ∈ S t j \in S_t j ∈ S t .
Canonical and Supercanonical Schedules
Let S S S be a feasible schedule of J J J on m m m machines. For each job j j j , let ρ j \rho_j ρ j and δ j \delta_j δ j denote its first and last processing blocks, that is, ρ j : = min { t ∈ [ T ] ∣ j ∈ S t } \rho_j := \min\{t \in[T] \mid j \in S_t\} ρ j := min { t ∈ [ T ] ∣ j ∈ S t } and δ j : = max { t ∈ [ T ] ∣ j ∈ S t } \delta_j := \max\{t \in[T] \mid j \in S_t\} δ j := max { t ∈ [ T ] ∣ j ∈ S t } . Let ≺ \prec ≺ order the jobs by nondecreasing δ j \delta_j δ 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 j 1 ≺ j 2 j_1 \prec j_2 j 1 ≺ j 2 and blocks t 1 < t 2 t_1 < t_2 t 1 < t 2 if ρ j 1 ≤ t 1 \rho_{j_1} \le t_1 ρ j 1 ≤ t 1 , j 2 ∈ S t 1 ∖ S t 2 j_2 \in S_{t_1} \setminus S_{t_2} j 2 ∈ S t 1 ∖ S t 2 , and j 1 ∈ S t 2 ∖ S t 1 j_1 \in S_{t_2} \setminus S_{t_1} j 1 ∈ S t 2 ∖ S t 1 . Schedule S S S is canonical if it admits no priority swap. We then call ≺ \prec ≺ its canonical ordering .
Suppose there exists a priority swap for jobs j 1 ≺ j 2 j_1 \prec j_2 j 1 ≺ j 2 at blocks t 1 < t 2 t_1 < t_2 t 1 < t 2 , as in Figure 1 . For small ε > 0 \varepsilon> 0 ε > 0 , there is a swap, where we process j 1 j_1 j 1 instead of j 2 j_2 j 2 during [ b t 1 , b t 1 + ε ) [b_{t_1}, b_{t_1} + \varepsilon) [ b t 1 , b t 1 + ε ) and j 2 j_2 j 2 instead of j 1 j_1 j 1 during [ b t 2 , b t 2 + ε ) [b_{t_2}, b_{t_2} + \varepsilon) [ b t 2 , b t 2 + ε ) . 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.
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 j 1 ≺ j 2 j_1 \prec j_2 j 1 ≺ j 2 at blocks t 1 < t 2 t_1 < t_2 t 1 < t 2 . Right: A delay swap for j 1 , j 2 j_1, j_2 j 1 , j 2 at blocks ρ j 2 < t \rho_{j_2} < t ρ j 2 < t .
Definition 3. A delay swap exists for distinct jobs j 1 j_1 j 1 and j 2 j_2 j 2 at blocks ρ j 2 < t \rho_{j_2} < t ρ j 2 < t if ρ j 1 < ρ j 2 < t < δ j 2 \rho_{j_1} < \rho_{j_2} < t < \delta_{j_2} ρ j 1 < ρ j 2 < t < δ j 2 , j 1 ∈ S t ∖ S ρ j 2 j_1 \in S_t \setminus S_{\rho_{j_2}} j 1 ∈ S t ∖ S ρ j 2 , and j 2 ∈ S ρ j 2 ∖ S t j_2 \in S_{\rho_{j_2}} \setminus S_t j 2 ∈ S ρ j 2 ∖ S t . Schedule S S S is supercanonical if it is canonical and admits no delay swap.
Thus, in a supercanonical schedule, if j 1 j_1 j 1 starts before j 2 j_2 j 2 but is not processed in B ρ j 2 B_{\rho_{j_2}} B ρ j 2 , then it can run in a block B t B_t B t with t ∈ ( ρ j 2 , δ j 2 ) t \in(\rho_{j_2}, \delta_{j_2}) t ∈ ( ρ j 2 , δ j 2 ) only if j 2 j_2 j 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 ( n 2 ) O(n^2) O ( n 2 ) blocks in polynomial time.
The Conflict Graph
Definition 4. The conflict graph of a schedule S S S of jobs J J J is the simple undirected graph G S = ( J , E S ) G^S = (J, E^S) G S = ( J , E S ) , where two distinct jobs j , k ∈ J j, k \in J j , k ∈ J are adjacent if there exists t ∈ [ T ] t \in[T] t ∈ [ T ] such that j , k ∈ S t j, k \in S_t j , k ∈ S t , that is, both are processed in block t t t .
A q q q -coloring of a graph H = ( V , E ) H = (V, E) H = ( V , E ) is a map c : V → [ q ] c : V \to[q] c : V → [ q ] such that c ( u ) ≠ c ( v ) c(u) \ne c(v) c ( u ) = c ( v ) for every edge { u , v } ∈ E \{u, v\} \in E { u , v } ∈ E . The smallest such q q q is the chromatic number χ ( H ) \chi(H) χ ( 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, χ ( G S ) \chi(G^S) χ ( G S ) is the minimum number of machines needed for a non-migratory realization of S S S .
For a graph H = ( V , E ) H = (V, E) H = ( V , E ) and a vertex v ∈ V v \in V v ∈ V , we denote the neighborhood of v v v by N H ( v ) : = { u ∈ V ∣ { u , v } ∈ E } N_H(v) := \{u \in V \mid\{u, v\} \in E\} N H ( v ) := { u ∈ V ∣ { u , v } ∈ E } and its degree by d H ( v ) : = ∣ N H ( v ) ∣ d_H(v) := |N_H(v)| d H ( v ) := ∣ N H ( v ) ∣ . Moreover, for a subset of vertices U ⊆ V U \subseteq V U ⊆ V , let H [ U ] H[U] H [ U ] denote the subgraph induced by U U U . Our coloring argument uses Kempe exchanges [15 ] .
Definition 5. Let c : V → [ q ] c: V \to[q] c : V → [ q ] be a coloring of a graph H = ( V , E ) H=(V,E) H = ( V , E ) , let a , b ∈ [ q ] a,b \in[q] a , b ∈ [ q ] be distinct colors, and let H a , b ( c ) : = H [ { v ∈ V ∣ c ( v ) ∈ { a , b } } ] H_{a,b}(c):=H[\{v \in V \mid c(v) \in\{a,b\}\}] H a , b ( c ) := H [{ v ∈ V ∣ c ( v ) ∈ { a , b }}] . For a union W W W of connected components of H a , b ( c ) H_{a,b}(c) H a , b ( c ) , the ( a , b ) (a,b) ( a , b ) -Kempe exchange on W W W interchanges the colors a a a and b b b on W W W and keeps all other colors.
A Kempe exchange produces another valid coloring, since every edge leaving W W W has its other endpoint colored neither a a a nor b b b .
For U ⊆ V U \subseteq V U ⊆ V , we define the external boundary of U U U in graph H = ( V , E ) H=(V,E) H = ( V , E ) by
∂ H U : = { v ∈ V ∖ U ∣ { u , v } ∈ E for some u ∈ U } . \partial_H U := \{v \in V \setminus U \mid\{u,v\} \in E \text{ for some } u \in U\}. ∂ H U := { v ∈ V ∖ U ∣ { u , v } ∈ E for some u ∈ U } .
If the boundary avoids two colors, these colors can be interchanged inside U U U .
Lemma 6. Let c : V → [ q ] c: V \to[q] c : V → [ q ] be a coloring of H = ( V , E ) H=(V,E) H = ( V , E ) , let U ⊆ V U \subseteq V U ⊆ V , and let a , b ∈ [ q ] a,b \in[q] a , b ∈ [ q ] be distinct colors that do not appear on ∂ H U \partial_H U ∂ H U . Then interchanging a a a and b b b on U U U yields a coloring that is an ( a , b ) (a,b) ( a , b ) -Kempe exchange.
Proof. Let W : = { u ∈ U : c ( u ) ∈ { a , b } } W := \{u \in U : c(u) \in\{a,b\}\} W := { u ∈ U : c ( u ) ∈ { a , b }} . An edge of H a , b ( c ) H_{a,b}(c) H a , b ( c ) leaving W W W would end at a vertex of ∂ H U \partial_H U ∂ H U with color a a a or b b b , which does not exist. Hence, W W W is a union of components of H a , b ( c ) H_{a,b}(c) H a , b ( c ) , so interchanging a a a and b b b on W W W is a Kempe exchange and produces a coloring.
Coloring the Conflict Graph
In this section, we prove the machine bound of Theorem 1 . Given a supercanonical schedule on m m m machines, we color its conflict graph with 2 m − 1 2m-1 2 m − 1 colors in strongly polynomial time. In § 4 , we show how to compute such a schedule.
Throughout this section, let S S S be a supercanonical schedule of J J J on m m m machines with canonical ordering ≺ \prec ≺ . Denote G : = G S G := G^S G := G S and N ( k ) : = N G ( k ) N(k) := N_G(k) N ( k ) := N G ( k ) .
Latest Common Blocks
For adjacent jobs j j j and k k k , define the last block in which both are processed by
L j k : = max { t ∈ [ T ] ∣ j , k ∈ S t } . L_{jk} := \max\{t \in[T] \mid j,k \in S_t\}. L j k := max { t ∈ [ T ] ∣ j , k ∈ S t } .
We show that once two neighbors k ≺ j k \prec j k ≺ j stop running together, job j j j does not run again until k k k has completed.
Lemma 7. Let k ∈ J k \in J k ∈ J and j ∈ N ( k ) j \in N(k) j ∈ N ( k ) with k ≺ j k \prec j k ≺ j . Then j ∉ S t j \notin S_t j ∈ / S t for every block t t t with L j k < t ≤ δ k L_{jk}<t\leq\delta_k L j k < t ≤ δ k .
Proof. Suppose for contradiction that j ∈ S t j \in S_t j ∈ S t for some block t t t with L j k < t ≤ δ k L_{jk}<t\leq\delta_k L j k < t ≤ δ k . Since t t t and δ k \delta_k δ k both exceed L j k L_{jk} L j k , maximality of L j k L_{jk} L j k gives k ∉ S t k \notin S_t k ∈ / S t and, as k ∈ S δ k k \in S_{\delta_k} k ∈ S δ k , also j ∉ S δ k j \notin S_{\delta_k} j ∈ / S δ k . Hence t ≠ δ k t \ne\delta_k t = δ k , so t < δ k t<\delta_k t < δ k . Moreover, we have ρ k ≤ L j k < t \rho_k \leq L_{jk}<t ρ k ≤ L j k < t . Thus, there is a priority swap for k ≺ j k \prec j k ≺ j at blocks t < δ k t<\delta_k t < δ k , contradicting canonicity.
Separators at Pauses
We show that whenever a job pauses, the jobs running together with it immediately before and after the pause separate the jobs processed entirely during the pause from the rest of the conflict graph. A pause of job k k k is a maximal nonempty sequence of blocks in which k k k does not run, preceded and followed by blocks in which it runs; see Figure 2 . Let t 1 t_1 t 1 and t 2 t_2 t 2 denote the blocks immediately before and after such a pause. We define
Figure 2. Schematic illustration of Theorems 8 and 9, with colors a a a (red), b b b (green), and other colors (gray), where f f f is uncolored. Left: Job p p p pauses between blocks t 1 t_1 t 1 and t 2 t_2 t 2 . The jobs in U = { u 1 , u 2 } U = \{u_1, u_2\} U = { u 1 , u 2 } are processed only during the pause, and Z = { f , z } Z = \{f, z\} Z = { f , z } contains the other jobs in B t 1 B_{t_1} B t 1 and B t 2 B_{t_2} B t 2 . Color a a a last meets f f f in B t 1 B_{t_1} B t 1 via p p p , while color b b b meets f f f later via u 1 u_1 u 1 . Middle: The conflict graph with coloring c c c , in which Z Z Z separates U U U from p p p and x x x , and Z ′ = { z } Z' = \{z\} Z ′ = { z } misses the colors a a a and b b b . Right: Exchanging a a a and b b b on U U U yields c ′ c' c ′ , in which only x x x has color b b b among the neighbors of f f f , so λ b ( c ′ ) < t 1 = λ a ( c ) \lambda_b(c') < t_1 = \lambda_a(c) λ b ( c ′ ) < t 1 = λ a ( c ) .
Z : = ( S t 1 ∪ S t 2 ) ∖ { k } and U : = { j ∈ J ∣ [ ρ j , δ j ] ⊆ ( t 1 , t 2 ) } . Z := (S_{t_1} \cup S_{t_2}) \setminus\{k\}
\qquad\text{and}\qquad
U := \{j \in J \mid[\rho_j,\delta_j] \subseteq(t_1,t_2)\}. Z := ( S t 1 ∪ S t 2 ) ∖ { k } and U := { j ∈ J ∣ [ ρ j , δ j ] ⊆ ( t 1 , t 2 )} .
Thus, Z Z Z consists of the jobs sharing block t 1 t_1 t 1 or t 2 t_2 t 2 with job k k k , and U U U consists of the jobs processed entirely during the pause. In particular, Z ∩ U = ∅ Z \cap U = \varnothing Z ∩ U = ∅ and ∣ Z ∣ ≤ 2 m − 2 |Z| \le2m - 2 ∣ Z ∣ ≤ 2 m − 2 , since S t 1 S_{t_1} S t 1 and S t 2 S_{t_2} S t 2 each contain job k k k and at most m − 1 m - 1 m − 1 other jobs.
Lemma 8. Every job processed in some block t t t with t 1 < t < t 2 t_1 < t < t_2 t 1 < t < t 2 belongs to Z ∪ U Z \cup U Z ∪ U . Consequently, the external boundary satisfies ∂ G U ⊆ Z \partial_G U \subseteq Z ∂ G U ⊆ Z .
Proof. Let j ∈ S t j \in S_t j ∈ S t for some t 1 < t < t 2 t_1 < t < t_2 t 1 < t < t 2 , and suppose that j ∉ Z j \notin Z j ∈ / Z . Then j ≠ k j \ne k j = k and j ∉ S t 1 ∪ S t 2 j \notin S_{t_1} \cup S_{t_2} j ∈ / S t 1 ∪ S t 2 . First, we show that j ≺ k j \prec k j ≺ k . Otherwise, k ≺ j k \prec j k ≺ j , and a priority swap exists for k ≺ j k \prec j k ≺ j at blocks t < t 2 t < t_2 t < t 2 , since ρ k ≤ t 1 < t \rho_k \le t_1 < t ρ k ≤ t 1 < t , j ∈ S t ∖ S t 2 j \in S_t \setminus S_{t_2} j ∈ S t ∖ S t 2 , and k ∈ S t 2 ∖ S t k \in S_{t_2} \setminus S_t k ∈ S t 2 ∖ S t . Next, we show that t 1 < ρ j t_1 < \rho_j t 1 < ρ j . Otherwise, ρ j < t 1 \rho_j < t_1 ρ j < t 1 since j ∉ S t 1 j \notin S_{t_1} j ∈ / S t 1 , and a priority swap exists for j ≺ k j \prec k j ≺ k at blocks t 1 < t t_1 < t t 1 < t , since ρ j < t 1 \rho_j < t_1 ρ j < t 1 , k ∈ S t 1 ∖ S t k \in S_{t_1} \setminus S_t k ∈ S t 1 ∖ S t , and j ∈ S t ∖ S t 1 j \in S_t \setminus S_{t_1} j ∈ S t ∖ S t 1 . Finally, we show that δ j < t 2 \delta_j < t_2 δ j < t 2 . Otherwise, t 2 < δ j t_2 < \delta_j t 2 < δ j since j ∉ S t 2 j \notin S_{t_2} j ∈ / S t 2 . Then ρ k ≤ t 1 < ρ j ≤ t < t 2 < δ j \rho_k \le t_1 < \rho_j \le t < t_2 < \delta_j ρ k ≤ t 1 < ρ j ≤ t < t 2 < δ j , k ∉ S ρ j k \notin S_{\rho_j} k ∈ / S ρ j , k ∈ S t 2 k \in S_{t_2} k ∈ S t 2 , and j ∉ S t 2 j \notin S_{t_2} j ∈ / S t 2 , so a delay swap exists for k k k , j j j , and block t 2 t_2 t 2 . Hence, j ∈ U j \in U j ∈ U .
For ∂ G U ⊆ Z \partial_G U \subseteq Z ∂ G U ⊆ Z , let u ∈ U u \in U u ∈ U and v ∉ U v \notin U v ∈ / U be adjacent, and let t t t be a block with u , v ∈ S t u,v \in S_t u , v ∈ S t . Then t 1 < ρ u ≤ t ≤ δ u < t 2 t_1 < \rho_u \le t \le\delta_u < t_2 t 1 < ρ u ≤ t ≤ δ u < t 2 , so v ∈ Z v \in Z v ∈ Z by the first statement. □
Thus, Z Z Z separates U U U from J ∖ ( Z ∪ U ) J \setminus(Z \cup U) J ∖ ( Z ∪ U ) in G G G (cf. Figure 2 ). By Theorem 6, any two colors absent from Z Z Z can therefore be interchanged on U U U .
Recoloring
Let q : = 2 m − 1 q := 2m - 1 q := 2 m − 1 , let f f f be the first job in ≺ \prec ≺ , and write G − f : = G [ J ∖ { f } ] G - f := G[J \setminus\{f\}] G − f := G [ J ∖ { f }] . Since deleting f f f preserves supercanonicity, we may assume by induction that G − f G - f G − f has a q q q -coloring. We recolor it by Kempe exchanges until some color is missing on the neighborhood N ( f ) N(f) N ( f ) , which we then assign to job f f f .
Let c c c be a q q q -coloring of G − f G - f G − f such that all q q q colors appear on N ( f ) N(f) N ( f ) . For each color a ∈ [ q ] a \in[q] a ∈ [ q ] , define the last block in which an a a a -color job runs with f f f by
λ a ( c ) : = max { t ∈ [ T ] ∣ f ∈ S t and c ( j ) = a for some j ∈ S t ∖ { f } } . \lambda_a(c) := \max\{t \in[T] \mid f \in S_t \text{ and } c(j) = a \text{ for some } j \in S_t \setminus\{f\}\}. λ a ( c ) := max { t ∈ [ T ] ∣ f ∈ S t and c ( j ) = a for some j ∈ S t ∖ { f }} .
Moreover, let Φ ( c ) : = min a ∈ [ q ] λ a ( c ) \Phi(c) := \min_{a\in[q]} \lambda_a(c) Φ ( c ) := min a ∈ [ q ] λ a ( c ) be the earliest such block over all colors. We choose a color whose last encounter with job f f f occurs earliest. A local exchange then ensures that another color appears alongside f f f only before that block.
Lemma 9 (Recoloring lemma). Let c c c be a q q q -coloring of G − f G-f G − f in which all q q q colors appear on N ( f ) N(f) N ( f ) . Then a Kempe exchange yields a q q q -coloring c ′ c' c ′ of G − f G-f G − f such that ∣ c ′ ( N ( f ) ) ∣ ≤ q − 1 |c'(N(f))| \le q-1 ∣ c ′ ( N ( f )) ∣ ≤ q − 1 or Φ ( c ′ ) < Φ ( c ) \Phi(c') < \Phi(c) Φ ( c ′ ) < Φ ( c ) .
Proof. Let a a a be a color with λ a ( c ) = Φ ( c ) \lambda_a(c) = \Phi(c) λ a ( c ) = Φ ( c ) , let t 1 : = λ a ( c ) t_1 := \lambda_a(c) t 1 := λ a ( c ) , and let p ∈ S t 1 ∖ { f } p \in S_{t_1} \setminus\{f\} p ∈ S t 1 ∖ { f } with c ( p ) = a c(p) = a c ( p ) = a . Then L f p = t 1 L_{fp} = t_1 L f p = t 1 . Block δ f \delta_f δ f contains at most m − 1 < q m-1 < q m − 1 < q jobs besides f f f , so some color does not appear there, and thus t 1 < δ f t_1 < \delta_f t 1 < δ f by definition of Φ \Phi Φ . Since f ≺ p f \prec p f ≺ p , we have δ f ≤ δ p \delta_f \le\delta_p δ f ≤ δ p , and Theorem 7 gives p ∉ S t p \notin S_t p ∈ / S t for all t 1 < t ≤ δ f t_1 < t \le\delta_f t 1 < t ≤ δ f . Hence, job p p p has a next processing block t 2 t_2 t 2 after t 1 t_1 t 1 , and δ f < t 2 \delta_f < t_2 δ f < t 2 .
Let Z Z Z and U U U be the sets of § 3.2 for the pause of p p p between t 1 t_1 t 1 and t 2 t_2 t 2 , and let Z ′ : = Z ∖ { f } Z' := Z \setminus\{f\} Z ′ := Z ∖ { f } . Since f ∈ S t 1 ∖ S t 2 f \in S_{t_1} \setminus S_{t_2} f ∈ S t 1 ∖ S t 2 ,
∣ Z ′ ∣ = ∣ ( S t 1 ∪ S t 2 ) ∖ { f , p } ∣ ≤ ( m − 2 ) + ( m − 1 ) = q − 2. |Z'| = |(S_{t_1} \cup S_{t_2}) \setminus\{f,p\}| \le(m-2) + (m-1) = q-2. ∣ Z ′ ∣ = ∣ ( S t 1 ∪ S t 2 ) ∖ { f , p } ∣ ≤ ( m − 2 ) + ( m − 1 ) = q − 2.
All jobs in Z ′ Z' Z ′ are adjacent to p p p , so color a a a is absent from Z ′ Z' Z ′ . Furthermore, some color b ≠ a b \ne a b = a is also absent from Z ′ Z' Z ′ . By Theorem 8, ∂ G − f U ⊆ Z ′ \partial_{G-f} U \subseteq Z' ∂ G − f U ⊆ Z ′ , so interchanging a a a and b b b on U U U is a Kempe exchange by Theorem 6. Let c ′ c' c ′ be the resulting coloring, which agrees with c c c outside U U U .
Suppose that all q q q colors still appear on N ( f ) N(f) N ( f ) under c ′ c' c ′ . Let j j j be a neighbor of f f f with c ′ ( j ) = b c'(j) = b c ′ ( j ) = b , and let t t t be a block with f , j ∈ S t f,j \in S_t f , j ∈ S t . We show that t < t 1 t < t_1 t < t 1 . If t = t 1 t = t_1 t = t 1 , then j ∈ S t 1 ∖ { f , p } ⊆ Z ′ j \in S_{t_1} \setminus\{f,p\} \subseteq Z' j ∈ S t 1 ∖ { f , p } ⊆ Z ′ , since c ′ ( p ) = a c'(p) = a c ′ ( p ) = a . This contradicts the absence of color b b b from Z ′ Z' Z ′ , where c ′ c' c ′ agrees with c c c . If t > t 1 t > t_1 t > t 1 , then t 1 < t ≤ δ f < t 2 t_1 < t \le\delta_f < t_2 t 1 < t ≤ δ f < t 2 , so Theorem 8 gives j ∈ Z ′ ∪ U j \in Z' \cup U j ∈ Z ′ ∪ U . Again j ∉ Z ′ j \notin Z' j ∈ / Z ′ , so j ∈ U j \in U j ∈ U , and hence c ( j ) = a c(j) = a c ( j ) = a . This contradicts λ a ( c ) = t 1 \lambda_a(c) = t_1 λ a ( c ) = t 1 . Therefore every job of color b b b meets f f f only before t 1 t_1 t 1 , and consequently Φ ( c ′ ) ≤ λ b ( c ′ ) < t 1 = Φ ( c ) \Phi(c') \le\lambda_b(c') < t_1 = \Phi(c) Φ ( c ′ ) ≤ λ b ( c ′ ) < t 1 = Φ ( c ) . ∎
We now prove that the power of migration is two. Inductively applying Theorem 9 yields the coloring in strongly polynomial time.
Theorem 10. Given a supercanonical schedule S S S of n n n jobs on m m m machines with T T T blocks, a ( 2 m − 1 ) (2m-1) ( 2 m − 1 ) -coloring of the conflict graph G S G^S G S can be computed in time polynomial in n n n and T T T , independently of the numerical input data.
Proof. We may assume m < n m < n m < n as otherwise each job could receive a distinct color. We use induction on n n n . The base case n = 0 n = 0 n = 0 is trivial. Let f f f be the first job in ≺ \prec ≺ . Since deleting f f f preserves supercanonicity, induction yields a q q q -coloring of G − f G-f G − f . We apply Theorem 9 while all q q q colors appear on N ( f ) N(f) N ( f ) , which frees a color or decreases the integer Φ ∈ [ ρ f , δ f ] \Phi\in[\rho_f,\delta_f] Φ ∈ [ ρ f , δ f ] . Hence, after at most T T T applications, some color is missing on N ( f ) N(f) N ( f ) , which we assign to f f f .
After precomputing all ρ j \rho_j ρ j and δ j \delta_j δ j in O ( m T ) O(mT) O ( m T ) time, each application of Theorem 9 takes O ( m T + n ) O(mT+n) O ( m T + n ) time. Indeed, one scan over the blocks yields all λ a \lambda_a λ a , the job p p p , and the block t 2 t_2 t 2 , and the sets U U U and Z ′ Z' Z ′ and the exchange take O ( m + n ) O(m+n) O ( m + n ) time. Since each of the n n n insertions requires at most T T T applications, the total running time is O ( n T ( m T + n ) ) O(nT(mT+n)) O ( n T ( m T + n )) . ∎
Constructing Supercanonical Schedules
We show that every instance feasible on m m m machines admits a supercanonical schedule with O ( n 2 ) O(n^2) O ( n 2 ) blocks, computable in strongly polynomial time. We first shrink windows to exclude delay swaps (§ 4.1 ), then compute and realize a min-cost allocation to exclude priority swaps (§ 4.2 ).
Window-Minimal Instances
A delay swap postpones a job’s first processing and thereby permits its window to shrink; see Figure 1 . We therefore shrink windows as far as feasibility allows.
Definition 11. An instance is window-minimal on m m m machines if it is feasible on m m m machines, but becomes infeasible when the window of any single job j j j is replaced by [ R j , D j ) ⊊ [ r j , d j ) [R_j,D_j) \subsetneq[r_j,d_j) [ R j , D j ) ⊊ [ r j , d j ) .
Any schedule of a window-minimal instance satisfies r j = b ρ j r_j=b_{\rho_j} r j = b ρ j and d j = b δ j + 1 d_j=b_{\delta_j+1} d j = b δ j + 1 .
Lemma 12. A schedule of a window-minimal instance admits no delay swap.
Proof. Suppose that a delay swap exists for jobs j 1 j_1 j 1 and j 2 j_2 j 2 at blocks ρ j 2 < t \rho_{j_2}<t ρ j 2 < t . For 0 < ε ≤ min { ∣ B ρ j 2 ∣ , ∣ B t ∣ } 0<\varepsilon\le\min\{|B_{\rho_{j_2}}|,|B_t|\} 0 < ε ≤ min { ∣ B ρ j 2 ∣ , ∣ B t ∣ } , we process j 1 j_1 j 1 instead of j 2 j_2 j 2 during [ b ρ j 2 , b ρ j 2 + ε ) [b_{\rho_{j_2}},b_{\rho_{j_2}}+\varepsilon) [ b ρ j 2 , b ρ j 2 + ε ) and j 2 j_2 j 2 instead of j 1 j_1 j 1 during [ b t , b t + ε ) [b_t,b_t+\varepsilon) [ b t , b t + ε ) . The number of running jobs and all processing amounts are unchanged, and no job runs twice at a time, since j 1 ∉ S ρ j 2 j_1\notin S_{\rho_{j_2}} j 1 ∈ / S ρ j 2 and j 2 ∉ S t j_2\notin S_t j 2 ∈ / S t . Both new pieces lie in their windows, since r j 1 ≤ b ρ j 1 < b ρ j 2 r_{j_1}\le b_{\rho_{j_1}}<b_{\rho_{j_2}} r j 1 ≤ b ρ j 1 < b ρ j 2 , b t + 1 ≤ d j 1 b_{t+1}\le d_{j_1} b t + 1 ≤ d j 1 by j 1 ∈ S t j_1\in S_t j 1 ∈ S t , and b t + 1 ≤ b δ j 2 < d j 2 b_{t+1}\le b_{\delta_{j_2}}<d_{j_2} b t + 1 ≤ b δ j 2 < d j 2 . In the resulting feasible schedule, j 2 j_2 j 2 is processed only within [ r j 2 + ε , d j 2 ) [r_{j_2}+\varepsilon,d_{j_2}) [ r j 2 + ε , d j 2 ) , contradicting window-minimality. □
Next, we compute window-minimal windows [ R j , D j ) ⊆ [ r j , d j ) [R_j,D_j)\subseteq[r_j,d_j) [ R j , D j ) ⊆ [ r j , d j ) . Initially, [ R j , D j ) : = [ r j , d j ) [R_j,D_j):=[r_j,d_j) [ R j , D j ) := [ r j , d j ) . We process the jobs once in a fixed order and, for each job j j j , first maximize R j R_j R j and then minimize D j D_j D j , keeping all other endpoints fixed. Since later updates only shrink other windows, an endpoint that cannot be improved now cannot be improved later.
We maintain a set A A A of event points containing all original release dates and deadlines and all endpoints introduced so far. Let a 1 < ⋯ < a ℓ a_1<\cdots<a_\ell a 1 < ⋯ < a ℓ be its elements, and let I k : = [ a k , a k + 1 ) I_k:=[a_k,a_{k+1}) I k := [ a k , a k + 1 ) and Δ k : = a k + 1 − a k \Delta_k:=a_{k+1}-a_k Δ k := a k + 1 − a k for k ∈ [ ℓ − 1 ] k\in[\ell-1] k ∈ [ ℓ − 1 ] . We use the standard allocation formulation for preemptive feasibility [11 ] , where x j k x_{jk} x j k denotes the amount of processing of job j j j assigned to interval I k I_k I k :
∑ k ∈ [ ℓ − 1 ] x j k = p j ∀ j ∈ J , ∑ j ∈ J x j k ≤ m Δ k ∀ k ∈ [ ℓ − 1 ] , 0 ≤ x j k ≤ Δ k ∀ j ∈ J , k ∈ [ ℓ − 1 ] , x j k = 0 if I k ⊈ [ R j , D j ) . (4) \begin{aligned}
\sum_{k\in[\ell-1]}x_{jk}&=p_j &&\forall j\in J,\\
\sum_{j\in J}x_{jk}&\le m\Delta_k &&\forall k\in[\ell-1],\\
0\le x_{jk}&\le\Delta_k &&\forall j\in J,\ k\in[\ell-1],\\
x_{jk}&=0 &&\text{if }I_k\not\subseteq[R_j,D_j). \tag*{(4)}
\end{aligned} k ∈ [ ℓ − 1 ] ∑ x j k j ∈ J ∑ x j k 0 ≤ x j k x j k = p j ≤ m Δ k ≤ Δ k = 0 ∀ j ∈ J , ∀ k ∈ [ ℓ − 1 ] , ∀ j ∈ J , k ∈ [ ℓ − 1 ] , if I k ⊆ [ R j , D j ) . (4)
This is a flow problem on the source-job-interval-sink network: source-job arcs have capacity p j p_j p j , job-interval arcs have capacity Δ k \Delta_k Δ k and exist only if I k ⊆ [ R j , D j ) I_k\subseteq[R_j,D_j) I k ⊆ [ R j , D j ) , and interval-sink arcs have capacity m Δ k m\Delta_k m Δ k . A flow of value ∑ j p j \sum_j p_j ∑ j p j corresponds to a feasible allocation. The windows [ R j , D j ) [R_j,D_j) [ R j , D j ) are feasible on m m m machines if and only if (LP) is feasible. Indeed, a schedule yields such an allocation, and McNaughton’s wrap-around rule [17 ] realizes every feasible allocation interval by interval. Placing a designated job j j j first in McNaughton’s construction makes it run during [ a k , a k + x j k ) [a_k,a_k+x_{jk}) [ a k , a k + x j k ) . Reversing time within the interval instead places it during [ a k + 1 − x j k , a k + 1 ) [a_{k+1}-x_{jk},a_{k+1}) [ a k + 1 − x j k , a k + 1 ) .
To maximize R j R_j R j , we call a candidate u ∈ A ∩ [ R j , D j ) u\in A\cap[R_j,D_j) u ∈ A ∩ [ R j , D j ) feasible if (LP) is feasible when j j j has window [ u , D j ) [u,D_j) [ u , D j ) and all other releases and deadlines are unchanged. Feasibility is monotone in u u u , so binary search finds the largest feasible candidate a h a_h a h . Let β \beta β be the minimum of x j h x_{jh} x j h subject to (LP) with window [ a h , D j ) [a_h,D_j) [ a h , D j ) for j j j . This is a min-cost flow problem with unit cost on arc ( j , h ) (j,h) ( j , h ) and zero cost on all other arcs. We set R j : = a h + 1 − β R_j:=a_{h+1}-\beta R j := a h + 1 − β and insert it into A A A . Symmetrically, to minimize D j D_j D j , we find the smallest feasible candidate deadline a h + 1 a_{h+1} a h + 1 , minimize x j h x_{jh} x j h subject to (LP) with window [ R j , a h + 1 ) [R_j,a_{h+1}) [ R j , a h + 1 ) , and set D j : = a h + β D_j:=a_h+\beta D j := a h + β .
Lemma 13. Given all other windows, a h + 1 − β a_{h+1}-\beta a h + 1 − β is the largest feasible release date of j j j , and symmetrically, a h + β a_h+\beta a h + β is the smallest feasible deadline of j j j .
Proof. We consider the release case, the deadline case is symmetric. By (LP), we have β ≤ Δ h \beta\le\Delta_h β ≤ Δ h . We first show that β > 0 \beta> 0 β > 0 . If a h + 1 = D j a_{h+1} = D_j a h + 1 = D j , then I h I_h I h is the only interval in the window of j j j , so β = p j > 0 \beta= p_j > 0 β = p j > 0 . Otherwise, β = 0 \beta= 0 β = 0 would make a h + 1 a_{h+1} a h + 1 a feasible candidate, contradicting the choice of a h a_h a h . Placing j j j last in I h I_h I h realizes an optimal allocation with release date a h + 1 − β a_{h+1} - \beta a h + 1 − β , proving feasibility. Conversely, a feasible schedule with release date u ∈ [ a h , a h + 1 ) u \in[a_h,a_{h+1}) u ∈ [ a h , a h + 1 ) yields an allocation for window [ a h , D j ) [a_h,D_j) [ a h , D j ) with β ≤ x j h ≤ a h + 1 − u \beta\le x_{jh} \le a_{h+1} - u β ≤ x j h ≤ a h + 1 − u , so u ≤ a h + 1 − β u \le a_{h+1} - \beta u ≤ a h + 1 − β . Release dates u ≥ a h + 1 u \ge a_{h+1} u ≥ a h + 1 are infeasible, by the choice of a h a_h a h and monotonicity if a h + 1 < D j a_{h+1} < D_j a h + 1 < D j , and since p j > 0 p_j > 0 p j > 0 otherwise.
Theorem 14. Every instance feasible on m m m machines admits a window-minimal instance satisfying [ R j , D j ) ⊆ [ r j , d j ) [R_j,D_j) \subseteq[r_j,d_j) [ R j , D j ) ⊆ [ r j , d j ) for all j ∈ J j \in J j ∈ J . Such an instance can be computed in strongly polynomial time.
Proof. Each minimization defining β \beta β has a nonempty compact feasible region, so an optimum exists, also for real input data. By Theorem 13, every update shrinks a window and preserves feasibility. Suppose that some final window [ R j , D j ) [R_j,D_j) [ R j , D j ) could be replaced by a strict subinterval. Then we can increase R j R_j R j or decrease D j D_j D j while keeping all other final windows. When this endpoint was optimized, all windows contained the final ones. Hence, the resulting schedule would contradict the optimality of that endpoint at that step.
Suppose that the input data is rational; scale it to integers. There are at most 4 n 4n 4 n event points: the original endpoints and at most two new endpoints per job. The network therefore has O ( n ) O(n) O ( n ) nodes and O ( n 2 ) O(n^2) O ( n 2 ) arcs. Both feasibility testing and minimizing x j h x_{jh} x j h can be performed in strongly polynomial time [19 ] . With integral capacities, we can choose integral optimal flows. Thus, all endpoints remain integral and within the original horizon. Each of the 2 n 2n 2 n updates solves O ( log n ) O(\log n) O ( log n ) such problems.
Constructing a Canonical Schedule
Let [ R j , D j ) [R_j,D_j) [ R j , D j ) be the window-minimal windows computed by Theorem 14, and let A \mathcal{A} A , I k I_k I k , and Δ k \Delta_k Δ k be as in its last iteration. By window-minimality, every feasible schedule completes job j j j at D j D_j D j . Thus, the canonical ordering ≺ \prec ≺ is fixed by nondecreasing deadlines, with ties broken by job index.
Let w j : = n + 1 − rank ≺ ( j ) w_j := n + 1 - \operatorname{rank}_{\prec}(j) w j := n + 1 − rank ≺ ( j ) , where rank ≺ ( j ) ∈ [ n ] \operatorname{rank}_{\prec}(j) \in[n] rank ≺ ( j ) ∈ [ n ] is the position of j j j in the canonical ordering ≺ \prec ≺ . We compute an optimal allocation x x x of
min Ψ ( x ) : = ∑ j ∈ J ∑ k ∈ [ ℓ − 1 ] w j ⋅ k ⋅ x j k subject to (LP) . (5) \min\ \Psi(x) := \sum_{j \in J} \sum_{k \in[\ell-1]} w_j \cdot k \cdot x_{jk} \quad\text{subject to (LP)}. \tag*{(5)} min Ψ ( x ) := j ∈ J ∑ k ∈ [ ℓ − 1 ] ∑ w j ⋅ k ⋅ x j k subject to (LP) . (5)
This is a min-cost flow problem on the network from § 4.1 , with cost w j k w_jk w j k on each job-interval arc ( j , k ) (j,k) ( j , k ) . The objective excludes priority swaps between different intervals, but does not determine the processing order within an interval. We therefore realize each interval’s allocation by a greedy rule that excludes priority swaps within that interval.
Fix an interval I k I_k I k . At time u ∈ I k u \in I_k u ∈ I k , let h : = a k + 1 − u h := a_{k+1} - u h := a k + 1 − u be the remaining length of I k I_k I k , and let y j y_j y j be the remaining amount of x j k x_{jk} x j k . Initially, u = a k u = a_k u = a k and y j = x j k y_j = x_{jk} y j = x j k . A job is forced if y j = h > 0 y_j = h > 0 y j = h > 0 , that is, it must run throughout the remainder of I k I_k I k . Initialize A \mathcal{A} A with all forced jobs. Add the earliest remaining jobs in the order ≺ \prec ≺ with y j > 0 y_j > 0 y j > 0 , until ∣ A ∣ = m |\mathcal{A}| = m ∣ A ∣ = m or no such job remains. We process A \mathcal{A} A for
τ : = min ( { h } ∪ { y j ∣ j ∈ A } ∪ { h − y j ∣ j ∉ A , y j > 0 } ) , \tau:= \min\bigl(\{h\} \cup\{y_j \mid j \in\mathcal{A}\} \cup\{h-y_j \mid j \notin\mathcal{A},\ y_j > 0\}\bigr), τ := min ( { h } ∪ { y j ∣ j ∈ A } ∪ { h − y j ∣ j ∈ / A , y j > 0 } ) ,
then increase u u u by τ \tau τ , decrease y j y_j y j by τ \tau τ for all j ∈ A j \in\mathcal{A} j ∈ A , and repeat until u = a k + 1 u = a_{k+1} u = a k + 1 . Thus, processing continues until an allocation finishes, an unselected job becomes forced, or the interval ends.
Lemma 15. In every interval I k I_k I k , the greedy rule realizes x x x with O ( n ) O(n) O ( n ) blocks, and no priority swap exists for two blocks in I k I_k I k .
Proof. We maintain 0 ≤ y j ≤ h 0 \le y_j \le h 0 ≤ y j ≤ h for every job j ∈ J j \in J j ∈ J and ∑ j ∈ J y j ≤ m h \sum_{j \in J} y_j \le mh ∑ j ∈ J y j ≤ mh , which hold initially by (LP). If h > 0 h > 0 h > 0 , at most m m m jobs are forced, so all of them belong to A A A , and ∣ A ∣ ≤ m |A| \le m ∣ A ∣ ≤ m . Hence, every job j ∉ A j \notin A j ∈ / A with y j > 0 y_j > 0 y j > 0 satisfies y j < h y_j < h y j < h , and thus τ > 0 \tau> 0 τ > 0 . For j ∈ A j \in A j ∈ A , both y j y_j y j and h h h decrease by τ \tau τ , so 0 ≤ y j ≤ h 0 \le y_j \le h 0 ≤ y j ≤ h is preserved by τ ≤ y j \tau\le y_j τ ≤ y j . For j ∉ A j \notin A j ∈ / A , only h h h decreases, so y j ≤ h y_j \le h y j ≤ h is preserved by τ ≤ h − y j \tau\le h-y_j τ ≤ h − y j . If ∣ A ∣ = m |A|=m ∣ A ∣ = m , both sides of ∑ j ∈ J y j ≤ m h \sum_{j \in J} y_j \le mh ∑ j ∈ J y j ≤ mh decrease by m τ m\tau m τ . Otherwise, A A A contains all jobs with y j > 0 y_j > 0 y j > 0 , so ∑ j ∈ J y j ≤ ∣ A ∣ h ≤ m h \sum_{j \in J} y_j \le|A|h \le mh ∑ j ∈ J y j ≤ ∣ A ∣ h ≤ mh . At h = 0 h=0 h = 0 , we obtain y j = 0 y_j=0 y j = 0 for every job j ∈ J j \in J j ∈ J , so x x x is realized in I k I_k I k .
A forced job remains forced until a k + 1 a_{k+1} a k + 1 , as y j y_j y j and h h h decrease equally. Every iteration ending before a k + 1 a_{k+1} a k + 1 completes the allocation of a job or makes a job forced. Each happens at most once per job, so there are at most 2 n + 1 2n+1 2 n + 1 iterations, each yielding one block.
Suppose that a priority swap exists for jobs j 1 ≺ j 2 j_1 \prec j_2 j 1 ≺ j 2 at blocks s < t s<t s < t in I k I_k I k . Since j 1 ∈ S t j_1 \in S_t j 1 ∈ S t , we have y j 1 > 0 y_{j_1}>0 y j 1 > 0 during block s s s . As j 1 ∉ S s j_1 \notin S_s j 1 ∈ / S s and j 1 ≺ j 2 j_1 \prec j_2 j 1 ≺ j 2 , the rule selects j 2 j_2 j 2 in block s s s only if j 2 j_2 j 2 is forced. Then j 2 j_2 j 2 runs until a k + 1 a_{k+1} a k + 1 , which contradicts j 2 ∉ S t j_2 \notin S_t j 2 ∈ / S t .
Theorem 16. Every instance feasible on m m m machines admits a feasible supercanonical schedule on m m m machines with O ( n 2 ) O(n^2) O ( n 2 ) blocks. Such a schedule can be computed in strongly polynomial time.
Proof. The allocation polytope is nonempty and compact, so an optimal allocation exists. By Theorem 15 , realizing x x x greedily in every interval yields a feasible schedule S S S for the windows [ R j , D j ) [R_j,D_j) [ R j , D j ) . Since [ R j , D j ) ⊆ [ r j , d j ) [R_j,D_j) \subseteq[r_j,d_j) [ R j , D j ) ⊆ [ r j , d j ) , schedule S S S is also feasible for the original instance.
Suppose that a priority swap exists for j 1 ≺ j 2 j_1 \prec j_2 j 1 ≺ j 2 at blocks s < t s<t s < t . By Theorem 15 , we have B s ⊆ I k B_s \subseteq I_k B s ⊆ I k and B t ⊆ I l B_t \subseteq I_l B t ⊆ I l with k < l k<l k < l . For 0 < ε ≤ min { ∣ B s ∣ , ∣ B t ∣ } 0<\varepsilon\le\min\{|B_s|,|B_t|\} 0 < ε ≤ min { ∣ B s ∣ , ∣ B t ∣ } , we move ε \varepsilon ε of j 1 j_1 j 1 from I l I_l I l to I k I_k I k and ε \varepsilon ε of j 2 j_2 j 2 from I k I_k I k to I l I_l I l . The capacity constraints remain satisfied, and so do the individual bounds, since j 1 ∉ S s j_1 \notin S_s j 1 ∈ / S s and j 2 ∉ S t j_2 \notin S_t j 2 ∈ / S t . Moreover, I k I_k I k lies in the window of j 1 j_1 j 1 , since R j 1 ≤ b ρ j 1 ≤ b s R_{j_1} \le b_{\rho_{j_1}} \le b_s R j 1 ≤ b ρ j 1 ≤ b s with R j 1 ∈ A R_{j_1} \in A R j 1 ∈ A , and D j 1 ≥ a l + 1 D_{j_1} \ge a_{l+1} D j 1 ≥ a l + 1 . Similarly, I l I_l I l lies in the window of j 2 j_2 j 2 , since R j 2 ≤ a k R_{j_2} \le a_k R j 2 ≤ a k and D j 2 ≥ D j 1 ≥ a l + 1 D_{j_2} \ge D_{j_1} \ge a_{l+1} D j 2 ≥ D j 1 ≥ a l + 1 . Now, the resulting allocation x ′ x' x ′ is feasible, and contradicts optimality of x x x , because
Ψ ( x ′ ) − Ψ ( x ) = ε ( w j 1 − w j 2 ) ( k − l ) < 0. \Psi(x')-\Psi(x)=\varepsilon(w_{j_1}-w_{j_2})(k-l)<0. Ψ ( x ′ ) − Ψ ( x ) = ε ( w j 1 − w j 2 ) ( k − l ) < 0.
Thus, S S S is canonical, and by Theorem 12, it is supercanonical. The schedule remains supercanonical when viewed as a schedule of the original instance, since supercanonicity does not depend on the windows.
By Theorem 15 , the greedy realization uses at most 2 n + 1 2n+1 2 n + 1 blocks per interval, so S S S has at most ( ℓ − 1 ) ( 2 n + 1 ) = O ( n 2 ) (\ell-1)(2n+1)=O(n^2) ( ℓ − 1 ) ( 2 n + 1 ) = O ( n 2 ) blocks, as ℓ ≤ 4 n \ell\le4n ℓ ≤ 4 n . The windows are computed in strongly polynomial time by Theorem 14 . The min-cost flow problem can be solved in strongly polynomial time [19 ] . After scaling the input to integers, we can choose an integral optimal allocation. Finally, the greedy rule performs O ( n ) O(n) O ( n ) iterations per interval, each with O ( n ) O(n) O ( n ) arithmetic operations.
Combining Theorem 16 , which yields a supercanonical schedule with O ( n 2 ) O(n^2) O ( n 2 ) blocks, with Theorem 10 proves Theorem 1 . Thus, the power of migration for preemptive scheduling with time windows is two.
Consequences and Extensions
Our migration-elimination theorem also has consequences for other scheduling problems. We discuss throughput maximization (§ 5.1 ), followed by speed augmentation and job partitioning (§ 5.2 ). Finally, we consider identical machines with restricted assignment and show that a constant factor increase in the number of machines no longer suffices (§ 5.3 ).
Throughput Maximization
In weighted preemptive throughput maximization , each job has a nonnegative weight, and the goal is to select a maximum-weight subset of jobs that can be feasibly scheduled on m m m identical machines. Let O P T m i g ( m ) \mathrm{OPT}_{\mathrm{mig}}(m) OPT mig ( m ) and O P T n m ( m ) \mathrm{OPT}_{\mathrm{nm}}(m) OPT nm ( m ) denote the optimal values with and without migration, respectively. Eliminating migration from an optimal migratory schedule by Theorem 1 and retaining the m m m heaviest of the 2 m − 1 2m-1 2 m − 1 machine classes yields
O P T n m ( m ) ≥ m 2 m − 1 O P T m i g ( m ) . (6) \mathrm{OPT}_{\mathrm{nm}}(m) \ge\frac{m}{2m-1}\mathrm{OPT}_{\mathrm{mig}}(m). \tag*{(6)} OPT nm ( m ) ≥ 2 m − 1 m OPT mig ( m ) . (6)
Koren, Dar, and Amir [16 ] showed that this is tight, and conjectured (2) for weights proportional to processing times. Our result confirms this conjecture, even for arbitrary weights. Combining our theorem with repeated applications of the single-machine FPTAS in [20 ] gives the following approximation guarantee against the migratory optimum.
Corollary 17. For every δ > 0 \delta> 0 δ > 0 , weighted preemptive throughput maximization on m m m identical machines admits a polynomial-time non-migratory algorithm with approximation ratio
[ 1 − ( 1 − 1 2 m − 1 ) m ] − 1 + δ ≤ ( 1 − e − 1 / 2 ) − 1 + δ < 2.542 + δ \left[1-\left(1-\frac{1}{2m-1}\right)^m\right]^{-1}+\delta\le\left(1-e^{-1/2}\right)^{-1}+\delta< 2.542+\delta [ 1 − ( 1 − 2 m − 1 1 ) m ] − 1 + δ ≤ ( 1 − e − 1/2 ) − 1 + δ < 2.542 + δ against the migratory optimum.
Proof. We may assume m ≤ n m \le n m ≤ n , since otherwise each individually feasible job gets its own machine. Apply the single-machine FPTAS [20 ] repeatedly to the remaining jobs, scheduling the selected jobs on one new machine in each of m m m iterations, as in the reduction of [13 ] . Write W i W_i W i for the weight selected after i i i iterations, with W 0 = 0 W_0 = 0 W 0 = 0 , and O = O P T m i g ( m ) O = \mathrm{OPT}_{\mathrm{mig}}(m) O = OPT mig ( m ) . The unselected jobs of a migratory optimum have weight at least O − W i O-W_i O − W i and, by Theorem 1 , partition into 2 m − 1 2m-1 2 m − 1 feasible single-machine classes. Thus, using the FPTAS with accuracy parameter ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and approximation guarantee 1 − ε 1-\varepsilon 1 − ε ,
W i + 1 − W i ≥ 1 − ε 2 m − 1 ( O − W i ) . W_{i+1}-W_i \ge\frac{1-\varepsilon}{2m-1}(O-W_i). W i + 1 − W i ≥ 2 m − 1 1 − ε ( O − W i ) .
Iterating this recurrence yields
W m ≥ [ 1 − ( 1 − 1 − ε 2 m − 1 ) m ] O . W_m \ge\left[1-\left(1-\frac{1-\varepsilon}{2m-1}\right)^m\right]O. W m ≥ [ 1 − ( 1 − 2 m − 1 1 − ε ) m ] O .
Choosing ε > 0 \varepsilon> 0 ε > 0 sufficiently small as a function of δ \delta δ gives the first bound. The uniform bound follows from ( 1 − 1 2 m − 1 ) m ≤ e − m / ( 2 m − 1 ) ≤ e − 1 / 2 \left(1-\frac{1}{2m-1}\right)^m \le e^{-m/(2m-1)} \le e^{-1/2} ( 1 − 2 m − 1 1 ) m ≤ e − m / ( 2 m − 1 ) ≤ e − 1/2 .
For weights proportional to processing times, Koren, Dar, and Amir [16 ] use the same iterative scheme to obtain a guarantee tending to 1 − e − 1 / 2 1-e^{-1/2} 1 − e − 1/2 . Theorem 17 extends this guarantee to arbitrary weights and improves the bound for each fixed m m m and sufficiently small δ \delta δ . For arbitrary weights, it improves the approximation ratio 12 + δ 12+\delta 12 + δ obtained by combining the Kalyanasundaram–Pruhs reduction [13 ] with the single-machine FPTAS, as reported in [14 ] .
For online throughput maximization, (2) reduces the loss in transferring guarantees to the migratory optimum from 6 − 5 / m 6-5/m 6 − 5/ m [13 ] to 2 − 1 / m 2-1/m 2 − 1/ m , improving the constants in [7 , 8 ] . More generally, retaining k ≤ m k \le m k ≤ m machine classes gives O P T n m ( k ) ≥ k 2 m − 1 O P T m i g ( m ) \mathrm{OPT}_{\mathrm{nm}}(k) \ge\frac{k}{2m-1}\mathrm{OPT}_{\mathrm{mig}}(m) OPT nm ( k ) ≥ 2 m − 1 k OPT mig ( m ) , improving the fraction k / ( 6 m ) k/(6m) k / ( 6 m ) in the machine-reduction argument of [18 ] .
Speed Augmentation and Job Partitioning
Instead of additional machines, Theorem 1 also gives an asymptotically optimal speedup bound for eliminating migration on the original number of machines.
Corollary 18. Every instance feasible with migration on m m m identical unit-speed machines can be scheduled without migration on m m m speed-two machines in strongly polynomial time. The speedup factor is asymptotically optimal.
Proof. By Theorem 1 , we compute a feasible non-migratory schedule on 2 m − 1 2m-1 2 m − 1 unit-speed machines in strongly polynomial time. We add an idle machine and group the 2 m 2m 2 m machines into m m m pairs, each simulated by one machine of speed 2. Consider a block B t B_t B t of length ℓ \ell ℓ . On each machine of a pair, at most one job is processed throughout B t B_t B t . The speed-2 machine processes the job of the first machine during the first half of B t B_t B t and the job of the second machine during the second half. Each job thus receives the same processing amount within B t B_t B t , so all processing times and windows are preserved, and every job is processed on a single machine. The number of blocks at most doubles.
For the lower bound, consider m + 1 m+1 m + 1 jobs with common window [ 0 , 1 ) [0,1) [ 0 , 1 ) and processing time m / ( m + 1 ) m/(m+1) m / ( m + 1 ) [3 Section 5] . McNaughton’s wrap-around rule [17 ] schedules them migratorily on m m m unit-speed machines. In every non-migratory schedule on m m m machines, some machine processes two jobs, which requires speed at least 2 m / ( m + 1 ) 2m/(m+1) 2 m / ( m + 1 ) . □
Equivalently, let s m i g ( J , m ) s_{\mathrm{mig}}(J,m) s mig ( J , m ) and s n m ( J , m ) s_{\mathrm{nm}}(J,m) s nm ( J , m ) denote the minimum common speed of m m m machines needed to schedule J J J with and without migration, respectively. Since running at speed s s s is equivalent to dividing all processing times by s s s , Theorem 18 yields
s m i g ( J , m ) ≤ s n m ( J , m ) ≤ 2 ⋅ s m i g ( J , m ) . s_{\mathrm{mig}}(J,m) \le s_{\mathrm{nm}}(J,m) \le2 \cdot s_{\mathrm{mig}}(J,m). s mig ( J , m ) ≤ s nm ( J , m ) ≤ 2 ⋅ s mig ( J , m ) .
An earlier speedup bound of 4 − 1 / m 4-1/m 4 − 1/ m follows implicitly from the non-migratory feasibility condition of Baruah and Fisher [1 Corollary 1] . Their condition was derived in the context of multiprocessor real-time scheduling of recurrent tasks, including periodic and sporadic task systems, and applies to arbitrary collections of jobs. Indeed, migratory feasibility bounds the total processing requirement of jobs whose windows lie in any interval by m m m times the interval length, and each job’s density p j / ( d j − r j ) p_j/(d_j-r_j) p j / ( d j − r j ) by 1. Running at speed 4 − 1 / m 4-1/m 4 − 1/ m therefore reduces the load and maximum job density to at most m 2 / ( 4 m − 1 ) m^2/(4m-1) m 2 / ( 4 m − 1 ) and m / ( 4 m − 1 ) m/(4m-1) m / ( 4 m − 1 ) , respectively, which are precisely the sufficient thresholds in their corollary. Theorem 18 improves this guarantee to 2.
Goossens, Richard, Lindström, Lupu, and Riouard [10 ] study offline job partitioning , which assigns each job to one processor before execution. Our results give machine and speed augmentation guarantees for this model. The stronger notion of task partitioning , usually called partitioned scheduling in the real-time literature [9 ] , requires all jobs of the same recurrent task to use the same processor. Our construction may assign different jobs of a task to different processors and therefore gives no guarantee for task partitioning.
A Lower Bound for Restricted Assignment
The preceding guarantees rely on every job being eligible on every machine. We now show that even two eligible machines per job can prevent elimination of migration with a constant factor increase in the number of machines.
Under restricted assignment, each job j j j may only be processed on the machines in its eligible set M j ⊆ [ m ] M_j \subseteq[m] M j ⊆ [ m ] . To eliminate migration, we use additional copies of the machines, where a copy of machine i i i may only process jobs j j j with i ∈ M j i \in M_j i ∈ M j .
There are two natural ways to count copies. In the uniform model, every machine has the same number μ \mu μ of copies, so μ m \mu m μ m machines are used in total. In the free model, the number of copies may be chosen separately for every machine, and we count the total number of copies, including the original machines. The free model is more permissive, so a lower bound of N N N copies in total in the free model implies μ ≥ N / m \mu\ge N/m μ ≥ N / m in the uniform model.
In the uniform model, Im and Moseley [12 ] show that speed 1 + ε 1+\varepsilon 1 + ε and μ = O ( 1 / ε 2 ) \mu= O(1/\varepsilon^2) μ = O ( 1/ ε 2 ) suffice to eliminate migration on related machines with restricted assignment, whereas without additional speed, no constant μ \mu μ suffices on related machines. Their lower bound relies on uniform copies: with free copies, copying only the fast machines yields O ( m ) O(m) O ( m ) copies in total. We show that under unit-speed restricted assignment with at most two eligible machines per job, Ω ( m log m ) \Omega(m\log m) Ω ( m log m ) copies in total may be necessary even in the free model, and thus μ = Ω ( log m ) \mu= \Omega(\log m) μ = Ω ( log m ) in the uniform model.
Proposition 19. Let m ≥ 1 m \ge1 m ≥ 1 and k : = ⌊ log 2 m ⌋ k := \lfloor\log_2 m\rfloor k := ⌊ log 2 m ⌋ . Under unit-speed restricted assignment, eliminating migration may require m + k 2 k − 1 m + k2^{k-1} m + k 2 k − 1 machine copies in total, even if every job is eligible on at most two machines. In particular, Ω ( m log m ) \Omega(m\log m) Ω ( m log m ) copies in total and μ = Ω ( log m ) \mu= \Omega(\log m) μ = Ω ( log m ) in the uniform model may be necessary.
Proof. We recursively construct an instance I k I_k I k on the machines [ 2 k ] [2^k] [ 2 k ] with all windows in [ 0 , 2 k ) [0,2^k) [ 0 , 2 k ) , and leave the remaining m − 2 k m-2^k m − 2 k machines idle. Let I 0 I_0 I 0 consist of a single job with processing time 1 1 1 , window [ 0 , 1 ) [0,1) [ 0 , 1 ) , and eligible machine 1. For k ≥ 1 k \ge1 k ≥ 1 , we let h : = 2 k − 1 h := 2^{k-1} h := 2 k − 1 . We take one copy of I k − 1 I_{k-1} I k − 1 on the machines 1 , … , h 1,\ldots,h 1 , … , h , and a second copy on the machines h + 1 , … , 2 h h+1,\ldots,2h h + 1 , … , 2 h with all windows shifted by h h h . Moreover, for every i ∈ [ h ] i \in[h] i ∈ [ h ] , we add a job z i z_i z i with processing time 2 h 2h 2 h , window [ 0 , 2 h ) [0,2h) [ 0 , 2 h ) , and eligible machines M z i = { i , i + h } M_{z_i} = \{i,i+h\} M z i = { i , i + h } (see Figure 3 ). Thus, every job is eligible on at most two machines, and the number of jobs satisfies ∣ I k ∣ = 2 ∣ I k − 1 ∣ + 2 k − 1 |I_k| = 2|I_{k-1}| + 2^{k-1} ∣ I k ∣ = 2∣ I k − 1 ∣ + 2 k − 1 with ∣ I 0 ∣ = 1 |I_0| = 1 ∣ I 0 ∣ = 1 , so ∣ I k ∣ = 2 k + k 2 k − 1 |I_k| = 2^k + k2^{k-1} ∣ I k ∣ = 2 k + k 2 k − 1 .
Figure 3. A migratory schedule of the instance I 3 I_3 I 3 of Theorem 19 on eight machines, with machines as rows and time on the horizontal axis. The dashed and dotted boxes contain the copies of I 2 I_2 I 2 and I 1 I_1 I 1 , respectively, the jobs x i x_i x i form the copies of I 0 I_0 I 0 , and the jobs y q y_q y q , z q z_q z q , and w i w_i w i are added on levels 1, 2, and 3. Each job is processed exactly on its eligible machines, and its processing time equals its window length. Without migration, each of the 8 + 3 ⋅ 4 = 20 8 + 3 \cdot4 = 20 8 + 3 ⋅ 4 = 20 jobs requires its own machine copy.
We show by induction on k k k that I k I_k I k is feasible with migration on 2 k 2^k 2 k machines. We schedule both copies of I k − 1 I_{k-1} I k − 1 recursively, and we process each job z i z_i z i on machine i + h i+h i + h during [ 0 , h ) [0,h) [ 0 , h ) and on machine i i i during [ h , 2 h ) [h,2h) [ h , 2 h ) . This is feasible, since the jobs of the first copy only use the machines 1 , … , h 1,\ldots,h 1 , … , h during [ 0 , h ) [0,h) [ 0 , h ) , and the jobs of the second copy only use the machines h + 1 , … , 2 h h+1,\ldots,2h h + 1 , … , 2 h during [ h , 2 h ) [h,2h) [ h , 2 h ) .
It remains to show that every non-migratory schedule of I k I_k I k uses a separate copy for each job. The recursion assigns to each machine i ∈ M i \in M i ∈ M and each level ℓ ∈ { 0 , … , k } \ell\in\{0,\ldots,k\} ℓ ∈ { 0 , … , k } exactly one copy of I ℓ I_\ell I ℓ that contains machine i i i , and the windows of these copies are nested intervals. Every job eligible on machine i i i is added in one of these copies and has its window, so any two jobs with a common eligible machine have overlapping windows. Moreover, every job has processing time equal to its window length, so in a non-migratory schedule, it occupies its machine copy throughout its window. Hence, no machine copy processes two jobs. Together with the m − 2 k m-2^k m − 2 k idle machines, every non-migratory schedule uses at least ∣ I k ∣ + m − 2 k = m + k 2 k − 1 |I_k|+m-2^k = m+k2^{k-1} ∣ I k ∣ + m − 2 k = m + k 2 k − 1 copies in total. Since 2 k − 1 > m / 4 2^{k-1} > m/4 2 k − 1 > m /4 and k > log 2 m − 1 k > \log_2m-1 k > log 2 m − 1 , this is Ω ( m log m ) \Omega(m\log m) Ω ( m log m ) , and the uniform model requires μ ≥ ( m + k 2 k − 1 ) / m = Ω ( log m ) \mu\ge(m+k2^{k-1})/m = \Omega(\log m) μ ≥ ( m + k 2 k − 1 ) / m = Ω ( log m ) .
AI disclosure
We used ChatGPT-6 Astra and Claude Opus 5.5 for mathematical assistance, language editing, and figure preparation.
We established the tight 3 m − 2 3m-2 3 m − 2 coloring bound for canonical schedules (Appendix § 8 ), introduced supercanonical schedules, and established the limitations of the minimum-degree approach (Appendix § 9 ). We developed the swap framework, proved the latest-block lemma (Theorem 7) and an earlier, weaker separator lemma, and proposed the inductive coloring strategy using Kempe exchanges. We also proposed the rank-weighted LP objective for constructing canonical schedules and simplified the coloring potential to Φ ( c ) = min a λ a ( c ) \Phi(c) = \min_a \lambda_a(c) Φ ( c ) = min a λ a ( c ) .
Building on this framework, ChatGPT-6 Astra developed the stronger separator lemma (Theorem 8), the quantities λ a ( c ) \lambda_a(c) λ a ( c ) , an initial sum-based potential, and the specific recoloring construction that completed the coloring argument (Theorem 9). It also provided the polynomial-time construction of a window-minimal instance.
We verified all AI-assisted contributions and take full responsibility for the content and correctness of the paper.
Appendices
Canonical Schedules: A Tight Coloring Bound
In this appendix, we revisit the approach of Kalyanasundaram and Pruhs [13 ] , who use a density argument to bound the minimum degree of the conflict graph of a canonical schedule. For a nonempty graph H = ( V , E ) H = (V, E) H = ( V , E ) , the minimum degree of H H H is δ ( H ) : = min v ∈ V d H ( v ) \delta(H) := \min_{v \in V} d_H(v) δ ( H ) := min v ∈ V d H ( v ) . They then apply the classical Szekeres–Wilf bound [21 ] : for every graph G = ( V , E ) G = (V, E) G = ( V , E ) ,
χ ( G ) ≤ 1 + max ∅ ≠ U ⊆ V δ ( G [ U ] ) . (7) \chi(G) \le1 + \max_{\varnothing\ne U \subseteq V} \delta(G[U]). \tag*{(7)} χ ( G ) ≤ 1 + ∅ = U ⊆ V max δ ( G [ U ]) . (7)
The bound follows by repeatedly removing a vertex of minimum degree and then greedily coloring the vertices in reverse order. Each vertex has at most max ∅ ≠ U ⊆ V δ ( G [ U ] ) \max_{\varnothing\ne U \subseteq V} \delta(G[U]) max ∅ = U ⊆ V δ ( G [ U ]) already colored neighbors, so a palette of one more color suffices. Thus, to bound the chromatic number of the conflict graph, it suffices to find a job of small degree in every nonempty induced subgraph.
By bounding the density of a supergraph of the conflict graph by 3 ( m − 1 ) 3(m - 1) 3 ( m − 1 ) , [13 ] obtain a job of degree at most 6 m − 6 6m - 6 6 m − 6 , and thus a non-migratory schedule on 6 m − 5 6m - 5 6 m − 5 machines. By bounding the degree of a suitable job directly, we improve this to 3 m − 2 3m - 2 3 m − 2 machines. However, this bound is tight, as there are canonical schedules whose conflict graph is a clique on 3 m − 2 3m - 2 3 m − 2 jobs. Hence, canonicity alone does not suffice for 2 m − 1 2m - 1 2 m − 1 machines, which motivates supercanonical schedules and the recoloring argument of § 3 .
Theorem 20. Let S S S be a canonical schedule on m m m machines. Then the chromatic number of the conflict graph satisfies χ ( G S ) ≤ 3 m − 2 \chi(G^S) \le3m - 2 χ ( G S ) ≤ 3 m − 2 , and this bound is tight.
We prove the upper bound in Sections A.1 to A.3 and its tightness in Section A.4. In more detail, we identify in Section A.1 a block in which many neighbors of a job k k k must be processed. Next, in Section A.2, we partition the neighborhood of k k k accordingly and bound most of its parts. Finally, in Section A.3, we find a job for which the remaining parts are small as well.
Throughout, let S S S be a canonical schedule on m m m machines with canonical ordering ≺ \prec ≺ , let G : = G S G := G^S G := G S , and let N ( k ) : = N G ( k ) N(k) := N_G(k) N ( k ) := N G ( k ) . We use the span [ ρ j , δ j ] [\rho_j, \delta_j] [ ρ j , δ j ] of a job j j j in place of its window, that is, r j : = b ρ j r_j := b_{\rho_j} r j := b ρ j and d j : = b δ j + 1 d_j := b_{\delta_j+1} d j := b δ j + 1 . Moreover, Theorem 7 only uses canonicity, so it also applies here.
Structure Lemma
Fix a job k k k with ∣ N ( k ) ∣ ≥ m |N(k)| \ge m ∣ N ( k ) ∣ ≥ m , as jobs with fewer neighbors have degree at most m − 1 ≤ 3 m − 3 m - 1 \le3m - 3 m − 1 ≤ 3 m − 3 . Let N 0 ( k ) N_0(k) N 0 ( k ) be the set of the m m m last neighbors of k k k in ≺ \prec ≺ . We define the critical block of k k k as the earliest last common block of k k k with a job in N 0 ( k ) N_0(k) N 0 ( k ) , that is,
γ k : = min { L j ′ k ∣ j ′ ∈ N 0 ( k ) } . \gamma_k := \min\{L_{j'k} \mid j' \in N_0(k)\}. γ k := min { L j ′ k ∣ j ′ ∈ N 0 ( k )} .
Moreover, we fix a pivot g k ∈ N 0 ( k ) g_k \in N_0(k) g k ∈ N 0 ( k ) with L g k k = γ k L_{g_k k} = \gamma_k L g k k = γ k . Thus, both k k k and g k g_k g k are processed in block γ k \gamma_k γ k , and L j ′ k ≥ γ k L_{j'k} \ge\gamma_k L j ′ k ≥ γ k for every j ′ ∈ N 0 ( k ) j' \in N_0(k) j ′ ∈ N 0 ( k ) . Every neighbor outside N 0 ( k ) N_0(k) N 0 ( k ) precedes the pivot. The following lemma therefore places all such neighbors whose spans contain γ k \gamma_k γ k in the same processing block, where the machine capacity bounds their number. The following structure lemma states that every neighbor of k k k that precedes the pivot and whose span contains the critical block is processed in the critical block (see Figure 4 ).
Figure 4. Schematic illustration of Theorem 21. Left: The critical block B γ k B_{\gamma_k} B γ k is the earliest last common block of k k k with a job in N 0 ( k ) N_0(k) N 0 ( k ) , attained by the pivot g k g_k g k , while L j ′ k > γ k L_{j'k} > \gamma_k L j ′ k > γ k . The neighbor j ≺ g k j \prec g_k j ≺ g k satisfies ρ j ≤ γ k ≤ δ j \rho_j \le\gamma_k \le\delta_j ρ j ≤ γ k ≤ δ j and is processed in B γ k B_{\gamma_k} B γ k . Right: If j j j were not processed in B γ k B_{\gamma_k} B γ k (dashed), then j j j runs in a later common block B L j k B_{L_{jk}} B L j k with k k k , in which g k g_k g k does not run. Exchanging the dark pieces is then a priority swap for j ≺ g k j \prec g_k j ≺ g k at blocks γ k < L j k \gamma_k < L_{jk} γ k < L j k .
Lemma 21. Let j ∈ N ( k ) j \in N(k) j ∈ N ( k ) with j ≺ g k j \prec g_k j ≺ g k and ρ j ≤ γ k ≤ δ j \rho_j \le\gamma_k \le\delta_j ρ j ≤ γ k ≤ δ j . Then j ∈ S γ k j \in S_{\gamma_k} j ∈ S γ k .
Proof. It suffices to show that L j k ≥ γ k L_{jk} \ge\gamma_k L j k ≥ γ k . Indeed, if L j k = γ k L_{jk} = \gamma_k L j k = γ k , then j ∈ S γ k j \in S_{\gamma_k} j ∈ S γ k . If L j k > γ k L_{jk} > \gamma_k L j k > γ k , then g k ∉ S L j k g_k \notin S_{L_{jk}} g k ∈ / S L j k by maximality of L g k k = γ k L_{g_k k} = \gamma_k L g k k = γ k , since k ∈ S L j k k \in S_{L_{jk}} k ∈ S L j k . Hence, if j ∉ S γ k j \notin S_{\gamma_k} j ∈ / S γ k , a priority swap exists for j ≺ g k j \prec g_k j ≺ g k at blocks γ k < L j k \gamma_k < L_{jk} γ k < L j k , since ρ j ≤ γ k \rho_j \le\gamma_k ρ j ≤ γ k , g k ∈ S γ k ∖ S L j k g_k \in S_{\gamma_k} \setminus S_{L_{jk}} g k ∈ S γ k ∖ S L j k , and j ∈ S L j k ∖ S γ k j \in S_{L_{jk}} \setminus S_{\gamma_k} j ∈ S L j k ∖ S γ k . We show L j k ≥ γ k L_{jk} \ge\gamma_k L j k ≥ γ k by distinguishing three cases.
Case 1: Suppose that δ j ≤ δ k \delta_j \le\delta_k δ j ≤ δ k , and assume for contradiction that L j k < γ k L_{jk} < \gamma_k L j k < γ k . If j ≺ k j \prec k j ≺ k , then Theorem 7 gives k ∉ S γ k k \notin S_{\gamma_k} k ∈ / S γ k , since L j k < γ k ≤ δ j L_{jk} < \gamma_k \le\delta_j L j k < γ k ≤ δ j . If k ≺ j k \prec j k ≺ j , then Theorem 7 gives j ∉ S δ j j \notin S_{\delta_j} j ∈ / S δ j , since L j k < δ j ≤ δ k L_{jk} < \delta_j \le\delta_k L j k < δ j ≤ δ k . Both contradict the definitions of γ k \gamma_k γ k and δ j \delta_j δ j . @page 16/22 starts_mid=1 ends_mid=1 graph H = ( V , E ) H = (V, E) H = ( V , E ) , the minimum degree of H H H is δ ( H ) : = min v ∈ V d H ( v ) \delta(H) := \min_{v \in V} d_H(v) δ ( H ) := min v ∈ V d H ( v ) . They then apply the classical Szekeres–Wilf bound [21 ] : for every graph G = ( V , E ) G = (V, E) G = ( V , E ) ,
χ ( G ) ≤ 1 + max ∅ ≠ U ⊆ V δ ( G [ U ] ) . (8) \chi(G) \le1 + \max_{\varnothing\ne U \subseteq V} \delta(G[U]). \tag*{(8)} χ ( G ) ≤ 1 + ∅ = U ⊆ V max δ ( G [ U ]) . (8)
The bound follows by repeatedly removing a vertex of minimum degree and then greedily coloring the vertices in reverse order. Each vertex has at most max ∅ ≠ U ⊆ V δ ( G [ U ] ) \max_{\varnothing\ne U \subseteq V} \delta(G[U]) max ∅ = U ⊆ V δ ( G [ U ]) already colored neighbors, so a palette of one more color suffices. Thus, to bound the chromatic number of the conflict graph, it suffices to find a job of small degree in every nonempty induced subgraph.
By bounding the density of a supergraph of the conflict graph by 3 ( m − 1 ) 3(m - 1) 3 ( m − 1 ) , [13 ] obtain a job of degree at most 6 m − 6 6m - 6 6 m − 6 , and thus a non-migratory schedule on 6 m − 5 6m - 5 6 m − 5 machines. By bounding the degree of a suitable job directly, we improve this to 3 m − 2 3m - 2 3 m − 2 machines. However, this bound is tight, as there are canonical schedules whose conflict graph is a clique on 3 m − 2 3m - 2 3 m − 2 jobs. Hence, canonicity alone does not suffice for 2 m − 1 2m - 1 2 m − 1 machines, which motivates supercanonical schedules and the recoloring argument of § 3 .
Theorem 20. Let S S S be a canonical schedule on m m m machines. Then the chromatic number of the conflict graph satisfies χ ( G S ) ≤ 3 m − 2 \chi(G^S) \le3m - 2 χ ( G S ) ≤ 3 m − 2 , and this bound is tight.
We prove the upper bound in Sections A.1 to A.3 and its tightness in Section A.4. In more detail, we identify in Section A.1 a block in which many neighbors of a job k k k must be processed. Next, in Section A.2, we partition the neighborhood of k k k accordingly and bound most of its parts. Finally, in Section A.3, we find a job for which the remaining parts are small as well.
Throughout, let S S S be a canonical schedule on m m m machines with canonical ordering ≺ \prec ≺ , let G : = G S G := G^S G := G S , and let N ( k ) : = N G ( k ) N(k) := N_G(k) N ( k ) := N G ( k ) . We use the span [ ρ j , δ j ] [\rho_j, \delta_j] [ ρ j , δ j ] of a job j j j in place of its window, that is, r j : = b ρ j r_j := b_{\rho_j} r j := b ρ j and d j : = b δ j + 1 d_j := b_{\delta_j+1} d j := b δ j + 1 . Moreover, Theorem 7 only uses canonicity, so it also applies here.
Structure Lemma
Fix a job k k k with ∣ N ( k ) ∣ ≥ m |N(k)| \ge m ∣ N ( k ) ∣ ≥ m , as jobs with fewer neighbors have degree at most m − 1 ≤ 3 m − 3 m - 1 \le3m - 3 m − 1 ≤ 3 m − 3 . Let N 0 ( k ) N_0(k) N 0 ( k ) be the set of the m m m last neighbors of k k k in ≺ \prec ≺ . We define the critical block of k k k as the earliest last common block of k k k with a job in N 0 ( k ) N_0(k) N 0 ( k ) , that is,
γ k : = min { L j ′ k ∣ j ′ ∈ N 0 ( k ) } . \gamma_k := \min\{L_{j'k} \mid j' \in N_0(k)\}. γ k := min { L j ′ k ∣ j ′ ∈ N 0 ( k )} .
Moreover, we fix a pivot g k ∈ N 0 ( k ) g_k \in N_0(k) g k ∈ N 0 ( k ) with L g k k = γ k L_{g_k k} = \gamma_k L g k k = γ k . Thus, both k k k and g k g_k g k are processed in block γ k \gamma_k γ k , and L j ′ k ≥ γ k L_{j'k} \ge\gamma_k L j ′ k ≥ γ k for every j ′ ∈ N 0 ( k ) j' \in N_0(k) j ′ ∈ N 0 ( k ) . Every neighbor outside N 0 ( k ) N_0(k) N 0 ( k ) precedes the pivot. The following lemma therefore places all such neighbors whose spans contain γ k \gamma_k γ k in the same processing block, where the machine capacity bounds their number. The following structure lemma states that every neighbor of k k k that precedes the pivot and whose span contains the critical block is processed in the critical block (see Figure 4 ).
Lemma 21. Let j ∈ N ( k ) j \in N(k) j ∈ N ( k ) with j ≺ g k j \prec g_k j ≺ g k and ρ j ≤ γ k ≤ δ j \rho_j \le\gamma_k \le\delta_j ρ j ≤ γ k ≤ δ j . Then j ∈ S γ k j \in S_{\gamma_k} j ∈ S γ k .
Proof. It suffices to show that L j k ≥ γ k L_{jk} \ge\gamma_k L j k ≥ γ k . Indeed, if L j k = γ k L_{jk} = \gamma_k L j k = γ k , then j ∈ S γ k j \in S_{\gamma_k} j ∈ S γ k . If L j k > γ k L_{jk} > \gamma_k L j k > γ k , then g k ∉ S L j k g_k \notin S_{L_{jk}} g k ∈ / S L j k by maximality of L g k k = γ k L_{g_k k} = \gamma_k L g k k = γ k , since k ∈ S L j k k \in S_{L_{jk}} k ∈ S L j k . Hence, if j ∉ S γ k j \notin S_{\gamma_k} j ∈ / S γ k , a priority swap exists for j ≺ g k j \prec g_k j ≺ g k at blocks γ k < L j k \gamma_k < L_{jk} γ k < L j k , since ρ j ≤ γ k \rho_j \le\gamma_k ρ j ≤ γ k , g k ∈ S γ k ∖ S L j k g_k \in S_{\gamma_k} \setminus S_{L_{jk}} g k ∈ S γ k ∖ S L j k , and j ∈ S L j k ∖ S γ k j \in S_{L_{jk}} \setminus S_{\gamma_k} j ∈ S L j k ∖ S γ k . We show L j k ≥ γ k L_{jk} \ge\gamma_k L j k ≥ γ k by distinguishing three cases.
Case 1: Suppose that δ j ≤ δ k \delta_j \le\delta_k δ j ≤ δ k , and assume for contradiction that L j k < γ k L_{jk} < \gamma_k L j k < γ k . If j ≺ k j \prec k j ≺ k , then Theorem 7 gives k ∉ S γ k k \notin S_{\gamma_k} k ∈ / S γ k , since L j k < γ k ≤ δ j L_{jk} < \gamma_k \le\delta_j L j k < γ k ≤ δ j . If k ≺ j k \prec j k ≺ j , then Theorem 7 gives j ∉ S δ j j \notin S_{\delta_j} j ∈ / S δ j , since L j k < δ j ≤ δ k L_{jk} < \delta_j \le\delta_k L j k < δ j ≤ δ k . Both contradict the definitions of γ k \gamma_k γ k and δ j \delta_j δ j .
Case 2: Suppose that δ j > δ k \delta_j > \delta_k δ j > δ k and j ∈ N 0 ( k ) j \in N_0(k) j ∈ N 0 ( k ) . Then L j k ≥ γ k L_{jk} \ge\gamma_k L j k ≥ γ k by definition of the critical block γ k \gamma_k γ k .
Case 3: Suppose that δ j > δ k \delta_j > \delta_k δ j > δ k and j ∉ N 0 ( k ) j \notin N_0(k) j ∈ / N 0 ( k ) . Then j ≺ j ′ j \prec j' j ≺ j ′ for every j ′ ∈ N 0 ( k ) j' \in N_0(k) j ′ ∈ N 0 ( k ) , and ρ j ≤ γ k ≤ L j ′ k ≤ δ k < δ j \rho_j \le\gamma_k \le L_{j'k} \le\delta_k < \delta_j ρ j ≤ γ k ≤ L j ′ k ≤ δ k < δ j . If j ∉ S L j ′ k j \notin S_{L_{j'k}} j ∈ / S L j ′ k , then j ′ ∈ S δ j j' \in S_{\delta_j} j ′ ∈ S δ j , as otherwise a priority swap exists for j ≺ j ′ j \prec j' j ≺ j ′ at blocks L j ′ k < δ j L_{j'k} < \delta_j L j ′ k < δ j . Since S δ j S_{\delta_j} S δ j contains j j j and at most m − 1 m-1 m − 1 other jobs, we obtain j ∈ S L j ′ k j \in S_{L_{j'k}} j ∈ S L j ′ k for some j ′ ∈ N 0 ( k ) j' \in N_0(k) j ′ ∈ N 0 ( k ) . Thus, L j k ≥ L j ′ k ≥ γ k L_{jk} \ge L_{j'k} \ge\gamma_k L j k ≥ L j ′ k ≥ γ k .
Neighborhood Decomposition
We partition the neighbors of k k k outside N 0 ( k ) N_0(k) N 0 ( k ) according to the position of their spans relative to the critical block γ k \gamma_k γ k and the span of k k k . Note that ρ k ≤ γ k ≤ δ k \rho_k \le\gamma_k \le\delta_k ρ k ≤ γ k ≤ δ k , since k k k is processed in block γ k \gamma_k γ k . We define
N 1 ( k ) : = { j ∈ N ( k ) ∖ N 0 ( k ) ∣ ρ j ≤ γ k ≤ δ j } , N 2 ( k ) : = { j ∈ N ( k ) ∖ N 0 ( k ) ∣ ρ j < ρ k and δ j < γ k } , N 3 ( k ) : = { j ∈ N ( k ) ∖ N 0 ( k ) ∣ γ k < ρ j and δ k < δ j } , N 4 ( k ) : = { j ∈ N ( k ) ∖ N 0 ( k ) ∣ γ k ∉ [ ρ j , δ j ] and [ ρ j , δ j ] ⊆ [ ρ k , δ k ] } . \begin{aligned}
N_1(k) &:= \{j \in N(k) \setminus N_0(k) \mid\rho_j \le\gamma_k \le\delta_j\},\\
N_2(k) &:= \{j \in N(k) \setminus N_0(k) \mid\rho_j < \rho_k \text{ and } \delta_j < \gamma_k\},\\
N_3(k) &:= \{j \in N(k) \setminus N_0(k) \mid\gamma_k < \rho_j \text{ and } \delta_k < \delta_j\},\\
N_4(k) &:= \{j \in N(k) \setminus N_0(k) \mid\gamma_k \notin[\rho_j,\delta_j] \text{ and } [\rho_j,\delta_j] \subseteq[\rho_k,\delta_k]\}.
\end{aligned} N 1 ( k ) N 2 ( k ) N 3 ( k ) N 4 ( k ) := { j ∈ N ( k ) ∖ N 0 ( k ) ∣ ρ j ≤ γ k ≤ δ j } , := { j ∈ N ( k ) ∖ N 0 ( k ) ∣ ρ j < ρ k and δ j < γ k } , := { j ∈ N ( k ) ∖ N 0 ( k ) ∣ γ k < ρ j and δ k < δ j } , := { j ∈ N ( k ) ∖ N 0 ( k ) ∣ γ k ∈ / [ ρ j , δ j ] and [ ρ j , δ j ] ⊆ [ ρ k , δ k ]} .
Thus, the spans of jobs in N 1 ( k ) N_1(k) N 1 ( k ) contain the critical block. The spans of jobs in N 2 ( k ) N_2(k) N 2 ( k ) lie before the critical block and start before k k k , and the spans of jobs in N 3 ( k ) N_3(k) N 3 ( k ) lie after the critical block and end after k k k . The spans of jobs in N 4 ( k ) N_4(k) N 4 ( k ) avoid the critical block and lie within the span of k k k .
Lemma 22. The sets N 0 ( k ) , … , N 4 ( k ) N_0(k), \ldots, N_4(k) N 0 ( k ) , … , N 4 ( k ) partition N ( k ) N(k) N ( k ) .
Proof. The sets are pairwise disjoint, since only spans in N 1 ( k ) N_1(k) N 1 ( k ) contain γ k \gamma_k γ k , spans in N 2 ( k ) N_2(k) N 2 ( k ) and N 3 ( k ) N_3(k) N 3 ( k ) are not contained in [ ρ k , δ k ] [\rho_k,\delta_k] [ ρ k , δ k ] , and δ j < γ k < ρ j \delta_j < \gamma_k < \rho_j δ j < γ k < ρ j is impossible. Let j ∈ N ( k ) ∖ ( N 0 ( k ) ∪ N 1 ( k ) ) j \in N(k) \setminus(N_0(k) \cup N_1(k)) j ∈ N ( k ) ∖ ( N 0 ( k ) ∪ N 1 ( k )) . Then δ j < γ k \delta_j < \gamma_k δ j < γ k or γ k < ρ j \gamma_k < \rho_j γ k < ρ j . In the first case, we have j ∈ N 2 ( k ) j \in N_2(k) j ∈ N 2 ( k ) if ρ j < ρ k \rho_j < \rho_k ρ j < ρ k , and otherwise [ ρ j , δ j ] ⊆ [ ρ k , δ k ] [\rho_j,\delta_j] \subseteq[\rho_k,\delta_k] [ ρ j , δ j ] ⊆ [ ρ k , δ k ] since δ j < γ k ≤ δ k \delta_j < \gamma_k \le\delta_k δ j < γ k ≤ δ k , thus j ∈ N 4 ( k ) j \in N_4(k) j ∈ N 4 ( k ) . In the second case, we have j ∈ N 3 ( k ) j \in N_3(k) j ∈ N 3 ( k ) if δ k < δ j \delta_k < \delta_j δ k < δ j , and otherwise [ ρ j , δ j ] ⊆ [ ρ k , δ k ] [\rho_j,\delta_j] \subseteq[\rho_k,\delta_k] [ ρ j , δ j ] ⊆ [ ρ k , δ k ] since ρ k ≤ γ k < ρ j \rho_k \le\gamma_k < \rho_j ρ k ≤ γ k < ρ j , so j ∈ N 4 ( k ) j \in N_4(k) j ∈ N 4 ( k ) . Therefore, the sets partition the neighborhood N ( k ) N(k) N ( k ) .
By definition, ∣ N 0 ( k ) ∣ = m |N_0(k)| = m ∣ N 0 ( k ) ∣ = m . The structure lemma bounds N 1 ( k ) N_1(k) N 1 ( k ) .
Corollary 23. It holds that ∣ N 1 ( k ) ∣ ≤ m − 2 |N_1(k)| \le m - 2 ∣ N 1 ( k ) ∣ ≤ m − 2 .
Proof. Every job j ∈ N 1 ( k ) j \in N_1(k) j ∈ N 1 ( k ) satisfies j ≺ g k j \prec g_k j ≺ g k , because j ∉ N 0 ( k ) j \notin N_0(k) j ∈ / N 0 ( k ) by Theorem 22, and ρ j ≤ γ k ≤ δ j \rho_j \le\gamma_k \le\delta_j ρ j ≤ γ k ≤ δ j . By Theorem 21, all jobs in N 1 ( k ) ∪ { k , g k } N_1(k) \cup\{k,g_k\} N 1 ( k ) ∪ { k , g k } are processed in block γ k \gamma_k γ k . Since k , g k ∉ N 1 ( k ) k,g_k \notin N_1(k) k , g k ∈ / N 1 ( k ) and at most m m m jobs are processed in a block, we obtain the bound ∣ N 1 ( k ) ∣ ≤ m − 2 |N_1(k)| \le m - 2 ∣ N 1 ( k ) ∣ ≤ m − 2 .
Figure 5. Schematic illustration of Theorem 22, showing spans instead of processing: the bar of a job j j j extends from the start of B ρ j B_{\rho_j} B ρ j to the end of B δ j B_{\delta_j} B δ j . The spans in N 1 ( k ) N_1(k) N 1 ( k ) contain the critical block γ k \gamma_k γ k . The spans in N 2 ( k ) N_2(k) N 2 ( k ) lie before γ k \gamma_k γ k and start before k k k , and the spans in N 3 ( k ) N_3(k) N 3 ( k ) lie after γ k \gamma_k γ k and end after k k k . The spans in N 4 ( k ) N_4(k) N 4 ( k ) avoid γ k \gamma_k γ k and lie within the span of k k k , so N 4 ( k ) N_4(k) N 4 ( k ) is empty if k k k is a root. The jobs in N 0 ( k ) N_0(k) N 0 ( k ) are the m m m last neighbors of k k k in ≺ \prec ≺ .
To exclude N 4 ( k ) N_4(k) N 4 ( k ) , we consider jobs whose span contains no other span. We say that a job j j j lies inside a job k ≠ j k \ne j k = j if [ ρ j , δ j ] ⊊ [ ρ k , δ k ] [\rho_j,\delta_j] \subsetneq[\rho_k,\delta_k] [ ρ j , δ j ] ⊊ [ ρ k , δ k ] , or [ ρ j , δ j ] = [ ρ k , δ k ] [\rho_j,\delta_j]=[\rho_k,\delta_k] [ ρ j , δ j ] = [ ρ k , δ k ] and j ≺ k j \prec k j ≺ k . This relation is transitive and irreflexive. A job k k k is a root if no job lies inside k k k . Since J J J is finite, every job is a root or some root lies inside it. Thus, roots have inclusion-minimal spans, with equal spans resolved by the order ≺ \prec ≺ . Choosing a root eliminates N 4 ( k ) N_4(k) N 4 ( k ) ; only the neighbors in N 2 ( k ) N_2(k) N 2 ( k ) and N 3 ( k ) N_3(k) N 3 ( k ) remain to be bounded.
Lemma 24. Let k k k be a root with ∣ N ( k ) ∣ ≥ m |N(k)| \ge m ∣ N ( k ) ∣ ≥ m . Then
∣ N ( k ) ∣ ≤ 2 m − 2 + ∣ N 2 ( k ) ∣ + ∣ N 3 ( k ) ∣ . |N(k)| \le2m - 2 + |N_2(k)| + |N_3(k)|. ∣ N ( k ) ∣ ≤ 2 m − 2 + ∣ N 2 ( k ) ∣ + ∣ N 3 ( k ) ∣.
Proof. For j ∈ N 4 ( k ) j \in N_4(k) j ∈ N 4 ( k ) , we have [ ρ j , δ j ] ⊊ [ ρ k , δ k ] [\rho_j,\delta_j] \subsetneq[\rho_k,\delta_k] [ ρ j , δ j ] ⊊ [ ρ k , δ k ] , the intervals are not equal because γ k ∈ [ ρ k , δ k ] \gamma_k \in[\rho_k,\delta_k] γ k ∈ [ ρ k , δ k ] but γ k ∉ [ ρ j , δ j ] \gamma_k \notin[\rho_j,\delta_j] γ k ∈ / [ ρ j , δ j ] . Thus, j j j lies inside k k k , so N 4 ( k ) = ∅ N_4(k)=\varnothing N 4 ( k ) = ∅ as k k k is a root by assumption. By Theorems 22 and 23, we obtain the bound ∣ N ( k ) ∣ ≤ m + ( m − 2 ) + ∣ N 2 ( k ) ∣ + ∣ N 3 ( k ) ∣ |N(k)| \le m + (m-2) + |N_2(k)| + |N_3(k)| ∣ N ( k ) ∣ ≤ m + ( m − 2 ) + ∣ N 2 ( k ) ∣ + ∣ N 3 ( k ) ∣ .
In Section A.3, we find a root k k k with ∣ N 2 ( k ) ∣ ≤ m − 1 |N_2(k)| \le m-1 ∣ N 2 ( k ) ∣ ≤ m − 1 and N 3 ( k ) = ∅ N_3(k)=\varnothing N 3 ( k ) = ∅ , which yields the desired bound ∣ N ( k ) ∣ ≤ 3 m − 3 |N(k)| \le3m-3 ∣ N ( k ) ∣ ≤ 3 m − 3 .
Root Sequence
Let k k k be a root with ∣ N ( k ) ∣ ≥ m |N(k)| \ge m ∣ N ( k ) ∣ ≥ m and N 3 ( k ) ≠ ∅ N_3(k) \ne\varnothing N 3 ( k ) = ∅ , and let e k e_k e k be the first job of N 3 ( k ) N_3(k) N 3 ( k ) in ≺ \prec ≺ . We define the successor k ′ k' k ′ of k k k as e k e_k e k if e k e_k e k is a root, and otherwise as the first root in ≺ \prec ≺ that lies inside e k e_k e k . Thus, the span of k ′ k' k ′ is contained in the span of e k e_k e k , and no root that lies inside e k e_k e k precedes k ′ k' k ′ in ≺ \prec ≺ . Moreover, we have that ρ k ≤ γ k < ρ e k ≤ ρ k ′ \rho_k \le\gamma_k < \rho_{e_k} \le\rho_{k'} ρ k ≤ γ k < ρ e k ≤ ρ k ′ , since e k ∈ N 3 ( k ) e_k \in N_3(k) e k ∈ N 3 ( k ) (see Figure 6 ). Moving to a successor advances the first processing block. The next lemma shows that, unless the successor already has degree less than m m m , its set N 2 N_2 N 2 has size at most m − 1 m-1 m − 1 . Repeating this step eventually reaches a root with small degree or with N 3 N_3 N 3 empty, completing the degree bound.
Figure 6. Schematic illustration of successor in root sequence and Theorem 25. The first job e k e_k e k of N 3 ( k ) N_3(k) N 3 ( k ) starts after the critical block γ k \gamma_k γ k and ends after k k k , and the successor k ′ k' k ′ is a root inside e k e_k e k . The job j ∈ N 2 ( k ′ ) j \in N_2(k') j ∈ N 2 ( k ′ ) ends before γ k ′ \gamma_{k'} γ k ′ , but its span contains γ k \gamma_k γ k , so j ∈ N 1 ( k ) j \in N_1(k) j ∈ N 1 ( k ) .
Lemma 25. Let k ′ k' k ′ be the successor of a root k k k with ∣ N ( k ′ ) ∣ ≥ m |N(k')| \ge m ∣ N ( k ′ ) ∣ ≥ m . Then
N 2 ( k ′ ) ⊆ N 1 ( k ) ∪ { k } . N_2(k') \subseteq N_1(k) \cup\{k\}. N 2 ( k ′ ) ⊆ N 1 ( k ) ∪ { k } .
Proof. Let e : = e k e := e_k e := e k , and let j ∈ N 2 ( k ′ ) ∖ { k } j \in N_2(k') \setminus\{k\} j ∈ N 2 ( k ′ ) ∖ { k } . Since e ∈ N 3 ( k ) e \in N_3(k) e ∈ N 3 ( k ) , we have γ k < ρ e \gamma_k < \rho_e γ k < ρ e and δ k < δ e \delta_k < \delta_e δ k < δ e . Moreover, j ≺ e j \prec e j ≺ e , since δ j < γ k ′ ≤ δ k ′ ≤ δ e \delta_j < \gamma_{k'} \le\delta_{k'} \le\delta_e δ j < γ k ′ ≤ δ k ′ ≤ δ e . For any j ′ ∈ N 0 ( k ) j' \in N_0(k) j ′ ∈ N 0 ( k ) , we have e ≺ j ′ e \prec j' e ≺ j ′ because e ∈ N ( k ) ∖ N 0 ( k ) e \in N(k) \setminus N_0(k) e ∈ N ( k ) ∖ N 0 ( k ) , hence by transitivity j ≺ j ′ j \prec j' j ≺ j ′ , and therefore we have j ∉ N 0 ( k ) j \notin N_0(k) j ∈ / N 0 ( k ) . Finally, δ j ≥ ρ k ′ ≥ ρ e > γ k \delta_j \ge\rho_{k'} \ge\rho_e > \gamma_k δ j ≥ ρ k ′ ≥ ρ e > γ k , since j j j and k ′ k' k ′ are adjacent. It remains to show that ρ j ≤ γ k \rho_j \le\gamma_k ρ j ≤ γ k and j ∈ N ( k ) j \in N(k) j ∈ N ( k ) , as then j ∈ N 1 ( k ) j \in N_1(k) j ∈ N 1 ( k ) by definition.
First, we show that ρ j ≤ δ k \rho_j \le\delta_k ρ j ≤ δ k . Otherwise, ρ e ≤ δ k < ρ j \rho_e \le\delta_k < \rho_j ρ e ≤ δ k < ρ j , since e e e and k k k are adjacent, and δ j < δ e \delta_j < \delta_e δ j < δ e . Hence, the span of j j j lies strictly inside the span of e e e . Let u u u be j j j or a root that lies inside j j j . Then u u u is a root that lies inside e e e with δ u ≤ δ j < δ k ′ \delta_u \le\delta_j < \delta_{k'} δ u ≤ δ j < δ k ′ , so u ≺ k ′ u \prec k' u ≺ k ′ , contradicting the choice of k ′ k' k ′ .
Next, we show that ρ j ≤ γ k \rho_j \le\gamma_k ρ j ≤ γ k . Suppose that γ k < ρ j ≤ δ k \gamma_k < \rho_j \le\delta_k γ k < ρ j ≤ δ k . Since ρ k ≤ γ k < ρ j \rho_k \le\gamma_k < \rho_j ρ k ≤ γ k < ρ j and k k k is a root, j j j does not lie inside k k k , so δ k < δ j \delta_k < \delta_j δ k < δ j and k ≺ j k \prec j k ≺ j . If j ∉ N ( k ) j \notin N(k) j ∈ / N ( k ) , then we have ρ j < δ k \rho_j < \delta_k ρ j < δ k , k ∉ S ρ j k \notin S_{\rho_j} k ∈ / S ρ j , and j ∉ S δ k j \notin S_{\delta_k} j ∈ / S δ k , so a priority swap exists for k ≺ j k \prec j k ≺ j at blocks ρ j < δ k \rho_j < \delta_k ρ j < δ k . Thus, j ∈ N ( k ) ∖ N 0 ( k ) j \in N(k) \setminus N_0(k) j ∈ N ( k ) ∖ N 0 ( k ) with γ k < ρ j \gamma_k < \rho_j γ k < ρ j and δ k < δ j \delta_k < \delta_j δ k < δ j , so j ∈ N 3 ( k ) j \in N_3(k) j ∈ N 3 ( k ) . Since j ≺ e j \prec e j ≺ e , this contradicts the choice of e e e .
Finally, we show that j ∈ N ( k ) j \in N(k) j ∈ N ( k ) . If δ j ≤ δ k \delta_j \le\delta_k δ j ≤ δ k and k ≺ j k \prec j k ≺ j , then δ j = δ k \delta_j = \delta_k δ j = δ k , so both j j j and k k k are processed in block δ k \delta_k δ k . If δ j ≤ δ k \delta_j \le\delta_k δ j ≤ δ k and j ≺ k j \prec k j ≺ k , then j ∈ S γ k j \in S_{\gamma_k} j ∈ S γ k or k ∈ S δ j k \in S_{\delta_j} k ∈ S δ j , as otherwise a priority swap exists for j ≺ k j \prec k j ≺ k at blocks γ k < δ j \gamma_k < \delta_j γ k < δ j . In both cases, we have j ∈ N ( k ) j \in N(k) j ∈ N ( k ) , because k ∈ S γ k k \in S_{\gamma_k} k ∈ S γ k . If δ k < δ j \delta_k < \delta_j δ k < δ j , then ρ j ≤ γ k ≤ L j ′ k ≤ δ k < δ j \rho_j \le\gamma_k \le L_{j'k} \le\delta_k < \delta_j ρ j ≤ γ k ≤ L j ′ k ≤ δ k < δ j for every j ′ ∈ N 0 ( k ) j' \in N_0(k) j ′ ∈ N 0 ( k ) . If j ∉ S L j ′ k j \notin S_{L_{j'k}} j ∈ / S L j ′ k , then j ′ ∈ S δ j j' \in S_{\delta_j} j ′ ∈ S δ j , as otherwise a priority swap exists for j ≺ j ′ j \prec j' j ≺ j ′ at blocks L j ′ k < δ j L_{j'k} < \delta_j L j ′ k < δ j . Since S δ j S_{\delta_j} S δ j contains j j j and at most m − 1 m-1 m − 1 other jobs, we obtain j ∈ S L j ′ k j \in S_{L_{j'k}} j ∈ S L j ′ k for some j ′ ∈ N 0 ( k ) j' \in N_0(k) j ′ ∈ N 0 ( k ) , and thus j ∈ N ( k ) j \in N(k) j ∈ N ( k ) .
Lemma 26. Some job has at most 3 m − 3 3m-3 3 m − 3 neighbors.
Proof. Starting from the first root in ≺ \prec ≺ , we repeatedly move to the successor as long as it exists. Since ρ k ≤ γ k < ρ k ′ \rho_k \le\gamma_k < \rho_{k'} ρ k ≤ γ k < ρ k ′ for every root k k k with successor k ′ k' k ′ , this terminates in a root k k k with ∣ N ( k ) ∣ < m |N(k)| < m ∣ N ( k ) ∣ < m or N 3 ( k ) = ∅ N_3(k) = \varnothing N 3 ( k ) = ∅ . If ∣ N ( k ) ∣ < m |N(k)| < m ∣ N ( k ) ∣ < m , we are done, so assume N 3 ( k ) = ∅ N_3(k) = \varnothing N 3 ( k ) = ∅ . We show that ∣ N 2 ( k ) ∣ ≤ m − 1 |N_2(k)| \le m-1 ∣ N 2 ( k ) ∣ ≤ m − 1 . If k k k is the successor of a root k 0 k_0 k 0 , then N 2 ( k ) ⊆ N 1 ( k 0 ) ∪ { k 0 } N_2(k) \subseteq N_1(k_0) \cup\{k_0\} N 2 ( k ) ⊆ N 1 ( k 0 ) ∪ { k 0 } by Theorem 25, so ∣ N 2 ( k ) ∣ ≤ ( m − 2 ) + 1 |N_2(k)| \le(m-2)+1 ∣ N 2 ( k ) ∣ ≤ ( m − 2 ) + 1 by Theorem 23. Otherwise, k k k is the first root in ≺ \prec ≺ , and N 2 ( k ) = ∅ N_2(k) = \varnothing N 2 ( k ) = ∅ . Indeed, for j ∈ N 2 ( k ) j \in N_2(k) j ∈ N 2 ( k ) , the job j j j or a root that lies inside j j j ends no later than δ j < γ k ≤ δ k \delta_j < \gamma_k \le\delta_k δ j < γ k ≤ δ k , and is thus a root preceding k k k . We conclude by Theorem 24 that ∣ N ( k ) ∣ ≤ 2 m − 2 + ( m − 1 ) = 3 m − 3 |N(k)| \le2m-2+(m-1)=3m-3 ∣ N ( k ) ∣ ≤ 2 m − 2 + ( m − 1 ) = 3 m − 3 .
We now prove the upper bound of Theorem 20. We show tightness of the chromatic bound in Section A.4.
Proof. For every nonempty J ′ ⊆ J J' \subseteq J J ′ ⊆ J , the schedule with processing sets S t ∩ J ′ S_t \cap J' S t ∩ J ′ is canonical, and its conflict graph is G [ J ′ ] G[J'] G [ J ′ ] . Applying Theorem 26 to this schedule yields δ ( G [ J ′ ] ) ≤ 3 m − 3 \delta(G[J']) \le3m-3 δ ( G [ J ′ ]) ≤ 3 m − 3 . Hence, χ ( G ) ≤ 3 m − 2 \chi(G) \le3m-2 χ ( G ) ≤ 3 m − 2 by (3).
Tightness
We show that the bound of Theorem 20 cannot be improved using canonicity alone.
Proposition 27. For every integer m ≥ 2 m \ge2 m ≥ 2 , there is a canonical schedule S \mathcal{S} S on m m m machines with the conflict graph G S G^{\mathcal{S}} G S being a clique on 3 m − 2 3m-2 3 m − 2 jobs.
Proof. Let U : = { u 1 , … , u m − 1 } U := \{u_1,\ldots,u_{m-1}\} U := { u 1 , … , u m − 1 } , V : = { v 1 , … , v m − 1 } V := \{v_1,\ldots,v_{m-1}\} V := { v 1 , … , v m − 1 } , and W : = { w 1 , … , w m } W := \{w_1,\ldots,w_m\} W := { w 1 , … , w m } , and let J : = U ∪ V ∪ W J := U \cup V \cup W J := U ∪ V ∪ W , so ∣ J ∣ = 3 m − 2 |J| = 3m - 2 ∣ J ∣ = 3 m − 2 . We index the jobs in the order u 1 , … , u m − 1 , v 1 , … , v m − 1 , w 1 , … , w m u_1,\ldots,u_{m-1},v_1,\ldots,v_{m-1},w_1,\ldots,w_m u 1 , … , u m − 1 , v 1 , … , v m − 1 , w 1 , … , w m . The schedule S S S has the unit blocks B t = [ t − 1 , t ) B_t = [t-1,t) B t = [ t − 1 , t ) for t ∈ [ 3 m ] t \in[3m] t ∈ [ 3 m ] with processing sets
S t : = { U ∪ { w m + 1 − t } if t ∈ { 1 , … , m } , U ∪ { v t − m } if t ∈ { m + 1 , … , 2 m − 1 } , V ∪ { w t − 2 m + 1 } if t ∈ { 2 m , … , 3 m − 1 } , W if t = 3 m . S_t := \begin{cases}
U \cup\{w_{m+1-t}\} & \text{if } t \in\{1,\ldots,m\},\\
U \cup\{v_{t-m}\} & \text{if } t \in\{m+1,\ldots,2m-1\},\\
V \cup\{w_{t-2m+1}\} & \text{if } t \in\{2m,\ldots,3m-1\},\\
W & \text{if } t = 3m.
\end{cases} S t := ⎩ ⎨ ⎧ U ∪ { w m + 1 − t } U ∪ { v t − m } V ∪ { w t − 2 m + 1 } W if t ∈ { 1 , … , m } , if t ∈ { m + 1 , … , 2 m − 1 } , if t ∈ { 2 m , … , 3 m − 1 } , if t = 3 m .
That is, the jobs of U U U run together with w m , … , w 1 w_m,\ldots,w_1 w m , … , w 1 and then with v 1 , … , v m − 1 v_1,\ldots,v_{m-1} v 1 , … , v m − 1 . Afterwards, the jobs of V V V run together with w 1 , … , w m w_1,\ldots,w_m w 1 , … , w m , and finally the jobs of W W W run together (see Figure 7 ). Every processing set contains exactly m m m jobs. For every job j j j , define the processing time p j p_j p j as the number of blocks in which j j j is processed, furthermore, define r j : = b ρ j r_j := b_{\rho_j} r j := b ρ j and d j : = b δ j + 1 d_j := b_{\delta_j+1} d j := b δ j + 1 . Hence, S S S is a feasible schedule on m m m machines.
Figure 7. The canonical schedule of Theorem 27 for m = 3 m = 3 m = 3 , with unit blocks. Left: The dashed lines separate the four phases, and the labels below indicate their processing sets. Right: Every pair of jobs is processed together, so the conflict graph is the complete graph K 7 K_7 K 7 .
The jobs of U U U , V V V , and W W W have their last blocks 2 m − 1 2m-1 2 m − 1 , 3 m − 1 3m-1 3 m − 1 , and 3 m 3m 3 m , respectively. With ties broken by index, the canonical ordering ≺ \prec ≺ is the order in which we indexed the jobs.
We show that S S S admits no priority swap. Suppose that a priority swap exists for j 1 ≺ j 2 j_1 \prec j_2 j 1 ≺ j 2 at blocks t 1 < t 2 t_1 < t_2 t 1 < t 2 . Since ρ j 1 ≤ t 1 \rho_{j_1} \le t_1 ρ j 1 ≤ t 1 , j 1 ∉ S t 1 j_1 \notin S_{t_1} j 1 ∈ / S t 1 , and j 1 ∈ S t 2 j_1 \in S_{t_2} j 1 ∈ S t 2 , we have ρ j 1 < t 1 < t 2 ≤ δ j 1 \rho_{j_1} < t_1 < t_2 \le\delta_{j_1} ρ j 1 < t 1 < t 2 ≤ δ j 1 . Thus, j 1 j_1 j 1 pauses in block t 1 t_1 t 1 . The jobs of U U U are processed in all blocks 1 , … , 2 m − 1 1,\ldots,2m-1 1 , … , 2 m − 1 and never pause, so j 1 ∉ U j_1 \notin U j 1 ∈ / U .
Suppose that j 1 = v i j_1 = v_i j 1 = v i . Job v i v_i v i is processed in block m + i m+i m + i and in all blocks 2 m , … , 3 m − 1 2m,\ldots,3m-1 2 m , … , 3 m − 1 . Hence, t 1 = m + l t_1 = m+l t 1 = m + l for some l > i l > i l > i . Since j 2 ∈ S m + l = U ∪ { v l } j_2 \in S_{m+l} = U \cup\{v_l\} j 2 ∈ S m + l = U ∪ { v l } and v i ≺ j 2 v_i \prec j_2 v i ≺ j 2 , we have j 2 = v l j_2 = v_l j 2 = v l . However, v l v_l v l is processed in all blocks 2 m , … , 3 m − 1 2m,\ldots,3m-1 2 m , … , 3 m − 1 , and in particular in block t 2 t_2 t 2 , contradicting j 2 ∉ S t 2 j_2 \notin S_{t_2} j 2 ∈ / S t 2 .
Suppose that j 1 = w i j_1 = w_i j 1 = w i . Since w i ≺ j 2 w_i \prec j_2 w i ≺ j 2 , we have j 2 = w l j_2 = w_l j 2 = w l for some l > i l > i l > i . Job w l w_l w l is processed in the blocks m + 1 − l m+1-l m + 1 − l , 2 m − 1 + l 2m-1+l 2 m − 1 + l , and 3 m 3m 3 m . We have m + 1 − l < m + 1 − i = ρ w i < t 1 m+1-l < m+1-i = \rho_{w_i} < t_1 m + 1 − l < m + 1 − i = ρ w i < t 1 , and w i ∈ S 3 m w_i \in S_{3m} w i ∈ S 3 m , so t 1 = 2 m − 1 + l t_1 = 2m-1+l t 1 = 2 m − 1 + l . Since 2 m − 1 + i < t 1 2m-1+i < t_1 2 m − 1 + i < t 1 , the only block after t 1 t_1 t 1 in which w i w_i w i is processed is 3 m 3m 3 m . Hence, we have t 2 = 3 m t_2 = 3m t 2 = 3 m , but w l ∈ S 3 m w_l \in S_{3m} w l ∈ S 3 m , contradicting j 2 ∉ S t 2 j_2 \notin S_{t_2} j 2 ∈ / S t 2 . Therefore, S S S is canonical.
Finally, every pair of distinct jobs is processed together in some block. Pairs within U U U , and pairs { u , w i } \{u,w_i\} { u , w i } with u ∈ U u \in U u ∈ U , are processed together in block m + 1 − i m+1-i m + 1 − i . Pairs { u , v i } \{u,v_i\} { u , v i } with u ∈ U u \in U u ∈ U are processed together in block m + i m+i m + i . Pairs within V V V , and pairs { v , w i } \{v,w_i\} { v , w i } with v ∈ V v \in V v ∈ V , are processed together in block 2 m − 1 + i 2m-1+i 2 m − 1 + i . Pairs within W W W are processed together in block 3 m 3m 3 m . Thus, we conclude that the conflict graph of the canonical schedule S S S is a complete graph on 3 m − 2 3m-2 3 m − 2 vertices.
The schedule of Theorem 27 is not supercanonical. For instance, a delay swap exists for w m w_m w m and w 1 w_1 w 1 at blocks ρ w 1 = m < 3 m − 1 \rho_{w_1} = m < 3m-1 ρ w 1 = m < 3 m − 1 , since it holds that ρ w m = 1 < m < 3 m − 1 < 3 m = δ w 1 \rho_{w_m} = 1 < m < 3m-1 < 3m = \delta_{w_1} ρ w m = 1 < m < 3 m − 1 < 3 m = δ w 1 , w m ∈ S 3 m − 1 ∖ S m w_m \in S_{3m-1} \setminus S_m w m ∈ S 3 m − 1 ∖ S m , and w 1 ∈ S m ∖ S 3 m − 1 w_1 \in S_m \setminus S_{3m-1} w 1 ∈ S m ∖ S 3 m − 1 . Moreover, the instance itself admits a non-migratory schedule on 2 m − 1 2m-1 2 m − 1 machines by Theorem 1 , so only this particular schedule requires 3 m − 2 3m-2 3 m − 2 machines. This shows that excluding delay swaps is essential for Theorem 10 .
Figure 8. The supercanonical schedule of Theorem 28 on two machines, with unit blocks numbered below the axis. Left: Every block contains exactly two jobs, and only j 3 j_3 j 3 , j 6 j_6 j 6 , and j 7 j_7 j 7 pause. Right: In the conflict graph, j 4 j_4 j 4 has degree 5 and every other job has degree 3, so the minimum degree exceeds 2 m − 2 = 2 2m-2=2 2 m − 2 = 2 .
Minimum Degree of Supercanonical Conflict Graphs
We show that a supercanonical conflict graph need not have a vertex of degree at most 2 m − 2 2m-2 2 m − 2 . Thus, the Szekeres–Wilf bound [21 ] does not suffice to establish ( 2 m − 1 ) (2m-1) ( 2 m − 1 ) -colorability. This motivates the recoloring argument using Kempe exchanges.
Proposition 28. There is a supercanonical schedule S S S on two machines with minimum degree δ ( G S ) = 3 \delta(G^S)=3 δ ( G S ) = 3 .
Proof. Let J : = { j 1 , … , j 8 } J := \{j_1,\ldots,j_8\} J := { j 1 , … , j 8 } . The schedule S S S has unit blocks B t = [ t − 1 , t ) B_t=[t-1,t) B t = [ t − 1 , t ) for t ∈ [ 13 ] t \in[13] t ∈ [ 13 ] , with processing sets
S 1 = { j 1 , j 7 } , S 2 = { j 1 , j 3 } , S 3 = { j 1 , j 2 } , S 4 = { j 2 , j 3 } , S 5 = { j 2 , j 4 } , S 6 = { j 3 , j 4 } , S 7 = { j 4 , j 7 } , S 8 = { j 4 , j 6 } , S 9 = { j 4 , j 5 } , S 10 = { j 5 , j 6 } , S 11 = { j 5 , j 8 } , S 12 = { j 6 , j 8 } , S 13 = { j 7 , j 8 } . \begin{aligned}
S_1 &= \{j_1,j_7\}, & S_2 &= \{j_1,j_3\}, & S_3 &= \{j_1,j_2\},\\
S_4 &= \{j_2,j_3\}, & S_5 &= \{j_2,j_4\}, & S_6 &= \{j_3,j_4\},\\
S_7 &= \{j_4,j_7\}, & S_8 &= \{j_4,j_6\}, & S_9 &= \{j_4,j_5\},\\
S_{10} &= \{j_5,j_6\}, & S_{11} &= \{j_5,j_8\}, & S_{12} &= \{j_6,j_8\},\\
S_{13} &= \{j_7,j_8\}.
\end{aligned} S 1 S 4 S 7 S 10 S 13 = { j 1 , j 7 } , = { j 2 , j 3 } , = { j 4 , j 7 } , = { j 5 , j 6 } , = { j 7 , j 8 } . S 2 S 5 S 8 S 11 = { j 1 , j 3 } , = { j 2 , j 4 } , = { j 4 , j 6 } , = { j 5 , j 8 } , S 3 S 6 S 9 S 12 = { j 1 , j 2 } , = { j 3 , j 4 } , = { j 4 , j 5 } , = { j 6 , j 8 } ,
For every job j j j , define p j p_j p j as the number of blocks in which j j j is processed, and let r j : = b ρ j r_j := b_{\rho_j} r j := b ρ j and d j : = b δ j + 1 d_j := b_{\delta_j+1} d j := b δ j + 1 . Every processing set contains exactly two jobs, so S S S is feasible on two machines. The last processing blocks are
( δ j 1 , … , δ j 8 ) = ( 3 , 5 , 6 , 9 , 11 , 12 , 13 , 13 ) , (\delta_{j_1},\ldots,\delta_{j_8})=(3,5,6,9,11,12,13,13), ( δ j 1 , … , δ j 8 ) = ( 3 , 5 , 6 , 9 , 11 , 12 , 13 , 13 ) ,
so, with ties broken by index, the canonical ordering is j 1 ≺ ⋯ ≺ j 8 j_1 \prec\cdots\prec j_8 j 1 ≺ ⋯ ≺ j 8 . Only j 3 , j 6 , j 7 j_3,j_6,j_7 j 3 , j 6 , j 7 pause between their first and last processing blocks, so only these can be the ≺ \prec ≺ -earlier job of a priority swap. During a pause of j 3 j_3 j 3 , the only ≺ \prec ≺ -later job processed is j 4 j_4 j 4 in block 5. However, j 4 j_4 j 4 also runs in block 6, the only subsequent processing block of j 3 j_3 j 3 . Similarly, for j 6 j_6 j 6 , the only possibility is j 8 j_8 j 8 in block 11, which also runs in block 12. Finally, the only job later than j 7 j_7 j 7 is j 8 j_8 j 8 , which runs in blocks 11, 12, 13. Its first two blocks precede the final block of j 7 j_7 j 7 , which also contains j 8 j_8 j 8 . Hence, no priority swap exists. The later-starting job of a delay swap must also pause. Job j 7 j_{7} j 7 starts in the first block, so it cannot be this job. During the pauses of j 3 j_{3} j 3 , the only processed job that starts before j 3 j_{3} j 3 is j 1 j_{1} j 1 , which also runs in the first block of j 3 j_{3} j 3 . Similarly, during the pauses of j 6 j_{6} j 6 , the only such job is j 4 j_{4} j 4 , which also runs in the first block of j 6 j_{6} j 6 . Thus, no delay swap exists, and S S S is supercanonical.
Every job other than j 4 j_{4} j 4 has three neighbors, while j 4 j_{4} j 4 has five. Hence, the minimum degree satisfies δ ( G S ) = 3 > 2 = 2 m − 2 \delta(G^{S}) = 3 > 2 = 2m - 2 δ ( G S ) = 3 > 2 = 2 m − 2 . □ \square □