Malleable scheduling beyond identical machines
Dimitris Fotakis Jannik Matuschke Orestis Papadigenopoulos
 
gobble

  Atom-specific persistent homology and its application to protein flexibility analysis 
    David Bramer^1 and
Guo-Wei Wei^1,2,3 [ Address correspondences  to Guo-Wei Wei. E-mail:wei@math.msu.edu]


^1 Department of Mathematics 

Michigan State University, MI 48824, USA

^2  Department of Biochemistry and Molecular Biology

Michigan State University, MI 48824, USA 

^3 Department of Electrical and Computer Engineering 

Michigan State University, MI 48824, USA 


    Received / Accepted
===========================================================================================================================================================================================================================================================================================================================================================================================


In malleable job scheduling, jobs can be executed simultaneously on multiple machines with the processing time depending on the number of allocated machines. In this setting, jobs are required to be executed non-preemptively and in unison, in the sense that they occupy, during their execution, the same time interval over all the machines of the allocated set. In this work, we study generalizations of malleable job scheduling inspired by standard scheduling on unrelated machines. Specifically, we introduce a general model of malleable job scheduling, where each machine has a (possibly different) speed for each job, and the processing time of a job j on a set of allocated machines S depends on the total speed of S with respect to j. For machines with unrelated speeds, we show that the optimal makespan cannot be approximated within a factor less than e/e-1, unless P = NP. On the positive side, we present polynomial-time algorithms with approximation ratios 2e/e-1 for machines with unrelated speeds, 3 for machines with uniform speeds, and 7/3 for restricted assignments on identical machines. Our algorithms are based on deterministic LP rounding. They result in sparse schedules, in the sense that each machine shares at most one job with other machines. We also prove lower bounds on the integrality gap of 1+φ for unrelated speeds (φ is the golden ratio) and 2 for uniform speeds and restricted assignments. To indicate the generality of our approach, we show that it also yields constant factor approximation algorithms for a variant where we determine the effective speed of a set of allocated machines based on the L_p norm of their speeds. 



arabic




§ INTRODUCTION



Since the late 60s, various models have been proposed by researchers <cit.> in order to capture the real-world aspects and particularities of multiprocessor task scheduling systems, i.e., large collections of identical processors able to process tasks in parallel. High performance computing, parallel architectures, and cloud services are typical applications that motivate the study of multiprocessor scheduling, both theoretical and practical. An influential model is Rayward-Smith's unit execution time and unit communication time (UET-UCT) model <cit.>, where each parallel job is partitioned into a set of tasks of unit execution time and these tasks are subject to precedence constraints modeled by a task graph.
The UET-UCT model and its generalizations have been widely studied and a large number of (approximation) algorithms and complexity results have been proposed <cit.>. 

However, the UET-UCT model mostly focuses on task scheduling and sequencing, and does not account for the amount of resources allocated to each job, thus failing to capture an important aspect of real-world parallel systems. Specifically, in the UET-UCT model, the level of granularity of a job (that is, the number of smaller tasks that a job is partitioned into) is decided a priori and 
is given as part of the input. 

However, it is common ground in the field of parallel processing that the unconditional allocation of resources for the execution of a job may jeopardize the overall efficiency of a multiprocessor system. A theoretical explanation is provided by Amdahl's law <cit.>, which suggests that the speedup of a job's execution can be estimated by the formula 1/(1-p) + p/s, where p is the fraction of the job that can be parallelized and s is the speedup due to parallelization (i.e., s can be thought of as the number of processors). 

Malleable Scheduling.

An interesting alternative to the UET-UCT model is that of malleable[Malleable scheduling also appears as moldable, while sometimes the two terms refer to slightly different models.] job scheduling <cit.>. In this setting, a set  of jobs is scheduled on a set  of parallel machines, while every job can be processed by more than one machine at the same time. In order to quantify the effect of parallelization, the processing time of a job j ∈ is determined by a function f_j : ℕ→ℝ_+ depending on the number of allocated machines.[We denote by ℝ_+ (resp. ℤ_+) the set of non-negative reals (resp. integers).]  Moreover, every job must be executed non-preemptively and in unison, i.e. having the same starting and completion time on each of the allocated machines. Thus, if a job j is assigned to a set of machines S starting at time τ, all machines in S are occupied with job j during the interval [τ, τ+f_j(|S|)]. It is commonly assumed that the processing time function of a job exhibits two useful and well-motivated properties: 



  * For every job j ∈, the processing time f_j(s) is non-increasing in the number of machines.[This property holds w.l.o.g., as the system always has the choice not to use some of the allocated machines.]

  * The total work of the execution of a job j on s machines, that is the product s · f_j(s), is non-decreasing in the number of machines.


The latter property, known as monotonicity of a malleable job, is justified by Brent's law <cit.>: One cannot expect superlinear speedup by increasing the level of parallelism. 
A great deal of theoretical results have been published on scheduling malleable jobs according to the above model (and its variants) for the objective of minimizing the makespan, i.e., the completion time of the last finishing job, or other standard objectives (see e.g., <cit.> and the references therein).
 
Although malleable job scheduling represents a va­liant attempt to capture real-world aspects of massively parallel processing, the latter exhibits even more complicated characteristics. Machine heterogeneity, data locality and hardware interconnection are just a few aspects of real-life systems that make the generalization of the aforementioned model necessary. In modern multiprocessor systems, machines are not all identical and the processing time of a job not only depends on the quantity, but also on the quality of the set of allocated machines. Indeed, different physical machines may have different capabilities in terms of faster CPUs or more efficient cache hierarchies. Moreover, the above heterogeneity may be job-dependent, in the sense that a specific machine may be faster when executing a certain type of jobs than another (e.g. memory- vs arithmetic-intensive applications <cit.>). Finally, the execution of a job on specific combinations of machines may also yield additional benefit (e.g., machines that are local in terms of memory hierarchy). 

Our Model: Malleable Scheduling on Unrelated Machines.

Quite surprisingly, no results exist on sche­duling malleable jobs beyond the case of identical machines, to the best of our knowledge, despite the significant theoretical and practical interest in the model. In this work, we extend the model of malleable job scheduling to capture more delicate aspects of parallel job scheduling. In this direction, while we still require our jobs to be executed non-preemptively and in unison, the processing time of a job j ∈ becomes a set function f_j(S), where S ⊆ is the set of allocated machines. We require that processing times are given by a non-increasing function, in the set function context, while additional assumptions on the scalability of f_j are made, in order to capture the diminishing utility property implied by Brent's law. 

These assumptions naturally lead to a generalized malleable job setting, where processing times are given by non-increasing supermodular set functions f_j(S), accessed by value queries. We show that makespan minimization in this general setting 

is inapproximable within 𝒪(||^1-) factors (unless P = NP, see Section <ref>). The general message of the proof is that unless we make some relatively strong assumptions on processing times (in the form e.g., of a relatively smooth gradual decrease in the processing time, as more machines are allocated), malleable job scheduling (even with monotone supermodular processing times) can encode combinatorial problems as hard as graph coloring. 

Thus, inspired by (standard non-malleable) scheduling models on uniformly related and unrelated machines, we introduce the notion of speed-implementable processing time functions. For each machine i and each job j there is a speed s_i,j∈ℤ_+ that quantifies the contribution of machine i to the execution of job j, if i is included in the set allocated to j. For most of this work, we assume that the total speed of an allocated set is given by an additive function σ_j(S) = ∑_i ∈ S s_i,j (but see also Section <ref>, where we discuss more general speed functions based on L_p-norms). 
A function is speed-implementable if we can write f_j(S) = f_j(σ_j(S)) for some function f_j : ℝ_+→ℝ_+.[For convenience, we use the identifier f_j for both functions. Since their arguments come from disjoint domains, it is always clear from the context which one is meant.]  Again, we assume oracle access to the processing time functions.

The notion of speed-implementable processing times allows us to quantify the fundamental assumptions of monotonicity and diminishing utility in a clean and natural way. More specifically, we make the following two assumptions on speed-implementable functions:


  * Non-increasing processing time: For every job j ∈, the processing time f_j(s) is non-increasing in the total allocated speed s ∈ℝ_+. 

  * Non-decreasing work: For every job j ∈, the work f_j(s) · s is non-decreasing in the total allocated speed s ∈ℝ_+. 

The first assumption ensures that allocating more speed cannot increase the processing time. The second assumption is justified by Brent's law, when the increase in speed coincides with an increase in the physical number of machines, or by similar arguments for the increase of the total speed of a single physical machine (e.g., memory access, I/O bottleneck <cit.> etc.). We remark that speed-implementable functions with non-in­creasing processing times and non-decreasing work do not need to be convex, and thus, do not belong to the class of supermodular functions. 

In order to avoid unnecessary technicalities, we additionally assume that for any job j ∈, f_j(0) = +∞, namely, no job can be executed on a set of machines of zero cumulative speed. 


In this work, we focus on the objective of minimizing the makespan C_max = max_j ∈ C_j, where C_j the completion time of job j. 
We refer to this setting as the problem of scheduling malleable jobs on unrelated machines. To further justify this term, we present a pseudopolynomial transformation of standard scheduling on unrelated machines to malleable scheduling with speed-implementable processing times (see Section <ref>). The reduction can be rendered polynomial by standard techniques, preserving approximation factors with a loss of 1+ε.




 §.§ Related Work

The problem of malleable job scheduling on identical machines has been studied thoroughly for more than three decades.
For the case of non-monotonic jobs, i.e., jobs that do not satisfy the monotonic work condition, Du and Leung <cit.> show that the problem is strongly NP-hard for more than 5 machines, while in terms of approximation, Turek, Wolf and Yu <cit.> provided the first 2-approximation algorithm for the same version of the problem. 
Jansen and Porkolab <cit.> devised a PTAS for instances with a constant number of machines, which was later extended by Jansen and Thöle <cit.> to a PTAS for the case that the number of machines is polynomial in the number of jobs.


For the case of monotonic jobs, Mounié, Rapine and Trystram <cit.> propose a 3/2-approximation algorithm, improving on the √(3)-approximation provided by the same authors <cit.>. 
Recently, Jansen and Land <cit.> gave an FPTAS for the case that || ≥ 8 ||/ε. 
Together with the approximation scheme for polynomial number of machines in <cit.>, this implies a PTAS for scheduling monotonic malleable jobs on identical machines.


Several papers also consider the problem of scheduling malleable jobs with preemption and/or under precedence constraints <cit.>.
An interesting alternative approach to the general problem is that of Srinivasa Prasanna, and Musicus <cit.>, who consider a continuous version of malleable tasks and develop an exact algorithm based on optimal control theory under certain assumptions on the processing time functions.
While the problem of malleable scheduling on identical machines is very well understood, this is not true for malleable extensions of other standard scheduling models, such as unrelated machines or the restricted assignment model. 



A scheduling model similar to malleable tasks is that of splittable jobs. In this regime, jobs can be split arbitrarily and the resulting parts can be distributed arbitrarily on different machines. 
For each pair of job j and machine i, there is a setup time s_ij and a processing time p_ij.
If a fraction x_ij∈ (0, 1] of job j is to be scheduled on machine i, the load that is incurred on the machine is s_ij + p_ijx_ij.
Correa et al. <cit.> provide an (1 + φ)-approximation algorithm for this setting (where φ is the golden ratio), which is based on an adaptation of the classic LP rounding result by Lenstra, Shmoys, and Tardos <cit.> for the traditional unrelated machine scheduling problem.
We remark that the generalized malleable setting considered in this paper also induces a natural generalization of the splittable setting beyond setup times, when dropping the requirement that jobs need to be executed in unison.
As in <cit.>, we provide a rounding framework based on a variant of the assignment LP from <cit.>. However, the fact that processing times are only given implicitly as functions in our setting makes it necessary to carefully choose the coefficients of the assignment LP, in order to ensure a constant integrality gap. Furthermore, because jobs have to be executed in unison, we employ a more sophisticated rounding scheme in order to better utilize free capacity on different machines.




 §.§ Contribution and Techniques



At the conceptual level, we introduce the notion of malleable jobs with speed-implementable processing times. Hence, we generalize the standard and well-studied setting of malleable job scheduling, in a direct analogy to fundamental models in scheduling theory (e.g., scheduling on uniformly related and unrelated machines). This new and much richer model gives rise to a large family of unexplored packing problems that may be of independent interest. 

From a technical viewpoint, we investigate the computational complexity and the approximability of this new setting. To the best of our understanding, standard techniques used for makespan minimization in the setting of malleable job scheduling on identical machines, such as the two-shelve approach (as used in <cit.>) and area charging arguments, fail to yield any reasonable approximation guarantees in our more general setting. 
This intuition is supported by the following hardness of approximation result (see Section <ref> for the proof).
theoremrestateHardness
For any ϵ > 0, there is no (e/e-1 - ϵ)-approximation algorithm for the problem of scheduling malleable jobs on unrelated machines, unless P=NP.

Note that the lower bound of e/e-1 is strictly larger than the currently best known lower bound of 1.5 for classic (non-malleable) scheduling on unrelated machines.


Our positive results are based on a linear programming relaxation, denoted by [LP(C)] and described in Section <ref>. This LP resembles the assignment LP for the standard setting of non-malleable scheduling <cit.>. However, in order to obtain a constant integrality gap we distinguish between “small” jobs that can be processed on a single machine (within a given target makespan), and “large” jobs that have to be processed on multiple machines. 
For the large jobs, we carefully estimate their contribution to the load of their allocated machines. Specifically, we introduce the notion of critical speed and use the critical speed to define the load coefficients incurred by large jobs on machines in the LP relaxation by proportionally distributing the work volume according to machine speeds. 
For the rounding, we exploit the sparsity of our relaxation's extreme points (as in <cit.>) and generalize the approach of <cit.>, in order to carefully distinguish between jobs assigned to a single machine and jobs shared by multiple machines.
theoremrestateUnrelated 
There exists a polynomial-time 2 e/e-1-appro­xi­mation algorithm for the problem of scheduling malleable jobs on unrelated machines.

An interesting corollary is that for malleable job scheduling on unrelated machines, there always exists an approximate solution where each machine shares at most one job with some other machines.

In addition, we consider the interesting special case of restricted assignment machines, namely, the case where each job is associated with subset M_j ⊆ of machines such that s_i,j = 1 for all j ∈ and i ∈ M_j and s_i,j = 0 otherwise. Finally, we consider the case of uniform speeds, where s_i,j = s_i for all i ∈ and j ∈. For the above special cases of our problem, we are able to get improved approximation guarantees by exploiting the special structure of the processing time functions, as summarized in the following two theorems.

theoremrestateRestricted
There exists a polynomial-time 7/3-approxi­mation algorithm for the problem of scheduling malleable jobs on restricted identical machines.


theoremrestateUniform
There exists a polynomial-time 3-approxi­mation algorithm for the problem of scheduling malleable jobs on uniform machines.



All our approximation results imply corresponding upper bounds on the integrality gap of the linear programming relaxation [LP(C)].
Based on an adaptation of a construction in <cit.>, we show a lower bound of 1+φ≈ 2.618 on the integrality gap of [LP(C)] for malleable job scheduling on unrelated machines, where φ is the golden ratio (see Section <ref>).
For the cases of restricted assignment and uniformly related machines, respectively, we obtain an integrality gap of 2.

Moreover, we extend our model and approach in the following direction. We consider a setting where the effective speed according to which a set S of allocated machines processing a job j is given by the L_p-norm σ^(p)_j(S) = ( ∑_i ∈ S (s_i,j)^p  )^1/p of the corresponding speed vector. In practical settings, we tend to prefer assignments to relatively small sets of physical machines, so as to avoid delays related to communication, memory access, and I/O (see e.g., <cit.>). By replacing the total speed (i.e., the L_1-norm) with the L_p-norm of the speed vector for some p ≥ 1, we discount the contribution of additional machines (especially of smaller speeds) towards processing a job j. Thus, as p increases, we give stronger preference to sparse schedules, where the number of jobs shared between different machines (and the number of machines sharing a job) are kept small. Interestingly, our general approach is robust to this generalization and it results in constant approximation factors for any p ≥ 1. 
Asymptotically, the approximation factor is bounded by p/p-ln p + √(p/ln p) and our algorithm smoothly converges to the classic 2-approximation algorithm for unrelated machine scheduling <cit.> as p tends to infinity (note that for the L_∞-norm, our setting is identical to standard scheduling on unrelated machines).
These results are discussed in Section <ref>.



Trying to generalize malleable job scheduling beyond the simple setting of identical machines, as much as possible, we believe that our setting with speed-implementable processing times lies on the frontier of the constant-factor approximability regime. We show a strong inapproximability lower bound of 𝒪(|  |^1-) for the (far more general) setting where the processing times are given by a non-increasing supermodular set functions. These results are discussed in Section <ref>. An interesting open question is to characterize the class of processing time functions for which malleable job scheduling admits constant factor (and/or logarithmic) approximation guarantees. 


§ THE GENERAL ROUNDING FRAMEWORK
 
In this section, we provide a high-level description of our algorithm. We construct a polynomial-time ρ-relaxed decision procedure for malleable job scheduling problems. This procedure takes as input an instance of the problem as well as a target makespan C and either asserts correctly that there is no feasible schedule of makespan at most C, or returns a feasible schedule of makespan at most ρ C.
It is well-known that a ρ-relaxed decision procedure can be transformed into a polynomial-time ρ-approximation algorithm <cit.> provided that one can compute proper lower and upper bounds to the optimal value of size polynomial in the size of the input.

Given a target makespan C, let 
    γ_j(C) := min{q ∈ℤ_+ f_j(q) ≤ C }
 be the critical speed of job j ∈. Moreover, we define for every i ∈ the sets J^+_i(C) := {j  f(s_i,j)≤ C} and J^-_i(C) := J \ J^+_i(C) to be the set of jobs that can or cannot be processed by i alone within time C, respectively. 
Note that γ_j(C) can be computed in polynomial-time by performing binary search when given oracle access to f_j.
When C is clear from the context, we use the short-hand notation γ_j, J^+_i, and J^-_i instead.
The following technical fact is equivalent to the non-decreasing work property and is used throughout the proofs of this paper:

Let f be a speed-implementable processing time function satisfying the properties of our problem. Then for every speed q ∈ℝ_+ we have that:


  * f(α q) ≤1/α f(q) for every α∈ (0,1), and

  * f(q') ≤q/q' f(q) for every q' ≤ q.



For the first inequality, since α∈ (0,1), it immediately follows that α q ≤ q. By the non-decreasing work property of f, we have that α q f(α q) ≤ q f(q), which implies that f(α q) ≤1/α f(q). The second inequality is just an application of the first by setting α = q'/q∈ (0,1).

For every target makespan C, let r_i,j := max{s_i,j, γ_j(C)}. The following feasibility LP is the starting point of the relaxed decision procedures we construct in this work:


    [LP(C)]:    ∑_i ∈ x_i,j  = 1 , ∀ j ∈
       ∑_j ∈f_j(r_i,j)r_i,j/s_i,j x_i,j≤ C  , ∀ i ∈
       x_i,j≥ 0  ,∀ j ∈, i ∈.



In the above LP, each variable x_i,j can be thought of as the fraction of job j that is assigned to machine i. The equality constraints (<ref>) ensure that each job is fully assigned to a subset of machines, while constraints (<ref>) impose an upper bound to the load of every machine.
Notice that for any job j and machine i such that j ∈ J^+_i(C), it has to be that s_i,j≥γ_j and, thus, for the corresponding coefficient of constraints (<ref>), we have f_j(r_i,j) r_i,j/s_i,j = f_j(s_i,j). Similarly, for any machine i and job j such that j ∈ J^-_i, we have that s_i,j≤γ_j and, thus, f_j(r_i,j) r_i,j/s_i,j = f_j(γ_j) γ_j/s_i,j.

As we prove in the following proposition, the above formulation is feasible for any C that is greater than the optimal makespan.

For every C ≥, where  is the makespan of an optimal schedule, [LP(C)] has a feasible solution.


Fix any feasible schedule of makespan  and let S_j ⊆ be the set of machines allocated to a job j in that schedule. 
For every i ∈,j ∈ set x_i,j = s_i,j/σ_j(S_j) if i ∈ S_j and x_i,j = 0, otherwise. We show that x is a feasible solution to [LP(C)].
Indeed, constraints (<ref>) are satisfied since ∑_i ∈ x_i,j = ∑_i ∈ S_js_i,j/σ_j(S_j) = 1 for all j ∈. 
For verifying that constraints (<ref>) are satisfied, let j ∈ and i ∈ S_j. By definition of S_j, it has to be that σ_j(S_j) ≥ s_i,j and σ_j(S_j) ≥γ_j, which implies that σ_j(S_j) ≥ r_i,j. Therefore, by replacing x_i,j = s_i,j/σ_j(S_j), the corresponding coefficient of (<ref>) becomes: f_j(r_i,j) r_i,j/s_i,js_i,j/σ_j(S_j) = f_j(r_i,j) r_i,j/σ_j(S_j)≤ f_j(S_j), where the last inequality follows by Fact <ref> and the fact that σ_j(S_j) ≥ r_i,j. Using the above analysis, we can see that for any i ∈ we have

    ∑_j ∈f_j(r_i,j) r_i,j/s_i,j x_i,j≤∑_j ∈|  i ∈ S_j  f_j(S_j)≤≤ C .
 


Assuming that C ≥, let x be an extreme point solution to [LP(C)]. We create the assignment graph 𝒢(x) with nodes V := ∪ and edges E := {{i,j}∈× x_i,j>0}, i.e., one edge for each machine-job pair in the support of the LP solution. Notice that 𝒢(x) is bipartite by definition. 
Furthermore, since [LP(C)] is structurally identical to the LP of unrelated machine scheduling <cit.>, the choice of x as an extreme point guarantees the following sparsity property:


<cit.>
For every extreme point solution x of [LP(C)], each connected component of 𝒢(x) contains at most one cycle.

As a graph with at most one cycle is either a tree or a tree plus one edge, the connected components of 𝒢(x) are called pseudotrees and the whole graph is called a pseudoforest.
It is not hard to see that the edges of an undirected pseudoforest can always be oriented in a way that every node has an in-degree of at most one. We call such a 𝒢(x) a properly oriented pseudoforest. Such an orientation can easily be obtained for each connected component as follows: We first orient the edges on the unique cycle (if it exists) consistently (e.g., clockwise) so as to obtain a directed cycle. 
Then, for every node of the cycle that is also connected with nodes outside the cycle, we define a subtree using this node as a root and we direct its edges away from that root (see e.g., Figure <ref>).

Now fix a properly oriented 𝒢(x) with set of oriented edges E̅. For j ∈, we define p(j) ∈ to be its unique parent-machine with (p(j), j) ∈E̅, if it exists, and T(j) = {i ∈ (j,i) ∈E̅} to be the set of children-machines of j, respectively. Notice, that for every machine i, there exists at most one j ∈ such that i ∈ T(j). The decision procedures we construct in this paper are based, unless otherwise stated, on the following scheme:

Algorithm: Given a target makespan C: 


  * If [LP(C)] is feasible, compute an extreme point solution x of [LP(C)] and construct a properly oriented 𝒢(x). (Otherwise, report that C <.)

  * A rounding scheme assigns every job j ∈ either only to its parent machine p(j), or to a subset of its children-machines T(j) (see Section <ref>).

  * According to the rounding, every job j ∈ that has been assigned to T(j) is placed at the beginning of the schedule (these jobs are assigned to disjoint sets of machines).

  * At any point a machine i becomes idle, it processes any unscheduled job j that has been rounded to i such that i = p(j).






§ ROUNDING SCHEMES
 
In each of the following rounding schemes, we are given as an input an extreme point solution x of [LP(C)] and a properly oriented pseudoforest 𝒢(x)=(V, E̅).



 §.§ A simple 4-approximation for unrelated machines



We start from the following simple rounding scheme: For each job j, assign j to its parent-machine p(j) if x_p(j),j≥1/2, or else, assign j to its children-machines T(j).
Formally, let ^(1) := {j ∈ x_p(j),j≥1/2} be the sets of jobs that are assigned to their parent-machines and ^(2) := ∖^(1) the rest of the jobs. Recall that we first run the jobs in ^(2) and then the jobs in ^(1) as described at the end of the previous section.
For i ∈, define J^(1)_i := {j ∈^(1) p(j) = i} and J^(2)_i := {j ∈^(2) i ∈ T(j)} as the sets of jobs in ^(1) and ^(2), respectively, that get assigned to i (note that |J^(2)_i| ≤ 1, as each machine gets assigned at most one job as a child-machine).
Furthermore, let ℓ_i := ∑_j ∈ J_i^(1) f_j(r_i,j) r_i,j/s_i,jx_i,j be the fractional load incurred by jobs in ^(1) on machine i in the LP solution x.


Let i ∈. Then ∑_j ∈ J^(1)_i f_j({i}) ≤ 2ℓ_i.


Let j ∈ J^(1)_i.
Since x_i,j≥1/2 by definition of ^(1), we get f_j(s_i,j) ≤ 2 f_j(s_i,j) x_i,j.
Furthermore, since s_i,j≤max{s_i,j, γ_j} = r_i,j, the by Fact <ref>, we have that f_j({i}) = f_j(s_i,j) ≤ f_j(r_i,j) r_i,j/s_i,j. Thus, by summing up over all jobs in J^(1)_i, we get


    ∑_j ∈ J^(1)_i f_j({i}) ≤ 2 ∑_j ∈ J^(1)_i f_j(r_i,j) r_i,j/s_i,j x_i,j = 2ℓ_i.






Let j ∈^(2). Then f_j(T(j)) ≤ 2C.


We assume that for all i ∈ T(j), s_i,j≤γ_j, since, otherwise, given some i' ∈ T(j) with s_i,j > γ_j, we trivially have that f_j(T(j)) ≤ f_j({i'}) ≤ f_j(γ_j) ≤ C. 

For any i ∈ T(j) and using the fact that r_i,j = γ_j, constraints (<ref>) imply that f_j(γ_j) γ_j/s_i,j x_i,j≤ C for all i ∈ T(j). 
Summing over all these constraints yields ∑_i ∈ T(j)f_j(γ_j)/Cγ_j x_i,j≤σ_i(T(j)).
Using the fact that ∑_i ∈ T(j) x_i,j > 1/2 because j ∈^(2), we get σ_i(T(j)) ≥1/2γ_j f_j(γ_j)/C. By combining this with the fact that f_j(γ_j) ≤ C, by definition of γ_j, and using Fact <ref>, this implies that f_j(T(j)) ≤ 2C.



Clearly, the load of any machine i ∈ in the final schedule is the sum of the load due to the execution of ^(1), plus the processing time of at most one job of ^(2). By Propositions <ref>, <ref> and the fact that ℓ_i ≤ C for all i ∈ by constraints (<ref>), it follows that any feasible solution of [LP(C)] can be rounded in polynomial-time into a feasible schedule of makespan at most 4C.



 §.§ An improved 2e/e-1≈ 3.163-approximation for unrelated machines



In the simple rounding scheme described above, it can be the case that the overall makespan improves by assigning some job j ∈^(2) only to a subset of the machines in T(j). This happens because some machines in T(j) may have significantly higher load from jobs of ^(1) than others, but job j will incur the same additional load to all machines it is assigned to.

We can improve the approximation guarantee of the rounding scheme by taking this effect into account and filtering out children-machines with a high load. Define ^(1) and ^(2) as before. Every job in j ∈ J^(1) is assigned to its parent-machine p(j), while every job j ∈^(2) is assigned to a subset of T(j), as described below.

For j ∈^(2) and θ∈ [0, 1] define S_j(θ) := { i ∈ T(j)  1 - ℓ_i/C≥θ}. Choose θ_j so as to minimize 2(1 - θ_j)C + f_j(S_j(θ_j)) (note that this minimizer can be determined by trying out at most |T(j)| different values for θ_j). 
We then assign each job in j ∈ J^(2) to the machine set S_j(θ_j).



By Proposition <ref>, we know that the total load of each machine i ∈ due to the execution of jobs from ^(1) is at most 2ℓ_i. Recall that there is at most one j ∈ J^(2) with i ∈ T(j). If i ∉ S_j(θ_j), then load of machine i bounded by 2ℓ_i ≤ 2C. If i ∈ S_j(θ_j), then the load of machine i is bounded by
 

    max_i' ∈ S_j(θ_j){2ℓ_i + f_j(S_j(θ_j)) }≤ 2(1 - θ_j)C + f_j(S_j(θ_j)),


where the inequality comes from the fact that 1 - ℓ_i'/C≥θ_j for all i' ∈ S_θ_j. The following proposition gives an upper bound on the RHS of (<ref>) as a result of our filtering technique and proves Theorem <ref>.

For each j ∈^(2), there exists a θ∈ [0,1] such that 2(1- θ)C + f_j(S_j(θ)) ≤2e/e-1 C.


We first assume that for all i ∈ T(j), it is the case that s_i,j≤γ_j and, thus, r_i,j = γ_j. In the opposite case, where there exists some i' ∈ T(j) such that s_i,j > γ_j, by choosing θ = 0, then (<ref>) can be upper bounded by 2C + f_j(S_j(0)) = 2C + f_j(T(j)) ≤ 2C + f_j(s_i',j) ≤ 3C and the proposition follows.

Define α := 2e/e-1. We show that there is a θ∈ [0, 1] with σ_j(S_j(θ)) ≥γ_j f_j(γ_j)/(α + 2 θ -2)C. Notice that, in that case, f_j(S_j(θ)) ≤ (α + 2 θ -2) C by Fact <ref>, implying the lemma.



Define the function g: [0,1] →ℝ_+ by g(θ) := σ_j (S_j(θ)). It is easy to see g is non-increasing integrable and that 
 
    ∫_0^1 g(θ) dθ = ∑_i ∈ T(j) s_i,j (1 - ℓ_i/C).
 
 See Figure <ref> for an illustration.

Now assume by contradiction that g(θ) < γ_j f_j(γ_j)/(α + 2 θ -2)C for all θ∈ [0, 1].
Note that ℓ_i + γ_j f_j(γ_j)/s_i,j x_i,j≤ C for every i ∈ T(j) by constraints (<ref>) and the fact that |J^(2)_i| ≤ 1.
Hence  f_j(γ_j)γ_j/C x_i,j≤ s_i,j(1 - ℓ_i/C) for all i ∈ T(j).
Summing over all i ∈ T(j) and using the fact that ∑_i ∈ T(j) x_i,j≥1/2 because j ∈^(2), we get


    f_j(γ_j)γ_j/2 C   ≤∑_i ∈ T(j) s_i,j (1 - ℓ_i/C) 
       = ∫_0^1 g(θ) dθ
       < f_j(γ_j)γ_j/C∫_0^11/α + 2 θ -2 dθ,


where the last inequality uses the assumption that g(θ) < γ_j f_j(γ_j)/(α + 2 θ_j -2)C for all θ∈ [0,1]. By simplifying the above inequality we get the contradiction


    1 < ∫_α-2^α1/λ dλ = ln(α/α -2) = 1,


which concludes the proof.

By the above analysis, our main result for the case of unrelated machines follows.

*


We can slightly improve the above algorithm by optimizing over the threshold of assigning each job to the parent- or children-machines in the assignment graph (see Appendix <ref> for details). This optimization gives a slightly better approximation guarantee of α = inf_β∈ (0,1){e^1/β - 1/β(e^1/β - 1 - 1)}≈ 3.14619.




The LP-based nature of our techniques allows the design of polynomial-time 𝒪(1)-approximation
algorithms for the objective of minimizing the sum of weighted completion times, i.e., ∑_j ∈ w_j C_j, where w_j is the weight and C_j is the completion time of job j ∈. This can be achieved by using the rounding theorems of this section in combination with the standard technique of interval-indexed formulations <cit.>.




 §.§ A 7/3-approximation for restricted identical machines



We are able to provide an algorithm of improved approximation guarantee for the special case of restricted identical machines. In this case, each job j∈ is associated with a set of machines _j ⊆, such that s_i,j = 1 for i ∈_j and s_i,j = 0, otherwise. Notice that our assumption that f_j(0) = + ∞, ∀ j ∈ implies that, in the restricted identical machines case, every job j has to be scheduled only on the machines of _j.

 

Given a feasible solution to [LP(C)] and a properly oriented 𝒢(x), we define the sets ^(1) := {j ∈ x_p(j),j = 1} and ^(2) := ∖^(1). The rounding scheme for this special case can be described as follows:

    
  * Every job j ∈^(1) is assigned to p(j) (which is the only machine in 𝒢(x) that is assigned to j).
    
  * Every job j ∈^(2)
    
        
  * is assigned to the set T(j) of its children-machines, if |T(j)| = 1 or |T(j)| ≥ 3.
        
  * is assigned to the subset S ⊆ T(j) that results in the minimum makespan over T(j), if |T(j)| = 2. Notice that for |T(j)|=2 there are exactly three such subsets.
    
    
  * As usual, the jobs of ^(2) are placed at the beginning of the schedule, followed by the jobs of ^(1).



Clearly, by definition of our algorithm, constraints (<ref>) and the fact that f_j(1) ≤ f_j(γ_j) γ_j for all j ∈, the load of any machine that only processes jobs of ^(1) is at most C. Therefore, we focus our analysis on the case of machines that process jobs from ^(2). Recall, that every machine i ∈ can process at most one job j ∈^(2) and, thus, the rest of the proof is based on analyzing the makespan of the machines of T(j), for each j ∈^(2). 



 
Any job j ∈^(2) can be assigned to the set T(j) with processing time most |T(j)| + 1/|T(j)| C.


Fix any job j ∈^(2). By summing over the constraints (<ref>) for i ∈ T(j) ∪{p(j)} (every machine in the support of j) and using constraints (<ref>), we have that γ_j f_j(γ_j) ≤ (|T_j|+1) C. By applying Fact <ref> and the non-increasing property of f_j, we have that: 


    f_j(|T(j)|)    ≤|T(j)| + 1/|T(j)| f_j(|T(j)| + 1) 
       ≤|T(j)| + 1/|T(j)| f_j(f_j(γ_j)/Cγ_j) 
       ≤|T(j)| + 1/|T(j)|C/f_j(γ_j) f_j(γ_j) 
       ≤|T(j)| + 1/|T(j)| C.



Taking into account that for any machine i ∈, the load due to the jobs of ^(1) is at most C, the above proposition gives a makespan of at most (1 + 4/3)C, for the machines T(j) of every job j ∈^(2) such that |T(j)| ≥ 3. The cases where |T(j)| ∈{1,2} need a more delicate treatment. For any i ∈ T(j), let ℓ_i := ∑_j' ∈^(1) | p(j') = i f_j'(1) ≤ C to be the load of i w.r.t. the jobs of ^(1).

For any job j ∈^(2) with |T(j)| = 1 that is assigned to its unique child i ∈ T(j), the total load of i is at most 2 C.


Consider a job j ∈^(2) of critical speed γ_j, such that |T(j)| = 1, and let i be the unique child-machine in T(j). By our assumption that i ∈_j and the fact that γ_j ≥ 1, we have that r_i,j = γ_i,j. By constraints (<ref>) of [LP(C)], it is the case that ℓ_i + γ_j f_j(γ_j) x_i,j≤ C. Therefore, since our algorithm assigns job j to i, the load of the latter becomes: ℓ_i + f_j(1) ≤ℓ_i + γ_j f_j(γ_j)x_i,j + γ_j f_j(γ_j)(1-x_i,j) ≤ C + γ_j f_j(γ_j)x_p(j),j, where we used the fact that f_j(1) ≤γ_j f_j(γ_j) and that x_i,j + x_p(j),j = 1 by constraints (<ref>). However, by constraints (<ref>) for p(j) ∈, we can see that γ_j f_j(γ_j)x_p(j),j≤ C, which completes the proof.



Consider any job j ∈^(2) with |T(j)| = 2 that is assigned to the subset S ⊆ T(j) that results in the minimum load. The load of any machine i ∈ S is at most 9/4C.


We first notice that for the case where γ_j ≤ |T(j)| = 2, by assigning j to all the machines of T(j), the total load of any i ∈ T(j) is at most: ℓ_i + f_j(T(j)) ≤ℓ_i + f_j(γ_j) ≤ 2C, by constraints (<ref>). Therefore, we focus on the case where γ_j ≥ 3 (since we assume that γ_j is an integer). For the machines of T(j), denoted by T(j) = {i_1,i_2 }, we assume w.l.o.g. that x_i_1,j≥ x_i_2,j. 

Our algorithm attempts to schedule j on the sets S_1 = {i_1}, S_2 = {i_2} and S_B = {i_1, i_2} and returns the assignment of minimum makespan. We can express the maximum load of T(j) in the resulting schedule as:
 

    min{ f_j(1) + ℓ_i_1, f_j(1) + ℓ_i_2, f_j(2) + max{ℓ_i_1, ℓ_i_2}}
       ≤ C+min{ f_j(1) - γ_j f_j(γ_j)x_i_1,j, f_j(1) - γ_j f_j(γ_j)x_i_2,j, f_j(2) +γ_j f_j(γ_j) max{- x_i_1,j, -x_i_2,j}}
       ≤  C + min{f_j(1) - γ_j f_j(γ_j) x_i_1,j, f_j(2) - γ_j f_j(γ_j) x_i_2,j}
       ≤ C + 1/2( f_j(1) +  f_j(2) - γ_j f_j(γ_j) (x_i_1,j + x_i_2,j) ) 
       = C + 1/2( f_j(1) +  f_j(2) - γ_j f_j(γ_j) (1 - x_p(j),i) ) ,

 
where the first inequality follows by the fact that ℓ_i ≤ C - γ_j f_j(γ_j)x_i,j, by constraints (<ref>). Furthermore, the second inequality follows by the assumption that x_i_1,j≥ x_i_2,j, while the third inequality follows by balancing the two terms of the minimization. Finally the equality follows by the fact that x_i_1,j + x_i_2,j = 1 - x_p(j),j, by constraints (<ref>).

By constraints (<ref>), we get that x_p(j),j≤C/γ_j f_j(γ_j), while by Fact <ref> we have that: γ_j f_j(γ_j) ≥ f_j(1), given that γ_j ≥ 3. Moreover, by Fact <ref>, we have that f_j(2) ≤3/2 C, using the analysis of Proposition <ref>. By combining the above, we get that 
 

    (<ref>)   ≤ C + 1/2( f_j(1) +  f_j(2)  - γ_j f_j(γ_j) +  γ_j f_j(γ_j) x_p(j),i) ) 
       ≤ C + 1/2(  f_j(1) +  f_j(2) -  f_j(1) + C ) 
       ≤9/4 C.

 

By considering the worst of the above scenarios, we can verify that the makespan of the produced schedule is at most 7/3 C, thus, leading to the following theorem.

*




 §.§ A 3-approximation for uniform machines



We prove an algorithm of improved approximation guarantee for the special case of uniform machines, namely, every machine i ∈ is associated with a unique speed s_i, such that s_i,j = s_i for all j ∈. Given a target makespan C, we say that a machine i is j-fast for a job j ∈ if f_j({i}) ≤ C, while we say that i is j-slow otherwise. 
As opposed to the previous cases, the rounding for the uniform case starts by transforming the feasible solution of [LP(C)] into another extreme point solution that satisfies a useful structural property, as described in the following proposition:

propositionrestatePropositionUniform
There exists an extreme point solution x of [LP(C)] that satisfies the following property: For each j ∈ there is at most one j-slow machine i ∈ such that x_i,j > 0 and x_i,j' > 0 for some job j' ≠ j. Furthermore, this machine, if it exists, is the slowest machine that j is assigned to.


Consider a job j and two j-slow machines i_1, i_2 ∈, such that x_i_1,j, x_i_2,j > 0.
Let also two jobs j_1, j_2 ∈, other than j, such that x_i_1, j_1>0 and x_i_2, j_2>0, assuming w.l.o.g. that s_i_2≥ s_i_1. We emphasize the fact j_1 and j_2 can correspond to the same job.
Recall that for any job j' and machine i', we have that r_i',j' = γ_j', if i' is j'-slow, and r_i',j' = s_i',j', if i' is j'-fast. 

We show that we can transform this solution into a new extreme point solution x' such that one of the following is true: (a) j is no longer supported by i_1 (i.e. x'_i_1,j = 0), or (b) j_2 is no longer supported by i_2 (i.e. x'_i_2,j_2 = 0) and x'_i_1,j_2 = x_i_1,j_2 +  x_i_2,j_2. 
Let a_i',j' be the coefficient of x_i',j' in the LHS of (<ref>) for some machine i' and job j'.
Since i_1,i_2 are j-slow machines, it is the case that 

    a_i_1,j = f_j(γ_j)γ_j/s_i_1≥ f_j(γ_j)γ_j/s_i_2 = a_i_2,j.

Suppose that we transfer an ϵ >0 mass from x_i_1,j to x_i_2,j (without violating constraints (<ref>)). Then the load of i_1 decreases by Δ_- = ϵ f_j(γ_j)γ_j/s_i_1, while the load of i_2 increases by Δ_+ = ϵ f_j(γ_j)γ_j/s_i_2. 
In order to avoid the violation of constraints (<ref>), we also transfer an ϵ_2 mass from x_i_2,j_2 to x_i_1,j_2, such that: 
ϵ_2 a_i_2,j_2 = Δ_+, i.e. ϵ_2 = ϵ1/a_i_2,j_2  f_j(γ_j)γ_j/s_i_2, given that any coefficients a_i',j' is strictly positive. Clearly, constraints (<ref>) for i_2 are satisfied since the fractional load of the machine stays the same as in the initial feasible solution. 
It suffices to verify that constraints (<ref>) for i_1 are also satisfied. 
Indeed, the difference in the load of i_1 that results from the above transformation can be expressed as ϵ_2 a_i_1,j_2 - Δ_-. 
However, it is the case that: 


    ϵ_2 a_i_1,j_2   = ϵa_i_1,j_2/a_i_2,j_2  f_j(γ_j)γ_j/s_i_2
       ≤ϵs_i_2/s_i_1  f_j(γ_j)γ_j/s_i_2 = ϵ f_j(γ_j)γ_j/s_i_1 = Δ_-


and therefore, constraint (<ref>) of i_1 remains feasible as the load difference is non-positive. 

In the last inequality, we used the fact that a_i_1,j_2/a_i_2,j_2≤s_i_2/s_i_1, which can be proved by case analysis: 

(i) If both i_1,i_2 are j_2-slow, then clearly 
    a_i_1,j_2/a_i_2,j_2 = f_j(γ_j_2) γ_j_2 / s_i_1/f_j(γ_j_2) γ_j_2 /s_i_2  =  s_i_2/s_i_1.


(ii) if i_2 is j_2-fast and i_1 is j_2-slow, we have that: 
    a_i_1,j_2/a_i_2,j_2 = f_j(γ_j_2) γ_j_2/s_i_1/f_j_2(s_i_2)≤s_i_2/s_i_1,
 since by Fact <ref>, we have that f_j_2(s_i_2) ≥ f_j(γ_j_2) γ_j_2/s_i_2. 

(iii) If both i_1,i_2 are j_2-fast, then 
    a_i_1,j_2/a_i_2,j_2 = f_j_2(s_i_1)/f_j_2(s_i_2)≤s_i_2/s_i_1,
 which follows by Fact <ref> and the fact that s_i_2≥ s_i_1.  


By the above analysis, we can keep exchanging mass in the aforementioned way until either x_i_1,j or x_i_2, j_2 becomes zero. In any case, job j shares at most one of i_1 and i_2 with another job, the above process. 
Notice that the above transformation always returns a basic feasible solution and reduces the total number of shared j-slow machines for a job j by one. Therefore, by applying the transformation at most ||+|| times, one can get a basic feasible solution that satisfies the required property. Finally, by the same argument it follows that for any job j ∈ that shares a j-slow machine i_j with other jobs, then i_j is the slowest that j is assigned to. In the opposite case, assuming that there is another j-slow machine i' such that s_i_j > s_i', repeated application of the above transformation would either move the total x_i',j mass from i' to i_j, or replace the assignment of all the shared jobs from i_j to i'.





Let x be an extreme point solution of [LP(C)] that satisfies the property of Proposition <ref> and let 𝒢(x) a properly oriented pseudoforest. By the above proposition, each job j has at most three types of assignments in 𝒢(x), regarding its set T(j) of children-machines: (i) j-fast machines F_j ⊆ T(j), (ii) exclusive j-slow machines D_j ⊆ T(j), i.e. j-slow machines that are completely assigned to j, and (iii) at most one shared j-slow machine i_j∈ T(j) (which is the slowest machine that j is assigned to).

We now describe the rounding scheme for the special case of uniform machines.


    
  * For any job j ∈ such that x_p(j),j≥1/2, j is assigned to its parent-machine p(j).
    
  * For any job j ∈ such that such that x_p(j),j < 1/2, j is assigned to a subset S ⊆ T(j), according to the following rule:
        
            
  * If F_j ≠∅, assign j to any i ∈ F_j, 
            
  * else if σ_j(D_j) ≥r_i,j f_j(r_i,j)/3 C, then assign j only to the machines of D_j (but not to the shared i_j). 
            
  * In any other case, j is assigned to D_j ∪{i_j}. 
        
    
  * As usual, the jobs that are assigned to more than one machines are placed at the beginning of the schedule, followed by the rest of the jobs.


Let ^(1) be the set of jobs that are assigned by the algorithm to their parent-machines and ^(2) = ∖^(1) be the rest of the jobs. 
By using the same analysis as in Proposition <ref>, we can see that the total load of any machine i ∈ that processes only jobs from ^(1) is at most 2C.
Since any machine can process at most one job from ^(2), it suffices to focus on the makespan of the set T(j) for any job j ∈^(2).

Clearly, for the case <ref>, the processing time of a job j on any machine i ∈ F_j is at most C, which, in combination with Proposition <ref>, gives a total load of at most 3C. 
Moreover, for the case <ref>, where a job j is scheduled on the machines of D_j ⊆ T(j), the total load of every i ∈ D_j is at most 3C. This follows by a simple application of Fact <ref>, since σ_j(D_j) ≥r_i,j f_j(r_i,j)/3 C≥γ_j f_j(γ_j)/3 C, and the fact that the machines of D_j are exclusively assigned to j. 

Finally, consider case <ref> of the algorithm, where σ_j(D_j) < r_i,j f_j(r_i,j)/3 C and j is scheduled on (D_j ∪{i_j}). By constraints (<ref>) and the fact that x_i_j, j + ∑_i ∈ D_j x_i,j > 1/2, it follows that σ_j(D_j∪{i_j}) ≥ f_j(r_i,j) r_i,j/2 C, which by Fact <ref> implies that f_j(D_j∪{i_j}) ≤ 2C. Notice that the above analysis implies the existence of a shared i_j machine, if the time the algorithm reaches case <ref>.


In order to complete the proof, it suffices to show that the load of the machine i_j (i.e. the only machine of T(j) that is shared with other jobs of ^(1)) is at most C. 
Let ℓ_i = ∑_j' ∈^(1)|i=p(j) f(r_i,j') r_i,j'/s_i,j' x_i,j' be the fractional load of a machine i due to the jobs of ^(1). 
Clearly, if i_j is the only child-machine of j, then it has to be that x_i_j,j>1/2 and the total load of i_j after the rounding is at most 2 ℓ_i_j + f_j(s_i_j) ≤ 2 ℓ_i + 2  f_j(s_i_j) x_i_j,j≤ 2 ℓ_i + 2  f_j(r_i,j) r_i,j/s_i_j x_i_j,j≤ 2C, using Proposition <ref> and Fact <ref>. 
Assuming that D_j ≠∅, by summing over constraints (<ref>) for all i ∈ D_j and using the fact that σ_j(D_j) < r_i,j f_j(r_i,j)/3 C, we get that ∑_i ∈ D_j x_i,j < 1/3. Therefore, combining this with the fact that x_i_j,j + ∑_i ∈ D_j x_i,j > 1/2, we conclude that x_i_j,j > 1/6. 
Now, for the fractional load ℓ_i_j of i_j due to the jobs of ^(1), by constraints (<ref>), we have that ℓ_i ≤ C - f_j(r_i,j) r_i,j/s_i_j x_i_j,j≤ C - f_j(r_i,j) 3 r_i,j C/6 r_i,j f_j(r_i,j)≤C/2, where we used that x_i_j,j > 1/6 and the fact that i_j is the smallest machine in T(j) and, thus, s_i_j≤σ_j (D_j) < r_i,j f_j(r_i,j)/3 C. By Proposition <ref>, the load of i_j due to the jobs of ^(1) after the rounding is at most 2 ℓ_i_j≤ C. Therefore, in every case, the load of any machine i ∈ T(j) for all j ∈^(2) is at most 3C, which leads to the following theorem.

* 



§ EXTENSION: SPARSE ALLOCATIONS VIA P-NORM REGULARIZATION


In the model of speed-implementable processing time functions, each function f_j(S) depends on the total additive speed, yet is oblivious to the actual number of allocated machines. However, the overhead incurred by the synchronization of physical machines naturally depends on their number. In this section, we study an extension of the speed-implementable malleable model, that captures the impact of the cardinality of a set of machines through the notion of effective speed. In this setting, every job j is associated with a speed regularizer p_j ≥ 1, while the total speed of a set S ⊆ is given by: σ^(p_j)_j(S) = ( ∑_i ∈ S s^p_j_i,j)^1/p_j. For simplicity, we assume that every job has the same speed regularizer.

Clearly, the choice of p controls the effect of the cardinality of a set to the resulting speed of an allocation, given that as p increases a sparse (small cardinality) set has higher effective speed than a non-sparse set of the same total speed. Notice that for p = 1, we recover the standard case of additive speeds, while for p →∞, parallelization is no longer helpful as lim_p →∞σ^(p)_j(S) = max_i ∈ S{s_i,j}. As before, the processing time functions satisfy the standard properties of malleable scheduling, i.e., f_j(s) is non-increasing while f_j(s) · s is non-decreasing in the total allocated speed.
For simplicity of presentation we assume that all jobs have the same regularizer p, i.e., p = p_j, ∀ j ∈, but we comment on the case of job-dependent regularizers at the end of this section.

Quite surprisingly, we can easily modify the algorithms of the previous section in order to capture the above generalization. Given a target makespan C, we start from a new feasibility program [LP^(p)(C)], which is given by constraints (<ref>), (<ref>) of [LP(C)], combined with: 



    ∑_j ∈ f_j(r_i,j) ( r_i,j/s_i,j)^p x_i,j≤ C, ∀ i ∈.


Note that γ_j(C) and r_i,j = max{γ_j(C),s_i,j} are defined exactly as before. As we can see, the only difference between [LP(C)] and [LP^(p)(C)] is that we replace each coefficient f_j(r_i,j)r_i,j/s_i,j with ( f_j(r_i,j) r_i,j/s_i,j)^p in constraints (<ref>) of the former. As we show in the following proposition, for any C ≥, where  is the makespan of an optimal schedule, [LP^(p)(C)] has a feasible solution.


For every C ≥, where  is the makespan of an optimal schedule, [LP^(p)(C)] has a feasible solution.


Consider an optimal solution of makespan , where every job j is assigned to a subset of the available machines S_j ⊆. Setting x_i,j = s^p_i,j/σ^p_j(S_j) if i ∈ S_j and x_i,j = 0, otherwise, we get a feasible solution that satisfies inequalities (<ref>), (<ref>), (<ref>). Indeed, for constraints (<ref>) we have ∑_i ∈ x_i,j = ∑_i ∈ S_js^p_i,j/(σ^(p)_j(S_j))^p = 1. Moreover, for every i ∈ S_j and j ∈, it is true that:


    f_j(r_i,j) ( r_i,j/s_i,j)^p x_i,j   = f_j(r_i,j)  ( r_i,j/s_i,j)^p (s_i,j/σ^(p)_j(S_j))^p 
       ≤(r_i,j/σ^(p)_j(S_j))^p f_j(r_i,j) 
       ≤(r_i,j/σ^(p)_j(S_j))^p-1 f_j(S_j) 
       ≤ f_j(S_j),


where in the second inequality, we use Fact <ref>, since r_i,j = max{s_i,j, γ_j(C)}≤σ^(p)_j(S_j). Moreover, we use the fact that r_i,j/σ^(p)_j(S_j)≤ 1 for all j ∈ and i ∈ S_j. 
By the above analysis, we can see that constraints (<ref>) are satisfied, since for all i ∈, we have: 


    ∑_j ∈ f_j(r_i,j) ( r_i,j/s_i,j)^p x_i,j≤∑_j ∈ J| i ∈ S_j  f_j(S_j) ≤≤ C.





The algorithm for this setting is similar to the one of the standard case (see Section <ref>) and is based on rounding a feasible extreme point solution of [LP^(p)(C)]. Moreover, the rounding scheme is a parameterized version of the simple rounding of Section <ref>, with the difference that the threshold parameter β∈ [0,1] (i.e., the parameter that controls the decision of assigning a job j to either p(j) or T(j)) is not necessarily 1/2. In short, given a pseudoforest 𝒢(x) on the support of a feasible solution x, the rounding scheme assigns any job j to p(j) if x_p(j),j≥β, or to T(j), otherwise.


Any feasible solution of  [LP^(p)(C)] can be rounded in polynomial-time into a feasible schedule of makespan at most ( 1/β + 1/(1-β)^1/p)C.


In order to prove the upper bound on the makespan of the produced schedule, we work similarly to the proof of Section <ref>.
Let ^(1) be the set of jobs that are assigned by our algorithm to their parent-machine and let ^(2) = ∖^(1) be the rest of the jobs. 


We first show that the total load of any machine i ∈ incurred by the jobs of ^(1) is at most 1/βC. By definition of our algorithm, for every job j ∈^(1) that is assigned to some machine i, it holds that x_i,j≥β. For the load of any machine i ∈ in the rounded schedule that corresponds to jobs of ^(1), we have: 


    ∑_j ∈^(1)|i = p(j) f_j(s_i,j)    = 1/β∑_j ∈^(1)|i = p(j) f_j(s_i,j) β
       ≤1/β∑_j ∈^(1)|i = p(j) f_j(s_i,j) x_i,j
       ≤1/β∑_j ∈^(1)|i = p(j) f_j(r_i,j) r_i,j/s_i,j x_i,j
       ≤1/β∑_j ∈^(1)|i = p(j) f_j(r_i,j) (r_i,j/s_i,j)^p x_i,j
       ≤1/β C,


where the second inequality follows by Fact <ref>, given that s_i,j≤ r_i,j. Moreover, the third inequality follows by the fact that r_i,j/s_i,j≥ 1 and, thus, r_i,j/s_i,j≤(r_i,j/s_i,j)^p. Finally, the last inequality follows by constraints (<ref>). 



The next step is to prove that every job j ∈^(2) has a processing time of at most (1/1-β)^1/p C. By definition of the algorithm, for any j∈^(2) it is the case that ∑_i ∈ T(j) x_i,j > 1-β. 
First notice that for any j ∈^(2) and i ∈ T(j), by constraints (<ref>), we have that f_j(r_i,j) ( r_i,j/s_i,j)^p x_i,j≤ C, which is equivalent to f_j(r_i,j)  r_i,j^p x_i,j≤ s_i,j^p C. By summing the previous inequalities over all machines i ∈ T(j), for any job j ∈^(2), we get: 



    (1-β) f_j(r_i,j)  r_i,j^p    ≤ f_j(r_i,j)  r_i,j^p ∑_i ∈ T(j)x_i,j
       ≤(σ^(p)_j(T(j)))^p C.


By the above analysis, we get that (σ^(p)_j(T(j)))^p ≥(1-β) f_j(r_i,j)/C r_i,j^p and, thus, 


    σ^(p)_j(T(j))    ≥((1-β) f_j(r_i,j)/C)^1/pr_i,j
       ≥((1-β) f_j(r_i,j)/C)^1/pγ_j,


where the last inequality follows by definition of r_i,j. Finally, by using Fact <ref> and the fact that ( C/f_j(γ_j))^1/p≤C/f_j(γ_j) since p ≥ 1, we get that f_j(σ^(p)_j(T(j)) ≤(1/1-β)^1/p C. As previously, the proof of the proposition follows by the fact that, by definition of our algorithm, each machine i ∈ processes at most one job from ^(2).


It is not hard to see that, given p, the algorithm can initially compute a threshold β∈ [0,1] that minimizes the above theoretical bound. Clearly, for p=1 the minimizer of the expression is β = 1/2, yielding the 4-approximation of the standard case, while for p → +∞ one can verify that β→ 1 and:


    lim_p → +∞inf_β∈ [0,1]( 1/β + 1/(1-β)^1/p) = 2.

 As expected, for the limit case where p → +∞, our algorithm converges to the well-known algorithm by Lenstra et al. <cit.>, given that our problem becomes non-malleable. By using the standard approximation β = 1 - ln (p)/p for p ≥ 2, the following theorem follows directly.

Any feasible solution of [LP^(p)(C)] for p ≥ 2 can be rounded in polynomial-time into a feasible schedule of makespan at most (p/p- ln (p) + √(p/ln(p)))C.

Note that an analogous approach can handle the case where jobs have different regularizers, with the approximation ratio for this scenario determined by the smallest regularizer that appears in the instance (note that the approximation factor is always at most 4).




§ HARDNESS RESULTS AND INTEGRALITY GAPS

We are able to prove a hardness of approximation result for the case of scheduling malleable jobs on unrelated machines. 

*

Following a similar construction as in <cit.> for the case of splittable jobs, we prove the APX-hardness of the malleable scheduling problem on unrelated machines by providing a reduction from the max-k-cover problem: Given a universe of elements 𝒰={e_1, … , e_m} and a family of subsets S_1,…, S_n ⊆𝒰, find k sets that maximize the number of covered elements, namely, maximize {| ⋃_i ∈ I S_i |  I ⊂ [n], |I| = k}. In <cit.>, Feige shows that it is NP-hard to distinguish between instances such that all elements can be covered with k disjoint sets and instances where no k sets can cover more than a (1 - 1/e ) + ϵ' fraction of the elements, for any ϵ' > 0. In addition, the same hardness result holds for instances where all sets have the same cardinality, namely m/k. Note that in the following reduction, while we allow for simplicity the speeds to take rational values, the proof stays valid under appropriate scaling.

Given a max-k-cover instance, where each set has cardinality m/k, we construct an instance of our problem in polynomial time as follows: We consider n jobs, one for each set S_j, and we define the processing time of each job to be f_j(S) = max{1/σ_j(S), 1}. It is not hard to verify that f_j(S) is non-increasing and σ_j(S)f_j(S) is non-decreasing in the total allocated speed. We consider a set 𝒫 of n-k common-machines, such that s_i,j = 1 for j ∈ and i ∈𝒫. Moreover, for every element e, we consider an element-machine i_e such that s_i_e,j = k/m if e ∈ S_j and s_i_e,j = 0, otherwise. In the following, we fix ϵ>0 such that 1/1-1/e + ϵ' = e/e-1 - ϵ.



Consider the case where all elements can be covered by k disjoint sets. Let 𝒞 be the family of sets in a cover. In that case, we can assign to each job j such that S_j ∈𝒞 the element-machines that correspond to S_j. Clearly, every such job allocates m/k machines of speed s_i,j = k/m, thus, receiving a total speed of one. The rest of the n-k jobs, can be equally distributed to the n-k common-machines, yielding a total makespan of = 1. 
On the other hand, consider the case where no k sets can cover more than a (1 - 1/e ) + ϵ' fraction of the elements. In this case, we can choose any n-k jobs and assign them to the common-machines with processing time exactly 1. Notice that since f_j(S) ≥ 1, every (common- or element-) machine can be allocated to at most one job (otherwise the makespan becomes at least 2). Given that exactly n-k jobs are scheduled on the common machines, we have k jobs to be scheduled on the m element-machines. Aiming for a schedule of makespan at most e/e-1 - ϵ, each of the k jobs that are processed by the element-machines should allocate at least 1-1/e + ϵ' speed, that is, at least m/k(1-1/e + ϵ') element-machines. Therefore, we need at least m (1 - 1/e + ϵ') machines in order to schedule the rest of the jobs within makespan e/e-1 - ϵ. However, by assumption on the instance of the max-k-cover, for any choice of k sets, at most (1 - 1/e + ϵ') m machines can contribute non-zero speed, which leads to a contradiction. Therefore, given a (e/e-1 - ϵ)-approximation algorithm for the problem of scheduling malleable jobs on unrelated machines, we could distinguish between the two cases in polynomial-time.


Notice that the above lower bound e/e-1 is strictly larger than the well-known 1.5-hardness for the standard (non-malleable) scheduling problem on unrelated machines. To further support the fact that the malleable version of the problem is harder than its non-malleable counterpart, we provide a pseudopolynomial transformation of the latter to malleable scheduling with speed-implementable processing times. 


There exists a pseudopolynomial transformation of the standard problem of makespan minimization on unrelated machines to the problem of malleable scheduling with speed-implementable processing times.


Consider an instance of the problem of scheduling non-malleable jobs on unrelated machines. We are given a set of machines  and a set of jobs  as well as processing times p_i,j∈ℤ_+ for each i ∈ and each j ∈, with the goal of finding an assignment minimizing the makespan.
We create an equivalent instance of malleable scheduling on unrelated machines on the same set of machines and jobs by defining the processing time functions and speeds as follows:
Let p_max := max_i ∈, j ∈ p_i,j.
For j ∈ define f_j(s) := p_max s^-1/p_max|||| and for each i ∈ define s_i,j := (p_max/p_i,j)^p_max||||.

Note that f_j({i}) = p_i,j. 
Furthermore it is easy to verify that the functions f_j fulfill the monotonic workload requirement and that 
f_j(S) > min_i ∈ S p_i, j - 1/||
for any S ⊆.
Therefore, any solution to the non-malleable problem corresponds to a solution of the malleable problem with the same makespan by running each job on the single machine it is assigned to.
Conversely, any solution to the malleable problem induces a solution of the non-malleable problem by running each job only on the fastest machine it is assigned to, increasing the makespan by less than 1. Since the optimal makespan of the non-malleable instance is integer, an optimal solution of the malleable instance induces an optimal solution of the non-malleable instance.

Note that the encoding lengths of the speed values are pseudopolynomial in the size of the encoding of the original instance. However, by applying standard rounding techniques to the original instance, we can ensure that the constructed instance has polynomial size in trade for a mild loss of precision. 

Notice that the above reduction can be rendered polynomial by standard techniques, preserving approximation factors with a loss of 1+ε. Finally, a simpler version of the above reduction becomes polynomial in the strong sense in the case of restricted identical machines. In brief, for any job j ∈, we define f_j(s) = p_j max{1/s,1}, where p_j is the processing time of the job in the non-malleable instance. Moreover, we set s_i,j = 1 for any job j that can be executed on machine i and s_i,j = 0, otherwise. 

From the side of algorithmic design, we are able to show the following lower bounds on the integrality gap of [LP(C)] for each of the variants we consider:


The integrality gap of [LP(C)] in the case of unrelated machines is lower bounded by 1+ φ≈ 2.618.


The instance establishing the lower bound follows a similar construction as in <cit.>.
Note that while in the following proof we allow speeds to take non-integer values, the result also holds for integer-valued speeds under appropriate scaling of the processing time functions. 
We consider a set = ' ∪{ĵ} of 2k+1 jobs to be scheduled on a set = _A ∪_B of machines. The set ' contains 2k jobs, each of processing time f_j(s) = max{1/s,φ/2}, where s is the total allocated speed, and these jobs are partitioned into k groups of two, J_ℓ for ℓ∈ [k]. Every group J_ℓ of two jobs, is associated with a machine i^A_ℓ such that s_i^A_ℓ,j = 2/φ for all j ∈ J_ℓ and s_i^A_ℓ,j = 0, otherwise. Let _A be the set of these machines and note that |_A| = k. Moreover, every job of ' is associated with a dedicated machine i^B_j such that s_i^B_j, j = 2 - φ, only for job j and s_i^B_j, j' = 0, otherwise. Let _B be the set of these machines. Finally, job ĵ has processing time f_ĵ(s) = max{1/s, 1}, while s_i,ĵ = 1 for all i ∈_A and s_i,ĵ = 0 for all i ∈_B.

In the above setting, it is not hard to verify that the makespan of an optimal solution is = 1+φ. Specifically, job ĵ uses exactly one machine of _A to be executed, given that additional machines cannot decrease its processing time. Let î∈_A be that machine and let J_ℓ̂ = {ĵ_̂1̂, ĵ_̂2̂} be the group of two jobs that is associated with î. Clearly, if at least one of ĵ_̂1̂ and ĵ_̂2̂ is scheduled only on its dedicated machine it is the case that f_ĵ_̂1̂(2-φ) = f_ĵ_̂2̂(2-φ) = 1/2 - φ = 1 + φ. On the other hand, if both ĵ_̂1̂ and ĵ_̂2̂ make use of their î, then the load of î is at least 1 + φ.

Consider the following solution of [LP(C)] for C = 1 + 1/k. Notice that for C = 1 + 1/k and k ≥ 1, we have that γ_j = ⌈1/C⌉ = ⌈k/k+1⌉ = 1 for any j ∈' and γ_ĵ = ⌈1/C⌉ = 1. Therefore, for any j ∈', we have r_i,j = max{γ_j, s_i,j} = 2/φ, ∀ i ∈_A and r_i,j = 1, ∀ i ∈_B. Finally, we have r_i,ĵ = 1, ∀ i ∈_A ∪_B.


For each job j ∈ that belongs to the group J_ℓ, we set x_i^A_ℓ,j = 1/φ for the assignment of j to its corresponding machine in _A and x_i^B_j,j = φ - 1/φ for the assignment to its dedicated machine of _B. Moreover, we set x_i, ĵ = 1/k for every i ∈_A. Notice that, for this assignment, constraints (<ref>) and (<ref>) are trivially satisfied. 

For verifying constraints (<ref>), for any machine i ∈_A with corresponding jobs j_1,j_2 ∈', we have:


    f_ĵ(r_i,ĵ)r_i,ĵ/s_i,ĵ x_i,ĵ   + f_j_1(r_i,j_1)r_i,j_1/s_i,j_1 x_i,j_1 + f_j_2(r_i,j_2)r_i,j_2/s_i,j_2 x_i,j_2
       = x_i,ĵ + φ/2 x_i,j_1 + φ/2 x_i,j_2
       = 1/k + 1 = C.


Finally, for any machine i ∈_B dedicated to a job j ∈', we have that:


    f_j(r_i,j)r_i,j/s_i,j x_i,j = 1/2-φ x_i,j = φ - 1/φ(2-φ) = 1 ≤ C,


where the last equality holds for number φ. Given the above construction, for k →∞, there exists an instance such that the integrality gap of [LP(C)] is at least 1 + φ, since:


    lim_k→∞/C = lim_k→∞1 + φ/1 + 1/k = 1 + φ≈ 2.618.





The integrality gap of [LP(C)] in the case of restricted identical machines is lower bounded by 2.


We consider a set  of k identical jobs, each of processing time f_j(s) = max{2/s , 1}, where s is the total allocated speed. It is not hard to verify that f_j is monotone non-increasing, while its work s max{2/s , 1} = max{2 , s} is non-decreasing. Every job i can be executed on a dedicated machine, let i_j, while there exists a common pool of k-1 machines 𝒫 that can be used by any job. Recall that in the restricted assignment case, every feasible pair (i,j) has unit speed. Clearly, the optimal makespan of the above family of instances for k ≥ 1 is = 2, since there exists at least one job that must be executed only on its dedicated machine. Assuming this is not the case, it has to be that exactly k jobs make use of the common pool of k-1 machines, which, by pigeonhole principle, cannot happen within a makespan of at least = 2. 

Consider the following solution of [LP(C)], for C = 2k/2k-1∈ (1,2): We set x_i_j,j = k/2k-1 for the assignment of each job to its dedicated machine and x_i,j = 1/2k-1 for every j ∈ and i ∈𝒫. According to this assignment, for every job j ∈ we have that γ_j = ⌈2/C⌉ = 1, while for any machine i we have r_i,j = max{s_i,j, γ_j} = 1. Therefore, for the dedicated machine of each job j, constraint (<ref>) corresponding to i_j is satisfied with equality since: f_j(r_i,j) r_i,j x_i_j,j = 2 x_i_j,j = 2k/2k-1 = C. Moreover, for any machine i ∈𝒫, constraints (<ref>) are also satisfied with equality, since,  ∑_j ∈ f_j(r_i,j) r_i,j x_i,j = 2k 1/2k-1 = C. Notice, that the above assignment satisfies constraints (<ref>) and (<ref>). According to the above construction, for k →∞, there exists an instance such that the integrality gap of [LP(C)] is at least 2, since:


    lim_k→∞/C = lim_k→∞ 2 (1 - 1/2k) = 2.

 
Finally, it is not hard to verify that C = 2k/2k-1 is the smallest C such that [LP(C)] is feasible. Indeed, by summing over constraints (<ref>), we get that 
    k = ∑_j∈(x_i_j, j + ∑_i ∈𝒫 x_i,j) ≤ kC/2 + (k-1) C/2≤ (k - 1/2)C,
 where the first inequality follows by constraints (<ref>).



The integrality gap of [LP(C)] in the case of uniform machines is lower bounded by 2.


We consider a set  of 2k+1 identical jobs, each of processing time f_j(s) = max{2/s , 1}, where s is the total allocated speed. It is not hard to verify that f_j is monotone non-increasing and has non-decreasing work. Moreover, we consider a set ℳ_S of 2k slow machines of speed s_i = 1 for all i ∈ℳ_S and a set ℳ_F of k fast machines of speed s_i = 2 for all i ∈ℳ_F. Clearly, the optimal makespan of the above family of instances for k ≥ 1 is = 2. By construction of the instance, the optimal makespan is always an integer number. Assuming that = 1, it has to be that every fast machine process at most one job (k jobs in total), while the set of slow machines should process exactly k jobs in pairs of two. By pigeonhole principle, since the number of jobs is 2k+1, there exist a job that remains to be scheduled and the minimum processing time of this job is one, a contradiction.

Consider the following solution of [LP(C)], for C = 2k+1/2k∈ (1,2): We set x_i,j = 1/4k for the assignment of every j ∈ on i ∈ℳ_S and x_i,j = 1/2k for the assignment of every j ∈ on i ∈ℳ_F. For C = 2k+1/2k, the critical value of any job j becomes γ_j = ⌈2/C⌉ = 2. Moreover, for any job j ∈ we have r_i,j = max_{γ_j,s_i} = 1 for i ∈ℳ_S and r_i,j = max_{γ_j,s_i} = 2 for i ∈ℳ_F. Clearly, constraints (<ref>) and (<ref>) of [LP(C)] are satisfied. For this assignment, for every i ∈ℳ_S, we have: 

    ∑_j ∈ f_j(r_i,j) r_i,j/s_i x_i,j = 2 ∑_j ∈ x_i,j = 2 2k+1/4k = C.
 Moreover, for every i ∈ℳ_F, we get: 

    ∑_j ∈ f_j(r_i,j) r_i,j/s_i x_i,j = ∑_j ∈ x_i,j = 2k+1/2k = C.

Therefore, constraints (<ref>) are satisfied for every i ∈ℳ_S ∪ℳ_F. Given the above construction, for k →∞, there exists an instance such that the integrality gap of [LP(C)] is at least 2, since:


    lim_k→∞/C = lim_k→∞ 2 (1 - 1/2k) = 2.

 
Finally, it is not hard to verify that C = 2k/2k-1 is the smallest C such that [LP(C)] is feasible. Indeed, by summing constraints (<ref>) over all j ∈, we get that: 2k+1 = ∑_j ∈( ∑_i∈ℳ_S x_i, j + ∑_i∈ℳ_S x_i,j) ≤ 2kC/2 + k C = 2k C, where the inequality follows by using constraints (<ref>).




§ THE CASE OF SUPERMODULAR PROCESSING TIME FUNCTIONS


In this paper we concentrated our study on speed-imple­mentable processing time functions.
However, the general definition of malleable scheduling, as given in Section <ref>, leaves room for many other possible variants of the problem with processing times given by monotone non-increasing set functions.
One natural attempt of capturing the assumption of non-decreasing workload is to assume that, for each job j ∈𝒥, the corresponding processing time function f_j is supermodular, i.e.,

    f_j(T ∪{i}) - f_j(T) ≥ f_j(S ∪{i}) - f_j(S)

for all S ⊆ T ⊆ℳ and i ∈ℳ∖ T.
The interpretation of this assumption is that the decrease in processing time when adding machine i diminishes the more machines are already used for job j (note that the terms on both sides of the inequality are non-positive because f_j is non-increasing).
For this setting, which we refer to as generalized malleable scheduling with supermodular processing time functions, we derive a strong hardness of approximation result.

There is no |𝒥|^1-ε-approximation for generalized malleable scheduling with supermodular processing time functions, unless P = NP.


We show this by reduction from graph coloring: Given a graph G = (V, E), what is the minimum number of colors needed to color all vertices such that no to adjacent vertices have the same color? It is well-known that this problem does not admit a |V|^1 - ε-approximation unless P = NP <cit.>.
  
Given a graph G = (V, E), we introduce a job j_v for each v ∈ V and a machine i_e for each e ∈ E.
For each v ∈ V, let δ(v) be the set of incident edges and define the corresponding set of machines S_v := {i_e : e ∈δ(v)}.
We define the processing time function of job j_v ∈𝒥 by 
    f_j_v(S) := 1 + |V| |S_v∖ S|.

It is easy to verify that these functions are non-increasing and supermodular.
We show that the optimal makespan for the resulting instance of generalized malleable scheduling is equal to the minimum number of colors needed to color the graph G.
  
First assume that G has a coloring with k colors. 
We create a schedule with makespan at most k as follows.
Arbitrarily label the colors {0, …, k-1} and let c(v) be the color of vertex v ∈ V. 
For each v ∈ V, start job j_v on the set of machines S_v at time c(v).
Because f_j_v(S_v) = 1, each job j_v is done at time c(v) + 1 and two jobs j_v, j_v' only run in parallel if c(v) = c(v').
Because no two adjacent vertices have the same color, c(v) = c(v') implies S_v ∩ S_v' = ∅.
Hence every machine runs at most one job at any given time, which shows that the schedule is feasible.
Its makespan is k as the last job starts at time k-1.
  
Now assume there is a schedule with makespan C. We show there is a coloring with at most ⌊ C ⌋ colors.
We can assume that C ≤ |V|, as otherwise the trivial coloring suffices.
Hence, for each v ∈ V, the subset of machines that job j_v is assigned to contains the set S_v.
Define the color of vertex v ∈ V by c(v) := ⌊ C_j_v⌋, i.e., the completion time of the corresponding job rounded down.
Note that c(v) ∈{1, …, ⌊ C ⌋}, because each job has a processing time of at least 1 and the last job finishes at time C.
Furthermore, if c(v) = c(v') for some v, v' ∈ V, then there is a time t where j_v and j_v' are both being processed in the schedule. Since each machine in S_v is assigned to job j_v and each machine in S_v' is assigned to job j_v', we conclude that S_v ∩ S_v' = ∅, i.e., v and v' are not adjacent.
Hence the coloring is feasible. 


By the above analysis, we conclude that any poly­nomial-time ||^1-ϵ-approximation algorithm for the generalized malleable scheduling problem with supermodular processing time functions would imply a |V|^1-ϵ-approximation algorithm for graph coloring, which is a contradiction, unless P = NP.



§ CONCLUSION

In this work, we propose and study a generalization of the malleable scheduling problem in the setting of non-identical machines. For this problem, we design constant approximation algorithms for the cases of unrelated, uniform and restricted identical machines. 
Although our generalized model widens the amount of applications captured comparing to the case of malleable scheduling of identical machines, it does not yet capture issues of interdependence between the machines in an explicit manner. As an example, consider the case where a set of machines performs better in combination due to locality or other aspects. 


In this direction, an interesting future work can be the study of the malleable scheduling problem with more general processing time functions that are able to capture the particularities of real-life resource allocation systems.







plainurl




§ APPENDIX




 §.§ A slight improvement by optimizing the threshold


Recall that in both algorithms for the unrelated machines case, the threshold for deciding whether a job j is assigned to p(j) or to T(j) is set to 1/2. While this is the optimal choice for the simple 4-approximate rounding scheme, we can achieve a slightly better bound for our improved algorithm by optimizing this threshold accordingly. 
Let β∈ (0,1) be the threshold such that a job j is assigned to p(j) when x_p(j),j≥β, or to the set T(j), when ∑_i ∈ T(j) x_i,j > 1 - β. 
Formally, let ^(1) := {j ∈ x_p(j),j≥β} be the set of jobs that are assigned to their parent-machines and ^(2) := ∖^(1) the rest of the jobs.
For j ∈^(2) and θ∈ [0, 1] define S_j(θ) := { i ∈ T(j)  1 - ℓ_i/C≥θ}. Choose θ_j so as to minimize 2(1 - θ_j)C + f_j(S_j(θ_j)) (note that this minimizer can be determined by trying out at most |T(j)| different values for θ_j). 
We then assign each job in j ∈ J^(2) to the machine set S_j(θ_j).

Recall that for any i ∈ there is at most one j ∈ J^(2) with i ∈ T(j). If i ∉ S_j(θ_j), then load of machine i is bounded by 1/βℓ_i ≤1/β C, where ℓ_i as defined in Section <ref>. If i ∈ S_j(θ_j), then the load of machine i is bounded by
 

    max_i' ∈ S_j(θ_j){β^-1ℓ_i + f_j(S_j(θ_j)) }≤β^-1(1 - θ_j)C + f_j(S_j(θ_j)),


where the inequality comes from the fact that 1 - ℓ_i'/C≥θ_j for all i' ∈ S_θ_j. 

We now fix β to be the unique solution of β^-1+1 = e^1/β - 1/β(e^1/β - 1 - 1) in the interval [0,1]. The following proposition gives an upper bound on the RHS of (<ref>) as a result of our filtering technique.


For each j ∈^(2), there is a θ∈ [0,1] with β^-1(1- θ)C + f_j(S_j(θ)) ≤e^1/β - 1/β(e^1/β - 1 - 1)C.



We first assume that for all i ∈ T(j), it is the case that s_i,j≤γ_j and, thus, r_i,j = γ_j. In the opposite case, where there exists some i' ∈ T(j) such that s_i,j > γ_j, by choosing θ = 0, then (<ref>) can be upper bounded by β^-1C + f_j(S_j(0)) = β^-1C + f_j(T(j)) ≤(β^-1+1)C. In that case, the proposition follows directly by the fact that β^-1+1 = e^1/β - 1/β(e^1/β - 1 - 1), by our choice of β.

Define α := e^1/β - 1/β(e^1/β - 1 - 1). We show that there is a θ∈ [0, 1] with σ_j(S_j(θ)) ≥γ_j f_j(γ_j)/(α + β^-1θ -β^-1)C. Then f_j(S_j(θ)) ≤ (α + β^-1θ -β^-1) C by Fact <ref>, implying the lemma.

Define the function g: [0,1] →ℝ_+ by g(θ) := σ_j (S_j(θ)). It is easy to see g is non-increasing integrable and that 
 
    ∫_0^1 g(θ) dθ = ∑_i ∈ T(j) s_i,j (1 - ℓ_i/C).
 
 
Now assume by contradiction that g(θ) < γ_j f_j(γ_j)/(α + β^-1θ - β^-1)C for all θ∈ [0, 1].
Note that ℓ_i + γ_j f_j(γ_j)/s_i,j x_i,j≤ C for every i ∈ T(j) by constraints (<ref>).
Hence  f_j(γ_j)γ_j/C x_i,j≤ s_i,j(1 - ℓ_i/C) for all i ∈ T(j).
Summing over all i ∈ T(j) and using the fact that ∑_i ∈ T(j) x_i,j≥ 1 - β because j ∈ J^(2), we get


    (1- β)f_j(γ_j)γ_j/C   ≤∑_i ∈ T(j) s_i,j (1 - ℓ_i/C)
       = ∫_0^1 g(θ) dθ
       < f_j(γ_j)γ_j/C∫_0^11/α + β^-1θ - β^-1 dθ,


where the last inequality uses the assumption that g(θ) < γ_j f_j(γ_j)/(α + β^-1θ_j - β^-1)C for all θ∈ [0,1]. By simplifying the above inequality, we get the contradiction


    1 - β/β < ∫_α-β^-1^α1/λ dλ = ln(α/α -β^-1) = 1 - β/β.



Therefore, by choosing α = inf_β∈ (0,1){e^1/β - 1/β(e^1/β - 1 - 1)}≈ 3.14619 [Note that the minimizer of this expression coincides with the unique solution of β^-1+1 = e^1/β - 1/β(e^1/β - 1 - 1) in the interval [0,1].], with threshold β≈ 0.465941, we can prove the following theorem.

There exists a polynomial-time 3.1461-approximation algorithm for the problem of scheduling malleable jobs on unrelated machines.


