The Fair Periodic Assignment Problem

$(iv)\Rightarrow (iii)$: Since all workers are either busy performing tasks or transitioning, the total number of workers at any time $t$ is $ℐ(t)+{ℳ}^{\ast }(t)$. By assumption, there exists a $t^{\prime }\in [0,T)$ such that ${ℳ}^{\ast }(t^{\prime })=0$, implying $ℐ(t^{\prime })+{ℳ}^{\ast }(t^{\prime })\le L$. Conversely, since $ℐ(t)$ attains its maximum at some $t^{\prime \prime }$, we have $ℐ(t^{\prime \prime })=L$, so $ℐ(t^{\prime \prime })+{ℳ}^{\ast }(t^{\prime \prime })\ge L$. Because the total number of workers is constant over time, we must have that $ℐ(t)+{ℳ}^{\ast }(t)=L\text{ for all }t\in [0,T).$

$(iii)\Rightarrow (ii)$: Integrating over the interval $[0,T)$ yields:

$(ii)\Rightarrow (i)$: If $c(ℐ)+c({ℳ}^{\ast })=LT$, then the schedule uses exactly $L$ workers over time, matching the theoretical lower bound. Hence, ${ℳ}^{\ast }$ must be optimal.

$(i)\Rightarrow (iv)$: Suppose, for contradiction, that ${ℳ}^{\ast }(t)\ge 1$ for all $t\in [0,T)$. Then, there exists a subset of transition arcs whose intervals fully cover $[0,T)$. Without loss of generality, let these intervals be ${𝒩}^{\ast }=\{[b_1,a_1],\mathrm{\dots },[b_m,a_m]\}$, where

We can now construct a shorter matching ${𝒩}^{\prime }=\{[b_1,a_m],[b_2,a_1],\mathrm{\dots },[b_m,a_{m-1}]\}$, which reduces the total transition time. This contradicts the optimality of ${ℳ}^{\ast }$. Therefore, ${ℳ}^{\ast }(t)=0$ must hold for some $t\in [0,T)$. $◀$

We begin by analyzing the time complexity. Recall that computing $L$ and the maximizer $t^{\ast }$ takes $𝒪(n\log n)$. Sorting $2n$ time points also takes $𝒪(n\log n)$, and the main loop of the algorithm executes $𝒪(n)$ operations, each taking $𝒪(1)$ time. Hence, the total runtime is $𝒪(n\log n)$.

To prove correctness, we show that the algorithm constructs a feasible assignment satisfying condition $(iv)$ from Theorem 3, which implies optimality.

We first show that the stack size when processing an event at time $t$ equals $L-ℐ(t)$. Initially, the stack is empty and $ℐ(t)=L$. Each step of the algorithm maintains this invariant through the following cases:

• $\mathrm{■}$

  Case 1 (Line 8): If $R[i]$ is a start, then $ℐ(t)$ increases by 1, and the stack size decreases by 1.

• $\mathrm{■}$

  Case 2 (Line 12): Otherwise, $R[i]$ is an end; $ℐ(t)$ decreases by 1, and the stack size increases by 1.

This invariant yields the following consequences:

1. 1.

   The stack size remains nonnegative at all times.

2. 2.

   When processing a start, the stack must be nonempty, ensuring a valid match.

3. 3.

   At termination, $ℐ(t)=L$ again, so the stack is empty.

Together, these observations confirm that all starts are matched to ends – by popping from the stack in Line 9 – ensuring feasibility of the assignment.

For optimality, note that all arcs match from a lower index to a higher index. In particular, no transition arcs “loop” around time $t=0$. Hence ${ℳ}^{\ast }(0)=0$, which implies the solution is optimal by property $(iv)$ of Theorem 3. $◀$

We first analyze the runtime. A crucial observation is that the distance of the current task to the next depends solely on the end time of the current task and start time of the next task. If unvisited tasks are stored in increasing order of start time, one can efficiently find the closest unvisited task. To this end, we store the unvisited tasks $𝒰$ in a self-balancing binary search tree, allowing us to maintain a fixed task order even as tasks are visited and removed throughout the course of the algorithm. Constructing this tree takes $𝒪(n\log n)$. Finding the next task $v$ and removing it from $𝒰$ both take $𝒪(\log n)$. Since $𝒪(n)$ operations are required until all tasks are visited, the total time complexity is $𝒪(n\log n)$.

Nearest Neighbor always returns a fair periodic assignment. It remains to show that this assignment requires at most $L+1$ workers. Suppose, to the contrary, that the assignment requires more than $L+1$ workers. Let $t=0$ correspond to the start of the first task that is visited. If the assignment requires more than $L+1$ workers, there is some task $i=(a,b)$ that is started after $L$ periods, i.e., after $L$ complete revolutions around the circle. This means that in the first $L$ periods, a task is performed at time $a$. Together with task $i$, this implies the existence of some small $\epsilon >0$ such that $ℐ(a+\epsilon )=L+1$, a contradiction. $◀$

The performance guarantee of Nearest Neighbor allows us to upper-bound the number of additional workers required to operate a fair assignment, i.e., the price of fairness.

An efficient assignment always requires exactly $L$ workers. Nearest Neighbor returns a fair solution with at most $L+1$ workers. This upper bound is tight, see, e.g., Figure 2. It follows that the price of fairness equals $\frac{(L+1)-L}{L}=\frac{1}{L}$. $◀$

Denote the optimal assignment by ${ℳ}^{\ast }$ and suppose, to the contrary, that transition arc $(i,j)\in {ℳ}^{\ast }$ is not contained in any idle interval. Choose any $t$ in the $T$-periodic interval $[b_i,a_j]$. Since $(i,j)$ is not contained in any idle interval, it follows from Definition 7 that $ℐ(t)=L$. As arc $(i,j)$ is also active at time $t$, it holds that $ℐ(t)+{ℳ}^{\ast }(t)\ge L+1$. By statement $(iii)$ of Theorem 3, this contradicts optimality of ${ℳ}^{\ast }$. $◀$

Our goal is to study how the connectivity of idle intervals determines the number of disjoint cycles in a periodic assignment. To this end, we introduce the idle interval graph, representing how the various tasks connect different idle intervals.

To see that this is well-defined, note that for all $i\in ℐ$. In other words, for each task there are unique idle intervals at its start and end time, respectively. By construction, the number of arcs $|ℬ|$ is always equal to exactly $n$. Moreover, any feasible periodic assignment covers all tasks once, and thereby implicitly includes all arcs of $\mathscr{H}$.

Figures 5(c) and 5(d) illustrate the idle interval graphs of instances A and B, respectively. The number of idle intervals, and hence the number of nodes in the graph, differs across the two instances. Moreover, we find that the idle interval graph of instance B is connected, while that of instance A is not.

It turns out that efficient solutions on instances with a connected idle interval graph always satisfy the following condition: if they are not fair, they contain overlapping transition arcs belonging to disjoint cycles.

We first show that at least two disjoint cycles must contain transition arcs traversing the same idle interval. To the contrary, suppose that no two cycles share arcs in an idle interval. Take any cycle ${𝒞}_1\in {ℳ}^{\ast }$, and denote by ${𝒮}_1\subseteq 𝒮$ all the idle intervals traversed along this cycle. By assumption, all the cycles in ${ℳ}^{\prime }={ℳ}^{\ast }\setminus {𝒞}_1$ only traverse idle intervals in ${𝒮}^{\prime }=𝒮\setminus {𝒮}_1$. Clearly, ${𝒮}^{\prime }$ is nonempty. Let ${ℬ}^{\prime }\subseteq ℬ$ be the arcs connecting ${𝒮}^{\prime }$ and ${𝒮}_1$. By connectivity of $\mathscr{H}$, this set is nonempty. Consider any arc $(k,l)\in {ℬ}^{\prime }$. Recall that this arc is induced by some task $i\in ℐ$. Without loss of generality, assume that $k\in {𝒮}_1$ and $l\in {𝒮}^{\prime }$. If task $i$ is covered by ${𝒞}_1$, this cycle would contain a transition arc in $l$, a contradiction. Similarly, if task $i$ is covered by some cycle in ${ℳ}^{\prime }$, it would contain a transition arc in $k$, another contradiction. Since the task must be covered on exactly one cycle, we conclude that there must exist two disjoint cycles containing transition arcs in the same idle interval.

Now assume that two disjoint cycles contain transition arcs in the same idle interval $[s,e]\in 𝒮$. We show that their transition arcs must overlap at some time in $[s,e]$.

Let ${𝒞}_1$ be the cycle whose earliest transition arc starts at time $s$. By definition of the idle interval and optimality of ${ℳ}^{\ast }$, such a cycle exists. We distinguish two cases. First, suppose that the transition arcs in ${𝒞}_1$ are continuously active from time $s$ until time $e$. Let ${𝒞}_2$ be any other disjoint cycle active in the same idle interval. Clearly, any transition arc from ${𝒞}_2$ will overlap with some arc of ${𝒞}_1$. Alternatively, suppose that the transition arcs in ${𝒞}_1$ are active from time $s$ until some time , and potentially later in the idle interval too. Let ${𝒞}_2$ be the disjoint cycle passing through the same idle interval whose earliest transition arc has the second-earliest start time. Denote this start time by $t_2$. If $t_2\le t_1$, the corresponding transition arc must intersect with some arc in ${𝒞}_1$. If $t_2>t_1$, no transition arcs are active in the interval $(t_1,t_2)$. This contradicts the definition of the idle interval and optimality of ${ℳ}^{\ast }$, stating that ${ℳ}^{\ast }(t)\ge 1$ for all $t\in [s,e]$. Hence, at least two transition arcs from disjoint cycles must overlap. $◀$

As outlined before, these overlapping arcs provide opportunities for patching. Indeed, we show that patching can always be used to obtain a fair and efficient solution on instances satisfying the conditions of Lemma 10.

First, let ${ℳ}^{\ast }$ be any fair solution with $L$ workers. This single cycle visits all nodes (idle intervals) and arcs (tasks) of the idle interval graph. Clearly, the idle interval graph must be connected.

Now suppose that the idle interval graph is connected, and let ${ℳ}^{\ast }$ be any solution with $L$ workers. If it consists of a single cycle, we are done. Assume that it consists of at least two disjoint cycles. By Lemma 10, there exists a pair of overlapping transition arcs $(i_1,j_1),(i_2,j_2)$ belonging to disjoint cycles. We can reduce the number of disjoint cycles by one through a patching operation. In particular, we replace the original, overlapping transition arcs by $(i_1,j_2)$ and $(i_2,j_1)$. The total transition time of the assignment, and hence the number of required workers, is unaffected by this operation. The number of disjoint cycles, however, decreases by one. As the original number of disjoint cycles is at most $n$, repeating this procedure at most $n-1$ times is guaranteed to return a fair solution with $L$ workers. $◀$

To illustrate the patching idea, we return to the idle interval graphs of instances A and B in Figures 5(c) and 5(d), respectively. In line with Theorem 11, we find that the graph of instance A, for which no fair solution with $L=2$ workers exists, is not connected. In contrast, the graph of instance B is connected, showing that this instance admits a fair solution with two workers. It does not imply, however, that every efficient solution to this instance is fair. For example, the solution consisting of two disjoint cycles $(I_1\to I_2\to I_1)$ and $(I_3\to I_4\to I_3)$ is efficient but not fair. However, these two disjoint cycles can be patched to form a single fair solution with two workers. For example, transition arcs $(I_1,I_2)$ and $(I_4,I_3)$ overlap at time $t=\frac{T}{4}$. Patching these two arcs yields the fair and efficient solution $(I_1\to I_3\to I_4\to I_2\to I_1)$.

We conclude our theoretical analysis by pointing out that Theorem 11 provides an elegant, alternative way of arriving at the price of fairness in Corollary 6. In particular, we can view the price of fairness as the minimum increase in the load required to make the idle interval graph connected. Consider an instance for which the idle interval graph is unconnected. It can easily be made connected by adding a series of artificial tasks that span the period exactly once and start and end at the start and end times of consecutive intervals, respectively. The resulting instance has load $L+1$, and always admits a fair assignment using $L+1$ workers.

We start with a complexity analysis. Computing an efficient assignment with Shift-Sort-and-Match takes $𝒪(n\log n)$. One can compute all cycles in $𝒪(n)$ by iterating once over all transition arcs. Constructing the cycle index arrays $U$ and $V$ also takes linear time. Sorting the transition arcs $R$ by increasing start time requires $𝒪(n\log n)$. All $𝒪(n)$ operations in the for-loop take $𝒪(1)$: patching itself takes constant time, and the arrays $U$ and $V$ allow us to update the cycle index of each task in constant time as well. Finally, calling Nearest Neighbor takes $𝒪(n\log n)$. The overall time complexity becomes $𝒪(n\log n)$.

It is clear that Patching returns a fair periodic assignment. To prove optimality, we distinguish between two cases. If the instance admits a fair solution with $L$ workers, by the proof of Theorem 11 it suffices to show that Patching successfully patches all overlapping transition arcs belonging to different cycles. If the instance does not admit such a solution, Nearest Neighbor returns an optimal fair solution requiring $L+1$ workers.

We now show that the algorithm correctly eliminates all overlapping transition arcs belonging to different cycles. In particular, we show that patching arc $(i,j)$ always overlaps with, and hence can be patched with, the next processed transition arc $(k,l)$, whenever $(k,l)$ belongs to the same idle interval as $(i,j)$.

Without loss of generality, assume that the initial patching arc $R[1]$ marks the start of an idle interval. Assume that the current patching arc is $(i,j)$, and we are processing arc $(k,l)$. In case the IF-statement on Line 9 evaluates to true, it must hold that $(k,l)$ belongs to a different idle interval than $(i,j)$. To the contrary, suppose that they belong to the same idle interval but $b_k>a_j$. Since we always update the patching arc to the processed transition arc with the latest end time, this would imply that no transition arcs are active in the interval $(a_j,b_k)$, contradicting the definition of idle interval and efficiency of $ℳ$. Since the arcs belong to different idle intervals, we do not perform patching but simply update the patching arc.

Now, assume that the two arcs belong to the same idle interval but to disjoint cycles, i.e., Line 11 evaluates to true. We can patch the two arcs whenever they overlap, i.e., whenever the interval $[b_i,a_j]\cap [b_k,a_l]=[\max \{b_i,b_k\},\min \{a_j,a_l\}]$ is nonempty. Since we process transition arcs in increasing order of their start time, it holds that $b_i\le b_k$. From Line 9, it follows that $a_j\ge b_k$. Hence, the two arcs overlap, and we perform a patching operation. Moreover, we update the patching arc to the processed transition arc with the latest end time.

Finally, in case the two arcs belong to the same idle interval but the same cycle, we do not perform a patching operation. Instead, on Line 21 we update the patching arc to preserve the required property that it has the maximum end time among all processed transition arcs. $◀$

Interestingly, we are not aware of a more efficient algorithm for testing the existence of a fair and efficient periodic assignment than Patching, which directly computes the optimal fair assignment. The obvious alternative way of testing the conditions of Theorem 11 is to construct the idle interval graph and perform a depth-first search to determine its connectivity. While the latter step takes linear time as $𝒪(|𝒮|+|ℬ|)=𝒪(n)$, computing the idle intervals themselves requires a sorting of the tasks, bringing the time complexity to $𝒪(n\log n)$, i.e., the same as Patching.