Approximation Results for Makespan Minimization with Budgeted Uncertainty

Abstract

We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which goes back to [3], once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs’ processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimize the worst-case scenario. We consider both the cases of identical and unrelated machines. Our main result is an EPTAS for the case of identical machines. We also provide a 3-approximation algorithm and an inapproximability ratio of $2-\epsilon$ for the case of unrelated machines.

This work was partially supported by DFG Project, “Robuste Online-Algorithmen für Scheduling-und Packungsprobleme”, JA 612/19-1, and ANR project ROBUST (ANR-16-CE40-0018).

1 Introduction

Classical optimization models suppose perfect information over all parameters. This can lead to optimal solutions having poor performance when the actual parameters deviate, even by a small amount, from the predictions used in the optimization model. Different frameworks have been proposed to overcome this issue, among which Robust Optimization which tackles the uncertainty by providing a set of possible values for these parameters, and considering the worst outcome over that set. In this paper, we consider the problem of scheduling a set of jobs J on the set of machines M, so as to minimize the makespan, and considering that the processing times are uncertain. What is more, we consider the budgeted uncertainty model introduced by [3] where each processing time varies between its nominal value and the latter plus some deviation. Further, in any scenario, at most $\varGamma$ of the uncertain parameters take the higher values, the other being at their nominal values.

Let us now formally define the Robust Scheduling on Unrelated Machines ($R|{\mathcal {U}^{\varGamma }}|C_{\max }$) problem. For any job $j \in J$ and machine $i \in M$, we denote by $\overline{p}_{ij} \ge 0$ the nominal processing time of j on i, and by $\hat{p}_{ij} \ge 0$ the (potential) deviation of j on i. A schedule $\sigma$ is a function from $J\rightarrow M$. We write $\sigma _i$ for the subset of jobs scheduled on machine i. Let ${\mathcal {U}^{\varGamma }}=\{\xi \in \{0,1\}^{|J|}:\Vert \xi \Vert _1\le \varGamma \}$ be the set of all possible scenarios where at most $\varGamma$ jobs deviate. For any $\xi \in {\mathcal {U}^{\varGamma }}$, we set $p^{\xi }_{ij}=\overline{p}_{ij} + \xi _{j} \hat{p}_{ij}$ to be the actual processing time of j on i in scenario $\xi$.

Let us now formalize some common terms, but with dependence on scenario $\xi$. The load of machine i in scenario $\xi$ is calculated as $\sum _{j\in \sigma _i} p^{\xi }_{ij}$. The makespan in scenario $\xi$ is the maximum load in scenario $\xi$, i.e., $C^{\xi }_{\max }(\sigma ) = \max _{i\in M} \sum _{j\in \sigma _i} p^{\xi }_{ij}$. Finally, $C_{\max }^{\varGamma }(\sigma ) = \max _{\xi \in {\mathcal {U}^{\varGamma }}} C_{\max }^{\xi }(\sigma )$ denotes the objective function we consider in Robust Scheduling, where the adversary takes the worst scenario among ${\mathcal {U}^{\varGamma }}$.

Next, we will state important observations about the objective function. We first need to introduce the following notations. Given a set of jobs $X_i$ scheduled on machine i, we define $\overline{p}(X_i)= \sum _{j\in X_i}\overline{p}_{ij}$, $\hat{p}(X_i)= \sum _{j\in X_i}\hat{p}_{ij}$, $\varGamma (X_i)$ as the set of the $\varGamma$ jobs of $X_i$ with the largest $\hat{p}_{ij}$ values (or $\varGamma (X_i)=\sigma _i$ when $|X_i| < \varGamma$) with ties broken arbitrarily. Finally, set $\hat{p}_{\varGamma }(X_i) = \hat{p}(\varGamma (X_i))$.

By definition we have $C_{\varGamma }(\sigma )= \max _{\xi \in {\mathcal {U}^{\varGamma }}} \max _{i\in M} \sum _{j\in \sigma _i} C_{\xi }(\sigma )$, and thus we can rewrite $C_{\varGamma }(\sigma )= \max _{i\in M} \max _{\xi \in {\mathcal {U}^{\varGamma }}} \sum _{j\in \sigma _i} C_{\xi }(\sigma ) = \max _{i\in M} C_{\varGamma }(\sigma _i)$, where $C_{\varGamma }(\sigma _i) = \max _{\xi \in {\mathcal {U}^{\varGamma }}} \sum _{j\in \sigma _i} C_{\xi }(\sigma )$ is the worst-case makespan on machine i. The benefit of rewriting $C_{\varGamma }(\sigma )$ in this form is that it is now clear that $C_{\varGamma }(\sigma _i) = \overline{p}(\sigma _i)+\hat{p}_{\varGamma }(\sigma _i)$ as the worst scenario $\xi$ for a fixed $\sigma _i$ is obtained by picking the $\varGamma$ jobs with highest $\hat{p}_{ij}$ and make them deviate. Thus, $R|{\mathcal {U}^{\varGamma }}|C_{\max }$ can also be thought as a “classical” scheduling problem (without adversary) where the makespan on a machine $C_{\varGamma }(\sigma _i)$ is simply the sum of all the nominal processing time of jobs of $\sigma _i$, plus only the $\varGamma$ largest deviating values of jobs of $\sigma _i$. We are now ready to define $R|{\mathcal {U}^{\varGamma }}|C_{\max }$.

Problem 1

Robust Scheduling on Unrelated Machines ($R|{\mathcal {U}^{\varGamma }}|C_{\max }$)

• Input: $(J, M, \overline{p}\in \mathbb {Q}^{|M|\times |J|}_+, \hat{p}\in \mathbb {Q}^{|M|\times |J|}_+)$ where J is the set of jobs, M the set of machines, $\overline{p}$ are the vectors of nominal processing times, and $\hat{p}$ the vectors of deviation

• Output: find a schedule $\sigma :J\rightarrow M$

• Objective function: min $C_{\varGamma }(\sigma )= \max _{\xi \in {\mathcal {U}^{\varGamma }}} \max _{i\in M} \sum _{j\in \sigma _i}[\overline{p}_{ij} + \xi _{j} \hat{p}_{ij}] = \max _{i\in M} C_{\varGamma }(\sigma _i)$, where $C_{\varGamma }(\sigma _i) = \overline{p}(\sigma _i)+\hat{p}_{\varGamma }(\sigma _i)$.

Following the classical three field notation, we denote by $R|{\mathcal {U}^{\varGamma }}|C_{\max }$ the previous problem. Notice that when all $\hat{p}_{ij}=0$ the problem corresponds to the classical $R||C_{\max }$, for which we denote by $C(\sigma _i)=\sum _{j \in \sigma _i}\overline{p}_{ij}$ the makespan on machine i. We are also interested in a simplification of the above problem. This simplification is Robust Scheduling on Identical Machines ($P|{\mathcal {U}^{\varGamma }}|C_{\max }$) where each has two processing times ($\overline{p}_j$ and $\hat{p}_j$), and we have $\overline{p}_{ij}=\overline{p}_j$ and $\hat{p}_{ij}=\hat{p}_j$ for any i.

Robust scheduling has been considered in the past, mostly for finite uncertainty sets without particular structure, see for instance [1, 6, 9, 10, 12]. More recently, [2, 5, 13] considered robust packing and scheduling with the budgeted uncertainty model ${\mathcal {U}^{\varGamma }}$ from [4]. Specifically, [5] (with authors in common) provided a 3-approximation algorithm and a $(1+\epsilon )$-approximation (PTAS) for $P|{\mathcal {U}^{\varGamma }}|C_{\max }$ but only for a constant $\varGamma$, as well as a randomized approximation algorithm for $R|{\mathcal {U}^{\varGamma }}|C_{\max }$ having an average ratio of $O(\log (m))$. They also considered problem $1|{\mathcal {U}^{\varGamma }}|\sum _jw_jC_{\max }$, proving that the problem is $\mathcal{NP}$-hard in the strong sense, and providing a polynomial-time algorithm when $w_j=1$ for $j\in J$. Authors of [13] considered the robust one-machine problem for four commonly-used objective criteria: (weighted) total completion time, maximum lateness/tardiness, and number of late jobs. They showed that some of these problems are polynomially solvable and provide mixed-integer programming formulations for others. Their results considered ${\mathcal {U}^{\varGamma }}$ as well as two closely related uncertainty sets. Paper [2] (with also authors in common) considers robust bin-packing problem for ${\mathcal {U}^{\varGamma }}$ and one of the uncertainty sets considered by [13], and provided constant-factor approximations algorithms for the two problems.

In this paper we improve the results of [5] for $P|{\mathcal {U}^{\varGamma }}|C_{\max }$ and $R|{\mathcal {U}^{\varGamma }}|C_{\max }$. In Sect. 2 we show that any c-approximation for the classical $R||C_{\max }$ problem leads to a $(c + 1)$-approximation for $R|{\mathcal {U}^{\varGamma }}|C_{\max }$, hence obtaining a 3-approximation algorithm for the latter problem, and a $(2 + \epsilon )$-approximation for $P|{\mathcal {U}^{\varGamma }}|C_{\max }$. We point out that this result improves the ad-hoc 3-approximation of [5] for $P|{\mathcal {U}^{\varGamma }}|C_{\max }$, while having a simpler proof. In Sect. 3, we show through a reduction from the Restricted Assignment Problem that there exists no $(2-\epsilon )$-approximation algorithm for $R|{\mathcal {U}^{\varGamma }}|C_{\max }$ unless $\mathcal{P}=\mathcal{NP}$. This implies that the best possible ratio (unless $\mathcal{P}=\mathcal{NP}$) for $R|{\mathcal {U}^{\varGamma }}|C_{\max }$ is somewhere between 2 and 3, contrasting with the classical $R||C_{\max }$ where the gap between $\frac{3}{2}$ and 2 is still open since [11].

In Sect. 4 we consider the $P|{\mathcal {U}^{\varGamma }}|C_{\max }$ problem and present the first step of our main result, namely a PTAS which is valid even when $\varGamma$ is part of the input, i.e., not constant. Having $\varGamma$ in the input (and not constant) requires a totally different technique from the one used in [5]. The algorithm is turned into an EPTAS in Sect. 5, i.e., a PTAS where the dependency of $\epsilon$ is not in the exponent of the encoding length.

2 A 3-Approximation for Unrelated Machines

Theorem 1

Any polynomial c-approximation for $R||C_{\max }$ implies a polynomial $(c + 1)$-approximation for $R|{\mathcal {U}^{\varGamma }}|C_{\max }$.

Proof

(Proof of Theorem 1). We design a dual approximation, i.e., given an instance I of $R|{\mathcal {U}^{\varGamma }}|C_{\max }$ and an threshold T, we either give a schedule $\sigma$ of I with $C_{\varGamma }(\sigma ) \le (c + 1) T$, or prove that $T < \mathrm {OPT}(I)$. Using a binary search on T this will imply a $(c+1)$-approximation algorithm.

For that, given an instance $I=(J, M, \overline{p}, \hat{p})$ of $R|{\mathcal {U}^{\varGamma }}|C_{\max }$, and T the current threshold, our objective is to define an instance $I' =(J, M, p)$ of the classical $R||C_{\max }$ problem. The transformation of a solution for $I'$ to a solution for I will be straightforward since the jobs and machines will be the same.

Given a machine i, let $B_i = \{j | \hat{p}_{ij} > \frac{T}{\varGamma }\}$ and $S_i = J \setminus B_i$. Define

$$\begin{aligned} p_{ij} := {\left\{ \begin{array}{ll} \overline{p}_{ij} + \hat{p}_{ij} &{} \text {if } j \in B_i \\ \overline{p}_{ij} &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

(1)

Let us now prove that (1) if $\mathrm {OPT}(I')>T$ then we have $\mathrm {OPT}(I)>T$, and (2) every schedule $\sigma$ with makespan $C^{I'}(\sigma )$ in $I'$ has a makespan at most $C^{I'}(\sigma )+T$ in I ($C_{\varGamma }(\sigma ) \le C^{I'}(\sigma )+T$).

For (1), we prove that $\mathrm {OPT}(I) \le T$ implies that $\mathrm {OPT}(I') \le T$. Let $\sigma$ be an optimal solution of I and i a machine. $C_{\varGamma }(\sigma ) \le T$ implies that $C_{\varGamma }(\sigma _i) \le T$ for any i, and thus that $\overline{p}(\sigma _i)+\hat{p}_{\varGamma }(\sigma _i) \le T$. Now, observe that $B_i \subseteq \varGamma (\sigma _i)$. Indeed, assume towards contradiction that there exists $j \in B_i \setminus \varGamma (\sigma _i)$. This implies that $|\varGamma (\sigma _i)|=\varGamma$. As by definition, any $j' \in \varGamma (\sigma _i)$ has $\hat{p}_{ij'} \ge \hat{p}_{ij} > \frac{T}{\varGamma }$, we get that $\hat{p}_{\varGamma }(\sigma _i) > T$, a contradiction. This implies $C^{I'}(\sigma _i) = \overline{p}(\sigma _i)+\hat{p}(B_i) \le \overline{p}(\sigma _i)+\hat{p}_{\varGamma }(\sigma _i) \le T$.

For (2), let $\sigma$ be a solution of $I'$. Let $i \in M$. Observe that $\hat{p}(\varGamma (\sigma _i)) \le \hat{p}(B_i)+T$ as $\varGamma (\sigma _i)$ contains at most $\varGamma$ jobs in $\sigma _i \setminus B_i$, and these jobs have $\hat{p}_{ij} \le \frac{T}{\varGamma }$. Thus, $C_{\varGamma }(\sigma _i)=\overline{p}(\sigma _i)+\hat{p}_{\varGamma }(\sigma _i) \le \overline{p}(\sigma _i)+\hat{p}(B_i)+T=C^{I'}(\sigma _i)+T$.

Thus, given a T and I we create $I'$ as above and run the c-approximation for $R||C_{\max }$ to get a solution $\sigma$. If $C^{I'}(\sigma ) > cT$ then $\mathrm {OPT}(I')>T$, implying $\mathrm {OPT}(I) > T$, and thus we reject T. Otherwise, we consider $\sigma$ as a solution for I, and $C_\varGamma (\sigma ) \le (c+1)T$.   $\square$

Using the well-known 2-approximation algorithm from [11], we obtain immediately the following.

Corollary 1

There is a 3-approximation for $R|{\mathcal {U}^{\varGamma }}|C_{\max }$.

Since by this reduction identical machines stay identical we also obtain the following using the EPTAS of [7] for the classical $Q||C_{\max }$ problem.

Corollary 2

For every $\epsilon > 0$ there is a $(2 + \epsilon )$-approximation for $P|{\mathcal {U}^{\varGamma }}|C_{\max }$ running in time $2^{O(1/\epsilon \log (1/\epsilon )^4)}+poly(n)$.

3 A $2-\epsilon$ Inapproximability for Unrelated Machines

For the classical $R||C_{\max }$ problem, when all $p_{ij} \in \{1,\infty \}$, deciding if the optimal value is at most 1 is polynomially solvable as it can be reduced to finding a matching in a bipartite graph. The result below shows that answering the same question for $R|{\mathcal {U}^{\varGamma }}|C_{\max }$ is $\mathcal{NP}$-complete.

Theorem 2

Given an instance I of $R|{\mathcal {U}^{\varGamma }}|C_{\max }$, it is NP-complete to decide if $\mathrm {OPT}(I) \le 1$ or $\mathrm {OPT}(I) \ge 2$, and thus for any $\epsilon > 0$ is no $(2-\epsilon )$-approximation algorithm for $R|{\mathcal {U}^{\varGamma }}|C_{\max }$ unless $\mathcal{P}=\mathcal{NP}$, even for $\varGamma =1$ and when each job can be scheduled on at most 3 machines.

Proof

Let us define a reduction from 3-SAT to $R|{\mathcal {U}^{\varGamma }}|C_{\max }$ with $\varGamma =1$. Let $I_0$ be an instance of 3-SAT with clauses $\{C_i, i \in [m_0]\}$ and variables $\{x_j, j \in [n_0]\}$. Each $C_i$ is of the form $l^1_i \vee l^2_i \vee l^3_i$ where $l^k_i \in \{x_j,\bar{x}_j\}$ for some j. We define an instance I of $R|{\mathcal {U}^{\varGamma }}|C_{\max }$ with $m=2n_0$ machines and $n=n_0+m_0$ jobs as follows. To each variable $x_j$ we associate two machines $\{j_f,j_t\}$. We create a set of $n_0$ variable jobs where for any $j \in [n_0]$, $\overline{p}_{j_fj}=\overline{p}_{j_tj}=1$, $\overline{p}_{i'j}=\infty$ for any other $i'$, and $\hat{p}_{ij}=0$ for any $i \in [m]$. For any clause $C_i$, $i \in [m_0]$ we define $M_i$: the set of 3 machines corresponding to literals $\{l^k_i\}$ satisfying $C_i$. For example, if $C_7 = x_1 \vee \bar{x}_3 \vee x_5$ then $M_7 = \{1_t,3_f,5_t\}$. We now define a set of $m_0$ clause jobs as follows. For any $j \in [n_0+1,n_0+m_0]$, job j represents clause $C_{j-n_0}$ with $\hat{p}_{ij}=1$ iff $i \in M_{j-n_0}$, $\hat{p}_{i'j}=\infty$ for any other $i'$, and $\overline{p}_{ij}=0$ for any $i\in [m]$. For example, job $j=n_0+7$ is associated to $C_7$ where in particular $\hat{p}_{1_tj}=\hat{p}_{3_fj}=\hat{p}_{5_tj}=1$. Notice that each clause job can be scheduled on at most 3 machines. Let us now verify that $I_0$ is satisfiable iff $\mathrm {OPT}(I)=1$.

$\Rightarrow$. Suppose $I_0$ is satisfied by assignment a. For any $j \in [n_0]$, we schedule j on $j_t$ if $x_j$ is set to false in a and on $j_f$ otherwise. For any $j \in [n_0+1,n_0+m_0]$, we schedule job j on any machine $i \in M_{j-n_0}$ corresponding to a literal satisfying $C_i$ in assignment a. Notice that in this schedule, a machine either receives exactly one variable job, implying a makespan of 1, or only clause jobs, also implying a makespan of 1 as $\varGamma =1$.

$\Leftarrow$. Suppose that $\mathrm {OPT}(I)=1$ and let us define an assignment a. This implies that any variable job j is either scheduled on machine $j_f$, in which case we set $x_j$ to true, or on machine $j_t$, in which case we set $x_j$ to false. As $\mathrm {OPT}(I)=1$, and clause job $j \in [n_0+1,n_0+m_0]$ is scheduled on a machine $i \in M_{j-n_0}$ that did not receive a variable job, implying that clause $j-n_0$ is satisfied by literal i.   $\square$

4 A PTAS for Identical Machines

Note that we can assume that $m < n$. If $m \ge n$, a trivial schedule with every job on a different machine is optimal. In some problems the encoding length may be much smaller than m, when m is only encoded in binary. However, here a polynomial time algorithm is allowed to have a polynomial dependency on m.

Recall that for the $P|{\mathcal {U}^{\varGamma }}|C_{\max }$ problem, given two n dimensional vectors $\hat{p}$ and $\overline{p}$ and the number of machine m, the objective is to create a schedule $\sigma$ that minimizes $\max _{i\in M} C_{\varGamma }(\sigma _i)$. Recall also that $C_{\varGamma }(\sigma _i)=\overline{p}(\sigma _i)+\hat{p}_{\varGamma }(\sigma _i)$, where $\overline{p}(\sigma _i)= \sum _{j\in \sigma _i}\overline{p}_{j}$, and $\hat{p}_{\varGamma }(\sigma _i)$ is the sum of the $\hat{p}_j$ values of the $\varGamma$ largest jobs (w.r.t. $\hat{p}_j$) of $\sigma _i$ (or the sum of all $\hat{p}_j$ values if $|\sigma _i| \le \varGamma$). To obtain a PTAS for $P|{\mathcal {U}^{\varGamma }}|C_{\max }$, we will reduce to the following problem, which admits an EPTAS (see [8]).

Problem 2

Unrelated Machines with few Machine Types

• Input: n jobs and a set M of m machines with processing times $p_{ij} \ge 0$ for job j on machine i. Moreover, there is a constant k and machine types $T_1\dot{\cup }\cdots \dot{\cup }T_k = \{1,\dotsc ,m\}$, such that every machine within a type behaves the same. Formally, for every $k'$, every $i, i'\in T_{k'}$ and every $j\le n$ it holds that $p_{ij}=p_{i'j}$

• Output: find a schedule $\sigma :J\rightarrow M$

• Objective function: minimize makespan $C(\sigma )= \max _{i\in M} C(\sigma _i)$, where $C(\sigma _i) = \sum _{j\in \sigma _i} p_{ij}$

Notice that the EPTAS of [8] for this problem provides an $(1+\epsilon )$-approximation running in time $f(|I|,\epsilon ,k)=2^{O(k\log (k)\frac{1}{\epsilon } \log ^4(\frac{1}{\epsilon }))}+poly(|I|)$.

We also introduce the following decision problem.

Problem 3

Unrelated Machines with few Machine Types and capacities

• Input: as above, but in addition every machine i has a capacity $c_{i}\in (0,1]$. Moreover, capacities are the same among a type (for any $k' \in [k]$, for any $i,i' \in T_{k'}$, $c_i = c_{i'}$)

• Output: decide if there is a schedule where $C(\sigma _i) \le c_i$ for any i.

Notice that the EPTAS for Problem 2 allows to approximately decide Problem 3 in the following sense.

Lemma 1

There is an algorithm that for any $\epsilon > 0$, either outputs a schedule with $C(\sigma _i) \le (1+\epsilon )\cdot c_i$ for any i, or reject the instance, proving that there is no schedule with $C(\sigma _i) \le c_i$ for any i. This algorithm runs in time $f(|I|,\epsilon ,k)$ where f is the complexity of the above EPTAS to get a $(1+\epsilon )$-approximation.

Proof

Let A be the EPTAS of [8] for Problem 2. Given a input I of Problem 3 we define an input $I'$ of Problem 2 in the following way. For every $j\le n$, scale $p_{ij}$ to $p_{ij} / c_i$. Then, if $A(I') \le (1+\epsilon )$, we can convert the solution found by A into a solution for I of makespan at most $(1+\epsilon ) \cdot c_i$ for any i. Otherwise, as A is a $(1+\epsilon )$-approximation, it implies that $\mathrm {OPT}(I') > 1$, and thus that no solution can have makespan at most $c_i$ for any i.   $\square$

Let us now describe the PTAS for $P|{\mathcal {U}^{\varGamma }}|C_{\max }$. Our objective is to provide a $(1+O(\epsilon ))$ dual approximation for $P|{\mathcal {U}^{\varGamma }}|C_{\max }$. The constant factor with $\epsilon$ can be ignored, since we can divide $\epsilon$ with this constant in the preprocessing.

1. Guess the makespan and scale $\mathrm {OPT}$ to 1. Let I be an input of $P|{\mathcal {U}^{\varGamma }}|C_{\max }$, and T be a positive value (representing the current threshold). We start by redefining I by scaling $p_j := \frac{p_j}{T}$. Our objective is now to produce a schedule $\sigma$ with $C_{\varGamma }(\sigma ) \le 1+\epsilon$, or to prove that $\mathrm {OPT}(I) > 1$.

2. Rounding deviations. Let us now define $I^1$ (having vectors $\overline{p}^1$ and $\hat{p}^1$) in the following way. For any j, if $\hat{p}_j < \epsilon /\varGamma$ then we set $\hat{p}^1_j\leftarrow 0$. Intuitively, this will only result in an error of at most $\varGamma \cdot \epsilon / \varGamma$ on every machine. Otherwise ($\hat{p}_j \ge \epsilon /\varGamma$), we define $\hat{p}^1_j$ by rounding $\hat{p}_j$ to the closest smaller value of the form $\epsilon /\varGamma \cdot (1 + \epsilon )^i$.

Observation 1

In $I^1$ there are at most $O(1/\epsilon \log (\varGamma /\epsilon ))$ deviation values, and at most $O(1/\epsilon \log (1/\epsilon ))$ deviation values in the interval $[\epsilon /\varGamma , 1/\varGamma ]$.

In the following, we will denote by $C^{I'}_\varGamma (\sigma )$ the cost of $\sigma$ for instance $I'$.

Observation 2

If $\mathrm {OPT}(I) \le 1$ then $\mathrm {OPT}(I^1) \le 1$. If we get solution $\sigma ^1$ of $I^1$, then $C^I_{\varGamma }(\sigma ^1) \le (1+\epsilon )C^{I^1}_{\varGamma }(\sigma ^1)+\epsilon$

It only remains now to either produce a good solution of $I^1$ (of cost at most $1+O(\epsilon )$), or prove that $\mathrm {OPT}(I^1) > 1$.

3. Machine thresholds. Given any solution $\sigma$ of $I^1$ such that $C^{I^1}_{\varGamma }(\sigma ) \le 1$, we can associate to $\sigma$ an outline $t = o(\sigma )$ which is defined as follows. For any machine i with more that $\varGamma$ jobs, the threshold value $t_i$ is such that any job on i with $\hat{p}_j > t_i$ deviates (belongs to $\varGamma (\sigma _i)$) and none of the jobs with $\hat{p}_j < t_i$ deviate. Notice that among jobs with $\hat{p}_j = t_i$, some may deviate, but not necessarily all. For any machine i with at most $\varGamma$ jobs, we define $t_i = 0$, implying again that any job with $\hat{p}_j > t_i$ deviates on i. Notice that in both cases we have $\hat{p}_{\varGamma }(\sigma _i) \ge \varGamma \cdot t_i$. Notice also that $C^{I^1}_{\varGamma }(\sigma ) \le 1$ implies $t_i \le \frac{1}{\varGamma }$. Indeed, if we had $t_i > \frac{1}{\varGamma }$, there would be $\varGamma$ deviating jobs with $\hat{p}_j > t_i$, implying $C^{I^1}_{\varGamma }(\sigma _i) > 1$, a contradiction. Let us denote by $\varDelta$ the set of all possible values of a $t_i$. According to Observation 1 we have $|\varDelta | =O(1/\epsilon \log (1/\epsilon ))$. Let $\mathcal {P}= \varDelta ^m$ be the set of all outlines (of solutions of cost at most 1).

Lemma 2

Consider a solution $\sigma ^{1*}$ of $I^1$ such that $C_\varGamma (\sigma ^{1*}) \le 1$, and let $t^* = o(\sigma ^{1*})$. Then, we can guess in $m^{O(1/\epsilon \log (1/\epsilon ))}$ time the vector $t^*$ (or a permutation thereof).

Proof

As $t^* \in T$, all the $t^*_i$ have a value in $\{0\}\cup [\frac{\epsilon }{\varGamma },\frac{1}{\varGamma }]$. Thus, as deviating values are rounded in $I^1$, there are only a constant number of possible threshold value and we can guess them. For every possible threshold, we guess how many machines in the optimal solution have it.   $\square$

Thus, we can now assume that we know the vector $t^*$.

4. Constructing an instance with few machine types and capacities. To give an insight of the correct reduction defined below, let us first see what happen if we define an instance $I^2(t^*)$ of $R||C_{\max }$ as follows. For simplicity, we also assume that there are no job with $\hat{p}_j = t^*_i$ on each machine i in the previously considered optimal solution of $I^1$. For any machine i and job j, define the processing time in $I^2(t^*)$ as $p_{ij}=\overline{p}_j+\hat{p}_j$ if $\hat{p}_j \ge t^*_i$, and $p_{ij}=\overline{p}_j$ otherwise. Then, consider the following implications.

• 1. if $OPT(I^1) \le 1$, then $\mathrm {OPT}(I^2(t^*)) \le 1$

• 2. for any solution $\sigma '$ of $I^2(t^*)$, $C^{I^1}_{\varGamma }(\sigma ') \le C^{I^2}(\sigma ')$ (implying that if there exists $\sigma '$ with $C^{I^2}(\sigma ') \le 1+\epsilon$, then we will have our solution for $I^1$ of cost $1+\epsilon$)

While Property (1) holds, this is not the case for Property (2). Indeed, suppose that in $\sigma '$ there is a machine i such that for all jobs j scheduled on i, $\hat{p}_j < t^*_i$. This implies that $C(\sigma _i)=\sum _{j \in \sigma _i} \overline{p}_j$. However, if we look now at $\sigma '$ in $I^1$, we get $C^{I^1}_{\varGamma }(\sigma _i)=C^{I^2}(\sigma _i) + \hat{p}(\varGamma (\sigma _i))$, which is greater than the claimed value. To solve this problem we have to remember in $R||C_{\max }$ that there will be a space of size at most $\varGamma \cdot t_i$ which will be occupied by deviations.

Let us now turn to the correct version.

Definition 1

For any $t \in \mathcal {P}$, we define the following input $I^2(t)$ of Problem 3. We set the machine capacity to

$$\begin{aligned} c_i := 1 - \varGamma \cdot t_i + \epsilon . \end{aligned}$$

The addition of $\epsilon$ is only a technicality to ensure that all $c_i$ are non-zero. Note that if there are less than $\varGamma$ jobs on i, then $t_i$ must be 0 and therefore $c_i = 1 + \epsilon$. For every job j set

$$\begin{aligned} p_{ij} := {\left\{ \begin{array}{ll} \overline{p}_j + \hat{p}_j - t_i &{}\text { if } \hat{p}_j \ge t_i, \\ \overline{p}_j &{}\text { if } \hat{p}_j < t_i. \\ \end{array}\right. } \end{aligned}$$

Note that at $\hat{p}_j = t_i$, the values of both cases are equal. Notice also that in $I^2(t)$ there are only $|\varDelta |$ different machine types.

Lemma 3

If $\mathrm {OPT}(I^1) \le 1$ and t is the outline of an optimal solution $\sigma ^2$, for any i, $C^{I^2(t)}(\sigma ^2_i) \le c_i$.

Proof

Let us consider jobs $\sigma ^2_i$ scheduled on machine i. If $t_i = 0$, then

$$\begin{aligned} \sum _{j\in \sigma ^2_i} p_{ij} = \sum _{j\in \sigma ^2_i} \overline{p}_j + \hat{p}_j \le 1 < c_i. \end{aligned}$$

Assume now $t_i > 0$, implying that $|\varGamma (\sigma ^2_i)| \ge \varGamma$. By choice of $t_i$, every job $j\in \varGamma (\sigma ^2_i)$ has $\hat{p}_j\ge t_i$ and every $j\in \sigma ^2_i\setminus \varGamma (\sigma ^2_i)$ has $\hat{p}_j\le t_i$. This implies

$$\begin{aligned} \sum _{j\in \sigma ^2_i} p_{ij} = \sum _{j\in \varGamma (\sigma ^2_i)} p_{ij} + \sum _{j\in \sigma ^2_i\setminus \varGamma (\sigma ^2_i)} p_{ij} = \sum _{j\in \varGamma (\sigma ^2_i)} [\overline{p}_j + \hat{p}_j - t_i] + \sum _{j\in \sigma ^2_i\setminus \varGamma (\sigma ^2_i)} \overline{p}_j \le 1 - \varGamma \cdot t_i < c_i. \end{aligned}$$

   $\square$

Lemma 4

For any $t \in \mathcal {P}$, if there is a solution $\sigma ^2$ of $I^2(t)$ such that $C^{I^2(t)}(\sigma ^2_i) \le (1+\epsilon )\cdot c_i$ for any i, then $C^{I^1}_{\varGamma }(\sigma ^2) \le (1 + \epsilon )^2$.

Proof

Let i be a machine. Then for every $j\in \sigma ^2_i$,

$$\begin{aligned} p_{ij} = {\left\{ \begin{array}{ll} \overline{p}_j + \hat{p}_j - t_i \ge \overline{p}_j &{}\text { if } \hat{p}_j \ge t_i, \\ \overline{p}_j &{}\text { if } \hat{p}_j < t_i. \end{array}\right. } \end{aligned}$$

Furthermore, for every $j\in \varGamma (\sigma ^2_i)$,

$$\begin{aligned} p_{ij} = {\left\{ \begin{array}{ll} \overline{p}_j + \hat{p}_j - t_i &{}\text { if } \hat{p}_j \ge t_i, \\ \overline{p}_j > \overline{p}_j + \hat{p}_j - t_i &{}\text { if } \hat{p}_j < t_i. \end{array}\right. } \end{aligned}$$

This implies,

$$\begin{aligned}&\quad \sum _{j\in \varGamma (\sigma ^2_i)} [\overline{p}_j + \hat{p}_j] + \sum _{j\in \sigma ^2_i\setminus \varGamma (\sigma ^2_i)} \overline{p}_j \le \varGamma \cdot t_i + \sum _{j\in \varGamma (\sigma ^2_i)} [\overline{p}_j + \hat{p}_j - t_i] + \sum _{j\in \sigma ^2_i\setminus \varGamma (\sigma ^2_i)} \overline{p}_j \\&\le \varGamma \cdot t_i + \sum _{j\in \varGamma (\sigma ^2_i)} p_{ij} + \sum _{j\in \sigma ^2_i\setminus \varGamma (\sigma ^2_i)} p_{ij} = \varGamma \cdot t_i + \underbrace{\sum _{j\in \sigma ^2_i} p_{ij}}_{\le (1 + \epsilon )\cdot c_i} \le \varGamma \cdot t_i + (1 + \epsilon )\cdot (1 - \varGamma \cdot t_i + \epsilon ) \le (1 + \epsilon )^2. \end{aligned}$$

   $\square$

Theorem 3

There is a $(1+\epsilon )$-approximation algorithm for $P|{\mathcal {U}^{\varGamma }}|C_{\max }$ running in time $O(m^{O(1/\epsilon \log (1/\epsilon ))} \times f(|I|,\epsilon ,O(1/\epsilon \log (1/\epsilon )))$ where f is the function of Lemma 1.

Proof

Given I input of $P|{\mathcal {U}^{\varGamma }}|C_{\max }$ and a threshold T, we run algorithm A of Lemma 1 on $I^2(t)$ for any $t \in \mathcal {P}$ with a precision $\epsilon$. If A rejects all the $I^2(t)$ then we can reject T according to Observation 2 and Lemma 3. Otherwise, there exists $t_0$ such that $A(I^2(t_0))$ outputs a schedule $\sigma ^2$ where $C^{I^2(t_0)}(\sigma ^2) \le (1+\epsilon )\cdot c_i$ for any i, implying $C^I_\varGamma (\sigma ^2) \le (1+\epsilon )C^{I^1}_\varGamma (\sigma ^2)+\epsilon \le (1+\epsilon )^3+\epsilon \le 1+5\epsilon$ according to Observation 2 and Lemma 4 (for sufficiently small $\epsilon$). Finally, the running time is as claimed due to the bound of $\mathcal {P}$ in Lemma 2.   $\square$

5 EPTAS for Identical Machines

The approach for an EPTAS is similar to the PTAS above. We would like to remove the bottleneck from the previous section, which is the guessing the thresholds. In the PTAS we notice that even if the thresholds were chosen incorrectly, but we find a solution to the derived problem, we can get a good solution for the initial problem. Informally, we will now still create an instance of Problem 3, but we only guess approximately the number of machines for each threshold.

We start by defining $I^1$ as in the previous section. Given any solution $\sigma ^1$ of $I^1$ such that $C^{I^1}_{\varGamma }(\sigma ^1) \le 1$, we can associate to $\sigma$ a restricted outline $\overline{m}=\overline{o}(\sigma )$ where $\overline{m}$ is defined as follows. Let $t=o(\sigma )$. For any threshold value $l \in \varDelta$, let $m_l= |\{i | t_i = l\}|$ be the number of machines with threshold l in $\sigma ^1$. We define $\overline{m}_{l} \in \{0, 1, 2, 4, 8,\dotsc , 2^{\lfloor \log (m)\rfloor }\}$ such that $\overline{m}_l \le m_l < 2 \overline{m}_l$. Let $\overline{\mathcal {P}}= \{\overline{m}\in \{0, 1, 2, 4, 8,\dotsc , 2^{\lfloor \log (m)\rfloor }\}^\varDelta \hbox { such that} \frac{m}{2} \le \sum _l \overline{m}_l\le m \}$ be the set of restricted outlines (of solutions of cost at most 1).

Lemma 5

Consider a solution $\sigma ^{1*}$ of $I^1$ such that $C_\varGamma (\sigma ^{1*}) \le 1$, and let $\overline{m}^* = \overline{o}(\sigma ^{1*})$. Then, we can guess in time $2^{O(1/\epsilon \log ^2(1/\epsilon ))} + m^{O(1)}$ the vector $\overline{m}^*$.

Proof

Clearly it suffices to iterate over all values $\overline{m}_{i}\in \big \{0, 1, 2, 4, 8,\dotsc , 2^{\lfloor \log (m)\rfloor }\big \}$, i.e., $O(\log (m))$ many. Guessing this number for every threshold value in $\varDelta$ takes $\log ^{O(1/\epsilon \log (1/\epsilon ))}(m)$ time. Consider first the case when $\log (m)/\log \log (m) \le 1/\epsilon \log (1/\epsilon )$. For sufficiently large m it holds that $\log ^{1/2}(m) \le \log (m)/\log \log (m) \le 1/\epsilon \log (1/\epsilon )$. Hence,

$$\begin{aligned} \log ^{O(1/\epsilon \log (1/\epsilon ))}(m) = (\log ^{1/2}(m))^{2 \cdot O(1/\epsilon \log (1/\epsilon ))} \le (1/\epsilon \log (1/\epsilon ))^{O(1/\epsilon \log (1/\epsilon ))} \le 2^{O(1/\epsilon \log ^2(1/\epsilon ))}. \end{aligned}$$

If on the other hand $\log (m)/\log \log (m) \ge 1/\epsilon \log (1/\epsilon )$, then

$$\begin{aligned} \log ^{O(1/\epsilon \log (1/\epsilon ))}(m) \le \log ^{O(\log (m)/\log \log (m))}(m) = 2^{O(\log (m)/\log \log (m)\cdot \log \log (m))} = m^{O(1)}. \end{aligned}$$

We conclude,

$$\begin{aligned} \log ^{O(1/\epsilon \log (1/\epsilon ))}(m) \le 2^{O(1/\epsilon \log ^2(1/\epsilon ))} + m^{O(1)}. \end{aligned}$$

From all the guesses, we report fail whenever $\sum _i m_i < m/2$ or $\sum _i m_i > m$.   $\square$

For any $\overline{m}\in \overline{\mathcal {P}}$, we define the following input $I^2(\overline{m})$ of Problem 3. We first create for any l a set $M_l$ of $\overline{m}_{l}$ machines where for each machine $i \in M_l$ the capacity and the $p_{ij}$ are defined as in Definition 1 for threshold $t_i=l$. Then, we create another set $M'_l$ of $\overline{m}_{l}$ machines (that we call cloned machines) with the same capacity and the same $p_{ij}$ values. Let $m' = \sum \overline{m}_{l}$. Notice that the total number of machines is $2m'$, with $m \le 2m' < 2m$. Thus, we have to ensure that not too many machines are used in total. For that purpose we add a set of $2m' - m$ dummy jobs D, where all $j \in D$ have $p_{ij}=\infty$ on the original machines $i \in M_l$ and $p_{ij}=c_i$ on every cloned machine $i \in M'_l$. Notice that the number of types is now $2|\varDelta |$, which is still small enough to get an EPTAS. Let us call the non-dummy jobs regular jobs.

Lemma 6

If $\mathrm {OPT}(I^1) \le 1$ and $\overline{m}$ is the restricted outline of an optimal solution, then there exists a solution $\sigma ^2$ of $I^2(\overline{m})$ such that for any i, $C^{I^2(\overline{m})}(\sigma ^2_i) \le c_i$.

Proof

Let $m^*_l= |\{i | t_i = l\}|$ be the number of machines with threshold l in the considered optimal solution of $I^1$. Let $l \in \varDelta$ be a threshold value. We first schedule $2\overline{m}_{l} - m^{*}_{l}$ many dummy jobs on cloned machines of $M'_l$. This will cover all dummy jobs, since

$$\begin{aligned} \sum _l[2 \overline{m}_{l} - m^{*}_{l}] = 2\sum _l \overline{m}_{l} - \sum _{l} m^{*}_{l} = 2m' - m. \end{aligned}$$

We will now schedule all remaining jobs on the empty machines. For every threshold value l we have $2 \overline{m}_l - (2\overline{m}_l - m^*_l) = m^*_l$ many empty machines. In other words, we are left with an instance with the exact same number of machines for each threshold as in the optimal solution and with the original jobs. As argued in Lemma 3, we get the desired claim.   $\square$

Lemma 7

For any $\overline{m}\in \overline{\mathcal {P}}$, if there is a solution $\sigma ^2$ of $I^2(\overline{m})$ such that $C^{I^2(\overline{m})}(\sigma _i^2) \le c_i+\epsilon$ for any i, then we can deduce a solution $\sigma ^3$ for $I^1$ with $C^{I^1}_{\varGamma }(\sigma ^3) \le (1 + 2\epsilon )^2$.

Proof

We will first normalize $\sigma ^2$. Since dummy jobs have $p_{ij}=c_i$ on cloned machines, in a $(1+\epsilon )$-approximation there can only be one per machine (assuming that $\epsilon < 1$). Indeed, there may still be a load of $\epsilon \cdot c_i$ from other jobs on the same machine. We want to ensure that every machine either has a dummy job or some regular load, but not both. For every threshold value $l \in \varDelta$, there can be at most $\overline{m}_l$ machines in $M'_l$ that have a dummy job. For any such machine in $M'_l$, we remove all the regular jobs (of total load of at most $\epsilon \cdot c_i$) from it and move them to one of the original machines in $M_l$, without using the same machine in $M_l$ twice. Since for any $i \in M_l$ we had $C^{I^2(\overline{m})}(\sigma ^2_i) \le (1 + \epsilon ) c_i$ before moving the jobs, and since regular jobs have the same processing time on machines $M_l$ and $M'_l$, after moving the jobs we get $C^{I^2(\overline{m})}(\sigma ^2_i) \le (1+2\epsilon ) c_i$ for any $i \in M_l$. We now have a solution violating the capacities by at most $2\epsilon \cdot c_i$ such that a machine with a dummy job has no other jobs.

We now forget about all dummy jobs and the machines they are on. What we are left with is a set of m machines (with some thresholds t) such that for any i we have $C^{I^2(\overline{m})}(\sigma ^2_i) \le (1+2\epsilon ) c_i$. By Lemma 4 we get the desired result.    $\square$

All in all, we were able to reduce the number of instances created to only $2^{O(1/\epsilon \log ^2(1/\epsilon ))} + m^{O(1)}$ many and removed the bottleneck from the PTAS this way. As in Theorem 3, given an instance of $P|{\mathcal {U}^{\varGamma }}|C_{\max }$ we will use the algorithm of Lemma 1 on $I^2(m)$ for any $m \in \overline{\mathcal {P}}$. This leads to the following result.

Theorem 4

There is a $(1+\epsilon )$-approximation algorithm for $P|{\mathcal {U}^{\varGamma }}|C_{\max }$ running in time $O(2^{O(1/\epsilon \log ^2(1/\epsilon ))} + m^{O(1)}) \times f(|I|,\epsilon ,O(1/\epsilon \log (1/\epsilon )))$ where f is the function of Lemma 1.