Online Makespan Scheduling Under Scenarios

There are at most $s$ machines per scenario that are not $s$-favorable. Let $s=\lceil \frac{m}{K}\rceil -1$. Since $m>s\cdot K$, there must be a machine $i$ which is not non-$s$-favorable with respect to any scenario. $◀$

In light of this observation, we propose the following algorithm: Upon the assignment of each job $j$, we find a machine $i$ that is $\left(\lceil m/K\rceil -1\right)$-favorable with respect to all scenarios $k$ with $j\in S_k$ and assign the job $j$ to the machine $i$.

Notice that the aforementioned competitive ratio is strictly smaller than $K+1$.

This algorithm is also applicable in the special case where every job appears in at most $k$ scenarios for a fixed $k\in \mathbb{N}$, yielding a ratio of $\left(m-1\right)/\lceil \frac{m}{k}\rceil +1$. Furthermore, plugging in $K=1$ yields the well-known competitive ratio of $2-1/m$ of Graham’s List Scheduling Algorithm.

For all jobs $j$ below, we assume $p_j=1$. The first instance ${ℐ}_1$ is given as follows: $n=m+1$, $S_1=\{1,3,\mathrm{\dots },m+1\}$, $S_2=\{2,3,\mathrm{\dots },m+1\}$.

We consider an arbitrary algorithm that places the first jobs $1$ and $2$ to two distinct machines, without loss of generality, to the first and second, respectively. In this case, the makespan at the end must be $2$, as two jobs $(j,j^{\prime })\ne (1,2)$ must be assigned to the same machine. However, the following assignment, which places the first two jobs together would have yielded a completion time of $1$: $J_1=\{1,2\},J_i=\{i+1\}\text{ for }2\le i\le m.$ Hence, no algorithm that places two unit weight jobs in $S_1\setminus S_2$ resp. $S_2\setminus S_1$ to two separate machines can attain a competitive ratio better than $2$.

In light of this, we consider another instance ${ℐ}_2$, on which assigning the first two jobs to the same machine leads to a failure. It is given by $n=m+2$, $S_1=\{1,3\}$, $S_2=\{2,4,5,6,\mathrm{\dots },m+2\}$, $S_3=\{3,4,5,\mathrm{\dots },m+2\}$. The first two jobs are indeed identical to those of ${ℐ}_1$.

By our considerations about the instance ${ℐ}_1$, we may assume that the first two jobs are assigned to the same machine, the first one without loss of generality. However, any assignment that places the first two jobs to the same machine admits makespan $2$: Otherwise, due to the third scenario, the jobs $\{3,\mathrm{\dots },m+2\}$ must occupy one machine each. The job $j$ that is placed to the first machine has a common scenario with either job $1$ (if $j=3$), or with job $2$ (otherwise). $◀$

On the other hand, this statement cannot be extended to $K=2$. To show this, we present a minimalistic yet insightful algorithm (Algorithm 1) for makespan scheduling under $K=2$ scenarios and $m=2$ machines. Our general idea is to fix a simple rule for assigning double-scenario jobs, i.e., jobs in $S_1\cap S_2$, and partition the single-scenario jobs $j\in S_1\mathrm{△}{S}_2$ so that the machines are reasonably balanced even after upcoming hypothetical double-scenario jobs.

Throughout our analysis, we only use two types of lower bounds for the offline optimum: Processing times $p_j$ of selected jobs $j$ whose completion times equal the makespan, and the average load of a selected scenario $S_k$. Hence, while searching for the worst-case sequence of the upcoming double-scenario jobs, we may replace the actual definition of competitiveness with that of a proxy one:

The proxy competitive ratio is an upper bound on the competitive ratio. The lower bounds that we use are already well-known; e.g., Graham’s List Scheduling Algorithm is analyzed by bounding the proxy competitive ratio from above. We take this approach, however, one step further and restrict ourselves to analyzing only some instances that attain the largest possible proxy competitive ratio (see next Observation). This is significantly more difficult for the competitive ratio in the usual sense, as a witness to having good or bad offline optima highly depends on how the processing times of jobs fit together numerically.

The above observation motivates the following parameter of significant value.

In Figure 1, we have $p(J_2\cap S_2\cap [n-2])>p(J_2\cap S_1\cap [n-2])$ and the second term of the denominator corresponds to the load $p(J_2\cap S_1\cap [n-1])$, i.e., the load of $J_2\cap S_1$ after the $(n-1)$-st job is assigned. In general, anticipation measures the minimum discrepancy of a machine with respect to different scenarios after machine $2$ is loaded with double-scenario jobs just enough to attain the makespan of the schedule together with machine $1$. In our algorithm, one of the goals is to keep $\alpha \le 2$ in order to brace ourselves for upcoming double-scenario jobs. The invariant which we maintain to this end is the following.

The last property might appear somewhat unnatural at the first glance, though it is crucial for bounding the anticipation $\alpha \le 2$ in the subsequent iterations.

Algorithm 1 shows how a single job $j$ is assigned given a schedule of the first $j-1$ jobs where Invariant 11 is maintained. To analyze the algorithm, we prove that instances satisfying the properties in Observation 9 are always assigned so that the first $n-1$ jobs maintain Invariant 11 and the last job results in a proxy competitive ratio of at most $5/3$.

A significant portion of the analysis is focused on proving that if line 9 is executed, Invariant 11 is indeed maintained. We refer the reader to the full version of the paper for further details.

In spite of the restrictions that arise from both the fixed double-scenario rule and how we evaluate lower bounds, we find out that our algorithm in the previous subsection is not far from being best possible.

To ease the notation once again, let $X≔3+\sqrt{17}$.

The first four jobs are given by $1,2\in S_1\setminus S_2$, $3,4\in S_2\setminus S_1$, $p_1=p_2=p_3=p_4$. Any algorithm with competitive ratio better than $2$ must assign these jobs so that the makespan equals $1$ at the end; otherwise, we may stop revealing further jobs so that the offline optimum equals $1$, while the makespan equals $2$.

The fifth job fulfills $5\in S_1\setminus S_2$ and $p_5=X$. Without loss of generality, it is assigned to the first machine.

The sixth job is given by $6\in S_2\setminus S_1$, $p_6=\frac{X}{2}$. Now there are two options:

1. (i)

   If the sixth job is also assigned to the first machine, we reveal the seventh job with $7\in S_2\setminus S_1$ and $p_7=X$. This job cannot be assigned to the first machine, as the makespan would then be $1+\frac{3X}{2}$, while the offline optimum is $X$. Indeed, this would imply a ratio of at least

   $$\frac{1+\frac{9+3\sqrt{17}}{2}}{3+\sqrt{17}}=\frac{9+\sqrt{17}}{8}.$$

   In particular, we obtain $p(S_1\cap J_1\cap [7])=p(S_2\cap J_2\cap [7])=1+X$.

2. (ii)

   If the sixth job is assigned to the second machine, we reveal the seventh job as $7\in S_1\cap S_2$ and $p_7=\frac{X}{2}$. Due to similar reasoning to the other case, the seventh job must be assigned to the second machine and we again have $p(S_1\cap J_1\cap [7])=p(S_2\cap J_2\cap [7])=1+X$.

See Figure 2 for the first seven jobs in each of the cases.

In both of these cases, we reveal the eighth job with $8\in S_1\cap S_2$ and $p_8=2+\frac{3X}{2}$. No matter where this job is assigned, the makespan is $3+\frac{5X}{2}$, whereas the optimal solution $\{1,\mathrm{\dots },7\}\dot{\cup }\{8\}$ achieves a makespan of $2+\frac{3X}{2}$. Therefore, the competitive ratio is bound to be at least

as desired. $◀$

Notice that the aforementioned family of instances fails to achieve small competitive ratios for reasons similar to those that require Property (iii) in Invariant 11.

It can also be shown through a simple array of instances that, no algorithm that satisfies Rule 7 can beat the bound of $5/3$, for which we refer the reader to the full version of the paper.

Initially, we study a subhypergraph $𝒮$ that we use as a building block throughout our construction. The hypergraph $𝒮$ is given by the nodes $V(𝒮)=\{1,\mathrm{\dots },7\}$ and hyperedges

The hyperedges have size at most $3$ and the set $E(𝒮)$ is closed under taking subsets of size at least $2$, i.e., if $e\in E(𝒮)$, $|e|=3$ and $e^{\prime }\subseteq e$ with $|e^{\prime }|=2$, then $e^{\prime }\in E(𝒮)$. The hypergraph $𝒮$ together with the maximal hyperedges $e_1,\mathrm{\dots },e_5$ is given in Figure 3.

We first assume that the seven nodes in $V(𝒮)$ are assigned to exactly two out of the three online colors. Since the online colors are initially symmetric, let us assume that we use the online colors $1$ and $2$. By a careful case distinction, we may observe:

In other words, we have induced monochromatic hyperedges of size $2$ with two different colors, both with respect to the online coloring. Applying this repeatedly, we can further force the algorithm to a monochromatic hyperedge of size $3$, which we show next.

In our construction, we would like to create copies of the graph $𝒮$ successively, which we denote by $𝒮(t)$ for incrementing $t\in \mathbb{N}$.

A straightforward application of the pigeonhole principle yields that, if we have seven subhypergraphs $𝒮(1),\mathrm{\dots },𝒮(7)$ that are each partitioned onto two online colors, at least three of them (without loss of generality $𝒮(1)$, $𝒮(2)$, $𝒮(3)$) must be partitioned onto the same two online colors. Again without loss of generality, these two online colors are $1$ and $2$. Considering Proposition 14, we can permute the colorings of the three copies $𝒮(1)$, $𝒮(2)$ and $𝒮(3)$ each offline so that for any offline color $u\in \{\mathrm{blue},\mathrm{red},\mathrm{yellow}\}$, there exists a copy $𝒮(t)$ with two (online) monochromatic hyperedges $e_i^t\in E(𝒮(t))$ $(i\in \{1,2\})$ of size $2$ avoiding the color $u$. The hypergraph in Figure 4 restricted to nodes of the form $j_s^i$ illustrate these edges.

Once the six edges in question are found, one can insert nodes $x_1$, $x_2$, $x_3$ in this order, revealing hyperedges as depicted in Figure 4. To avoid a monochromatic edge, both $x_1$ and $x_2$ must be assigned the third online color. Keeping this in mind, it follows that $x_3$ cannot be assigned an online color without creating a monochromatic edge with respect to the online coloring. Together with the fact that the offline coloring indeed has makespan $1$, we obtain:

It remains to consider the case where copies of the subhypergraph $𝒮$ are partitioned among the three colors, i.e., its nodes $\{1,\mathrm{\dots },7\}$ are partitioned in nonempty sets $J_1\dot{\cup }{J}_2\dot{\cup }{J}_3$.

In our construction, we exploit this property as follows: Let us consider a copy $𝒮(t)$ and fix two of its nodes $v_i(t)\in J_i$, $v_{i^{\prime }}(t)\in J_{i^{\prime }}$ provided by Lemma 16 as well as a third node $v_{i^{\prime \prime }}(t)\in J_{i^{\prime \prime }}$, where $i^{\prime \prime }\notin \{i,i^{\prime }\}$. By their choice, the nodes $v_i(t)$ ($i\in \{1,2,3\}$) admit at most two offline colors and avoid a third offline color $C\in \{\mathrm{blue},\mathrm{red},\mathrm{yellow}\}$.

In this case, the subhypergraph $𝒮(t)$ is called a $C$ palette (i.e., yellow palette, blue palette or red palette) and the corresponding nodes $v_i(t)$ are called palette nodes. In particular, $c(v_i(t))\ne C$ holds for the palette nodes of a $C$ palette. The choice of the name is motivated by the fact that, if we connect a new node $w$ to e.g. yellow palette nodes, we are still allowed to extend the offline coloring by $c(w)=\mathrm{yellow}$, while maintaining that the makespan of the offline coloring is $1$.

Below is a summary of our construction for the case where Lemma 15 is not applicable. Essentially, we create copies of the subhypergraph $𝒮$ which we connect with the existing hypergraph. The online color of the node $v$ is denoted by $\phi (v)$ and its (current) offline color by $c(v)$.

1. (i)

   We create up to $13$ copies of the subhypergraph $𝒮$. By Lemma 15, we may assume that at least $7$ of the copies are assigned to all three online colors (we truncate this step as soon as $7$ such copies can be found). We handpick $7$ such copies of $𝒮$, calling them $𝒮(1),\mathrm{\dots },𝒮(7)$.

2. (ii)

   We permute the offline coloring on each copy of $𝒮$ so that $𝒮(1)$, $𝒮(4)$ and $𝒮(7)$ are yellow palettes, $𝒮(2)$ and $𝒮(5)$ are blue palettes, and $𝒮(3)$ and $𝒮(6)$ are red palettes.

3. (iii)

   We reveal a node $w_{𝒜}$ which is connected to palette nodes $v_i(1)\in V(𝒮(1))\cap J_i$ for $i\in \{1,2,3\}$. The assignment to the online color $\phi (w_{𝒜})$ leads to a monochromatic hyperedge $\{v_{\phi (w_{𝒜})}(1),w_{𝒜}\}$ of online color $\phi (w_{𝒜})$. We define $v_{𝒜}≔v_{\phi (w_{𝒜})}(1)$.

4. (iv)

   We reveal three nodes $w_{ℬ1}$, $w_{ℬ2}$ and $w_{ℬ3}$ that are connected by the hyperedge $\{w_{ℬ1},w_{ℬ2},w_{ℬ3}\}$ to each other. Moreover, for each $s\in \{1,2,3\}$, the node $w_{ℬs}$ is connected to the palette nodes $v_i(s+1)$ for $i\in \{1,2,3\}$. There is an $i\ne \phi (w_{𝒜})$ such that $\{v_i(s+1),w_{ℬs}\}$ is a monochromatic edge of online color $i$ for a suitable copy $𝒮(s)$, $s\in \{1,2,3\}$. For this $s$, we define $v_{ℬ}≔v_i(s+1)$ and $w_{ℬ}≔w_{ℬs}$.

5. (v)

   We reveal further copies of $𝒮$ together with edges described below, until a copy $𝒞$ is assigned to all three online colors. In the copy $𝒞$, we denote the nodes $v_i(t)$ by $w_{𝒞t}$ for clarity. The nodes $w_{𝒞t}$ of the copy $𝒞$ are connected to the palettes $𝒮(5)$, $𝒮(6)$, $𝒮(7)$ by edges depending on their offline colors, in that nodes $w_{𝒞t}$ with $c(w_{𝒞t})=C$ are connected to the palette nodes $v_i(s)$ for all $i\in \{1,2,3\}$ and $s\in \{5,6,7\}$ such that $𝒮(s)$ is a $C$ palette, see Figure 6. As the nodes $w_{𝒞t}$ are assigned to all three online colors, a makespan of $2$ is also achieved in the online color $i\notin \{\phi (w_{𝒜}),\phi (w_{ℬ})\}$. More precisely, there exists a monochromatic edge $\{v_i(s),w_{𝒞t}\}$ of the online color $i$. We rename $v_{𝒞}≔v_i(s)$ and $w_{𝒞}≔w_{𝒞t}$.

6. (vi)

   We permute the offline coloring in each of the connected components created in (iii), (iv) and (v) again, so that $c(v_j)=\mathrm{blue}$ and $c(w_j)=\mathrm{yellow}$ for $j\in \{𝒜,ℬ,𝒞\}$.

7. (vii)

   We add a final node $v_n$ together with hyperedges $\{v_n,v_j,w_j\}$ for each $j\in \{𝒜,ℬ,𝒞\}$. Now, the online color $\phi (v_n)$ that this node is assigned to admits a makespan of $3$, while extending the offline coloring by $c(v_n)=\mathrm{red}$ maintains an offline coloring with makespan $1$.

Notice that we have maintained an offline coloring of the nodes with makespan $1$ so far up to the very last node, and the last node $n$ neighbors only blue and yellow nodes by construction and therefore the offline assignment $c(n)=\mathrm{red}$ does not increase the makespan. In total, this yields that the offline optimal value is $1$. A careful enumeration of introduced hyperedges reveals that $233$ hyperedges suffice to create a monochromatic hyperedge for any of the cases demonstrated, which proves Theorem 13.

Here, we abstain from presenting a proof of Theorem 2. Our construction in this general case is also based on incrementally creating monochromatic edges of each online color. However, we are faced with two fundamental challenges:

1. (i)

   The monochromatic hyperedges increase in size rather slowly, yet unless they have size of $m-1$, they are not strong enough to act as a palette for other hyperedges in the same sense as here.

2. (ii)

   To use our construction for Corollary 3, we restrict to hypertrees. This is a significant constraint, as it roughly implies that every palette may be used at most once.

Therefore, we include a more intricate recursive construction with much larger hypergraphs in the full version of the paper.