Efficient Approximation Schemes for Scheduling on a Stochastic Number of Machines

Here, we study both minimization problems and a maximization problem. All types of algorithms defined here are required to have polynomial running times (and our algorithms will in fact have strongly polynomial running times). For a minimization problem, an $ℛ$-approximation algorithm is an algorithm that always finds a solution that is feasible and has a cost at most $ℛ$ times the cost of an optimal solution. For a maximization problem, an $ℛ$-approximation algorithm is an algorithm that always finds a feasible solution of value at least $\frac{1}{ℛ}$ times the value of an optimal solution. The approximation ratio of a given algorithm is the infimum value of the parameter $ℛ$ such that this algorithm is an $ℛ$-approximation algorithm.

A PTAS is a class of approximation algorithms such that for any $\mathrm{\epsilon }>0$ the class has a $(1+\mathrm{\epsilon })$-approximation algorithm. An efficient polynomial time approximation scheme (EPTAS) is a stronger concept. This is a PTAS whose running time is of the form $h(\mathrm{\epsilon })\cdot poly(N)$ where $h$ is some (computable but not necessarily polynomial) function and $poly(N)$ is a polynomial function of the length $N$ of the (binary) encoding of the input. We will justify the assumption $m\le n$ later, and therefore the running time can be rewritten in this form when the polynomial is on $m$ and $n$. A fully polynomial time approximation scheme (FPTAS) is an even stronger concept, defined like an EPTAS, but the function $h$ must be a polynomial in $\frac{1}{\mathrm{\epsilon }}$. In this paper, we are interested in EPTAS’s.

A PTAS may have time complexity of the form $n^{g(\mathrm{\epsilon })}$, where $g$ can be any function of $\frac{1}{\mathrm{\epsilon }}$ and even a power tower function. However, an EPTAS cannot have such a running time, which makes it more efficient. The concept of an EPTAS is related to fixed parameter tractable (FPT) algorithms [16].

In this paper, we focus on finding EPTAS’s for the three objectives. We develop an EPTAS for the makespan minimization problem in Section 2. Then, in Section 3 we establish an EPTAS for the Santa Claus maximization problem Pr-SantaClaus. Last, in the full version of this work we modify our scheme for Pr-makespan in order to obtain an EPTAS for Pr-norm. Due to space limitations, some of the proofs of the first two results are given in the full version, and the last EPTAS for Pr-norm is presented in the full version as well. In the recent work [9], a PTAS was designed for Pr-makespan, and another PTAS was designed for Pr-SantaClaus. Those PTAS’s are of forms that do not allow a simple modification of the PTAS into an EPTAS, and in particular for Pr-SantaClaus a dynamic program over a state space whose size is exponential is used (a function of $\mathrm{\epsilon }$ appears in the exponent of the input size), and for both schemes enumeration steps of such sizes are applied.

For all objectives, we assume that $n>m$ holds. If $n\le m$, this means that every job can be assigned to its own bag. For each scenario, it is possible to apply an EPTAS for the corresponding problem (see for example [2], the details for previous work are discussed further below) and thereby get an EPTAS for the required problem.

The problems studied here generalize strongly NP-hard problems, and therefore one cannot expect to obtain an FPTAS (unless $P=NP$), and thus our results are the best possible. Specifically, the special case of each one of the three problems where the number of machines is known, i.e., the probability function has a single value $q_m$ that is equal to $1$, and other probabilities are equal to zero, is known to be NP-hard in the strong sense. The three objectives studied here are the three main objectives previously studied for scheduling on identical machines.

Stein and Zhong [33] introduced the scheduling problem with an unknown number of machines but in their model the number of machines is selected later by an adversary. The problem was mostly studied with respect to makespan minimization. In the deterministic variant [33], the goal is to assign a set of jobs with known properties to identical machines. However, only an upper bound $m$ on the number of machines is given. Jobs have to be partitioned into $m$ subsets, such that every subset will act as an inseparable bag. Then, the number of machines $k$ (where $2\le k\le m$) becomes known, and the schedule is created using the bags, without unpacking them, as in the problem that we study here, and after the number of machines is revealed, the bags are assigned to the machines, as in the problem that we study. Thus, this problem also has two steps or levels of computation, but the worst case out of all possible values of $k$ is analyzed, where the comparison for each value of $m$ is to an optimal offline solution for $k$ identical machines and arbitrary bags. It is not hard to see that a constant approximation ratio (of at most $2$) can be obtained using a round-robin approach even for jobs of arbitrary sizes (via pre-sorting). An improved upper bound of $\frac{5}{3}+\mathrm{\epsilon }$ was shown using a much more careful assignment to bags [33].

A variant where machines have speeds (similar to uniformly related machines) was defined and studied by [18] with respect to makespan. In that version, the number of machines $m$ is known, but not their speeds. The number of required bags is equal to the number of machines, but some machines may have speed zero, so the case of identical machines and the makespan objective is seen as binary speeds in this work. There are several input types of interest, which are arbitrary jobs, unit size jobs, sand (one large job that can be cut into any required parts), and pebbles (jobs that have arbitrary sizes, but they are relatively small) [18, 30]. Tight bounds were proved for the case of sand and makespan with and without speeds [33, 18], and for the Santa Claus objective without speeds [33]. All these values are strictly smaller than $1.6$. For sand, since any partition of the input jobs is allowed, linear programming can be used to find the best partition. In the case with speeds for arbitrary sizes of jobs the algorithm of [18] has an approximation ratio of at most $2-\frac{1}{m}$, while special cases allow smaller ratios [18, 30].

In [5], Balkanski et al. relate the problem of scheduling with an unknown number of machines and an unknown set of speeds to online algorithms with predictions. In online problems with predictions [31], the algorithm receives information on the input, where such information could have been computed via machine learning. This model takes into account both the situation where the input matches the prediction exactly and the case where it does not. It is required for the algorithm to have a relatively good performance for every input, but the performance has to be better if the input was predicted correctly. In many algorithms the performance improves as the input gets closer to the predicted input. The work of [5] provides results of this flavor.

Optimizing the worst scenario is pessimistic and does not allow one to take information learned from previous data into account, while the study of the expected value as in our stochastic problem allows us to prefer the typical scenarios in the bag assignment algorithm. See also [4, 8, 32, 17] for related work.

As we mentioned, the most relevant work to our work on the stochastic problem is [9], where two PTAS’s are provided. It is also mentioned in that work that FPTAS’s for the case where $m$ is seen as a constant can be designed using standard methods. The problem is called stochastic due to the probability distribution on scenarios. However, since this distribution is simply a convex combination of the costs for different scenarios, the methods are related to those often used for deterministic algorithms and worst case analysis. The convex combination complicates the problem and it requires carefully tailored methods for the algorithmic design. We follow the standard worst case studies of two-stage stochastic optimization problems, and we study the optimization problems of optimizing the expected value of the random variable.

All three objectives were studied initially for known numbers of identical machines, for which simple greedy approximation algorithms were presented first. Some time later PTAS’s were designed. Finally EPTAS’s were designed or it was observed that one of the known PTAS’s is an EPTAS or can be converted into an EPTAS, which is the best possible result for each one of the three cases unless $P=NP$. We provide additional details for each one of the objectives. The makespan objective was introduced by Graham [22, 23], where greedy algorithms were studied (see also [13, 20]). Twenty years later a PTAS was designed [25]. Hochbaum [24] mentions that one of the approaches of assigning large jobs of rounded sizes (namely, solving an integer linear program in fixed dimension) gives an EPTAS, and attributes this approach to D. Shmoys (see [26, 11] for recent results). The Santa Claus objective (where the name was introduced much later [7]) was studied with respect to greedy heuristics [21, 15, 14]. A PTAS which is actually an EPTAS was designed by Woeginger [34]. The ${\mathrm{\ell }}_{𝔭}$ norm objective function was studied with respect to greedy heuristics [10, 12, 29], and a PTAS and an EPTAS were designed [1]. The same authors generalized their results for other objectives that satisfy natural conditions [2]. The ${\mathrm{\ell }}_{𝔭}$ norm of a vector is seen as a more suitable measure of fairness of a schedule compared to bottleneck measures [3, 6], and therefore we study this objective additionally to those studied in [9].

We develop new techniques to address the uncertainty in the problems. We expect these techniques to be used in later work on approximating related variants.

We use rounding and discretization as in other work on scheduling, though we apply it not only on job sizes but also on bag sizes. The difficulty in relating new sizes to optimal solutions lies in the difference in objectives, since here the optimal value is not defined by a single schedule. However, we are still able to find such a relation using enumeration of sets of values, that is, via guessing. Since jobs are assigned to bags, we introduce configuration integer programs (IP’s) on collections of bags, which can be seen as a generalization of previously known approaches. Our configuration IP’s are based on the use of templates, where a template defines the contents of a bag, and configurations, where a configuration is an allocation of bags to one machine in a given scenario. We solve this IP using an algorithm for solving an IP in fixed dimension. All earlier steps of our schemes are highly motivated given the goal of creating such an IP and ensuring that it has a fixed dimension.

Machine numbers are split to intervals such that the most difficult interval for each guessed information is solved using an IP, while the others are solved using greedy approaches. The number of intervals for scenarios differs based on the specific problem.

While the sketched approach allows us to design an EPTAS for makespan minimization, the other objectives are harder to approximate. In order to tackle them, we develop an important tool called approximated histograms. Those are histograms of solution costs or values, and we use them in order to reduce the number of relevant scenarios to a constant. The condition for using the approximated histogram is a monotonicity assumption regarding the feasibility of solutions for different scenarios and the monotonicity of the costs for a given solution among scenarios in which it is feasible.

Our first step is to guess the value of opt within a multiplicative factor of $1+\mathrm{\epsilon }$. That is, we would like to enumerate a polynomial number of candidate values, where the enumerated set will contain (at least one) value that is in the interval $[\text{opt},(1+\mathrm{\epsilon })\cdot \text{opt})$. We will show that for a guess in this interval we indeed find a solution of cost $(1+\mathrm{\Theta }(\mathrm{\epsilon }))\cdot \text{opt}$. The next lemma shows that it is possible to enumerate such a set of candidate values since ${\log }_{1+\mathrm{\epsilon }}n\le \frac{n}{\mathrm{\epsilon }}$. Our algorithm performs this enumeration.

In what follows, with a slight abuse of notation, we let opt be the value of this guessed candidate value (which is not smaller than opt and it is larger by at most a factor of $1+\mathrm{\epsilon }$ if the guess is correct). We will show that if there is a feasible solution to Pr-makespan whose expected value of the cost is at most opt, then we will construct a feasible solution with expected value of the cost being at most $(1+\mathrm{\Theta }(\mathrm{\epsilon }))\cdot \text{opt}$. By the above lemma, this means that the problem admits an EPTAS as desired.

Now, we provide a method to gain structure on the set of feasible solutions that we need to consider for finding a near optimal solution. Given a feasible solution, the size of bag $i$ denoted as $P(i)$ is the total size of jobs assigned to this bag, that is, $P(i)={\sum }_{j:{\sigma }_1(j)=i}{p}_j$.

In what follows, we will increase the size of a bag to be the next value of the form $(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\cdot \text{opt}$ for a non-negative integer $r$ (except for empty bags for which the allowed size remains zero). Thus, we will not use precise sizes for bags but upper bounds on sizes, and we call them allowed sizes. We let $P^{\prime }(i)$ be this increased (allowed) size of bag $i$, that is, $P^{\prime }(i)={\min }_{r:(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\text{opt}\ge P(i)}(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\text{opt}$. Since for every subset of bags, the total allowed size of the bags in the set is at most $1+\mathrm{\epsilon }$ times the total size of the bags in the subset, we conclude that this rounding of the bag sizes will increase the cost of any solution by a multiplicative factor of at most $1+\mathrm{\epsilon }$ (and therefore the expected value also increases by at most this factor). Thus, in what follows, we will consider only bag sizes that belong to the set $B=\{(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\text{opt}:r=0,1,\mathrm{\dots },\frac{1}{{\mathrm{\epsilon }}^2}\}\cup \{0\}$. We use this set by Lemma 3. We conclude that the following holds.

Note that the allowed size of a bag may be slightly larger than the actual total size of jobs assigned to the bag. Later, the allowed size acts as an upper bound (without a lower bound), and we take the allowed size into account in the calculation of machine completion times in some cases (instead of the size).

We apply a similar rounding method for job sizes. Recall that by our guess, every job $j$ has size at most opt (see Lemma 1). Next, we apply the following modification to the jobs of sizes at most ${\mathrm{\epsilon }}^2\text{opt}$. Whenever there is a pair of jobs, each of which has size at most ${\mathrm{\epsilon }}^2\text{opt}$, we unite the two jobs (i.e., we delete the two jobs, adding a new job whose size is the sum of the two sizes of the two deleted jobs). This is equivalent to restricting our attention to solutions of the first stage where we add the constraint that the two (deleted) jobs must be assigned to a common bag. We repeat this process as long as there is such a pair. If there is an additional job of size at most ${\mathrm{\epsilon }}^2\text{opt}$, we delete it from the instance, and in the resulting solution (after applying the steps below on the resulting instance) we add the deleted job to bag $1$. This is done after the entire algorithm completes running, so it may increase the makespan of every scenario and therefore the expected value of the makespan, but we do not take it into account in the algorithm or in calculating allowed sizes of bags. This addition of the deleted job increases the makespan of every scenario by at most ${\mathrm{\epsilon }}^2\text{opt}$, so the resulting expected value of the makespan will be increased by a multiplicative factor of at most $1+{\mathrm{\epsilon }}^2$. We consider the instance without this possible deleted job, and we prove the following.

We next round up the size of every job $j$ to be the next value that is of the form ${(1+\mathrm{\epsilon })}^r\cdot \text{opt}$ for an integer $r$. The size of every job cannot decrease and it may increase by a multiplicative factor of at most $1+\mathrm{\epsilon }$. Job sizes are still larger ${\mathrm{\epsilon }}^2\cdot \text{opt}$ and the sizes do not exceed $(1+\mathrm{\epsilon })\cdot \text{opt}$. Thus, the number of different job sizes is $O({\log }_{1+\mathrm{\epsilon }}\frac{1+\mathrm{\epsilon }}{{\mathrm{\epsilon }}^2})\le \frac{2}{{\mathrm{\epsilon }}^3}-1$. We increase the allowed size of each non-empty bag by another multiplicative factor of $1+\mathrm{\epsilon }$, and round it up again to the next value of the form $\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2$. Thus, the expected value of the makespan of a feasible solution increases by a multiplicative factor of at most ${(1+\mathrm{\epsilon })}^2$, where one factor of $1+\mathrm{\epsilon }$ is due to the rounding of jobs, and the second one is due to bringing allowed sizes back to the form $\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2$. So by our guessing step, there is a feasible solution with expected value of the makespan of at most ${(1+\mathrm{\epsilon })}^3(1+2\mathrm{\epsilon })(1+3\mathrm{\epsilon })\text{opt}$ that uses only bags with allowed size in $B^{\prime \prime }=\{(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\text{opt}:r=0,1,\mathrm{\dots },\frac{1+2\mathrm{\epsilon }}{{\mathrm{\epsilon }}^2}+2\}\cup \{0\}$.

A bag is called tight if the set of jobs of this bag cannot use a bag of a smaller allowed size. Note that any solution where some bags are not tight can be converted into one where all bags are tight without increasing the cost. Note that the allowed size of a non-zero bag of allowed size $(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\text{opt}$ can be written in the form $(r+\frac{1}{\mathrm{\epsilon }})\cdot {\mathrm{\epsilon }}^2\cdot \text{opt}$, and since $\frac{1}{\mathrm{\epsilon }}$ is integral, the allowed size of each bag is an integer multiple of ${\mathrm{\epsilon }}^2\cdot \text{opt}$.

In our algorithm, we would like to focus on values of $k$ for which the structure of bags is crucial. Now, we will detect values of $k$ for which there always exists a good assignment of bags to machines (for reasonable sets of bags). Let $P$ be the total size of all jobs (after the transformation applied on jobs for a fixed value of opt). The total size (not the allowed size) of all bags is $P$, and we can compute the makespan based on the actual sizes of bags which are total sizes of jobs (after merging and rounding) assigned to the bags. The motivation is that for very small values of $k$ the maximum bag size is so small compared to $\frac{P}{k}$ that bags can be seen as very small jobs, and one can apply a greedy algorithm [22] for assigning the bags, and still obtain a solution with a small makespan (based on bag sizes).

We use the property that no bag has an allowed size above $2\cdot \text{opt}$. Our algorithm computes the maximum value of $k$ for which $2\text{opt}\le \mathrm{\epsilon }\cdot \frac{P}{k}$ holds, and afterwards it excludes values of $k$ for which $2\text{opt}\le \mathrm{\epsilon }\cdot \frac{P}{k}$ holds. We will have that the cost of the solution obtained for the scenario is at most $(1+\mathrm{\epsilon })\cdot \frac{P}{k}$, since bag sizes satisfy the condition for bags in the statement of Lemma 7, and therefore we can use the first part of this lemma. This is a valid approach as adding a scenario where $2\text{opt}\le \mathrm{\epsilon }\cdot \frac{P}{k}$ to the calculation of the approximation ratio will not increase the approximation ratio beyond the value $1+\mathrm{\epsilon }$, and the running time for computing a good solution for such a value of $k$ is polynomial in $m,n$. Thus, we assume that $2\text{opt}>\mathrm{\epsilon }\cdot \frac{P}{k}$ holds for every $k$.

We consider the remaining scenarios. In what follows, we consider the assignment of jobs to bags and the assignment of the bags to machines in each scenario $k$ subject to the condition that $2\text{opt}>\mathrm{\epsilon }\cdot \frac{P}{k}$ and the optimal makespan of the scenario is at most $(3/{\mathrm{\epsilon }}^2)\cdot \text{opt}$. In particular, it means that the number of bags of positive allowed sizes assigned to a machine in such a scenario is at most $3/{\mathrm{\epsilon }}^3$, since we consider allowed bag sizes not smaller than $\mathrm{\epsilon }\cdot \text{opt}$ (if we exclude bags of allowed size zero).

Our next guessing step is motivated by linear grouping of the ${\text{opt}}_k$ values. To illustrate this step, consider a histogram corresponding to the costs of a fixed optimal solution satisfying all above structural claims, where the width of the bar corresponding to scenario $k$ is $q_k$ and its height is the value of the makespan in this scenario (that is, ${\text{opt}}_k$). Observe that when $k$ is increased, the optimal makespan does not increase (without loss of generality, since the same assignment of bags can be used), so by plotting the bars in increasing order of $k$ we get a monotone non-decreasing histogram, where the total area of the bars is the expected value of the makespan of the optimal solution and the total width of all the bars is $1$ (since we assume that all scenarios are included in the histogram and every scenario $\kappa$ satisfies the condition $2\text{opt}>\mathrm{\epsilon }\cdot \frac{P}{\kappa }$ by scaling the probabilities of the remaining scenarios such that the total probability becomes $1$). We sort the indexes of scenarios with (strictly) positive probabilities ($q_k$ values) and we denote by $K$ the resulting sorted list. For every $k\in K$, we compute the total width of the bars with indexes at most $k$ (using the ordering in $K$, i.e., in increasing indexes), and denote this sum by $Q_k$. We also let $Q_k^{\prime }=Q_k-q_k$. Thus, $Q_k$ is the total probability of scenarios in $\{1,2,\mathrm{\dots },k\}$, and $Q_k^{\prime }$ is the total probability of scenarios in $\{1,2,\mathrm{\dots },k-1\}$. The set $K$ does not contain scenarios with probability zero, but if $q_{k-1},q_k>0$, it holds that $Q_{k-1}=Q_k^{\prime }$. According to the definitions, it holds that $Q_k-Q_k^{\prime }=q_k$ for $k\in K$, and the interval $[Q_k^{\prime },Q_k)$ on the horizontal axis corresponds to scenario $k$.

The idea of the next parts is to get an overestimator for the histogram by extending the value of $k$ to the right, and an underestimator by extending it to the left. The two areas below them will differ only by at most $O(\mathrm{\epsilon }\cdot \text{opt})$, so the overestimator can also differ from the original histogram area by at most this amount.

Next, we compute an upper bound histogram $W$ as follows. We start with selecting a sublist $K^{\prime }$ of $K$. The motivation is that schedules will be computed later only for scenarios in $K^{\prime }$, and they will be copied to scenarios of some of the larger indexes. The set $K^{\prime }$ acts as a representative set, and we show that it is possible to restrict ourselves to such a set. Since we increase upper bounds on the makespan for some scenarios, the feasibility is not harmed.

An index $k\in K$ belongs to $K^{\prime }$ if there exists an integer $\mathrm{\ell }$ such that . The motivation is that we would like to consider points which are integral multiples of ${\mathrm{\epsilon }}^3$ and the set $K^{\prime }$ contains all values of $k\in K$ for which such special values belong to the interval $[Q_k^{\prime },Q_k)$. Values of makespan will be increased such that the makespan function will still be piecewise linear, but it will have a smaller number of image values.

For every $k\in K^{\prime }$, the new upper bound histogram is defined as ${\text{opt}}_k$ for all points with horizontal value between $Q_k^{\prime }$ and up to $Q_{k^{\prime }}^{\prime }$ where $k^{\prime }>k$ is the index just after $k$ in the sublist $K^{\prime }$ or up to the last point where the histogram is defined ($Q_t$ for the maximum value $t\in K$) if $k$ is the largest element of $K^{\prime }$. Since the original histogram was monotone non-increasing, the new histogram is pointwise not smaller than the original histogram. The possible modification is in the interval $[Q_k,Q_{k^{\prime }}^{\prime })$ if $k$ is not the maximum value of $K^{\prime }$, and in this case there may be a change for $k+1,\mathrm{\dots },k^{\prime }-1$ (that is, if $k^{\prime }\ge k+2$). If $k$ is the largest element of $K^{\prime }$ but not of $K$, there may be a change for all $t\in K$ such that $t\ge k+1$. Thus, an upper bound on the total area below the histogram $W$ is not smaller than the expected value of the makespan of the optimal solution.

We use the modified histogram $W$ to obtain another bound. For that we see $W$ as a step function whose values are the corresponding points in the upper edge of the histogram. We define a new histogram by letting it be $W(x+{\mathrm{\epsilon }}^3)$ for all $x\in [0,1]$ (and zero for cases that $W$ is undefined due to an argument above $1$). In this way we delete a segment of length ${\mathrm{\epsilon }}^3$ from $W$ and we shift the resulting histogram to the left. Since the makespan for every scenario never exceeds $(3/{\mathrm{\epsilon }}^2)\cdot \text{opt}$, every point in $W$ has a height of at most $\frac{3\text{opt}}{{\mathrm{\epsilon }}^2}$ and we deleted a segment of width of ${\mathrm{\epsilon }}^3$, the total area that we delete is at most $3\mathrm{\epsilon }\text{opt}$. The resulting histogram is pointwise at most the original histogram (and thus also not larger than $W$). This property holds since every value ${\text{opt}}_k$ was extended to the right for an interval not longer than ${\mathrm{\epsilon }}^3$. Thus, if we consider $W$ instead of the original histogram, we increase the cost of the solution by a multiplicative factor not larger than $(1+3\mathrm{\epsilon })$.

The guessing step that we use is motivated by this function $W$. We let $W_k$ be the height of the histogram $W$ in the bar corresponding to the scenario $k$. The relevant values of $k$ are those in $K^{\prime }$, and the histogram $W$ only has values of the form ${\text{opt}}_k$ for $k\in K^{\prime }$. We guess the histogram $W$. This means to guess the optimal makespan of $O(\frac{1}{{\mathrm{\epsilon }}^3})$ scenarios, where makespans can be one of at most $\frac{3}{{\mathrm{\epsilon }}^4}$ different values. This holds since all allowed bag sizes are integer multiples of ${\mathrm{\epsilon }}^2\cdot \text{opt}$, so makespans are also integer multiples of ${\mathrm{\epsilon }}^2\cdot \text{opt}$, and the makespan of each scenario is at most $\frac{3\text{opt}}{{\mathrm{\epsilon }}^2}$. Thus, the number of possibilities of this guessing step is upper bounded by a function of $\frac{1}{\mathrm{\epsilon }}$ which is $O({(\frac{1}{\mathrm{\epsilon }})}^{O(1/{\mathrm{\epsilon }}^3)})$.

In what follows, we consider the iteration of the algorithm defined below when we use the value of the guess corresponding to the optimal solution. Algorithmically, we will try all possibilities, check the subset of those for which we can provide a feasible solution, and output the best feasible solution obtained in this exhaustive enumeration. The running time of the next algorithm is multiplied by the number of possibilities.

A template of a bag is a multiset of job sizes assigned to a common bag. We consider only multisets for which the total size of jobs is at most $(1+6\mathrm{\epsilon })\cdot \text{opt}$ since the largest allowed size of any bag is smaller. Since the number of distinct job sizes (in the rounded instance) is upper bounded by $\frac{2}{{\mathrm{\epsilon }}^3}-1$ and there are at most $\frac{2}{{\mathrm{\epsilon }}^2}$ jobs assigned to a common bag (since the rounded size of each job is above ${\mathrm{\epsilon }}^2\cdot \text{opt}$), we conclude that the number of templates is at most ${(\frac{2}{{\mathrm{\epsilon }}^3})}^{(2/{\mathrm{\epsilon }}^2)}$, which is a constant depending only on $\frac{1}{\mathrm{\epsilon }}$. The reason is that each bag has $\frac{2}{{\mathrm{\epsilon }}^2}$ slots for jobs, such that each one may be empty or contain a job of one of the sizes. This calculation proves an upper bound on the number of possible templates, and we use a single template for every multiset of job sizes even when one multiset can be found in more than one way in the last calculation.

We are going to have a non-negative counter decision variable $y_t$ for every template $t$, where this variable stands for the number of bags with template $t$. Let $\tau$ be the set of templates, and assume that a template is represented by a vector. The length of such a vector is the number of different (rounded) job sizes, and for every index $\mathrm{\ell }$, the $\mathrm{\ell }$-th component of the vector of the template (denoted by $t_{\mathrm{\ell }}$) is the number of jobs with size equal to the $\mathrm{\ell }$-th job size that are packed into a bag with this template. In order for such an assignment of the first stage to be feasible, we have the following constraints where $n_{\mathrm{\ell }}$ denotes the number of jobs in the rounded instance whose size is the $\mathrm{\ell }$-th job size of the (rounded) instance.

The first constraint states that the number of bags is at most $m$. If this number is strictly smaller than $m$, then the remaining bags have allowed sizes of zero and they will not contain jobs. The second constraint, which is a family of constraints, states that the correct numbers of jobs of each size are assigned to templates, according to the number of copies of each template. Observe that the number of constraints in this family of constraints is a constant depending on $\mathrm{\epsilon }$ (it is at most $\frac{2}{{\mathrm{\epsilon }}^3}$), and all coefficients in the constraint matrix are (non-negative) integers not larger than $\frac{2}{{\mathrm{\epsilon }}^2}$.

We augment $K^{\prime }$ with the minimum index in $K$ if this index does not already belong to $K^{\prime }$, in order to satisfy the condition that for every index of $K$ there is some index of $K^{\prime }$ that is not larger. Consider a scenario $\kappa \in K^{\prime }$ (satisfying the condition that $2\text{opt}>\mathrm{\epsilon }\cdot \frac{P}{\kappa }$), and the optimal makespan of scenario $\kappa$, which is at most $\frac{3\text{opt}}{{\mathrm{\epsilon }}^2}$. Recall that in scenario $\kappa$ the number of non-empty bags assigned to each machine is at most $\frac{3}{{\mathrm{\epsilon }}^3}$. Define a configuration of a machine in scenario $\kappa$ to be a multiset of templates such that the multiset has at most $\frac{3}{{\mathrm{\epsilon }}^3}$ templates (counting multiple copies of templates according to their multiplicities) and the total size of the templates encoded in the multiset is at most $W_{\kappa }$, which is the guess of a value of the histogram $W$. The number of configurations is at most ${({(\frac{2}{{\mathrm{\epsilon }}^3})}^{(2/{\mathrm{\epsilon }}^2)})}^{\frac{3}{{\mathrm{\epsilon }}^3}}$, and this is also an upper bound on the number of suitable configurations (whose total allowed size of bags does not exceed $W_{\kappa }$). Since our mathematical program will not limit the makespan of any scenario, we use an upper bound for it by not allowing configurations whose total allowed sizes exceed the planned makespan for the scenario. We let $C^{(\kappa )}$ denote the set of configurations for scenario $\kappa$, where $c\in C^{(\kappa )}$ is a vector of $|\tau |$ components where component $c_t$ for $t\in \tau$ is the number of copies of template $t$ assigned to configuration $c$. Components are non-negative integers not larger than $\frac{3}{{\mathrm{\epsilon }}^3}$. For scenario $\kappa \in K^{\prime }$, we will have a family of non-negative decision variables $x_{c,\kappa }$ (for all $c\in C^{(\kappa )}$) counting the number of machines with this configuration.

For each such scenario $\kappa$, we have a set of constraints each of which involves only the template counters (acting as a family of global decision variables) and the family of the $\kappa$-th local family of decision variables, namely the ones corresponding to this scenario. The family of constraints for the scenario $\kappa \in K^{\prime }$ are as follows.

Observe that the number of constraints in such a family of constraints is upper bounded by a constant depending only on $\mathrm{\epsilon }$ (which is the number of possible templates plus $1$) and the coefficients in the constraint matrix are again all integers of absolute value at most a constant depending only on $\mathrm{\epsilon }$ (at most $\frac{3}{{\mathrm{\epsilon }}^3}$.).

All decision variables are forced to be non-negative integers and we would like to solve the feasibility integer program defined above (with all constraints and decision variables). The right hand side vector consists of integers that are at most $n$ (using $m\le n$). Such an integer linear program is a two-stage stochastic IP. Using the property that the number of scenarios in $K^{\prime }$ is upper bounded by a function of $\frac{1}{\mathrm{\epsilon }}$, we conclude that the integer linear program has a fixed dimension. Thus, we use Lenstra’s algorithm to solve it instead of an algorithm for two-stage stochastic IP.

We obtain a feasible solution $(x,y)$ if such a solution exists. Based on such a feasible solution, we assign jobs to bags using the $y$ variables. That is, for every $t\in \tau$, we schedule $y_t$ bags using template $t$. By the constraint ${\sum }_{t\in \tau }{y}_t\le m$ there are at most $m$ bags, and the other bags will be empty. Next, for every bag and every size $p$ of jobs in the rounded instance, if the template assigned to the bag has $\alpha$ jobs of this size, we will assign $\alpha$ jobs of this size to this bag. Doing this for all sizes and all bags is possible by the constraints ${\sum }_{t\in \tau }{t}_{\mathrm{\ell }}\cdot y_t=n_{\mathrm{\ell }},\forall \mathrm{\ell }$, and these constraints ensure that all jobs are assigned to bags. Note that the modification for jobs consisted of merging small jobs. When such a merged job is assigned, this means that a subset of jobs is assigned. Reverting jobs to their original sizes does not increase any of the costs, since no rounding steps decreased any sizes. Next consider the assignment of bags to machines in each scenario. Consider a scenario ${\kappa }^{\prime }\in K$, and let $\kappa$ be the largest index in $K^{\prime }$ such that $\kappa \le {\kappa }^{\prime }$. Assign $x_{c,\kappa }$ machines to configuration $c$ (for all $c\in C^{(\kappa )}$). It is possible by the constraint ${\sum }_{c\in C^{(\kappa )}}{x}_{c,\kappa }=\kappa \le {\kappa }^{\prime }$. If a configuration $c$ assigned to machine $i$ is supposed to pack $c_t$ copies of template $t$, we pick a subset of $c_t$ bags whose assigned template is $t$ and assign these bags to machine $i$. We do this for all templates and all machines. In this way we assign all bags by the constraints ${\sum }_{c\in C^{(\kappa )}}{c}_t\cdot x_{c,\kappa }-y_t=0,\forall t\in \tau$. If ${\kappa }^{\prime }>\kappa$, at least one machine will not receive any configuration and therefore it will not receive any bags or jobs, and we refer to such a machine as empty. Since the configurations we used in scenario $\kappa$ have a total size of jobs of at most $W_{\kappa }$, we conclude the following.

Our scheme is established by noting that an optimal solution satisfying the assumptions of the guessed information provides us a multiset of templates all of which are considered in $\tau$ and a multiset of configurations (and all of them have total size of templates not larger than $W$) for which the corresponding counters satisfy the constraints of the integer program. Thus, we conclude our first main result.

We consider an optimal solution opt, and analyze the information that one can guess in order to be able to approximate it. We assume without loss of generality that ${\text{opt}}_k\le {\text{opt}}_{k^{\prime }}$ for all $k>k^{\prime }$, since a solution for scenario $k$ can be used for scenario $k^{\prime }$ (by assigning the bags of $k-k^{\prime }$ machines in an arbitrary way). Recall that we can assume that for every value of $k$ in the support of $q$ the instance has at least $k$ non-zero sized jobs, since we assume $n>m$. We will use the next lemma for our proof.

We would like to split the sequence of scenarios into four parts (where some of the parts may be empty). The suffix (with the largest numbers of machines) will contain scenarios for which the assignment of bags is unimportant since the gain from them in the objective function value opt is small either because the probability is zero or because the number of machines is large. This suffix may be empty. There will also be a prefix (which could be empty) of machines for which the specific assignment to bags is unimportant because the number of machines is small and any reasonable assignment into bags allows a good schedule. For this prefix we will use different arguments from the ones we used for Pr-makespan. For the remaining scenarios, the prefix will consist of scenarios for which the gain is also small, and a suffix of the most important scenarios.

The first step is to guess the maximum scenario $k_{\max }$ for which ${\text{opt}}_{k_{\max }}\ge \mathrm{\epsilon }\cdot \text{opt}$ holds, out of scenarios with strictly positive probabilities, that is, such that $q_{k_{\max }}>0$ holds. This index is well-defined since there exists an index $k$ for which $q_k>0$ and ${\text{opt}}_k\ge \text{opt}$. There are at most $m$ possible values for this guess. While opt still denotes an optimal solution, we do not guess or use its value as a part of the algorithm. Let $LB$ be equal to ${\text{opt}}_{k_{\max }}$ rounded down to the next integer power of $1+\mathrm{\epsilon }$. For a fixed job $j^{k_{\max }}$ (see Lemma 10), the number of possible values for $LB$ is $O(\frac{n}{\mathrm{\epsilon }})$. Since the index $j^{k_{\max }}$ is also not known, the number of possible values for $LB$ is $O(\frac{n^2}{\mathrm{\epsilon }})$.

The proof of the next lemma is obtained by selecting a set of consecutive scenarios minimizing the total weighted profit out of $\frac{1}{\mathrm{\epsilon }}$ disjoint sequences of scenarios of similar forms. The proof of the lemma requires the knowledge not only of opt but of all values of the form ${\text{opt}}_i$. However, we use the lemma to obtain the information that given the correct value $LB$ (this is a rounded value, so we will be able to guess it), there is a pair of values $k,k^{\prime }$ and a value $\rho$ that specify the only properties of opt that we use for our algorithm.

In this step we guess several additional values. As mentioned above, we guess the value of $LB$ (which is a power of $1+\mathrm{\epsilon }$ and it is equal to ${\text{opt}}_{k_{\max }}$ within a multiplicative factor of $1+\mathrm{\epsilon }$ since ${\text{opt}}_{k_{\max }}\in [LB,LB\cdot (1+\mathrm{\epsilon }))$), the value of $\rho$ (by guessing $r^{\prime }$ from the proof of Lemma 11, that is, we guess the power of $\frac{1}{\mathrm{\epsilon }}$), and two indexes . That is, we would like to enumerate a set of polynomial number of candidate values of four components vectors that contains at least one vector with first component value that is $LB$, with a second component whose value is $\rho$, and the two indexes in the third and fourth components of that vector. The next lemma shows that it is possible to enumerate such a set of candidate values. Our algorithm performs this enumeration.

In what follows, we let $LB$ be the first component value of the guessed information, $\rho$ be the second component value of the guessed information, and $k,k^{\prime }$ be the two guessed scenarios (where it is possible that $k^{\prime }=0$ is not an actual scenario). We will show that if there is a feasible solution to Pr-SantaClaus for which the guessed information describes the solution and its expected value of the objective is opt, then we will construct a feasible solution with expected value of the objective being at least $(1-\mathrm{\Theta }(\mathrm{\epsilon }))\cdot \text{opt}$. This means that the problem admits an EPTAS as desired.

We let $UB=LB\cdot \rho$. Furthermore, for every scenario $\kappa$ with , we set $q_{\kappa }=0$. From now on we drop the assumption that the sum of all $q$ values is $1$ and instead of that we use the assumption that these are non-negative numbers with sum at most $1$. This modification of the vector ($q$) decreases the expected value of the Santa Claus value of the optimal solution by at most $\mathrm{\epsilon }\cdot \text{opt}$ (and it does not increase the objective function value of any feasible solution to our problem). The justification for this is as follows. From Lemma 11 it follows that there is a quadruple of integers $k,k^{\prime },\rho ,{\log }_{1+\mathrm{\epsilon }}LB$ (where each integer belongs to the set that we test for this integer) for which there is a solution of profit at least $\frac{\text{opt}}{1+\mathrm{\epsilon }}-\mathrm{\epsilon }\cdot \text{opt}\ge {(1-\mathrm{\epsilon })}^3\cdot \text{opt}$ with the first two properties stated in the lemma, and for every scenario $\kappa$ such that the profit is at least zero.

Next, we use the above guessing step in order to partition the input into two independent inputs. First, a job $j\in 𝒥$ is called huge if its size is strictly larger than $UB$, that is, if $p_j>UB$ (and otherwise it is non-huge).

We pack every huge job into its own bag and we let $h$ denote the number of huge jobs (where we will show that $h\le m-1$ holds). Every huge job can cover one machine in every scenario $\kappa \ge k$ regardless of its exact size (because for all these scenarios we consider solutions for which ${\text{opt}}_{\kappa }$ is not larger than $\rho \cdot LB=UB$). On the other hand, the non-huge jobs (i.e., jobs of sizes at most $UB$) will be packed into bags of size at most $3\cdot UB$. The packing of the non-huge jobs into bags will be optimized according to the scenarios of indexes at least $k$ (and at most $k_{\max }$), and we will ignore the scenarios of indexes smaller than $k$ when we pack the non-huge jobs into bags. The resulting bags of the non-huge jobs together with the set of the huge jobs (which are bags consisting of a single job) will be packed into $\kappa \le k^{\prime }$ machines (in the corresponding scenario $\kappa$) based on existing EPTAS for the Santa Claus problem on identical machines (seeing bags as jobs). We will show that if indeed we use bags of sizes at most $3\cdot UB$ when we pack the non-huge jobs into bags, then the scenarios of indexes at most $k^{\prime }$ can be ignored. We show that this holds for any collection of bags of this form, that is, where every huge job has its own bag and other bags have total sizes of jobs not exceeding $3\cdot UB$. Thus, even though the bags are defined based on scenarios where the number of machines is at least $k$, still the scenarios with at most $k^{\prime }$ machines have good solutions. We will also show that it is possible to restrict ourselves to these types of collections of bags.

Consider an optimal solution for $\kappa$ machines and the original jobs. We show that this schedule can be modified into a schedule of the bags, such that the profit of the schedule is smaller by a factor not exceeding $1-3\mathrm{\epsilon }$. Thus, an optimal schedule of the bags is not worse, and by using an EPTAS the profit may decrease by another factor of $1-\mathrm{\epsilon }$. The adaptation of the schedule is as follows. The huge jobs are assigned as before, since each of them has its own bag. All non-huge jobs are removed, and each machine receives bags until it is not possible to add another bag without exceeding the previous load or no unassigned bags remain. Given the property that the total size of bags is equal to the total size of jobs, it is either the case that the loads are equal to previous loads (in which case the value is unchanged) or there is at least one unassigned bag. In the latter case, no machine load decreased by more than an additive term of $3\cdot UB$, and therefore the value is at least the previous one minus $3\cdot UB$. To complete the assignment, all remaining bags are assigned arbitrarily. Since ${\text{opt}}_{\kappa }\ge \frac{\rho \cdot LB}{\mathrm{\epsilon }}=\frac{UB}{\mathrm{\epsilon }}$ and the resulting value is at least ${\text{opt}}_{\kappa }-3\cdot UB$, we find by $3\cdot UB\le 3\mathrm{\epsilon }\cdot {\text{opt}}_{\kappa }$ that ${\text{opt}}_{\kappa }-3\cdot UB\ge (1-3\mathrm{\epsilon })\cdot {\text{opt}}_{\kappa }$. $◀$

The number of partitions into bags is finite for fixed $m,n$ (it does not exceed $m^n$). Consider the set of partitions for which a solution of profit at least ${\text{opt}}_{\kappa }$ can be obtained for any $\kappa \in [k,k_{\max }]$. There is at least one such partition for the correct guess. For every partition it is possible to define a vector of $m$ components, such that total sizes of bags appear in a non-increasing order. Consider the partition among the considered partitions for which the number of huge jobs that have their own bags is maximum, and out such partitions, one where the vector is lexicographically minimal. We claim that this partition satisfies the requirements.

Assume by contradiction that the number of huge jobs that do not have their own bags is not $h$. Consider a bag with a huge job that contains at least one additional job. This will be named the first bag. Consider a bag whose total size is at most $UB$, which must exist due to Lemma 13. This last bag does not have a huge job since the size of a huge job is above $UB$, and we call it the second bag. Move all contents of the first bag into the second bag excluding one huge job. For any $\kappa \in [k,k_{\max }]$, since ${\text{opt}}_{\kappa }\le UB$, the assignment of bags to machines does not reduce the objective function value below ${\text{opt}}_{\kappa }$. This holds because there is at most one machine whose total size was reduced (for every $\kappa \in [k,k_{\max }]$), but if such a machine exists, it still has a huge job whose size is above $UB$. Thus, the new partition is also one of the considered partitions. The new partition has a larger number of huge jobs assigned into their own bags, because the second bag was not such a bag and the first bag became such a bag. This contradicts the choice of assignment to bags. Thus, the partition into bags consists of $h$ bags with huge jobs and $m-h\ge 1$ bags with non-huge jobs.

Next, consider only the components of the vector which do not correspond to bags of huge jobs. This vector is also minimal lexicographically out of vectors for partitions of the non-huge jobs into $m-h$ bags. Assume by contradiction that the first component is above $2\cdot UB$. Consider the bag of the first component (called the first bag now) and a bag with a total size at most $UB$ (called the second bag now). Move one job from the first bag to the second bag. The second bag now has a total size of at most $2\cdot UB$ (since a non-huge job was moved). The first bag now has a smaller total size, but still larger than $UB$. The sorted vector is now smaller lexicographically, and it is still possible to obtain a solution of profit at least ${\text{opt}}_{\kappa }$ for any $\kappa \in [k,k_{\max }]$, similarly to the proof given here for huge jobs, which is a contradiction. $◀$

In summary, we can focus on the scenarios interval $[k,k_{\max }]$, assume that huge jobs have their own bags, and remaining bags have total sizes not exceeding $2\cdot UB$.

Motivated by the last partitioning of the original input into four parts, and the fact that only scenarios with indexes at least $k$ and at most $k_{\max }$ need to be considered, we apply the following transformation. First, for every we let $q_{\kappa }=0$, in the sense we can augment every solution to the remaining instance (with only a subset of scenarios) into an EPTAS for the original instance before this change to $q$. Furthermore, for every $\kappa >k_{\max }$ we let $q_{\kappa }=0$ in the sense we can ignore the profit of such scenarios. Then, every huge job is packed into a separate bag. Such a bag suffices to cover one machine in every remaining scenario. Therefore, our second step in the transformation is the following one. We delete the huge jobs from $𝒥$, we decrease the index of each remaining scenario by $h$ (in particular the new indexes in the support of $q$ will be in the interval $[k-h,k_{\max }-h]$), and we enforce the condition that every bag size is at most $2\cdot UB$.

As one can see, the transformations here are more complicated compared to those used in the previous section, and they have to be carefully designed and analyzed. However, now we are ready to apply methods that resemble the previous section. Using the fact that for every remaining scenario we have that ${\text{opt}}_{\kappa }$ is between $LB$ and $UB$, and the fact that $\frac{UB}{LB}=\rho \le {(\frac{1}{\mathrm{\epsilon }})}^{1/\mathrm{\epsilon }+1}$ we are able to apply the methods we have developed for the makespan minimization problem to obtain an EPTAS for Pr-SantaClaus, as we do next.

We next provide a method to gain structure on the set of feasible solutions that we need to consider for finding a near optimal solution. Given a feasible solution, the size of bag $i$ denoted as $P(i)$ is the total size of jobs assigned to this bag, that is, $P(i)={\sum }_{j:{\sigma }_1(j)=i}{p}_j$.

In what follows, we will decrease the size of a bag to be the next value of the form $(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\cdot LB$ for an integer $r\ge 0$ (except for empty bags for which the allowed size remains zero). Thus, we will not use precise sizes for bags but lower bounds on sizes, and we call them “allowed sizes” in what follows. For bags of allowed size zero the meaning remains that such a bag is empty. We let $P^{\prime }(i)$ be this decreased (allowed) size of bag $i$, that is, $P^{\prime }(i)={\max }_{r:(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\cdot LB\le P(i)}(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\cdot LB$. The allowed size is not smaller than $\mathrm{\epsilon }\cdot LB$ and it is smaller than the size by an additive term of at most ${\mathrm{\epsilon }}^2\cdot LB$. Thus, for every subset of bags, the total allowed size of the bags in the set is at least $\frac{1}{1+\mathrm{\epsilon }}$ times the total size of the bags in the subset, we conclude that this rounding of the bag sizes will decrease the value of any solution by a multiplicative factor of at most $1+\mathrm{\epsilon }$ (and therefore the expected value also decreases by at most this factor), and it will not increase the value of a solution for any scenario. Thus, in what follows, we will consider only bag sizes that belong to the set $B=\{(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\cdot LB:r\in \mathbb{Z},r\ge 0,(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\cdot LB\le 2.5\cdot UB\}\cup \{0\}$. We use this set by Lemma 16. We conclude that the following holds.

Note that the allowed size of a bag may be slightly smaller than the actual total size of jobs assigned to the bag. Later, the allowed size acts as a lower bound (without an upper bound), and we sometimes take the allowed size into account in the calculation of machine completion times.

We apply a similar rounding method for job sizes. Recall that by our transformation, every job $j$ has size at most $UB$ (since huge jobs were removed from the input). Next, we apply the following modification to the jobs of sizes at most ${\mathrm{\epsilon }}^2\cdot LB$. While there is a pair of jobs of sizes at most ${\mathrm{\epsilon }}^2\cdot LB$, we unite such a pair of jobs. If there is an additional job of size at most ${\mathrm{\epsilon }}^2\cdot LB$, we delete it from the instance, and in the resulting solution (after applying the algorithm below on the resulting instance) we add the deleted job to an arbitrary bag. This deletion of the deleted job decreases the Santa Claus value of every scenario by at most ${\mathrm{\epsilon }}^2\cdot LB$, so the resulting expected value of the Santa Claus value will be decreased by at most ${\mathrm{\epsilon }}^2\cdot LB$. Adding the job back does not decrease the value. We consider the instance without this possibly deleted job, and we prove the following.

Next, we round down the size of every job $j$ to be the next value that is of the form ${(1+\mathrm{\epsilon })}^r$ for an integer $r$. The size of every job cannot increase and it may decrease by a multiplicative factor of at most $1+\mathrm{\epsilon }$. Job sizes are still larger than ${\mathrm{\epsilon }}^3\cdot LB$ and not larger than $UB\le {(\frac{1}{\mathrm{\epsilon }})}^{1/\mathrm{\epsilon }+1}\cdot LB$. Thus, the number of different job sizes is $O({\log }_{1+\mathrm{\epsilon }}{(\frac{1}{\mathrm{\epsilon }})}^{1/\mathrm{\epsilon }+4})\le \frac{2}{{\mathrm{\epsilon }}^3}-1$. We decrease the allowed size of each bag by another multiplicative factor of $1+\mathrm{\epsilon }$. Bags sizes are rounded down again to the next value of the form $\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2$, and since the smallest allowed size was $(\mathrm{\epsilon }-2{\mathrm{\epsilon }}^2)\cdot LB$ and $\frac{\mathrm{\epsilon }-2{\mathrm{\epsilon }}^2}{1+\mathrm{\epsilon }}\ge \mathrm{\epsilon }-3{\mathrm{\epsilon }}^2$, the allowed bag sizes become $B^{\prime \prime }=\{(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\cdot LB:r\in \mathbb{Z},r\ge -3,(\mathrm{\epsilon }+r{\mathrm{\epsilon }}^2)\cdot LB\le 3\cdot UB\}\cup \{0\}$, and the expected value of the Santa Claus value of a feasible solution decreases by a multiplicative factor of at most $\frac{1-2\mathrm{\epsilon }}{1-3\mathrm{\epsilon }}$. By our guessing step and our transformation, there is a feasible solution with expected value of the Santa Claus value of at least $(1-\mathrm{\epsilon }){(1-3\mathrm{\epsilon })}^2\cdot \text{opt}$.

A bag is called tight if the set of jobs of this bag cannot use a bag of a larger allowed size. Note that any solution where some bags are not tight can be converted into one where all bags are tight without decreasing the expected value of the objective.

Our next step is to guess an approximated histogram of the optimal Santa Claus value in all scenarios. This step and the next step of formulating a template-configuration integer program of fixed dimension are similar to the ones we have established for Pr-makespan. Using these additional steps we manage to prove our second main result.