Scheduling on Identical Machines with Setup Time and Unknown Execution Time

One of the simplest examples of the setup time family is the constant setup time, where the setup time is a certain constant independent of the batch. Formally, the setup time is represented as $c(X)=1$ for $X\in 2^J\setminus \{\mathrm{\varnothing }\}$ and $c(\mathrm{\varnothing })=0$. It is not difficult to see that any partition of the jobs $(X_1,\mathrm{\dots },X_m)$ is optimal for the problem (1).

In production systems with attachments, jobs are partitioned based on their types. Let $T$ be the set of types and ${(J_t)}_{t\in T}$ is the partition of jobs with types $T$, i.e., ${\bigcup }_{t\in T}{J}_t=J$ and $J_t\cap J_{t^{\prime }}=\mathrm{\varnothing }$ for all distinct $t,t^{\prime }\in T$. Let $w_t$ be the setup time for type $t$. Then, the setup time for $X\subseteq J$ is defined as $c(X)={\sum }_{t\in T:X\cap J_t\ne \mathrm{\varnothing }}{w}_t$. Additionally, we say that a type-specific setup time $c$ is unweighted if $w_t=1$ for all $t\in T$, i.e., $c(X)=|\{t\in T:X\cap J_t\ne \mathrm{\varnothing }\}|$ for $X\subseteq J$. We can obtain a PTAS for the problem (1) with type-specific setup times by treating each $J_t$ as a single job and applying a PTAS for the load balancing problem [19]. Moreover, for the unweighted case, the problem (1) is solvable in polynomial time because an optimal solution can be obtained by simply balancing the number of types assigned to each machine.

In cloud computing environments, where each job requires the installation of multiple libraries, and each library takes a fixed amount of time to install. The setup time needed to process a batch of jobs is the total installation time of the required libraries. Let $L$ be the set of libraries, and let $L_j\subseteq L$ be the set of required libraries for job $j\in J$. Let $w_{\mathrm{\ell }}$ be the installation time for library $\mathrm{\ell }\in L$. Then, the setup time for $X\subseteq J$ is defined as $c(X)={\sum }_{\mathrm{\ell }\in {\bigcup }_{j\in X}{L}_j}{w}_{\mathrm{\ell }}$. Note that if every job $j\in J$ requires a unique library (i.e., $|L_j|=1$), this is a type-specific setup time. This setup time is a monotone submodular function; more specifically, it is a weighted coverage function. Hence, we can apply the $\mathrm{O}(\sqrt{n\text{/}\log n})$-approximation algorithm for the uniform submodular load balancing problem [33] to solve the problem (1).

For applications like repair companies, the setup time is defined by the optimal value of a traveling salesman problem (TSP) instance. Let $(V,d)$ be a metric space with an origin $o\in V$. The origin corresponds to the location of the company. Each job $j\in J$ is associated with a point $v_j\in V$. Then, the setup time for $X\subseteq J$ is defined as the optimal value of the TSP on $V^{\prime }=\{v_j:j\in X\}\cup \{o\}$. Note that this class of setup times is a generalization of type-specific setup times. Indeed, for a star metric $(T\cup \{o\},d)$ where $d(t,o)=w_t/2$ for all $t\in T$ and $d(t,t^{\prime })=(w_t+w_{t^{\prime }})/2$ for all distinct $t,t^{\prime }\in T$, the setup time is $c(X)={\sum }_{t\in T:X\cap J_t\ne \mathrm{\varnothing }}{w}_t$ for $X\subseteq J$ when $v_j=t$ for each job $j\in J_t$. For TSP-based setup times, the problem (1) can be viewed as the $m$-TSP. It is known that the $m$-TSP admits a $2.5$-approximation algorithm [12, 8].

Fix an instance, and let $\mathrm{OPT}$ be the optimal makespan. For a subset of jobs $J^{\prime }$, we denote $\mathrm{ALG}(J^{\prime })$ as the makespan of the algorithm, assuming that jobs in $J^{\prime }$ are given at time $0$. Note that $\mathrm{ALG}(J^{\prime })\le \rho \cdot \mathrm{OPT}$ by the monotonicity of the optimal makespan with respect to the jobs.

If the instance contains no job, then $\mathrm{IGNORE}$ is clearly optimal. Thus, we assume that the instance contains at least one job. Let $t^{\ast }$ be the last release time of the jobs. Then, $\mathrm{OPT}\ge t^{\ast }$ as the last released job can only be processed from $t^{\ast }$.

Suppose that the machines are idle at time $t^{\ast }$. Let $R$ be the set of jobs processed in the last subschedule by the IGNORE strategy. Then, the makespan of IGNORE is

On the other hand, suppose that some machines are not idle at time $t^{\ast }$. Then $t^{\ast }$ is in the second last subschedule of the algorithm, and the last subschedule starts right after the second-to-last subschedule ends. Let $R$ and $S$ be the sets of jobs processed in the last and the second-to-last subschedules, respectively. Then, the makespan of IGNORE is

Therefore, the competitive ratio of IGNORE is at most $2\rho +1$. $◀$

It should be noted that this reduction remains valid even when the competitive ratio $\rho$ of $\mathrm{ALG}$ depends on the number of machines $m$ or the number of jobs $n$, provided it is monotonically nondecreasing with respect to $n$. From this theorem, the optimum competitive ratio is the same up to a constant factor regardless of the release time.

As the makespan of the algorithm is $c(J)+p(J)$ and the optimal makespan is at least $(C(J)+p(J))/m$ by Lemma 1, the competitive ratio is at most

where the second inequality is implied by the subadditivity of the setup time $c$. $◀$

Second, we analyze the competitive ratio of the list scheduling algorithm.

The makespan of the algorithm is at most

where the inequality holds by Lemma 1. Thus, the competitive ratio is at most $\mathrm{O}(n/m)$. $◀$

Next, we provide an $\mathrm{O}\left(\sqrt{n\text{/}m}\right)$-competitive algorithm, which is an improved version of the list scheduling algorithm. The idea is to reduce the total setup time by grouping jobs. The algorithm first divides the jobs into $m+\lceil \sqrt{mn}\rceil$ batches in such a way that this partition minimizes the maximum setup time, under the condition that each batch contains at most $\lceil \sqrt{n\text{/}m}\rceil$ jobs. Then, it processes the batches according to the list scheduling algorithm, which greedily allocates an unprocessed batch to any available machine. The formal description of this algorithm is summarized in Algorithm 1.

Let $(X_1^{\ast },\mathrm{\dots },X_m^{\ast })$ be the optimal schedule and let $\mathrm{OPT}$ denote the optimal makespan ${\max }_{i\in [m]}(c(X_i^{\ast })+p(X_i^{\ast }))$. Define $k=m+\lceil \sqrt{mn}\rceil$, and let $(X_1,\mathrm{\dots },X_k)$ be a $k$-partition of the jobs $J$ that minimizes ${\max }_{i\in [k]}c(X_i)$ subject to $|X_i|\le \lceil \sqrt{n\text{/}m}\rceil$ for all $i\in [k]$.

We first observe that ${\max }_{i\in [k]}c(X_i)\le \mathrm{OPT}$. This is because by dividing each $X_i^{\ast }$ with $i\in [m]$ into $\lceil |X_i^{\ast }|/\sqrt{n\text{/}m}\rceil$ sub-batches of almost equal size, we can obtain a partition $(Y_1,\mathrm{\dots },Y_k)$ that refines $(X_1^{\ast },\mathrm{\dots },X_m^{\ast })$. Here, we have $|Y_{i^{\prime }}|\le {\max }_{i\in [m]}\lceil |X_i^{\ast }|/\lceil |X_i^{\ast }|/\sqrt{n\text{/}m}\rceil \rceil \le \lceil \sqrt{n\text{/}m}\rceil$ for all $i^{\prime }\in [k]$. Thus, it holds that ${\max }_{i\in [k]}c(X_i)\le {\max }_{i\in [k]}c(Y_i)\le {\max }_{i\in [m]}c(X_i^{\ast })\le \mathrm{OPT}$.

Then, the makespan of the algorithm is at most

where the first inequality follows from the subadditivity of the setup time and the second inequality from Lemma 1. Hence, Algorithm 1 is $\mathrm{O}\left(\sqrt{n\text{/}m}\right)$-competitive. $◀$

By combining Theorems 3 and 5, we obtain the following corollary.

If $m\le n^{1/3}$, then the algorithm that processes the batch $J$ by a single machine is $m=\mathrm{O}(n^{1/3})$-competitive by Theorem 3. On the other hand, if $m>n^{1/3}$, the competitive ratio of Algorithm 1 is $\mathrm{O}\left(\sqrt{n\text{/}m}\right)=\mathrm{O}(n^{1/3})$ by Theorem 5. Thus, an $\mathrm{O}(n^{1/3})$-competitive algorithm exists for either case. $◀$

In the rest of this subsection, we provide an $\mathrm{O}(\log n/\log \log n)$-competitive algorithm for the preemptive sUETS problem. For a given instance of the sUETS problem, let $q$ be an integer such that $q^q\ge n>{(q-1)}^{q-1}$. Note that $q=\mathrm{\Theta }(\log n/\log \log n)$. The execution of our algorithm consists of $q+1$ phases. Without loss of generality, we may assume that $m\ge 2q$, since otherwise the competitive ratio of the algorithm in Theorem 3 is $m=\mathrm{O}(q)=\mathrm{O}(\log n/\log \log n)$.

The intuition of our algorithm is as follows. Our algorithm repeatedly completes a $(1-1/q)$-fraction of the jobs in each phase. Consequently, all the jobs can be processed in $\mathrm{O}(q)$ iterations. This increases the cost of the setup time by a factor of $\mathrm{O}(q)$. Additionally, we ensure that at least $m/q$ machines work at any point of the algorithm. This guarantees that the cost in terms of execution time will only increase by a factor of at most $q$. By these properties, the competitive ratio of the algorithm is $\mathrm{O}(q)=\mathrm{O}(\log n/\log \log n)$.

Let us explain our algorithm more precisely. Initially, it computes an $m$-partition $(X_1,\mathrm{\dots },X_m)$ of the jobs $J$ that minimizes the maximum setup time ${\max }_{i\in [m]}c(X_i)$. In the first phase, $X_i$ is allocated to machine $i$ for each $i\in [m]$. Then, each machine processes the assigned batch until either the machine completes the batch or the number of uncompleted machines becomes less than or equal to $\lfloor m/q\rfloor$. At that time, the machines still processing will preempt their batches. In the $k$th phase ($k=2,3,\mathrm{\dots },q$), the algorithm computes an $m$-partition $(Y_1^{(k)},\mathrm{\dots },Y_m^{(k)})$ of the remaining jobs such that, for any $i\in [m]$, $|Y_i^{(k)}|\le n/q^{k-1}$ and $Y_i^{(k)}\subseteq X_j$ for some $j\in [m]$. We can always obtain such a partition by dividing each batch left in the previous phase into $q$ sub-batches. Thereafter, each machine processes the assigned batch until either the batch is completed or the number of uncompleted machines becomes less than or equal to $\lfloor m/q\rfloor$. At the end of $q$th phase, the number of remaining jobs is at most $(n/q^{q-1})\cdot \lfloor m/q\rfloor \le m\cdot (n/q^q)\le m$. In the $(q+1)$st phase, the algorithm assigns up to one remaining job to each machine. A formal description of the algorithm is provided in Algorithm 2.

Let $q$ be an integer such that $q^q\ge n>{(q-1)}^{q-1}$. If , then the competitive ratio is $m=\mathrm{O}(q)=\mathrm{O}(\log n/\log \log n)$ by Theorem 3. Thus, we assume $m\ge 2q$.

Let $\mathrm{OPT}$ be the optimal makespan and let $p_{\max }={\max }_{j\in J}{p}_j$. In addition, let ${\tau }_k$ be the time length of phase $k\in [q+1]$. By the definition of the algorithm, the jobs in $R^{(k-1)}\setminus R^{(k)}$ are completed in phase $k\in [q]$. Thus, the total execution time of jobs in phase $k\in [q]$ is at most $p(R^{(k-1)}\setminus R^{(k)})+p_{\max }\cdot \lfloor m/q\rfloor$ because at most $\lfloor m/q\rfloor$ jobs are partially executed. Taking into account the setup time of at most ${\max }_{i\in [m]}c(X_i)$ and the time for preemption of at most ${\max }_{i\in [m]}c(X_i)+p_{\max }$, the length of phase $k\in [q]$ is

where the second inequality is by Lemma 1 and the third is by $m\ge 2q$. In addition, by Lemma 1, the time length ${\tau }_{q+1}$ of phase $q+1$ is

Thus, the makespan of Algorithm 2 is

Hence, the competitive ratio of Algorithm 2 is $\mathrm{O}(q)=\mathrm{O}(\log n/\log \log n)$. $◀$

Let $n=m^3$ and $c(X)=1$ for any non-empty batch $X\subseteq J$ (i.e., constant setup times). We will set the execution time $1$ for at most $m$ jobs (referred to as heavy jobs) and $0$ for the other jobs (referred to as light jobs) depending on the behavior of a given online algorithm. It is not difficult to see that the optimal makespan is at most $2$.

We fix an online algorithm. Let us consider its behavior when every job is light. Suppose that every batch assigned to machines consists of at most $m$ jobs. Then, the algorithm assigns at least $n/m=m^2$ batches to the machines in total. Consequently, some machines must process at least $m$ batches, which requires $m$ setups. Thus, the makespan is at least $m$ in this case, and we have done.

Conversely, suppose that the algorithm allocates a batch consisting of more than $m$ jobs in the instance where every job is light. In another instance where $m$ jobs in the first such batch are set to be heavy, the algorithm’s behavior is the same until the batch is assigned. Thus, the algorithm assigns all the heavy jobs to one machine, and the makespan is at least $m$. Therefore, in both cases, the competitive ratio is at least $\mathrm{\Omega }(m)=\mathrm{\Omega }(n^{1/3})$. $◀$

Next, we provide a lower bound for the preemptive setting.

Let $(X_1^{\ast },\mathrm{\dots },X_m^{\ast })$ be an optimal schedule and let $\mathrm{OPT}$ be the optimal makespan. In addition, let $k=\lfloor \sqrt{m}\rfloor$ and $(X_1,\mathrm{\dots },X_k)$ be a $k$-partition of $J$ that minimizes ${\max }_{i\in [k]}c(X_i)$. We analyze the algorithm that allocates each batch $X_i$ to $\lfloor m/k\rfloor$ machines. The makespan of the algorithm is at most ${\max }_{i\in [k]}\left(c(X_i)+\frac{p(X_i)}{\lfloor m/k\rfloor }+{\max }_{j\in X_i}{p}_j\right)$. By the choice of $(X_1,\mathrm{\dots },X_k)$ and the subadditivity of the setup time $c$, we have

where we denote $X_i^{\ast }=\mathrm{\varnothing }$ for $i>k$. Therefore, by Lemma 1 and (2), the makespan is at most

which means that the competitive ratio of the algorithm is $\mathrm{O}(\sqrt{m})$. $◀$

By combining Theorems 12 and 5, we can obtain the following corollary.

If $m\le \sqrt{n}$, then the algorithm in Theorem 12 is $\mathrm{O}(\sqrt{m})=\mathrm{O}(n^{1/4})$-competitive. On the other hand, if $m>\sqrt{n}$, the competitive ratio of Theorem 5 is $\mathrm{O}(\sqrt{n\text{/}m})=\mathrm{O}(n^{1/4})$. Thus, in either case, there is an $\mathrm{O}(n^{1/4})$-competitive algorithm. $◀$

For the preemptive mUETS problem, Algorithm 2 is also $\mathrm{O}(\log n/\log \log n)$-competitive, and this is asymptotically best possible as we will see in Theorem 18. Thus, even when we are allowed to assign a job batch to more than one machine, we cannot improve the competitive ratio with respect to the number $n$ of jobs. In contrast, we show that the competitive ratio with respect to the number $m$ of machines can be exponentially improved by allowing batches to be assigned to multiple machines.

Let $q$ be an integer such that $q^q>m\ge {(q-1)}^{q-1}$ and let $k^{\ast }$ be $\lfloor {\log }_{q}m\rfloor +1$. Here, $k^{\ast }\le q$ and . We have $q\ge 2$ from the assumption that $m\ge 2$.

Our algorithm for the preemptive mUETS is similar to Algorithm 2 for the preemptive sUETS. However, instead of splitting the uncompleted batch into several smaller batches of similar size, the algorithm increases the number of machines assigned to that batch. This ensures that the competitive ratio of the algorithm does not depend on the number of jobs $n$.

Our algorithm computes an $m$-partition $(X_1,\mathrm{\dots },X_m)$ of the jobs $J$ that minimizes the maximum setup time ${\max }_{i\in [m]}c(X_i)$. In the first phase, each batch $X_i$ is allocated to one machine. Then, each batch is processed until it is completed, or the number of uncompleted batches becomes less than or equal to $\lfloor m/q\rfloor$. In the $k$th phase ($k=2,3,\mathrm{\dots },k^{\ast }$), each uncompleted batch $X_i$ is assigned to $q^{k-1}$ machines, and it is processed until it is completed, or the number of uncompleted batches becomes $\lfloor m/q^k\rfloor$. If the number of uncompleted batches becomes smaller than $\lfloor m/q^k\rfloor$ because multiple batches are completed simultaneously, then break the tie arbitrarily and defer the rest batches to the next phase. Note that this allocation is feasible because $\lfloor m/q^{k-1}\rfloor \cdot q^{k-1}\le m$. At the end of the $k^{\ast }$th phase, all the batches are completed since $\lfloor m/q^{k^{\ast }}\rfloor =0$ by $k^{\ast }=\lfloor {\log }_{q}m\rfloor +1>{\log }_{q}m$. Our algorithm is formally described in Algorithm 4. It should be noted that this algorithm is based on a similar idea to that of [15, Algorithm 1].

Let $\mathrm{OPT}$ be the optimal makespan and let $p_{\max }={\max }_{j\in J}{p}_j$. For each $k\in [k^{\ast }]$, let $S^{(k)}=I^{(k-1)}\setminus I^{(k)}$ be the set of indices of batches that have been completed in the $k$th phase. By the definition of the algorithm, we have

Let ${\tau }_k$ be the time length of phase $k\in [k^{\ast }]$. We first bound it for $k\in [k^{\ast }-1]$. As every batch in $S^{(k+1)}$ is not finished in phase $k$ and the preemption takes time at most ${\max }_{i\in S^{(k)}}(c(X_i)+{\max }_{j\in X_i}{p}_j)\le 2\mathrm{O}\mathrm{P}\mathrm{T}$, we have

Note that $x/\lfloor x\rfloor \le 2$ if $x\ge 1$ and $m/q^k\ge 1$ for $k\in [k^{\ast }-1]$. Thus, we have

for every $k\in [k^{\ast }-1]$.

Next, we bound the time length ${\tau }_{k^{\ast }}$ of phase $k^{\ast }$. As the batch $X_i$ for each $i\in S^{(k^{\ast })}$ is processed by $q^{k^{\ast }-1}$ machines, we have

Hence, by (3) and (4), the makespan of the algorithm is

Therefore, the competitive ratio of Algorithm 4 is $\mathrm{O}(q)=\mathrm{O}(\log m/\log \log m)$. $◀$