New Bounds for Truthful Scheduling on Two Unrelated Selfish Machines

According to the definition in Section 1, randomized MIS algorithms are monotone, task-independent and scale-free (MIS) with probability one. Therefore, by fixing the random bits of a randomized MIS algorithm, we obtain a deterministic MIS algorithm with probability one. We provide next a formal description of deterministic MIS algorithms.

A task allocation algorithm is monotone if for every two processing time matrices T and T^′ which differ only on machine i, \(\ {\sum }_{j=1}^{n} (X^{\mathcal {A},T}_{ij}-X^{\mathcal {A},T^{\prime }}_{ij})(T_{ij}-T^{\prime }_{ij}) \le 0\) (see [4]). That is, the load of a machine increases as long as the processing times on this machine decrease. An algorithm is task-independent if the allocation of a task depends only on its processing times. To be precise, for any two time matrices T and T^′ such that \(T_{ij} =T^{\prime }_{ij}\) for task j and all i ∈ [m], the allocation of task j is identical, i.e., \(X^{\mathcal {A},T}_{ij} = X^{\mathcal {A},T^{\prime }}_{ij}, \text { for all } i \in [m]\). An algorithm is scale-free if the multiplication of all processing times by the same positive number does not change the allocation. That is, for any \(T \in \mathbb {R}^{m\times n}_{++}\) and λ > 0, the output of the algorithm on the inputs T and λT is identical.

Deterministic MIS algorithms for m = 2 have been characterized by Lu [17]:

Let \(\mathcal {C}\) be the class of (randomized) algorithms which randomly assign a threshold z_j and a condition T_1j < z_jT_2j or T_1j ≤ z_jT_2j to each task j and then proceed as given in Theorem 1 for the deterministic case. With probability one a randomized MIS algorithm is a MIS algorithm, and therefore of the form given by Theorem 1. Hence, to find the best approximation ratio, it is enough to consider only algorithms in \(\mathcal {C}\). Next, we show that to find the best approximation ratio, we can restrict ourselves to a subclass of \(\mathcal {C}\).

Let \(\mathcal {P}_{n}\) be the family of Borel probability measures supported on the positive orthant, i.e. \(\text {supp}(\mathbb {P}) \subseteq \mathbb {R}_{++}^{n}\) for all \(\mathbb {P} \in \mathcal {P}_{n}\), where \(\text {supp}(\mathbb {P})\) is the support of \(\mathbb {P}\). We use \(\mathbf {E}_{\mathbb {P}}[\ ]\) and \(\mathbf {P}_{\mathbb {P}}[ \ ]\) to denote the expectation and the probability over the measure \(\mathbb {P}\), respectively. In the sequel we use the notions of a probability measure and the corresponding probability distribution interchangeably. For a \( \mathbb {P} \in \mathcal {P}_{n}\) we define algorithm \(\mathcal {A}^{\mathbb {P}}\) as follows:

Denote the family of all algorithms of the form above by \(\mathcal {A}^{\mathcal {P}_{n}}\): Consider a measure \(\mathbb {P} \in \mathcal {P}_{n}\) and the corresponding algorithm \(\mathcal {A}^{\mathbb {P}} \in \mathcal {A}^{\mathcal {P}_{n}}\). Let \(X^{\mathbb {P},T}\in \{0,1\}^{2 \times n}\) be the randomized allocation produced by \(\mathcal {A}^{\mathbb {P}}\) on time matrix T. The expected makespan of \(\mathcal {A}^{\mathbb {P}}\) on T is

Recall that M^∗(T), defined in (2), denotes the optimal makespan for T. Let \(R_{n}(\mathbb {P}, T)\) be the expected approximation ratio of \(\mathcal {A}^{\mathbb {P}}\) on T and \(R_{n}(\mathbb {P})\) be the worst-case approximation ratio:

It could happen that for some \(\mathbb {P}\) the ratio \( R_{n}(\mathbb {P},T)\) is unbounded in T. We do not consider these cases as we know that R_n ≤ 1.5861 (see Section 2.2). For ease of presentation, we work on \(\overline {\mathbb {R}}_{+}=\mathbb {R}_{+} \cup \{\infty \}\) so that the supremum \(\sup _{T \in \mathbb {R}_{++}^{2\times n}} \ R_{n}(\mathbb {P}, T)\) is always defined.

When a tie \(\frac {T_{1j}}{T_{2j}} = z_{j}\) occurs for some j ∈ [n], algorithms from the family \(\mathcal {A}^{\mathcal {P}_{n}}\) send task j to the second machine. In general, an algorithm in \(\mathcal {C}\) could send the task to the first or the second machine. Next, we show that this behavior at the ties does not affect the worst-case performance:

Theorem 2 is proven in Section 7.1 and has the following implication:

By Corollary 1, the best approximation ratio over all randomized MIS algorithms is

Later in the paper we show that \(R_{n}(\mathbb {P})\) is invariant under permutations of the tasks for every \(\mathbb {P}\in \mathcal {P}_{n}\) (see Theorem 3). Therefore, to compute R_n using (7), we can restrict the optimization to the distributions \(\mathbb {P}\in \mathcal {P}_{n}\) invariant under permutations of the random variables corresponding to the thresholds (z₁,…,z_n) (see Theorem 4). For such distributions, \(R_{n}(\mathbb {P})\) is determined by the worst-case performance of \(\mathcal {A}^{\mathbb {P}}\) on each pair of the tasks. See Section 3.2, and Proposition 2 in particular, for more detail. This means that for every \(T\in \mathbb {R}^{2\times n}_{++}\), one can find the expected approximation ratio of \(\mathcal {A}^{\mathbb {P}}\) by applying to all pairs of tasks the algorithm \(\mathcal {A}^{\mathbb {P}_{2}}\), where \(\mathbb {P}_{2}\) is the bivariate marginal distribution of \(\mathbb {P}\) (by invariance, this distribution is the same for all pairs of thresholds). We use this property of family \(\mathcal {A}^{\mathcal {P}_{n}}\) to construct problem (13) for R_n, which is one of the main results of this paper.

The best approximation ratio for all monotone task allocation algorithms is unknown. For deterministic algorithms with n tasks and m machines, when n and m tend to infinity, the ratio lies in the interval [1 + ϕ, m], where ϕ is the golden ratio. The upper bound is due to Nisan and Ronen [23], and the lower bound is due to Koutsoupias and Vidali [14]. To compute this lower bound, the authors use a matrix of processing times where the numbers of rows and columns tend to infinity. If n or m is finite, the lower bound may be different. Koutsoupias and Vidali [14] present bounds for several finite time matrices as well. For randomized algorithms, the best approximation ratio lies in the interval \([2- \frac {1}{m}, \ 0.83685m]\). The lower bound is due to Mu’alem and Schapira [21] who use Yao’s minimax principle (for some details on this principle see, e.g., Motwani and Raghavan [20]). The upper bound is due to Lu and Yu [18]. The gap between the bounds grows with m, and the case with the smallest number of machines, m = 2, has gained much attention in the literature.

For m = 2, Nisan and Ronen [23] have shown that the best approximation ratio of deterministic monotone algorithms is equal to 2, for any finite n. The ratio for randomized monotone algorithms lies in the interval [1.5,1.5861]. Chen et al. [3] compute the upper bound using an algorithm from the family \(\mathcal {A}^{\mathcal {P}_{n}}\) with independently distributed thresholds. The lower bound is the earlier mentioned bound by Mu’alem and Schapira [21]. There exist tighter lower bounds for certain cases. Lu [17] shows that algorithms from the family \(\mathcal {A}^{\mathcal {P}_{n}}\) (and thus, by Corollary 1, all randomized MIS algorithms) cannot achieve a ratio better than \(\frac {25}{16}\) (= 1.5625) for sufficiently large n. Chen et al. [3] prove that an algorithm \(\mathcal {A}^{\mathbb {P}}\) cannot do better than 1.5852 when \(\mathbb {P}\) is a product measure, i.e., when the thresholds are independent random variables.

The cases with m = 2 and small n > 2 are not well studied. Chen et al. [3] theoretically establish the upper bound 1.5861 for any finite n. They also present numerical computations of upper bounds smaller than 1.5861 for some n. Finding these smaller bounds requires solving non-convex optimization problems. However, the numerical method used by Chen et al. [3] does not guarantee global optimality.

The case with m = 2 and n = 2 is the simplest one, but even for this case the best approximation ratio is unknown. The ratio for algorithms from the family \(\mathcal {A}^{\mathcal {P}_{2}}\) lies in the interval [1.505949,1.5068]. The upper bound is due to Chen et al. [3], the lower bound is computed by Lu [17] using Yao’s minimax principle. Notice that Lu [17] states that the lower bound is 1.506, but we repeated the calculations from this paper and obtained the number 1.505949. Thus, when reporting results, we use this number as the currently best lower bound. We improve this bound and show that |R₂ − 1.505996| < 10^− 6, in particular, R₂ < 1.506.

From the description above, one can see that the existing bounds for truthful scheduling on unrelated machines are obtained using ad hoc procedures or (for the lower bounds) Yao’s minimax principle. This paper develops a unified approach to construct upper and lower bounds on R_n for any fixed n and provides an alternative to Yao’s minimax principle for the construction of lower bounds. As a result, we improve the bounds for truthful scheduling for m = 2 and n ∈{2,3,4}.

Next, we compare our approach to the existing methods for upper bounds in [2, 3, 7, 15] that use optimization. Our method for upper bounds generalizes the approach by Chen et al. [3]. The generalization considers a broader class of algorithms and provides stronger upper bounds for n ≤ 4. Our approach is fundamentally different from the methods in [2, 7, 15]. To begin with, our method is suitable for the minimum makespan problem on unrelated machines, while the methods in [2, 7, 15] are not guaranteed to work for this problem. Next, [2, 7, 15] use LP relaxations of the corresponding integer programs while we use the tools from continuous optimization to obtain possibly non-linear, but tractable approximations. Moreover, [2, 7, 15] consider truthful in expectation mechanisms only while we work with universally truthful ones.

We obtain new bounds only for small n ≤ 4 because of the growing size of the lower bound optimization problems. One can try to solve these problems in a more computationally efficient way using, for instance, the column generation technique (see, e.g., Gilmore and Gomory [10]). As a result, one could expect to obtain new bounds for n > 4 with our approach since the solution to the upper bound problem is a relatively simple construction based on the solution to the lower bound problem, as described in Section 4. However, improving the efficiency of the lower bound computation is out of the scope of the current paper.

For a given number of tasks n, let S_n be the symmetric, or permutation, group on n elements. Given a vector \(\mathbf {z} \in \mathbb {R}^{n}\) and π ∈ S_n, the corresponding permutation of the elements of z by π is denoted by zπ. The group S_n corresponds to column permutations in a given time matrix T. We define another group, S_inv, which corresponds to row permutations in T. S_inv consists of the identity action ^id. and the action ^inv. which takes element-wise reciprocals of any vector \(\mathbf {x} =(x_{1},\dots ,x_{n}) \in \mathbb {R}_{++}^{n}\): Now, we define the action of S_inv×S_n on \(\mathcal {P}_{n}\). Given \(\mathbb {P}\in \mathcal {P}_{n}\), γ ∈ S_inv, π ∈ S_n and a random variable \(\mathbf {z} \sim \mathbb {P}\), we consider the transformation z → ^γzπ. We define \({{~}^{\gamma }\mathbb {P}\pi } \in \mathcal {P}_{n}\) as the distribution of ^γzπ. Next, we prove that problem (7) is convex and invariant under the action of S_inv×S_n on \(\mathbb {P}\). As a result, to find the infimum in (7), it is enough to optimize over the distributions \(\mathbb {P}\) invariant under the action of S_inv×S_n. This approach is regularly used in convex programming, see Dobre and Vera [5], Gatermann and Parrilo [9] or de Klerk et al. [13].

Given distributions \(\mathbb {P}_{1},\dots ,\mathbb {P}_{k} \in \mathcal {P}_{n}\), and weights α_i ≥ 0 for all i ∈ [k] such that \({\sum }_{i=1}^{k}\alpha _{i}=1\), we define the convex combination \({\sum }_{i=1}^{k}\alpha _{i} \mathbb {P}_{i} \in \mathcal {P}_{n}\) as the distribution where we draw from P_i, i ∈ [k] with probability α_i. The construction of \({\sum }_{i=1}^{k}\alpha _{i} \mathbb {P}_{i}\) and definitions (3), (4) imply that Therefore, using (5), we have

that is, \(R_{n}(\mathbb {P})\) is convex in \(\mathbb {P}\). Now, we show the invariance of \(R_{n}(\mathbb {P})\) under the action of S_inv×S_n.

The proof of Theorem 3 is presented in Section 7.2.

From Theorem 4, problem (7) is invariant under permuting the tasks and the machines. In the sequel we exploit the invariance under permuting the tasks only. First, this simplifies the presentation. Second, in our numerical computations using the invariance under the two types of permutations produced the same bounds as using invariance under task permutations only.

Let \(\mathcal {C}_{n} \subset \mathcal {P}_{n}\) be the family of probability measures invariant under the actions of S_n:

In the rest of the paper we restrict the optimization to the distributions from \(\mathcal {C}_{n}\).

Proposition 1 next is straightforward but crucial for our analysis.

By Proposition 1, if \(\mathbb {P}\in \mathcal {C}_{n}\), then all univariate marginal distributions of \(\mathbb {P}\) are identical and all bivariate marginal distributions of \(\mathbb {P}\) are identical. Denote the corresponding univariate and bivariate CDFs by \(F_{\mathbb {P}}\) and \(H_{\mathbb {P}}\), respectively, and define

First, we present a result by Chen et al. [3], which follows from Lu and Yu [19]

Notice that this upper bound is defined by only two tasks out of n. Using Proposition 2, we obtain the following formulation for \(R_{n}(\mathbb {P})\):

The proof of Theorem 5 is provided in Section 7.3.

The next corollary is the main result of this section, and we use it throughout the rest of the paper.

To implement the ideas above, we have to optimize over distributions. For this purpose we represent a distribution via its CDF. To characterize CDFs, we follow Nelsen [22]. For \(\mathbf {x}, \mathbf {y}\in \mathbb {R}^{n}\) such that x_i ≤ y_i for all i ∈ [n], we define the n-box \(\mathcal {B}_{xy}: = \left [x_{1}, y_{1} \right ] \times \left [ x_{2}, y_{2}\right ] \times {\dots } \times \left [ x_{n}, y_{n} \right ]. \) The set of vertices of \(\mathcal {B}_{xy}\) is V_xy = {x₁,y₁} ×{x₂,y₂} ×… ×{x_n,y_n} . The sign of vertex b ∈ V_xy is defined by Given a set \(D \subseteq \mathbb {R}\), define \(\overline {D}:=\left (D\cup \{0\} \cup \{\infty \}\right )\). A function \(G: \overline {\mathbb {R}}^{n} \rightarrow \mathbb {R}\) is called n-increasing on \(\overline {D}^{n}\) when

The following family of functions captures the concept of CDF.

To construct the upper bound, we restrict the inner maximization in problem (13) to a subset of \(\mathbb {R}_{++}\). We do this using the next lemma.

For a finite \(\mathcal {S} \subset \mathbb {R}_{++}\) and \(g \in \mathcal {G}_{n}(\mathcal {S})\), we define the restriction of the objective in problem (13) to \(\mathcal {S}\):

By Lemma 1, \(\phi ^{g}=\phi ^{\mathbb {P}}|_{\overline {\mathcal {S}}^{2}}\) for some \(\mathbb {P} \in \mathcal {P}_{n}\).

Let \(S\subset \mathbb {R}_{++}\). To compute the lower bound \(R_{n}(\mathcal {S})\) from (17), we use the epigraph form of the optimization problem for \(R_{n}(\mathcal {S})\):

The optimization variable in the problem above is g. This variable is a vector in \(\mathbb {R}^{(|\mathcal {S}|+2)^{n}}\) which represents a function \(g \in \mathcal {G}_{n}(\mathcal {S})\). We slightly abuse the notation and do not use a bold symbol for g to underline that g corresponds to a function with a finite support. Family \(\mathcal {G}_{n}(\mathcal {S})\) is an infinite family of functions g, and each of these functions is defined on a finite set \(\overline {\mathcal {S}}^{n}\) with cardinality \((|\mathcal {S}|+2)^{n}\). For the purpose of optimization, this means that we consider all vectors \(g\in \mathbb {R}^{(|\mathcal {S}|+2)^{n}}\) which satisfy the four conditions in Definition 1 and the invariance property. All mentioned conditions are linear, and there are finitely many of them. Therefore the optimization over the infinite family of functions \(\mathcal {G}_{n}(\mathcal {S})\) can be written as a finite LP. We use the invariance of g (the second constraint) and Conditions 3-4 in Definition 1 to reduce the number of variables in problem (18) (the size of g as a vector). To ensure that g corresponds to an n-increasing function as specified in (14), it is enough to consider \(\mathbf {x}, \mathbf {y} \in \overline {\mathcal {S}}^{n}\) such that x_i,y_i are consecutive points in \(\mathcal {S}\) for all i ∈ [n]. This reduces the number of constraints in problem (18).

To compute the upper bound \(R_{n}(\mathbb {P})\) using formulation (17), we first construct a good-guess distribution \(\mathbb {P}\). Given a set \(\mathcal {S}\) and the solution g to the lower bound problem (17) on \(\mathcal {S}\), we use the distribution \(\mathbb {P}_{g}\) which corresponds to the CDF (15) based on g. To construct this CDF, we choose a number \(a>\max \{s: s\in \mathcal {S}\}\), as explained in the proof of Lemma 1. In the rest of this section we work with \(\mathcal {S}_{a}=\mathcal {S} \cup \{a\}\). To solve (17) for \(\mathbb {P}_{g}\), we define the following set of intervals:

This set of intervals covers \(\mathbb {R}_{+}\), therefore by (17)

We solve the inner maximization problem in (19) for each pair \(i,j \in [|\mathcal {S}|+2]\). The expression for \(\phi ^{\mathbb {P}_{g}}\) (12) for the case xy ≥ 1 is different from the case xy < 1. To simplify the computations when the line xy = 1 crosses the rectangle I_i×I_j, we restrict our attention to \(\mathcal {S}\) of a particular type. Consider a collection of k − 1 positive real numbers r₁ < r₂ < ⋯ < r_k− 1 < 1, let

For any \(a>\tfrac {1}{r_{1}}\), \(\mathcal {S}_{k,a}=\mathcal {S}_{k}\cup \{a\}\) subdivides \(\mathbb {R}_{+}\) into 2k+ 1 intervals \(\mathcal {I}_{\mathcal {S}_{k}}\). First, consider a pair of intervals \(I_{i},I_{j} \in \mathcal {I}_{\mathcal {S}_{k}}\) such that i∉{1,2k+ 1} and j∉{1,2k+ 1} (i.e., neither of them are the first or the last interval). Due to the choice of \(\mathcal {S}_{k}\), the line xy = 1 crosses the rectangle I_i × I_j if and only if i + j = 2k + 1. Denote the bivariate marginal CDF and the univariate marginal CDF of \(\mathbb {P}_{g}\) by H_g and F_g, respectively. Then

We construct the CDF of \(\mathbb {P}_{g}\) using (15), therefore

That is, the marginal CDFs are constant on I_i × I_j and I_i, respectively. As the range of a CDF is [0,1], we conclude that for x ∈ I_i,y ∈ I_j, \(\phi ^{\mathbb {P}_{g}}(x, y)\) is non-increasing in x and non-decreasing in y. The latter holds since for any \( \mathbb {P} \in \mathcal {P}_{2}\) invariant under S₂ and for any \(x,y \in \mathbb {R}\),

Hence the optimal value of the inner maximization problem in (19) can be obtained by first substituting the CDFs (22) into the function (21) and then substituting x = s_i− 1, y = s_j. Note that this optimum is not attained. For the case i + j = 2k + 1, i.e., when the line xy = 1 crosses the rectangle I_i × I_j, the result holds due to the choice of \(\mathcal {S}_{k}\).

When i ∈{1,2k+ 1} or j ∈{1,2k+ 1}, the function \(\phi ^{\mathbb {P}_{g}}(x, y)\) simplifies, and we solve such cases separately. The solution approach resembles the one from the previous paragraph.

In numerical experiments we use uniform finite sets

Table 2 shows the best obtained bounds and the k we use to compute these bounds.

We round the lower bounds \(R_{n}(\mathcal {S}^{u}_{k})\) down and the upper bounds \(R_{n}(\mathbb {P}_{g})\) up. We verify all upper bounds with exact arithmetics using the MATLAB symbolic package and the following procedure. First, we obtain the optimal solution g to problem (18) and round the elements of the set \(\mathcal {S}^{u}_{k}\) and the number a to the 8^th digit. Next, we transform the rounded values into rational numbers and compute \(R_{n}(\mathbb {P}_{g})\) as a rational number. By Lemma 1 and Theorem 6, the rounded g provides the algorithm \(\mathcal {A}^{\mathbb {P}_{g}}\) with the worst-case approximation ratio \(R_{n}(\mathbb {P}_{g})\).

The upper bound for n = 2 in Table 2 is worse than the best existing upper bound. We improve our result and obtain a new best exiting upper bound for n = 2 in the next section.

To compute a new upper bound on R₂, we restrict the set of functions in problem (26) to the family of piecewise rational univariate CDFs. We say that a function is piecewise rational if it can be written as a fraction where both the numerator and the denominator are polynomials. The domain of each CDF is subdivided into pieces by \(\mathcal {S}_{k}\) defined in (20). Given \(\mathcal {S}_{k}\), we introduce a collection of intervals:

Given \(\mathcal {I}_{\mathcal {S}_{k}}\) and a family of continuous functions \(\mathcal {F}\), we consider CDFs which “piecewisely” belong to \(\mathcal {F}\).

In this subsection, for a given \(\mathcal {S}_{k}\), we choose \(\mathcal {F}\) in Definition 2 to be the family of linear univariate functions

Then \(\mathcal {C}_{\mathcal {F}}(\mathcal {S}_{k})\) includes, in particular, the CDFs from [3, 17, 18, 23] where the authors use piecewise functions with domains subdivided into two, four, or six intervals. We observe that the upper bounds are better when the domains are subdivided more times or when each piece has a more complex form than a constant function, i.e., when c¹ can be non-zero. We improve upon the existing upper bounds by using a larger number of pieces and letting c¹ be non-zero in each piece. Define

Let \(\mathcal {X}:=\left \{ (x,y) \in \mathbb {R}^{2}_{++}{:} \ xy \ge 1 \right \}\). Consider two formulations for \( R_{2}\left (\mathcal {C}_{\mathcal {F}}(\mathcal {S}_{k})\right )\) which are equivalent to problem (30)

The second equality follows from the equivalence of problems (30) and (29) since for \(\mathcal {S}_{k}\) defined in (20) xy ≥ 1 implies x ∈ I_i, y ∈ I_j with i + j ≥ 2k + 1. We use problems (35) and (36) to approximate \(R_{2}\left (\mathcal {C}_{\mathcal {F}}(\mathcal {S}_{k})\right )\) with high precision. Namely, we use relaxations of problem (35) to compute lower bounds on \(R_{2}\left (\mathcal {C}_{\mathcal {F}}(\mathcal {S}_{k}) \right )\), and we use feasible solutions to problem (36) to compute upper bounds on \(R_{2}\left (\mathcal {C}_{\mathcal {F}}(\mathcal {S}_{k}) \right )\).

For \(F \in \mathcal {C}_{\mathcal {F}}(\mathcal {S}_{k})\) satisfying (28) and (33), the variables in problem (35) are \(\left (t,\{{c_{i}^{0}}\}_{i=1}^{k},\{{c^{1}_{i}}\}_{i=1}^{k} \right ) \). This problem is LP with infinitely many constraints: each \((x,y) \in \mathcal {X}\) induces a linear constraint. Such problems can be well approximated using the cutting-plane approach introduced by Kelley [12]. Namely, we start with a finite set \(\mathcal {Y} \subset \mathcal {X}\) and restrict the set of constraints in (35) to its finite subset generated by \((x,y) \in \mathcal {Y}\). As a result, we obtain a finite linear problem. Denote its optimal solution by \((\underline {F}, \ \underline {t})\). Then \(\underline {t}\) is a lower bound on \(R_{2}\left (\mathcal {C}_{\mathcal {F}}(\mathcal {S}_{k}) \right )\).

Next, we substitute \(\underline {F}\) in (36) and find a feasible t. We compute the supremum for each pair i,j ∈ [2k] with i + j ≥ 2k + 1 using the Karush-Kuhn-Tucker (KKT) conditions. For each pair of intervals the inner maximization problem in (36) either is linearly constrained or satisfies the Mangasarian-Fromovitz constraint qualification. Therefore the optimum is among the KKT points, see, e.g., Section 3 in Eustaquio et al. [8] for more details. All problems are simple and have similar structure. Therefore we do not write the KKT conditions explicitly, but consider all possible critical points from the first order conditions and from the boundary conditions. This set contains all the KKT points, and thus the optimal one. At the end we choose the point (x,y) with the maximal value of \(\phi ^{\underline {F}}(x,y)\) among the critical points. See Section 7.4 for more details. Let \(\overline {t}\) be the maximum of \(\phi ^{\underline {F}}(x,y)\) over all pairs of intervals. The solution \((\underline {F},\overline {t})\) is feasible for problem (36). Thus \(\overline {t}\) is an upper bound on \(R_{2}\left (\mathcal {C}_{\mathcal {F}}(\mathcal {S}_{k}) \right )\). Let (x^∗,y^∗) be a point such that \(\phi ^{\underline {F}}(x^{*},y^{*})=\overline {t}\). If \(|\overline {t}-\underline {t}|>10^{-8}\), we proceed from the beginning by restricting problem (35) to the updated set \(\mathcal {Y} \leftarrow \mathcal {Y}\cup \{(x^{*},y^{*})\}\). Otherwise we stop.

To obtain numerical results, we use uniform sets \(\mathcal {S}^{u}_{k}\) of the form (24). We work with family \(\mathcal {C}_{\mathcal {F}}(\mathcal {S}^{u}_{k})\) from Definition 2, where the underlying family of functions \(\mathcal {F}\) is defined in (33). We initialize the cutting-plane procedure with \(\mathcal {Y}=\left \{(x,y): x,y \in \mathcal {S}^{u}_{k}, \ xy\ge 1\right \}\). The best obtained upper bound is indicated in bold in Table 3, it is stronger than the currently best upper bound 1.5068.

We verify the upper bound 1.5059964 using exact arithmetics in a similar way as we do it for the upper bounds in Table 2 of Section 4.3.

The cutting-plane approach from Section 5.1 generates not only the upper bound with the corresponding CDF, but also the set of points \(\mathcal {Y}\). Using \(\mathcal {Y}\), we build a new set \(\mathcal {S}^{*}_{k}\) of the form (20), which is not uniform as in (24). We consider all \((x,y) \in \mathcal {Y}\) involved in the binding constraints of problem (35) at the last cutting-plane iteration. Next, we take the corresponding x, y and their reciprocals, order ascending, round to the 8^th digit and obtain \(\mathcal {S}^{*}_{k}\) with k = 82. For this set the lower bound \(R_{n}(\mathcal {S}^{*}_{k})\) from problem (18) is 1.5059953, which is stronger than our lower bound from Table 2. As a result, the lower and upper bounds become very close to each other: |R₂ − 1.505996|≤ 10^− 6.

We begin with a lemma.

Recall the definitions of S_inv and S_n from Section 3. Let σ_id be the identity action of S₂ and σ_swap be the non-identity action of S₂. We say that that the group S₂×S_n acts on a matrix in \(\mathbb {R}^{2\times n}\) by permuting the two rows and the n columns of this matrix. Namely, for \(A\in \mathbb {R}^{2\times n}\) and (σ,π) ∈ S₂×S_n, we define the action of (σ,π) ∈ S₂×S_n on A by We show that for any \(T \in \mathbb {R}^{2\times n}_{++}\) the optimal makespan M^∗(T) is invariant under the actions of S₂×S_n on T. Moreover, the expected makespan \(M(\mathbb {P},T)\) is invariant under the actions of S₂×S_n on T and S_inv×S_n on \(\mathbb {P}\). These two results together imply Theorem 3.

By Proposition 2, \(R_{n}(\mathbb {P}) \le \sup _{x,y \in \mathbb {R}_{++}}\phi ^{\mathbb {P}}(x,y)\). Next, we prove the opposite inequality. Consider \(\mathbb {P} \in \mathcal {C}_{n}\). We start with the case n = 2 and proceed similarly to Lu and Yu [19]. Denote the bivariate marginal distribution of \(\mathbb {P}\) by \(\mathbb {P}_{2}\). Consider a time matrix \(T \in \mathbb {R}_{++}^{2\times 2}\) and denote \(\frac {T_{11}}{T_{21}}\) by x, \(\frac {T_{12}}{T_{22}}\) by y. Construct the following matrix T₀: The expected makespan of \(\mathcal {A}^{\mathbb {P}_{2}}\) on this instance is \(M(\mathbb {P}_{2},T_{0})\):

Denote the minimum makespan on T₀ by M^∗. By construction M^∗≤ 1, hence

This holds for all \(x, y \in \mathbb {R}_{++}\), therefore

Now, fix n > 2. Choose a small 𝜖 > 0 and consider the following time matrix T_𝜖: The expected makespan of \(\mathcal {A}^{\mathbb {P}}\) on this instance, \(M(\mathbb {P},T_{\epsilon })\), satisfies and the optimal makespan, M^∗(T_𝜖), satisfies Using the result for n = 2,

which holds for all \(x, y \in \mathbb {R}_{++}\).

In this section we find possible critical points for the function

with F defined in (28) using (33) on I_i × I_j such that i,j ∈ [2k], i + j ≥ 2k + 1. By construction, in each interval F is differentiable, and ϕ^F is differentiable on I_i × I_j (the expression simplifies for i = 1 and j = 2k). The first derivatives of the function ϕ^F(x,y) are:

Next, we consider the three possible cases for i,j. For each of these cases we substitute F(x), F(y) from (28) and find the analytical solution to the system \(\frac {\partial \phi ^{F}(x,y)}{\partial x}=0, \ \frac {\partial \phi ^{F}(x,y)}{\partial y}=0\). For this purpose we use Wolfram|Alpha [28]. The obtained solution is denoted by (x^∗, y^∗). The sign of the derivatives is unknown, so we start with the set {s_i− 1,s_i,x^∗}×{s_j− 1,s_j,y^∗} as possible critical points. If i + j = 2k + 1 (that is, the line xy = 1 crosses the rectangle I_i × I_j), we additionally consider the set \(\left \{(x^{*},\tfrac {1}{x^{*}}),(\tfrac {1}{y^{*}}, y^{*})\right \}\). We check all resulting pairs for feasibility and exclude the infeasible ones.

When x ∈ I₁ or y ∈ I_2k, ϕ^F(x,y) simplifies by construction of (28). In our computations we analyze these situations separately.