JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

1

Algorithms for Scheduling Malleable Tasks

arXiv:1501.04343v8 [cs.DC] 4 Feb 2018

Xiaohu Wu, and Patrick Loiseau
Abstract—Due to the ubiquity of batch data processing in cloud computing, the related problems of scheduling malleable batch tasks
have received significant attention recently. In this paper, we consider a fundamental model where a set of n tasks is to be processed
on C identical machines and each task is specified by a value, a workload, a deadline and a parallelism bound. Within the parallelism
bound, the number of machines assigned to a task can vary over time without affecting its workload. For this model, we first give two
core results: the definition of an optimal state under which multiple machines could be utilized by a set of tasks with hard deadlines,
and, an algorithm achieving such a state. The optimal utilization state plays a key role in the design and analysis of scheduling
algorithms (i) when several typical objectives are considered, such as social welfare maximization, machine minimization, and
minimizing the maximum weighted completion time, and, (ii) when the algorithmic design techniques such as greedy and dynamic
programming are applied to the social welfare maximization problem. As a result, we give four new or improved algorithms for the
above problems.

F

1

I NTRODUCTION

Cloud computing has become the norm for a wide range
of applications and batch processing constitutes the most
significant computing paradigm [1]. Applications such as
web search index update, monte carlo simulations and bigdata analytics require executing a new type of parallel tasks
on clusters, termed malleable tasks. Two basic features of
malleable tasks are about workload and parallelism bound.
There are multiple machines, and, throughout the execution,
the number of machines assigned to a task can vary over
time within the parallelism bound but its workload is not
affected by the number of used machines [2], [3]. Beyond
understanding how to schedule the fundamental batch task
model, many efforts are also devoted to its online version
[4], [5], [6] and its extension in which each task contains
several subtasks with precedence constraints [7], [8]. In
practice, for better efficiency, companies such as IBM have
integrated these smarter scheduling algorithms for various
time metrics [8] (than the popular dominant resource fairness strategy) into their batch processing platforms [9].
In scheduling theory, the above malleable task model can
be viewed as an extension of the classic model of scheduling
preemptive tasks on a single or multiple machines where
the parallelism bound is one [10], [11]. When each task
has to be completed by some deadline, the results from
the special single machine case have already implied that
the state of optimally utilizing machines plays a key role in
the design and analysis of scheduling algorithms under several objectives [11]. In particular, the famous EDF (Earliest
Deadline First) rule can achieve an optimal schedule for the
single machine case. It is initially designed so as to find an
exact algorithm for scheduling batch tasks to minimize the
maximum task lateness (i.e., task’s completion time minus
due date) [12]. So far, numerous applications of this rule
•
•

Xiaohu Wu is with Fondazione Bruno Kessler, Trento, Italy.
E-mail: xiaohuwu@fbk.eu
Patrick Loiseau is with Univ. Grenoble Alpes, LIG, France and MPI-SWS,
Germany. E-mail: patrick.loiseau@univ-grenoble-alpes.fr

Manuscript received April 19, 2005; revised August 26, 2015.

have been found, e.g., (i) to design exact algorithms for the
extended model with release times [13] and for scheduling
tasks with deadlines (and release times) to minimize the
total weighted number of tardy tasks [14], and (ii) as a
significant principle in the analysis of scheduling feasibility
for real-time systems [15].
Similarly, we are convinced that, as far as malleable
tasks are concerned, achieving such an optimal resource
utilization state is also very important for designing and
analyzing scheduling algorithms (i) under various objectives, or (ii) when different algorithmic design techniques
such as greedy and dynamic programming are applied. The
intuition for this is that, if the utilization state was not
optimal in an algorithm, its performance could be improved
by utilizing the machines optimally to allow more tasks
to be completed. All these considerations motivate us to
develop an theoretical framework proposed in this paper.
Before this paper, a greedy algorithm was proposed in
s−1
[3] that achieves a performance guarantee C−k
C · s ; here,
C is the number of machines, k is the maximum parallelism
bound of all tasks, s is the minimum slackness of all tasks
where each task’s slackness is defined to be the ratio of
its deadline to its minimum execution time, which is the
time when a task is always allocated the maximum number
of machines during the execution. k is a system parameter
and is assumed to be finite [16]. Intuitively, s characterizes
the resource allocation urgency (e.g., s = 1 means that the
maximum amount of machines have to be allocated to a task
at every time slot to meet its deadline).
1.1

Our Results

Core result (Section 3). The core result of this paper is to
identify a sufficient and necessary condition under which a
set of independent malleable tasks could be all completed by
their deadlines on C machines, also referred to as boundary
condition in this paper.
In particular, by understanding the basic constraints of
malleable tasks, we first identify and formally define a state
in which C machines can be said to be optimally utilized by

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

a set of tasks with deadlines in terms of resource utilization.
Then, we propose an optimal scheduling algorithm LDF(S )
(Latest Deadline First) that achieves such an optimal state.
The LDF(S ) algorithm has a polynomial time complexity
of O(n2 ) and is different from the EDF algorithm that
gives an optimal schedule in the single-machine case. Here,
the maximum deadline of tasks is assumed to be finitely
bounded by a constant.
Applications (Sections 4 and 5). The above core results
have several applications to propose new or improved
algorithmic design and analysis for scheduling malleable
tasks under different objectives. The scheduling objectives
considered in this paper include:
(a)
(b)

(c)

social welfare maximization: maximize the sum of
values of tasks completed by their deadlines;
machine minimization: minimize the number of machines needed to produce a feasible schedule for a
set of tasks such that each task is completed by their
deadline;
maximum weighted completion time minimization: minimize the maximum weighted completion time of
tasks.

Here, the first and second objectives above have been considered in [2], [3], [8]. The second objective that concerns
the optimal utilization of machines has been considered for
other types of tasks [17] but we are the first to consider it for
malleable tasks. After applying the core results above, we
obtain the following algorithmic results:
(i)

(ii)

(iii)
(iv)

an improved greedy algorithm GreedyRLM with a
performance guarantee s−1
s for social welfare maximization with a time complexity of O(n2 );
the first exact dynamic programming algorithm for
social welfare maximization with a pseudo-polynomial time complexity of O(max{ndL C L , n2 }), where
L is the number of deadlines, D and d are the
maximum workload and deadline of tasks;
the first exact algorithm for machine minimization
with a time complexity of O(n2 , Ln log n);
a polynomial time (1+)-approximation algorithm for
maximum weighted completion time minimization.

In the greedy algorithm of [3], the tasks are considered
in the non-decreasing order of their marginal values of tasks
(i.e., the ratio of a task’s value to its size), and only if a
task could be fully completed by its deadline according to
the currently remaining resource, it will be accepted and
allocated possibly different number of machines over time
according to an allocation algorithm; otherwise, it will be
rejected. In this paper, we also show that
•

•

for social welfare maximization, s−1
s is the best possible performance guarantee that a class of greedy
algorithms could achieve where they consider tasks
in the non-increasing order of their marginal values.
as a result, the proposed greedy algorithm of this
paper is the best possible among this kind of greedy
algorithms.

The second algorithm for social welfare maximization
can work efficiently when L is small since its time complexity is exponential in L. However, this may be reasonable

2

in a machine scheduling context. In scenarios like [7], tasks
are often scheduled periodically, e.g., on an hourly or daily
basis, and many tasks have a relatively soft deadline (e.g.,
finishing after four hours instead of three will not trigger a financial penalty). Then, the scheduler can negotiate
with the tasks and select an appropriate set of deadlines
{τ1 , τ2 , · · · , τL }, thereafter rounding the deadline of a task
down to the closest τi (1 ≤ i ≤ L). By reducing L, this could
permit to use the dynamic programming (DP) algorithm
rather than GreedyRLM in the case where the slackness s
is close to 1. With s close to 1, the approximation ratio of
GreedyRLM approaches 0 and possibly little social welfare
is obtained by adopting GreedyRLM while the DP algorithm
can still obtain the almost optimal social welfare.
Technical Difference. The second algorithm can be viewed
as an extension of the pseudo-polynomial time exact algorithm in the single machine case [10] that is also designed
via the generic dynamic programming procedure. However,
before our work, how to enable this extension to malleable
tasks was not clear as indicated in [2], [3]. This is mainly due
to the lack of a notion of the optimal state of machines being
utilized by malleable tasks with deadlines and the lack of an
algorithm that achieves such a state. In contrast, the optimal
state in the single machine case can be defined much more
easily and achieved by the EDF algorithm. The core results
of this paper are the enabler of a DP algorithm.
The way of applying the core results to a greedy algorithm is less obvious since in the single machine case there
is no corresponding algorithm to hint its role in the algorithmic design. For the above class of greedy algorithms,
we manage to give a new algorithm analysis, figuring out
what resource allocation features of tasks can benefit and
determine the algorithm’s performance. This analysis is an
extended analysis of the greedy algorithm for the standard
knapsack problem [22] and it does not rely on the dualfitting technique, on which the algorithm in [3] is built.
Here, the problem could be viewed as an extension of
the knapsack problem where each item has two additional
constraints in a two-dimensional space: a (time) window
in which an item could be placed and a maximum width
of the space that it could utilize at every moment. Two of
the most important algorithms there are either based on the
DP technique or of greedy type, that also considers items
by their marginal values [22]; we give in this paper their
counterparts in the scenario of malleable tasks.
In the construction of the greedy and optimal scheduling
algorithms, we are inspired by the algorithm in [3]. After
our definition of the optimal state and a new analysis of the
above class of greedy algorithms, we found that the algorithm in [3] could achieve an optimal resource utilization
state from the maximum deadline of tasks d to some earlier
time slot t. However, this is achieved by guaranteeing the
existence of a time slot t0 earlier than t such that the number
of available machines at t0 is ≥ k , which leads a suboptimal
utilization of resources. In our algorithm, we only require t0
to be such that the number of available machines at t0 is ≥ 1,
which leads to an optimal resource utilization. More details
could be found in the remarks of Section 3.2.
The above third and fourth algorithms are obtained
by respectively applying the above core result to a binary

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

3

search procedure, and the related results in [8].
1.2

Related works

Now, we introduce the related works. The linear programming approaches to designing and analyzing algorithms for the task model of this paper [2], [3] and its
variants [4], [5], [7] have been well studied1 . All these
works consider the same objective of maximizing the social welfare. In [2], Jain et al. proposed an algorithm with
C
an approximation ratio of (1 + C−k
)(1 + ) via deterministic rounding of linear programming. Subsequently, Jain et
al. [3] proposed a greedy algorithm GreedyRTL and used
the dual-fitting technique to derive an approximation ratio
C−k
s−1
C · s . In [7], Bodik et al. considered an extension of
our task model, i.e., DAG-structured malleable tasks, and,
based on randomized rounding of linear programming, they
proposed an algorithm with an expected approximation
1
ratio
of α(λ) for every λ i> 0, where α(λ) = λ1 · e− λ ·
h
(1−1/λ)C−k

TABLE 1
Main Notation
Notation
C
T
Ti
Di , di , vi
ki
yi (t)
W (t)
W (t)
leni

i

si

κ

·ln λ·(1− C )
2ωκ
. The online version of our task
1 − e−
model is considered in [4], [5]; again based on the dual-fitting
technique, two weighted greedy algorithms are proposed
respectively for non-committed and committed scheduling
1
and achieve the competitive ratios of crA = 2 + O( ( √
3 s−1)2 )
cr (s·ω(1−ω))

where s > 1 [3] and Aω(1−ω)
where ω ∈ (0, 1) and
1
s > ω(1−ω)
.
In addition, Nagarajan et al. [8] considered DAGstructured malleable tasks and propose two algorithms with
approximation ratios of 6 and 2 respectively for the objectives of minimizing the total weighted completion time and
the maximum weighted lateness of tasks. Nagarajan et al.
showed that optimally scheduling deadline-sensitive malleable
tasks in terms of resource utilization is a key to the solutions to
scheduling for their objectives. In particular, seeking a schedule
for DAG tasks can be transformed into seeking a schedule
for tasks with simpler chain-precedence constraints; then
whenever there is a feasible schedule to complete a set of
tasks by their deadlines, Nagarajan et al. proposed a nonoptimal algorithm where each task is completed by at most
2 times its deadline and give two procedures to obtain nearoptimal completion times of tasks in terms of the above two
objectives.
Technically, the works [2], [3], [4], [5], [7] formulate
their problem as an Integer Program (IP) and relax the IP
to a relaxed linear program (LP). The techniques in [2],
[7] require to solve the LP to obtain a fractional optimal
solution and then manage to round the fractional solution
to an integer solution of the IP that corresponds to an
approximate solution to their original problem. In [3], [4],
[5], the dual fitting technique first finds the dual of the LP
and then construct a feasible algorithmic solution X to the
dual in some greedy way. This solution corresponds to a
feasible solution Y to their original problems, and, due to
the weak duality, the value of the dual under the solution X
(expressed in the form of the value under Y multiplied by
a parameter α ≥ 1) will be an upper bound of the optimal
value of the IP, i.e., the optimal value that can be achieved
in the original problem. Therefore, the approximation ratio
1. We refer readers to [11], [18] for more details on the general
techniques to design scheduling algorithms.

Explanation
the total number of machines
a set of tasks to be scheduled on C machines
a task in T
the workload, deadline, and value of a task Ti
the parallelism bound of Ti , i.e., the maximum
number of machines that can be allocated to and
utilized by Ti simultaneously
the number of machines allocated to Ti at a time
slot t where yi (t) ∈ {0, 1, · · · , ki } and set all
yi (t) to 0 initially
the total number of machines thatP
are allocated
out to the tasks at t, i.e., W (t) = Ti ∈T yi (t)
the total number of machines idle at t, i,e.,
W (t) = C − W (t)
the minimum execution time of Ti where Ti is
allocated ki machines in the entire execution
i
process, i.e., leni = d D
e
k

s
d, D
vi0
{τ1 , · · · , τL }
Di

di
the slackness of a task, i.e., len
, measuring the
i
urgency of machine allocation to complete Ti by
the deadline
the minimum slackness of all tasks of T , i.e.,
minTi ∈T si
the maximum deadline and workload of all tasks
of T , i.e., d = maxTi ∈T di and D = maxTi ∈T Di
vi
the marginal value of Ti , i.e., vi0 = D
i
the set of the deadlines di of all tasks Ti of T ,
where 0 = τ0 < τ1 < · · · < τL = d
all the tasks {Ti,1 , Ti,2 , · · · , Ti,ni } of T that
have a deadline τi , 1 ≤ i ≤ L

of the algorithm involved in the dual becomes clearly 1/α.
Here, the approximation ratio is a lower bound of the ratio
of the actual value obtained by the algorithm to the optimal
value.
A part of results of this paper appeared at the Allerton
conference in the year 2015 [19], [20]. Following [19], [20],
a recent work also gave a similar (sufficient and necessary)
feasibility condition to determine whether a set of malleable
tasks could be completed by their deadlines and showed
that such a condition is central to the application of the
LP technique to the three problems of this paper: greedy
and exact algorithms for social welfare maximization and an
exact algorithm for machine minimization. Guo & Shen first
used the LP technique to give a new proof of this feasibility
condition in the core result. Based on this condition, the
authors gave a new formulation of the original problems as
IP programs, different from the ones in [2], [3]. This new
formulation enables from a different perspective proposing
almost the same algorithmic results as this paper, e.g., for
the machine minimization problem an exact algorithm with
a time complexity O((n + d)3.5 Ls (log n + log k)), and for
the social welfare maximization problem an exact algorithm
with a complexity O(n·(C·d)d ), where Ls is the length of the
LP’s input. In addition, we have shown that the best performance guarantee is s−1
s when a greedy algorithm considers
tasks in the non-increasing order of their marginal values.
Guo & Shen also considered another standard to determine
the order of tasks, and proposed a greedy algorithm with a
2
performance guarantee C−k
C and a complexity O(n + nd).

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

2

M ODEL AND P ROBLEM D ESCRIPTION

There are C identical machines and a set of n tasks
T = {T1 , T2 , · · · , Tn }. The task Ti is specified by several
characteristics: (1) value vi , (2) demand (or workload) Di , (3)
deadline di , and (4) parallelism bound ki . Time is discrete and
the time horizon is divided into d time slots: {1, 2, · · · , d},
where d = maxTi ∈T di and the length of each slot may
be a fixed number of minutes. A task Ti can only utilize
the machines located in time slot interval [1, di ]. The parallelism bound ki limits that, at any time slot t, Ti can
be executed on at most ki machines simultaneously. Let
k = maxTi ∈T ki be the maximum parallelism bound; here,
ki is a system parameter and k is therefore assumed to be
finite [16]. An allocation of machines to a task Ti is a function
yi : [1, di ] → {0, 1, 2, · · · , ki }, where yi (t) is the number of
machines allocated to task Ti at a time slot t ∈ [1, di ]. In this
model, Di , di ∈ Z + for all Ti ∈ T .
P For the system of C machines, denote by W (t) =
Ti ∈T yi (t) the system’s workload at time slot t; and by
W (t) = C − W (t) its complementary, i.e., the amount of
available machines at time t. We say that time t is fully
utilized if W (t) = 0, and is not fully utilized if W (t) > 0.
In addition, we assume that the maximum deadline of
tasks is bounded. Given the model above, the following
three scheduling objectives are considered separately in this
paper:
•

•

•

The first objective is social welfare maximization and
it aims to choose an a subset S ⊆ T and produce
a feasible schedule
for S so as to maximize the
P
social welfare
Ti ∈S vi (i.e., the sum of values of
tasks completed by deadlines); here, the value vi of
a task Ti is gained if P
and only if it is fully allocated
by the deadline, i.e., t≤di yi (t) ≥ Di , and partial
execution of a task yields no value.
The second objective is machine minimization, i.e.,
seeking the minimum number of machines needed
to produce a feasible schedule of T on C machines
such that the task’s parallelism bound and deadline
constraints are not violated.
The third objective is to minimize the maximum
weighted lateness of tasks, i.e., minTi ∈T {vi ·(ti −di )},
where ti is the completion time of a task Ti .

Furthermore, we denote by [l] and [l]+ the sets {0, 1, · · · , l}
and {1, 2, · · · , l} for a positive integer l. Let leni = dDi /ki e
denote the minimum execution time of Ti . Define by si =
di
leni the slackness of Ti , measuring the urgency of machine
allocation (e.g., si = 1 may mean that Ti should be allocated
the maximum amount of machines ki at every t ∈ [1, di ])
and let s = minTi ∈T si be the slackness of the least flexible
vi
task (s ≥ 1). Denote by vi0 = D
the marginal value of task Ti ,
i
i.e., the value obtained by the system per unit of demand. We
assume that the demand of each task is an integer. Let D =
maxTi ∈T {Di } be the demand of the largest task. Given a set
of tasks T , the deadlines di of all tasks Ti ∈ T constitute a
finite set {τ1 , τ2 , · · · , τL }, where L ≤ n, τ1 , · · · , τL ∈ Z + ,
and 0 = τ0 < · · · < τL = d. Let Di = {Ti,1 , Ti,2 , · · · , Ti,ni }
PL
denote the set of tasks with deadline τi , where i=1 ni = n
(i ∈ [L]+ ).

4

The notation of this section is used in the entire paper
and summarized in Table 1. Throughout this paper, we use
i, j , m, l, or m0 as subscripts to index the element of different
sets such as tasks and use t or t to index a time slot.

3

O PTIMAL S CHEDULE

In this section, we identify a state under which C machines can be said to be optimally utilized by a set of tasks.
We then propose a scheduling algorithm that achieves such
an optimal state. Besides Table 1, the additional notation to
be used in this section is summarized in Table 2.
3.1

Optimal Resource Utilization State

In this paper, all tasks are denoted by a set T , and we
denote by S ⊆ T an arbitrary subset of T ; all tasks of T
with a deadline τl are denoted by Dl and we denote by
Sl = S ∩Dl all tasks of S with a deadline τl (l ∈ [L]+ ). In this
subsection, we define the maximum amount of workload of
S that could be processed in a fixed time interval [τm +1, τL ]
on C machines for all m ∈ [L − 1], where τL = d, i.e., the
maximum deadline of tasks.

Fig. 1. The green areas denote the maximum demand of Ti that need
or could be processed in [τL−m + 1, τL ].

We first define the maximum amount of resource, denoted
by λm (S), that could be utilized by S in [τL−m + 1, τL ] in
an idealized case where there is an indefinite number of
machines, i.e., C = ∞, for all m ∈ [L]+ . To define this, we
clarify the maximum amount of resource that an individual
task Ti can utilize in [τL−m + 1, τL ]. The basic constraints of
malleable tasks with deadlines imply that:
•
•

the deadline of Ti limits that Ti can only utilize the
machines in [1, di ], and
the parallelism bound limits that Ti can only utilize
at most ki machines simultaneously at every time
slot.

The tasks with di ≤ τL−m cannot be executed in the interval
[τL−m + 1, τL ]. Let us consider a task Ti with di ∈ [τL−m +
1, τL ]. The number of time slots available in [τL−m + 1, di ] is
di − τL−m in the discrete case, and, also recall that leni the
(minimum) execution time of Ti when it always utilizes the
maximum number ki of machines throughout the execution.
In the illustrative Fig. 1, the green area in the left (resp. right)
subfigure denotes the maximum demand of a task, i.e., Di
(resp. ki · (di − τL−m )), that could or need be processed in
[τL−m + 1, τL ] in the case where the minimum execution
time is such that leni ≤ di − τL−m (resp. leni > di − τL−m ).
As a consequence of the observation above, λm (S)
equals the sum of the maximum workload of every task

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

5

in S that could executed in [τL−m + 1, τL ] and is defined as
follows.
Definition 1. Initially, set λm (S) to zero for all m ∈ [L]. In the
case where C = ∞ (i.e., the capacity constraint is ignored), for
all m ∈ [L]+ , λm (S) is defined as follows:

λm (S) ← λm (S) + βi , for every task Ti ∈ S ,
where βi is such that
•
•

i.e., the size of all the colored areas in [τ0 + 1, τ2 ].
Generalizing the above process, we derived a recursive
definition of λC
m (S).
Definition 2. In the case where C is finite (i.e., with the capacity
constraint), for all m ∈ [L], the maximum amount of resource
λC
m (S) that could be utilized by S in [τL−m + 1, τL ] is defined
by the following recursive procedure:

if Ti ∈ S1 ∪ · · · ∪ SL−m where di ≤ τL−m , βi ← 0;
if Ti ∈ SL−m+1 ∪ · · · ∪ SL where di ≥ τL−m + 1, as
illustrated in Figure 1,
–
–

in the case that leni ≤ di − τL−m , βi ← Dj ;
otherwise, βi ← ki · (di − τL−m ).

Here, βi represents the maximum workload of a task Ti that could
be executed in [τL−m + 1, τL ].
Built on Definition 1, we move to the case where C is
finite and define the maximum amount of resource λC
m (S)
that can be utilized by S on C machines in every [τL−m +
1, τL ], m ∈ [1, L].

•

set λC
0 (S) to zero trivially;

•

C
C
set λ
m (S) to the sum of λm−1 (S) and
C
min λm (S) − λm−1 (S), C · (τL−m+1 − τL−m ) .

We finally state our definition that formalizes the concept
of optimal utilization of C machines by a set S of malleable
tasks with deadlines:
Definition 3 (Optimal Resource Utilization State). We say
that C machines are optimally utilized by a set of tasks S , if, for
all m ∈ [L]+ , S utilizes λC
m (S) resources in [τL−m + 1, d] on C
machines.
P
C
We define µC
m (S) =
Ti ∈S Di −λL−m (S) as the remaining (minimum) workload of S that needs to be processed
after S has maximally utilized C machines in [τm + 1, τL ]
for all m ∈ [L − 1].
Lemma 1 (Boundary Condition). If there exists a feasible
schedule for S , the following inequality holds for all m ∈ [L − 1]:

µC
m (S) ≤ C · τm ,
which is referred to as boundary condition in this paper.

Fig. 2. Derivation from the definition λm (S) to λC
m (S).

To help readers grasp the underlying intuition in the
process of deriving λC
m (S) from λm (S), we first illustrate
this process in the case where L = 2 with the help of Fig. 2.
Fig. 2 (left) illustrates the parameter λm (S) in Definition 1,
where the green area denotes λ1 (S) and the green and blue
areas together denote λ2 (S). As illustrated in Fig. 2 (right),
due to the capacity constraint that C is finite, we have that
(i)

C · (τ2 − τ1 ) is the maximum possible workload
that could be processed in [τ1 + 1, τ2 ] due to the
capacity constraint, and λ1 (S) is the maximum
available workload of S that needs to be processed
in [τ1 + 1, τ2 ] due to the deadline and parallelism
constraints. As a result, on C machines, the maximum workload λC
1 (S) of S that can be processed in
[τ1 + 1, τ2 ] is the size of the green area in [τ1 + 1, τ2 ],
i.e.,
λC
1 (S) = min{C · (τ2 − τ1 ), λ1 (S)} = C · (τ2 − τ1 ).

(ii)

After λC
1 (S) workload of S has been processed in
[τ1 + 1, τ2 ], the remaining workload of S that needs
to processed in [1, τ1 ] is λ2 (S) − λC
1 (S); the maximum workload that could be processed in [1, τ1 ]
is C · τ1 due to the capacity constraint. As a result,
λC
2 (S) is defined as follows:

λC
2 (S)
λC
1 (S)

=
+ min{C · (τ1 − τ0 ), λ2 (S) −
= min{C · (τ2 − τ0 ), λ2 (S)} = λ2 (S),

λC
1 (S)}

Proof. Recall the definition of λC
L−m (S) in Definition 2.
After S has maximally utilized the machines in [τm + 1, d]
and been allocated the maximum amount of resource, i.e.,
λC
L−m (S), if there exists a feasible schedule for S , the total
amount of the remaining demands of S to be processed
should be no more than the capacity C · τm in [1, τm ].

3.2

Scheduling Algorithm

In this section, we assume that S satisfies the boundary
condition above, and, propose an algorithm LDF(S ) that
achieves the optimal resource utilization state, producing
a feasible schedule for S .
3.2.1

Overview of LDF(S )

Initially, for all Ti ∈ S and t ∈ [1, d], we set the allocation
yi (t) to zero and LDF(S ) runs as follows:
1)

2)

the tasks in S are considered in the non-increasing
order of the deadlines, i.e., in the order of SL , SL−1 ,
· · · , S1 ;
for a task Ti being considered, the algorithm
Allocate-B(i), presented as Algorithm 2, is called to
allocate Di resource to Ti under the constraints of
deadline and parallelism bound.

At a high level, we show in the following that, only if S
satisfies the boundary condition and the resource utilization
satisfies some properties upon every completion of AllocateB(·), all tasks in S will be fully allocated.

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

6

Fig. 3. The resource allocation state of Ti and the previous tasks S 0 respectively upon completion of Fully-Utilize(i), Fully-Allocate(i), and
AllocateRLM(i, 1, t2 + 1) where L = m = 3: the blue area in the rectangle denotes the allocation to the previous tasks that satisfies Property 1 and
Property 2 before executing Allocate-B(i) while the green area in the interval [1, τ3 ] denotes the allocation to Ti at every time slot.

TABLE 2
Main Notation for the algorithms LDF(S ), Fully-Utilize(i),
Fully-Allocate(i), and AllocateRLM(i, θ1 , x)
Notation
S
Si
λm (S)

λC
m (S)

µC
m (S)

Ti
S0
S0
t0
t1
t2
t0
t00 , t000

Explanation
a set of tasks to be allocated by LDF(S ) and
S⊆T
the tasks of S with a deadline τi
the maximum amount of resource that could be
utilized by S in [τL−m + 1, τL ] in an idealized
case where there is an indefinite number of
machines, m ∈ [L]+
the maximum amount of resource that can be
utilized by S on C machines in every
[τL−m + 1, τL ], m ∈ [L]+
the remaining workload of S that needs to be
processed after S has optimally utilized C
machines
in [τm + 1, τL ], i.e.,
P
C
µC
m (S) =
Ti ∈S Dj − λL−m (S), m ∈ [L − 1]
a task that is being allocated by the algorithm
LDF(S ); the actual allocation is done by
Allocate-B(i)
so far, all tasks that have been fully allocated by
LDF(S ) and are considered before Ti
S 00 = S 0 ∪ {Ti }
a turning point defined in Property 2, with time
slots respectively later than and no later than t0
having different resource utilization state
similar to t0 , a turning point defined in Lemma 3
upon completion of Fully-Utilize(i)
similar to t0 , a turning point defined in Lemma 6
upon completion of Fully-Allocate(i)
the latest time slot in [1, τm ] with W (t0 ) > 0
a time slot that satisfies some property defined
and only used in Section 3.2.3

Now, we begin to elaborate this high-level idea. In
LDF(S ), when a task Ti is being considered, suppose that
the allocated task Ti belongs to Sm and denote by S 0 ⊆
SL ∪ · · · ∪ Sm the tasks that have been fully allocated so far
and are considered before Ti . Here, S satisfies the boundary
condition and so do all its subsets including S 0 and S 0 ∪{Ti }.
Before the execution of Allocate-B(i), we assume that the
resource utilization satisfies the following two properties:
Recall the optimal resource utilization state in Definitions 3, and the first property is that such an optimal
resource utilization state of C machines is achieved by the
current allocation to S 0 .
0
Property 1. For all l ∈ [L]+ , S 0 is allocated λC
l (S ) resource in
C
0
[τL−l + 1, d] where λl (S ) is defined in Definition 2.

The second property is that a stepped-shape resource uti-

lization state is achieved in [1, τm ] by the current allocation
to S 0 .
Property 2. If there exists a time slot t ∈ [1, τm ] such that
W (t) > 0, let t0 be the latest slot in [1, τm ] such that W (t0 ) > 0;
then we have W (1) ≥ W (2) ≥ · · · ≥ W (t0 ).
If Property 1 and Property 2 hold, we will show in Section 3.2.2 and 3.2.3 that, there exists an algorithm AllocateB(i) such that, upon completion of Allocate-B(i), the following two properties are satisfied:
Property 3. Ti is fully allocated.
Property 4. The resource allocation to S 0 ∪ {Ti } still satisfies
Property 1 and Property 2.
Due to the existence of the above Allocate-B(i), only
if S satisfies the boundary condition, S can be fully allocated by LDF(S ). The reason for this can be explained by
induction. When the first task Ti in S is considered, S 0 is
empty, and, before the execution of Allocate-B(i), Property 1
and Property 2 holds trivially. Further, upon completion
of Allocate-B(i), Ti will be fully allocated by Allocate-B(i)
due to Property 3, and Property 4 still holds. Then, assume
that S 0 that denotes the current fully allocated tasks is
nonempty and Property 1 and Property 2 hold; the task Ti
being considered by LDF(S ) will still be fully allocated and
Property 3 and Property 4, upon completion of AllocateB(i). Hence, all tasks in S will be finally fully allocated upon
completion of LDF(S ).
In the rest of this subsection, we will propose an algorithm Allocate-B(i) mentioned above such that, upon completion of Allocate-B(i), Property 3 and Property 4 holds, if,
before the execution of Allocate-B(i), the resource allocation
to S 0 satisfies Property 1 and Property 2 hold. Then, we
immediately have the following proposition:
Proposition 1. If S satisfies the boundary condition, LDF(S )
will produce a feasible schedule of S on C machines.
Overview of Allocate-B(i). The construction of AllocateB(i) will proceed with two phases. In the first phase, we
introduce what operations are feasible to make Ti fully allocated Di resource under Property 1 and Property 2. We will
use two algorithms Fully-Utilize(i) and Fully-Allocate(i) to
describe them, and the sketch of this phase is as follows:
•

From the deadline di towards earlier time slots,
Fully-Utilize(i) makes Ti fully utilize the maximum

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

7

amount of machines available at every slot. Upon its
completion, the resource allocation state is illustrated
in Fig. 3 (left) and will be described in Lemma 3.
If Ti is not fully allocated yet, as illustrated in Fig. 3
(middle), Fully-Allocate(i) transfers the allocation of
the previous tasks S 0 at the time slots closest to di to
the latest slots in [1, di ] that have idle machines, so
that, ki machines are finally allocated to Ti at each
of these slots closest to di ; as a result, Ti is fully
allocated.

Upon completion of Fully-Utilize(i), in the other case that
the total allocation to S 00 is < C · τm , even for Ti , it may not
be fully allocated. In this case, there exists a slot t ∈ [1, τm ]
such that W (t) > 0, and let t1 denote the latest such time
slot in [1, τm ].
In Fully-Utilize(i), upon completion of the allocation to
Ti at t ∈ [1, t1 ], if Ti has not been fully allocated yet, it
is allocated ki machines at t, i.e., yi (t) = ki , and these
allocations in [1, t1 ] are non-decreasing, i.e.,

Upon completion of Fully-Allocate(i), the resource allocation state may not satisfy Property 1 and Property 2, as
illustrated by Fig. 3 (middle). We therefore propose an
algorithm AllocateRLM(i, η1 , x) in the second phase:

Before executing Fully-Utilize(i), the numbers of idle machines have a stepped shape, i.e., W (1) ≥ · · ·P
≥ W (t0 ) by
Property 2, where W (t) = C − W (t) = C − Tj ∈S 0 yj (t).
Upon its completion, with yi (t) machines occupied by Ti ,
we conclude that

•

•

the allocation of the previous tasks at every slot t
closest to the deadline is again transferred to the latest slots that have idle machines, and, the allocation
of Ti in the earliest slots is transferred to t; the final
resource allocation state is illustrated in Fig. 3 (right).

Following the above high-level ideas, the details of the
first and second phases are respectively presented in Section 3.2.2 and Section 3.2.3.
3.2.2

Phase 1

Now, we introduce Fully-Utilize(i) and Fully-Allocate(i)
formally. Before their execution, recall that we assume in the
last subsection Ti ∈ Sm ; the allocation to the previously allocated tasks in S 0 satisfies Properties 1 and 2. The whole set
of tasks S to be scheduled satisfies the boundary condition
where S 0 S .
Initially, set yi (t) to zero for all time slots, and, FullyUtilize(i) operates as follows:
for every time slot t from the deadline di to 1, set
P i
yi (t) ← min{ki , Di − dt=t+1
yi (t), W (t)}.
Pdi
Here, ki is the parallelism bound, Di − t=t+1
yi (t) is the
remaining workload to be processed upon completion of its
allocations at slots t + 1, · · · , di , and W (t) is the number
Pdi
of machines idle at t; specially,
y (t) is set to 0,
t=di +1 i
representing the allocation to Ti is zero before the allocation
begins. Their minimum denotes the maximum amount of
machines that Ti can or needs to utilize at t after the
allocation to Ti at slots t + 1, · · · , di .
Before executing Fully-Utilize(i), the resource allocation
to the previous tasks S 0 satisfies Property 1. Its execution
does not change the previous allocation to S 0 . Let
•

yi (1) ≤ yi (2) ≤ · · · ≤ yi (t1 ).

Lemma 3. Upon completion of Fully-Utilize(i), in the case that
the total allocation to S 00 is < C · τm ,
•

for all t ∈ [1, t1 ], if the total allocation of Ti in [t, di ] is
Pdi
< the workload of Ti , i.e., Di − t=t
yi (t) > 0, we have
yi (t) = ki ;

•

the numbers of idle/unallocated machines in [1, t1 ] have a
stepped shape, i.e., W (1) ≥ · · · ≥ W (t1 ) > 0.

With the current resource allocation state shown in
Lemma 3, we are enabled to propose the algorithm FullyAllocate(i) to make Ti fully allocated. Deducting the current
resource allocated to Ti , let Ω denote the remaining workload of Ti to be allocated more resource, i.e.,
P
Ω = Di − t≤di yi (t).
For every slot t ∈ [1, t1 ], the number yi (t) of machines
allocated to Ti at t is ki in the case that Ω > 0 by Lemma 3.
The total workload Di is ≤ ki · di , and, with the parallelism
bound, Fully-Allocate(i) considers each slot t from di towards t1 + 1 and operates as follows repeatedly at each t
until Ω = 0:
1)

2)

3)

S 00 = S 0 ∪ {Ti }.
Since di = τm , the workload of Ti can only be processed
in [1, τm ]; the maximum workload of S 00 that could be
processed in [τm + 1, τL ] still equals its counterpart when
S 0 is considered. We come to the following conclusion in
order to not violate the boundary condition:
Lemma 2. Upon completion of Fully-Utilize(i), all tasks of S
would have been fully allocated in the caseP
that theP
total allocaτm
tion to S 00 in [1, τm ] is C ·τm , i.e., C ·τm = Tj ∈S 00 t=1
yj (t).
Proof. See the appendix for detailed proof.

4)

∆ ← min{ki − yi (t), Ω}.
Notes. ki − yi (t) is the maximum number of additional machines that could be utilized at T with its
previous allocation yi (t).
Call Routine(∆, 1, 0, t), presented as Algorithm 1.
Notes. Routine(·) aims to increase the number of
available machines W (t) at t to ∆ by transferring
the allocation of other tasks to an earlier time slot.
Allocate W (t) more machines to Ti at t: yi (t) ←
yi (t) + W (t), and, Ω ← Ω − W (t).
Notes. Ω denotes the currently remaining workload to be processed; in this iteration, if Ω > 0
currently, ∆ = ki − yi (t) and the allocation yi (t)
of Ti at t becomes ki .
t ← t − 1.

Now, we explain the existence of Ti0 in line 12 of
Routine(·) and the reason why Ti will be finally fully allocated by Fully-Allocate(i). The only operation that changes
the allocation to Ti occurs at the third step of FullyAllocate(i). Hence, we have

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

Algorithm 1: Routine(∆, η1 , η2 , t)
1
2

3
4
5
6
7
8
9
10
11
12
13

while W (t) < ∆ do
t0 ← the current time slot earlier than and closest
to t so that W (t0 ) > 0;
if η1 = 1 then
if there exists no such t0 then
f lag ← 1, break;
else
0
if t0 ≤ tth
m , or there exists no such t then
f lag ← 1, break;
if η2 = 1 then
Pt0 −1
if t=1 yi (t) ≤ W (t) then
f lag ← 1, break;
let i0 be a task such that yi0 (t) > yi0 (t0 );
yi0 (t) ← yi0 (t) − 1, yi0 (t0 ) ← yi0 (t0 ) + 1;

Lemma 4. Fully-Allocate(i) never decreases the allocation yi (t)
to Ti at any time slot t ∈ [1, di ] during its execution, compared
with the yi (t) just before executing Fully-Allocate(i).
We could also prove by contradiction that
Lemma 5. When Routine(∆, 1, 0, t) is called, the task Ti0 in
line 12 always exists if (i) the condition in line 4 is false, (ii)
yi (t0 ) = ki , and (iii) yi (t) < ki and W (t) = 0.
Proof. See the Appendix for the detailed proof.
At each iteration of Fully-Allocate(i), if there exists a
t0 such that W (t0 ) > 0 in the loop of Routine(·), with
Lemmas 3 and 4, we have yi (t0 ) = ki . Since Ω > 0 and
yi (t) < ki , when Routine(·) is called, we have W (t) = 0;
otherwise, this contradicts Lemma 3. With Lemma 5, we
will conclude that the task Ti0 in line 11 exists when it is
called by Fully-Allocate(i). In addition, the operation at line
12 of Routine(·) does not change the total allocation to Ti0 ,
and violate the parallelism bound ki0 of Ti0 since the current
yi0 (t0 ) is no more than the initial yi0 (t).
Proposition 2. Upon completion of Fully-Allocate(i), the task Ti
is fully allocated.
Proof. Fully-Allocate(i) ends up with one of the following
three events. The first is that the condition in line 4 of
Routine(·) is true. Then, with Lemma 2, all tasks in S
has been fully allocated. If the first event doesn’t happen,
the second is Ω = 0 and Ti has been fully allocated. If
the first and second events don’t happen, the third occurs
after finishing the iteration of Fully-Allocate(i) at time slot
t1 + 1; then, there is a slot t0 in [1, t1 + 1] that are not fully
utilized. As a result, we have that Ti has been fully allocated;
otherwise, Ω > 0, which implies yi (t1 + 1) = ki , and we
have yi (t) = ki for all t ∈ [di ]+ due to Lemma 3, which
contradicts Ω > 0. Finally, the theorem holds.
Upon completion of Fully-Utilize(i), the resource allocation feature is described in Lemma 3 and illustrated in Fig. 3
(left). Built on this, Fully-Allocate(i) considers every slot
from di to t1 +1; as illustrated in Fig. 3 (middle) and roughly

8

explained there, upon completion of Fully-Allocate(i), the
resource allocation feature is described as follows.
Lemma 6. Upon completion of Fully-Allocate(i), if there exists a
t ∈ [1, τm ] such that W (t) > 0, let t2 be the latest such slot:
•

•

for all t ∈ [1, t2 ], if the total allocation of Ti in [t, di ] is
Pdi
< Di (i.e., Di − t=t
yi (t) > 0), we have yi (t) = ki ;
the numbers of available machines in [1, t2 ] have a stepped
shape, i.e, W (1) ≥ · · · ≥ W (t2 ) > 0.

Here t2 ≥ t1 .
Proof. See the Appendix for the formal proof.
3.2.3 Phase 2
Now, we introduce AllocateRLM(i, η1 , x). Recall that t0
always denotes the slot closest to but earlier than τm (i.e.,
the latest slot in [1, τm ]) such that W (t0 ) > 0 and, before
executing AllocateRLM(·), t0 = t2 due to Lemma 6. The
resource allocation feature before executing AllocateRLM(i,
η1 , x) is described in Lemma 6 and illustrated in Fig. 3
(middle); the underlying intuition of AllocateRLM(i, η1 , x)
is described in Section 3.2.1 and, upon its completion, the
resource allocation feature is illustrated in Fig. 3 (right).
Formally, AllocateRLM(i, η1 , x) considers each slot t
from di to x and operates as follows repeatedly
each t
Pat
t−1
until the total allocation of Ti in [1, t − 1], i.e., t=1 yi (t),
equals zero, where η1 = 1 and x = t2 + 1 in this section:
Pt−1
1) ∆ ← min{ki − yi (t), t=1 yi (t)}.
Notes. ∆ denotes the maximum allocation of Ti
before t that can be transferred to t with the parallelism constraint.
2) if ∆ = 0, go to the step 5; otherwise, execute the
steps 3-5.
3) set f lag ← 0 and call Routine(∆, η1 , 1, t).
Notes. Routine(·) aims to increase the number
W (t) of available machines at t to ∆. With Lemma 6,
the slots t0 earlier than but closest to t2 + 1 in
Routine(·) will become fully utilized one by one and,
together with the next step 4, upon completion of
the iteration at t, for all t ∈ [t0 + 1, di ], W (t) = 0.
4) set θ ← W (t). Allocate θ more machines to Ti :

yi (t) ← yi (t) + W (t),
and reduce the allocations of Ti at the earliest
slots by θ: in particular, let t00 be such a slot that
Pt00 −1
Pt00
t=1 yi (t) ≥ θ , and execute
t=1 yi (t) < θ and
the following operations:
Pt00 −1
a) set θ ← θ − t=1 yi (t), and, for every t ∈
[1, t00 − 1], yi (t) ← 0;
b) yi (t00 ) ← yi (t00 ) − θ.

5)

Notes. The number of idle machines at t becomes
zero again, i.e., W (t) = 0. The allocation yi (t) of Ti
at every t ∈ [1, t00 − 1] is zero.
if Routine(∆, η1 , 1, t) does not change the value
of f lag , i.e., f lag = 0, t ← t − 1; otherwise, exit
AllocateRLM(i, η1 , x).

Here, at each slot t, when Routine(·) is called, ∆ > 0, and
yi (t) < ki . Further, we have W (t) = 0; otherwise, this

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

contradicts Lemma 6. Hence, with Lemma 5, we conclude
that the task Ti0 in line 12 of Routine(·) exists.
Based on our notes in the description of AllocateRLM(·),
we conclude that
Proposition 3. Upon completion of AllocateRLM(i, 1, x) where
x = t2 + 1, the final allocation to S 00 can guarantee that
Property 4 holds where S 00 = S 0 ∪ {Ti }.
Proof. Fully-Utilize(i), Fully-Allocate(i) and AllocateRLM(i,
η1 , x) never change the allocation at any slot in [τm + 1, d].
AllocateRLM(i, 1, x) ends up with one of the following four
events. The first event occurs when the condition in line 4 of
Routine(·) is true; then, the proposition holds trivially since
all the slots t ∈ [1, di ] have been fully utilized, i.e., W (t) = 0.
If the first event doesn’t occur, the second
Pt−1event is that, for
the first time, at some t ∈ [t2 + 1, di ], t=1 yi (t) = 0; then,
we have that, Ti is fully allocated Di resource in [t, di ] ⊆
[t2 + 1, di ]. The third event occurs when the condition in
line 10 of Routine(·) is true. In the following, we will analyze
the resource utilization state when either of the second and
third events occurs.
Recall that t0 is defined in line 2 of Routine(·) where each
slot in [t0 + 1, di ] will be fully utilized; when the second or
third event occurs, all the slots in [t0 +1, di ] are fully utilized,
i.e., W (t) = 0, for all t ∈ [t0 + 1, di ]. Upon completion of
the iteration of AllocateRLM(·) at t when the third event
occurs, or, at t+1 when the second event occurs, we have the
following three points, in contrast to the allocation achieved
just before executing Allocate-B(i),
(i)

(ii)
(iii)
(iv)

t0 ∈ [1, t2 ] and the allocation to the previous tasks S 0
at every t ∈ [1, t0 − 1] is still the allocation achieved
before executing Allocate-B(i);
Pt0 −1
0
t=1 yi (t) = 0, i.e., the allocation to Ti in [1, t − 1]
is zero and Ti is fully allocated Di resource in [t0 , di ];
the allocation to S 0 at t0 is not decreased;
the allocation to Ti at t0 does not change.

Noticing the above resource allocation state in [1, di ] where
di = τm , since Property 2 holds before executing AllocateB(i), we conclude that Property 2 still holds upon its completion where t0 = t0 . Without loss of generality, assume that
t0 ∈ [τm0 −1 + 1, τm0 ] for some m0 ∈ [m]+ . Then, all the slots
in [τm0 + 1, di ] have been fully utilized and the allocation in
[τm + 1, d] does not change at all; hence, we have that every
interval [τl + 1, d], where m0 ≤ l ≤ L, is optimally utilized
by S 0 ∪ {Ti } due to Property 1. Since the total allocation to
S 0 in [1, τm0 −1 ] isn’t changed by Allocate-B(i) if m0 − 1 > 0,
due to Property 1, the interval [τm0 −1 +1, d] is still optimally
utilized by S 0 and the task Ti is fully allocated Di resource in
this interval; hence, it is still optimally utilized by S 0 ∪ {Ti }.
Further, every interval [τl + 1, d] is also optimally utilized
where 1 ≤ l ≤ m0 − 1. Hence, the theorem holds.
If the first three events don’t occur, the fourth event
occurs upon completion of the iteration of AllocateRLM(·)
at t = t2 + 1, i.e., the last iteration. In this case, we have that
the conditions in lines 4 and 10 of Routine(·) are always false
where at each iteration of AllocateRLM(·) there always exists
such t0 (defined in line 2 of Routine(·) with W (t0 ) > 0); due
to the current resource allocation state, we conclude that, at
each of the slots in [t2 + 1, di ], Ti is allocated ki machines.

9

Upon completion of AllocateRLM(·), there exists a t0 defined
in line 2 of Routine(·), and, let t000 denote the earliest slot
at which yi (t000 ) 6= 0 where t000 ≤ t0 ; then, similar to our
conclusion in the second and third events, we have that
(i)
(ii)
(iii)

the first point here is the same as the first and third
points in the last paragraph;
Ti is fully allocated Di resource in [t000 , di ];
if t000 > t0 , the allocation to Ti at each t ∈ [t000 + 1, t0 ]
does not change and yi (t) = ki due to Lemma 6,
and, the allocation to Ti at t000 is greater than zero.

Similar to our analysis in the last paragraph for other events,
we conclude that the proposition holds.
Proposition 2 and Proposition 3 finish to show that
Allocate-B(i) satisfies Property 3 and Property 4 and hence
completes the proof of Proposition 1. We finally analyze the
time complexity of Allocate-B(i).
Lemma 7. The time complexity of Allocate-B(·) is O(n).
Proof. See the Appendix for the proof.
Algorithm 2: Allocate-B(i)
1
2
3

Fully-Utilize(i);
Fully-Allocate(i);
AllocateRLM(i, 1, t2 + 1);

Since LDF(S ) considers a total of n tasks, its complexity
is O(n2 ) with Lemma 7. Finally, we draw a main conclusion
in this section from Lemma 1 and Proposition 1:
Theorem 1. A set of tasks S can be feasibly scheduled and be
completed by their deadlines on C machines if and only if the
boundary condition holds, where the feasible schedule of S could
be produced by LDF(S ) with a time complexity O(n2 ).
In other words, if LDF(S ) cannot produce a feasible
schedule for S on C machines, then S cannot be successfully
scheduled by any algorithm; as a result, LDF(S ) is optimal.
The relationships between the various algorithms of this
paper are illustrated in Fig. 4 where GreedyRLM will be
introduced in the next section.
Remarks. We are inspired by the GreedyRTL algorithm [3]
in the construction of LDF(·). In terms of the two algorithms
themselves, LDF(·) considers tasks in the decreasing order
of deadlines while the order is determined by the marginal
values in GreedyRTL(·). In both algorithms, the allocation to
a task Ti is considered from di to 1 (once in GreedyRTL, and
possibly three times in LDF(·)); to make time slots t closest
to the deadline of a task Ti being considered fully utilized,
the key operations are finding a time slot t0 earlier than t
such that there exists a task Ti0 with yi0 (t) > yi0 (t0 ) when
W (t), and transferring a part of the allocation of Ti0 at t
to t0 . In GreedyRTL(·), the existence of Ti0 requires that (i)
the number W (t0 ) of available machines at t0 is ≥ k and
(ii)2 W (t) < ki ; as a result, before doing any allocation
to Ti at t, the existence could be proved by contradiction.
In LDF(·), to achieve the optimality of resource utilization,
2. The particular condition there is W (t)
Pdi
y (t)}.
t=t+1 i

<

min{ki , Di −

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

10

Fig. 4. Relationship among Algorithms: for A → B , the blue and green arrows denote the relations that the algorithm A calls B , and, the algorithm
B is executed upon completion of A.

one requirement for such existence is relaxed to be that the
number of available machines at t0 is ≥ 1. The existence is
guaranteed by (i) first make every time slot from di to 1 fully
utilized, as what Fully-Utilize(i) does, and (ii) a steppedshape resource utilization state in [1, di ] upon completion of
the allocation to the last task, as described in Property 2.

a total of C · d01 such tasks, where  ∈ (0, 1) is small enough;
(iii) for all Tj ∈ D2 , vj0 = 1, kj = 1 and Dj = d02 − d01 + 1.
Greedy will always fully allocate resource to the tasks in
D1 , with all the tasks in D2 rejected to be allocated any
resource. The performance guarantee of Greedy will be no
C·d01
more than C·[(1+)(d0 −1)+1·(d
0 −d0 +1)] . Further, with  → 0,
1

2

1

this performance guarantee approaches

4

A PPLICATIONS : PART I

In this section, we illustrate the application of the results
in Section 3 to the greedy algorithm for social welfare
maximization.
In terms of the maximization problem, the general form of
a greedy algorithm is as follows [22], [23]: it tries to build a
solution by iteratively executing the following steps until
no item remains to be considered in a set of items: (1)
selection standard: in a greedy way, choose and consider an
item that is locally optimal according to a simple criterion
at the current stage; (2) feasibility condition: for the item
being considered, accept it if it satisfies a certain condition
such that this item constitutes a feasible solution together
with the tasks that have been accepted so far under the
constraints of this problem, and reject it otherwise. Here,
an item that has been considered and rejected will never
be considered again. The selection criterion is related to the
objective function and constraints, and is usually the ratio of
’advantage’ to ’cost’, measuring the efficiency of an item. In
the problem of this paper, the constraint comes from the
capacity to hold the chosen tasks and the objective is to
maximize the social welfare; therefore, the selection criterion
here is the ratio of the value of a task to its demand that will
refer to as the marginal value of this task.
Given the general form of greedy algorithm, we define a
class GREEDY of algorithms that operate as follows:
1)

2)

Considers the tasks in the non-increasing order of
the marginal value; assume without loss of generality that v10 ≥ v20 ≥ · · · ≥ vn0 ;
Denoting by A the set of the tasks that have been accepted so far, a task Ti being considered is accepted
and fully allocated iff there exists a feasible schedule
for A ∪ {Ti }.

In the following, we refer to the generic algorithm in
GREEDY as Greedy.
Proposition 4. The best performance guarantee that a greedy
algorithm in GREEDY can achieve is s−1
s .
Proof. Let us consider a special instance: (i) let Di = {Tj ∈
T |di = d0i }, where i ∈ [2]+ , d02 and d01 ∈ Z + , and d02 > d01 ;
(ii) for all Tj ∈ D1 , vj0 = 1 + , Dj = 1, kj = 1, and, there is

d02
d02 −d01 +1

s−1
s

d01 −1
d02 .

and
=
When
s=
Hence, the proposition holds.
4.1

d02

d01
d02 .

In this instance,

→ +∞,

d01
d02

=

s−1
s .

Notation

Greedy will consider tasks sequentially. The first considered task will be accepted definitely and then it will
use to the feasibility condition to determine whether or not
to accept or reject the next task according to the current
available resource and the characteristics of this task. To
describe the process under which Greedy accepts or rejects
tasks, we define the sets of consecutive accepted (i.e., fully
allocated) and rejected tasks A1 , R1 , A2 , · · · . Specifically, let
Am = {Tim , Tim , · · · , Tjm } be the m-th set of the adjacent
tasks that are accepted by Greedy where i1 = 1 while
Rm = {Tjm +1 , · · · , Tim+1 −1 } is the m-th set of the adjacent that are rejected tasks following the set Am , where
m ∈ [K]+ for some integer K . Integer K represents the
last step: in the K -th step, AK 6= ∅ and RK can be empty or
non-empty. We also denote by cm the maximum deadline of
all rejected tasks of ∪m
l=1 Rl , i.e.,

cm = maxTi ∈∪m
{di },
l=1 Rl
and by c0m the maximum deadline of ∪m
l=1 Al , i.e.,

c0m = maxTi ∈∪m
{di }.
l=1 Al
While the tasks in Am ∪ Rm are being considered, we
refer to Greedy as being in the m-th phase. Before the
execution of Greedy, we refer to it as being in the 0-th phase.
Upon completion of the m-th phase of Greedy, we define a
threshold parameter tth
m such that
(i)
(ii)

if cm ≥ c0m , set tth
m = cm , and
0
if cm < c0m , set tth
m to any time slot in [cm , cm ].

m
Here, di ≤ tth
m for all Ti ∈ ∪j=1 Rj . For ease of the
th
subsequent exposition, we let t0 = 0 and tth
K+1 = d. We
also add a dummy time slot 0 but the task Ti ∈ T can not
get any resource there, that is, yi (0) = 0 forever. We also let
A0 = R0 = AK+1 = RK+1 = ∅. Besides the notation in
Section 2, the additional key notation used for this section is
also summarized in Table 3.

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

TABLE 3
Main Notation for Section 4
Notation
A1 , R1 ,
A2 , · · · ,
RK
cm
c0m
tth
m

4.2

Explanation
the sets of consecutive accepted (i.e., fully allocated)
and rejected
SK tasks by Greedy where
m=1 Am ∪ Rm = T
the maximum deadline of all rejected tasks of ∪m
l=1 Rl
the maximum deadline of ∪m
l=1 Al
a threshold parameter such that (i) if cm ≥ c0m , set
0
th
tth
m = cm , and (ii) if cm < cm , set tm to any time slot
in [cm , c0m ]; when introducing GreedyRLM, it will be
set to a specific value

A New Algorithmic Analysis

We will show that as soon as the resource allocation done
by Greedy satisfies some features, its performance guarantee
can be deduced immediately, i.e., the main result of this
subsection is Theorem 2.
For all m ∈ [K]+ , upon completion of Greedy, we define
the following two features that we want the allocation to
∪m
j=1 Aj to satisfies:
Sm
Feature 1. The total allocation to j=1 Aj in [1, tth
m ] is at least
r · C · tth
m , where r ∈ [0, 1].
Sm
Feature 2. For each task Ti ∈ j=1 Aj , its maximum amount


of demand that can be processed in each tth
l + 1, d is processed
where m ≤ l ≤ K , i.e.,
di
P
t=tth
l +1


yi (t) = min Di , ki (di − tth
l ) .

Theorem 2. If Greedy achieves a resource allocation structure
that satisfies Feature 1 and Feature 2 for all m ∈ [K]+ , it gives
an r-approximation to the optimal social welfare.

11

Lemma 9. The following schedule achieves an upper bound of
the optimal social welfare of the MSW-II problem, ignoring the
capacity constraint:
1)

2)

Proof. See the appendix for the detailed proof.
Lemma 10. For all m ∈ [K]+ , the total value generated by
0
executing the allocation to T10 , · · · , Tm
is no larger than 1−r
r
times the total value generated by the allocation to ∪m
l=1 Al in
[1, tth
m ].
Proof. See the appendix for the detailed proof.
0
In the case that m = K , the total value from T10 , · · · , TK
is no larger than 1−r
times
the
total
value
from
the
allocar
th
tion to ∪K
l=1 Al in [1, tK ]. Hence, the total value generated
1
by the schedule in Lemma 9 is no larger than 1 + 1−r
r = r
times the total value generated by the allocation to all tasks
of A1 , · · · , AK . By Lemmas 9 and 8, Theorem 2 holds.

4.3

Lemma 8. The optimal social welfare of the MSW-II problem
is an upper bound of the optimal social welfare of the MSW-I
problem.
Proof. See the appendix for the detailed proof.
Due to Feature 1, Feature 2, and the fact that the marginal
0
value of Tm
is no larger than the ones of the tasks of ∪m
l=1 Al ,
we derive the following two lemmas:

Optimal Algorithm Design

We now introduce the executing process of the optimal
greedy algorithm GreedyRLM, presented as Algorithm 3:
(1)
(2)

In the rest of Section 4.2, we prove Theorem 2; we will
first provide an upper bound of the optimal social welfare.
Proof Overview. We refer to the original problem of
scheduling A1 , R1 , · · · , AK , RK on C machines to maximize the social welfare as the MSW-I problem.
In the following, we define a relaxed version of the
MSW-I problem. Assume that R0m consists of a single task
0
whose deadline is tth
Tm
m , whose size is infinite, and whose
marginal value is the largest one of the tasks in Rm , denoted
by v 0m ; here, different from the task in Rm , we assume
0
that there is no parallelism constraint on Tm
whose bound
0
is C . In addition, partial execution of the task Tm
and
the tasks of A1 , · · · , AK can yield linearly proportional
Pdi
value, e.g., if a task Ti ∈ Al is allocated t=1
yi (t) < Di
Pdi
resource by its deadline, a value ( t=1 yi (t)/Di ) · vi will
still be added to the social welfare. We refer to the problem
of scheduling A1 , R01 , · · · , AK , R0K on C machines as the
MSW-II problem.

for all tasks of A1 , · · · , AK , their allocation is the same
as the one achieved by Greedy with Features 1 and 2
satisfied;
0
for all m ∈ [K]+ , execute a part of task Tm
such that

th
the amount of processed
workload
in
t
+
1, tth
m−1
m is

th
(1 − r) · tth
m − tm−1 · C .

(3)

considers the tasks in the non-increasing order of the
marginal value.
in
P the m-th phase, for a task Ti being considered, if
t≤di min{W (t), ki } ≥ Di , call Allocate-A(i), presented as Algorithm 4, where the details on FullyUtilize(i) and AllocateRLM(i, 0, tth
m + 2) can be found
in Section 3.2.2 and Section 3.2.3.
if the allocation condition is not satisfied, set the
threshold parameter tth
m of the m-th phase that is
defined by lines 8-15 of Algorithm 3.

When the condition in line 5 of GreedyRLM is true, every
accepted task can be fully allocated Di resource using FullyUtilize(i). The reason for the existence of Ti0 in Routine(·)
is the same as the reason when introducing LDF(S ) since
W (t0 ) > 0.
Proposition 5. GreedyRLM gives an s−1
s -approximation to the
optimal social welfare with a time complexity of O(n2 ).
Now, we begin to prove Proposition 5. The time complexity of Allocate-A(i) depends on AllocateRLM(·). Using
the time complexity analysis of AllocateRLM(·) in Lemma 7,
we get that AllocateRLM(·) has a time complexity of O(n),
and, the time complexity of GreedyRLM is O(n2 ). Due to
Theorem 2, in the following, we only need to prove that
Features 1 and 2 holds in GreedyRLM where r = s−1
s , which
is given in Propositions 6 and 7.
The utilization of GreedyRLM is derived mainly by
analyzing the resource allocation state when a task Ti cannot
be fully allocated (the condition in line 5 of GreedyRLM is
not satisfied), and we have that

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

12

exceed Di . Finally, upon completion of the whole execution
of Allocate-A(·), we have that

Algorithm 3: GreedyRLM
Input : n tasks with typei = {vi , di , Di , kj }
Output: A feasible allocation of resources to tasks
1

2

3
4
5
6
7
8
9

•

initialize: yi (t) ← 0 for all Ti ∈ T and 1 ≤ t ≤ d,
m = 0, tth
m = 0;
sort tasks in the non-increasing order of the marginal
values: v10 ≥ v20 ≥ · · · ≥ vn0 ;
i ← 1;
while i ≤ n do
P
if t≤di min{W (t), ki } ≥ Di then
Allocate-A(i);
// in the (m + 1)-th phase
else
if Ti−1 has ever been accepted then
m ← m + 1; // in the m-th phase, the
allocation to Am was completed; the
first rejected task is Tjm = Ti

10
11

P
while t≤di+1 min{W (t), ki+1 } < Di+1 do
i ← i + 1;
/* the last rejected task is Tim+1 −1 = Ti
and Rm = {Tjm , · · · , Tim+1 −1 }

12
13
14
15

16

*/

if cm ≥ c0m then
tth
m ← cm ;

else
set tth
m to time slot just before the first time
slot t with W (t) > 0 after cm or to c0m if
there is no time slot t with W (t) > 0 in
[cm , c0m ];

i ← i + 1;

Algorithm 4: Allocate-A(i)
1
2
3

Fully-Utilize(i);
if di ≥ tth
m + 2 then
AllocateRLM(i, 0, tth
m + 2) where t2 = t1 that are
defined in Section 3.2.2;

Proposition 6. Upon completion of GreedyRLM, Feature 1 holds
in which r = s−1
s .
Proof. See the Appendix for the detailed proof.
In GreedyRLM, when a task Ti is accepted (lines 5 and 6),
Allocate-A(·) is called to make it fully allocated. In AllocateA(·), Fully-Utilize(·) and AllocateRLM(·) are sequentially
called; both of them consider time slots t from the deadline
towards earlier ones: (i) Fully-Utilize(·) makes Ti utilize the
remaining (idle) machines at t, and it does not change the
allocations of the previous tasks; (ii) at every t, if Ti does not
utilize the maximum number of machines it can utilize (i.e.,
yi (t) < ki ), AlloacteRLM(·) (a) transfers the allocations of
the previous allocated tasks to an earlier slot that is closest
to t but not fully utilized (i.e., with idle machines), and
(b) increases the allocation of Ti at t to the maximum (i.e.,
ki ) and, correspondingly reduce the equal allocations at the
earliest slots, ensuring the total allocation to Ti does not

the number of allocated machines at each slot does
not decrease,

in contrast to that amount just before executing AllocateA(·). For every accepted task Ti ∈ Am , upon completion
of Allocate-A(·), time slot tth
m + 1 is not fully utilized by
th
the definition of tth
,
i.e.,
W
(t
m
m + 1) > 0. Further, we have
that whenever Allocate-A(·) completes the allocation to a
previous task Ti ∈ Am0 where m0 < m, tth
m + 1 is also not
fully utilized then. Based on this, we draw the following
conclusion.
Lemma 11. Due to the definition of tth
m , we have for all m ≤ j ≤
K that
Sm
(1) [tth
j + 1, d] is optimally utilized by l=1 Al upon completion of the allocation to it using Allocate-A(i);
(2) for the total amount of the allocations to Ti in the interval
[tth
j + 1, d] just upon completion of Allocate-A(i), it does
not change upon completion of GreedyRLM.
Proof. We first prove the first point. Given a m0 ∈ [m]+ , for
every Ti ∈ Am0 , upon completion of Allocate-A(i), W (tth
j +
1) > 0 for all j ∈ [m, K]; based on this,
we conclude that,
Pdi
in the case where di ≥ tth
y (t) = Di if
j + 1, either
t=tth +1 i
j

th
di − tth
j > leni or yi (t) = ki for all t ∈ [tj + 1, di ] otherwise.
The reason for this conclusion is similar to our analysis for
the fourth event when proving Proposition 3; here, there
always exists a slot tth
j + 1 that is not fully utilized, i.e.,
th
W (tj + 1) > 0, leading to that the t0 defined in line 2 of
Routine(·) always exists where W (t0 ) > 0.
Now, we prove the second point in Lemma 11. For
every l ∈ [m0 , K], we observe the subsequent execution of
Allocate-A(·) whose input is a task in Al and could conclude
that,

1)
2)

upon its completion, the allocations to Ti in [1, tth
l ]
are still the ones before executing Allocate-A(·);
Allocate-A(·) can only change the allocations of Ti in
the time range [tl0 +1, tl0 +1 ] where l0 ∈ [l, K] and the
total amount of allocations in [tl0 + 1, tl0 +1 ] upon its
completion is still the amount before its execution.

As a result, we have that, upon completion of Allocate-A(i),
every subsequent execution of Allocate-A(·) never change
the total amount of allocations of Ti in [tl00 + 1, tl00 +1 ] for all
l00 ∈ [m, K].
In the following, it suffices to prove the above two
points. In the execution of Allocate-A(·), Fully-Utilize(·) is
first called and it does not change the allocation to the
previous tasks; then, AllocateRLM(·, 0, tth
l ) is called in which
only Routine(·) (i.e., its lines 12 and 13) in the step 3 can
change the allocation to the previous tasks including Ti . In
lines 12 and 13, a previous task Ti0 is found to change its
allocations at t and t0 ; here, t0 is defined in lines 2 and 7 of
0
Routine(·) and tth
l < t < t. As a result, Allocate-A(·) cannot
change the allocations of the previous tasks in [1, tth
l ]; for all
th
0
t ∈ [tth
l0 + 1, tl0 +1 ] where l ∈ [l, K], during the execution of
the iteration of AllocateRLM(·) at t, we have t0 > tth
l0 . Hence,
the change to the allocations of the previous tasks can only
th
happen in the interval [tth
l0 + 1, tl0 +1 ].

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

From the first and second points of Lemma 11, we could
conclude that


Proposition 7. Given a m
∈ [1, K], tth
l + 1, d is optimally
Sm
utilized by every task Ti ∈ j=1 Aj for all l ∈ [m, K].

5

A PPLICATIONS : PART II

In this section, we illustrate the applications of the results
in Section 3 to (i) the dynamic programming technique for
social welfare maximization, (ii) the machine minimization
objective, and (iii) the objective of minimizing the maximum
weighted completion time.
5.1

Dynamic Programming

For any solution, there must exist a feasible schedule for
the tasks selected to be fully allocated by this solution. So,
the set of tasks in an optimal solution satisfies the boundary
condition by Lemma 1. Then, to find the optimal solution,
we only need address the following problem: if we are given
C machines, how can we choose a subset S of tasks in T
such that (i) this subset satisfies the boundary condition,
and (ii) no other subset of selected tasks achieves a better
social welfare? This problem can be solved via dynamic
programming (DP). To propose a DP algorithm, we need to
identify a dominant condition for the model of this paper
[18]. Let F ⊆ T and recall that the notation λC
m (F) in
Section 3.1. Now, we define a L-dimensional vector
C
C
C
H(F) = (λC
1 (F) − λ0 (F), · · · , λL (F) − λL−1 (F)),
+
C
where λC
m (F) − λm−1 (F), m ∈ [L] , denotes the optimal
resource that F can utilize on C machines in the segmented
timescale [τL−m + 1, τL−m+1 ] after F has utilized λC
m−1 (F)
resource in [τL−m+1 + 1, τL ]. Let v(F) denote the total
value of the tasks in F and then we introduce the notion
of one pair (F, v(F)) dominating another (F 0 , v(F 0 )) if
H(F) = H(F 0 ) and v(F) ≥ v(F 0 ), that is, the solution to
our problem indicated by (F, v(F)) uses the same amount
of resources as (F 0 , v(F 0 )), but obtains at least as much
value.

Algorithm 5: DP(T )
1
2
3
4
5
6
7

8
9

10
11

12

F ← {T1 };
A(1) ← {(∅, 0), (F, v(F))};
for i ← 2 to n do
A(j) ← A(i − 1);
for each (F, v(F)) ∈ A(i − 1) do
if {Ti } ∪ F satisfies the boundary condition then
if there exist a pair (F 0 , v(F 0 )) ∈ A(i) so that
(1) H(F 0 ) = H(F ∪ {Ti }), and (2)
v(F 0 ) ≥ v(F ∪ {Ti }) then
Add ({Ti } ∪ F, v({Ti } ∪ F)) to A(i);
Remove the dominated pair (F 0 , v(F 0 ))
from A(i);
else
Add ({Ti } ∪ F, v({Ti } ∪ F)) to A(i);
return arg max(F ,v(F ))∈A(n) {v(F)};

13

We now give the general DP procedure DP(T ), also
presented as Algorithm 5 [18]. Here, we iteratively construct
the lists A(i) for all i ∈ [n]+ . Each A(i) is a list of pairs
(F, v(F)), in which F is a subset of {T1 , T2 , · · · , Ti } satisfying the boundary condition and v(F) is the total value
of the tasks in F . Each list only maintains all the dominant
pairs. Specifically, we start with A(1) = {(∅, 0), ({T1 }, v1 )}.
For each i = 2, · · · , n, we first set A(i) ← A(i − 1), and for
each (F, v(F)) ∈ A(i − 1), we add (F ∪ {Ti }, v(F ∪ {Ti }))
to the list A(i) if F ∪ {Ti } satisfies the boundary condition.
We finally remove from A(i) all the dominated pairs. DP(T )
will select a subset S of T from all pairs (F, v(F)) ∈ A(n)
so that v(F) is maximum.
Proposition 8. DP(T ) outputs a subset S of T = {T1 , · · · , Tn }
such that v(S) is the maximum value subject to the condition that
S satisfies the boundary condition; the time complexity of DP(T )
is O(ndL C L ).
Proof. The proof is similar to the one in the knapsack
problem [18]. By induction, we need to prove that A(i)
contains all the non-dominated pairs corresponding to feasible sets F ∈ {T1 , · · · , Ti }. When i = 1, the proposition
holds obviously. Now suppose it hold for A(i − 1). Let
F 0 ⊆ {T1 , · · · , Ti } and H(F 0 ) satisfies the boundary condition. We claim that there is some pair (F, v(F)) ∈ A(i) such
that H(F) = H(F 0 ) and v(F) ≥ v(F 0 ). First, suppose that
Ti ∈
/ F 0 . Then, the claim follows by the induction hypothesis
and by the fact that we initially set A(i) to A(i − 1) and removed dominated pairs. Now suppose that Ti ∈ F 0 and let
F10 = F 0 − {Ti }. By the induction hypothesis there is some
(F1 , v(F1 )) ∈ A(i − 1) that dominates (F10 , v(F10 )). Then,
the algorithm will add the pair (F1 ∪ {Ti }, v(F1 ∪ {Ti })) to
A(i). Thus, there will be some pair (F, v(F)) ∈ A(i) that
dominates (F 0 , v(F 0 )). Since the size of the space of H(F)
is no more than (C · T )L , the time complexity of DP(T ) is
ndL C L .
Proposition 9. Given the subset S output by DP(T ), LDF(S )
gives an optimal solution to the welfare maximization problem
with a time complexity O(max{ndL C L , n2 }).
Proof. It follows from Propositions 8 and 1.
Remark. As in the knapsack problem [18], to construct the
algorithm DP(T ), the pairs of the possible state of resource
utilization and the corresponding best social welfare have to
be maintained and a L-dimensional vector has to be defined
to indicate the resource utilization state. This seems to imply
that we cannot make the time complexity of a DP algorithm
polynomial in L.
5.2

Machine Minimization

Given a set of tasks T , the minimal number of machines
needed to produce a feasible schedule of T is exactly the
minimum C ∗ such that the boundary condition is satisfied,
by Theorem 1, where the feasible schedule could be produced with a time complexity O(n2 ). An upper bound of the
minimum C ∗ is k · n and this minimum C ∗ can be obtained
through a binary search procedure with a time complexity
of log (k · n) = O(log n); the corresponding algorithm is
presented as Algorithm 6.

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

Lemma 12. In each iteration of the binary search procedure,
the time complexity of determining the satisfiability of boundary
condition (line 4 of Algorithm 6) is O(L · n) where L ≤ n.
Proof. See the Appendix for the proof.
With Lemma 12, the loop of Algorithm 6 has a complexity O(L · n · log n). Based on the above discussion, we
conclude that
Proposition 10. Algorithm 6 produces an exact algorithm for
the machine minimization problem with a time complexity of
O(n2 , L · n · log n).
Algorithm 6: Machine Minimization)
1

2
3
4

5

L ← 1 , U ← k · n;

// L and U are respectively
the lower and upper bounds of the minimum
number of needed machines

mid ← L+U
2 ;
while U − L ≤ 1 do
if the boundary condition is satisfied with C = C ∗
then
U ← mid;

7

else
L ← mid;

8

mid ←

6

9
10

5.3

L+U
2 ;

C∗ ← U ;
// the optimal number of machines
call the algorithm LDF(T ) to produce a schedule of T
on C ∗ machines;

Minimizing Maximum Weighted Completion Time

Under the task model of this paper and for the objective
of minimizing the maximum weighted completion time
of tasks, a direction application of LDF(S ) improves the
algorithm in [8] by a factor 2. In [8], with a polynomial time
complexity, Nagarajan et al. find a completion time di for
each task Ti that is 1 +  times the optimal in terms of the
objective here; then they propose a scheduling algorithm
where each task can be completed by the time at most 2
times di . As a result, an (2 + 2)-approximation algorithm
is obtained. Instead, by using the optimal scheduling algorithm LDF(S ), we have that
Proposition 11. There is a (1 + )-approximation algorithm
for scheduling independent malleable tasks under the objective of
minimizing the maximum weighted completion time of tasks.

6

C ONCLUSION

In this paper, we study the problem of scheduling n
deadline-sensitive malleable batch tasks on C identical machines. Our core result is a new theory to give the first
optimal scheduling algorithm so that C machines can be
optimally utilized by a set of batch tasks. We further derive
four algorithmic results in obvious or non-obvious ways: (i)
the best possible greedy algorithm for social welfare maximization with a polynomial time complexity of O(n2 ) that
achieves an approximation ratio of s−1
s , (ii) the first dynamic

14

programming algorithm for social welfare maximization
with a polynomial time complexity of O(max{ndL C L , n2 }),
(iii) the first exact algorithm for machine minimization with
a polynomial time complexity of O(n2 , L · n · log n), and (iv)
an improved polynomial time approximation algorithm for
the objective of minimizing the maximum weighted completion time of tasks, reducing the previous approximation
ratio by a factor 2. Here, L and d are the number of deadlines
and the maximum deadline of tasks.

R EFERENCES
[1] Han Hu, Yonggang Wen, Tat-Seng Chua, and Xuelong Li. ”Toward
scalable systems for big data analytics: A technology tutorial.” IEEE
Access (2014): 652-687.
[2] Jain, Navendu, Ishai Menache, Joseph Naor, and Jonathan Yaniv. ”A
Truthful Mechanism for Value-Based Scheduling in Cloud Computing.” In the 4th International Symposium on Algorithmic Game Theory,
pp. 178-189, Springer, 2011.
[3] Navendu Jain, Ishai Menache, Joseph Naor, and Jonathan Yaniv.
”Near-optimal scheduling mechanisms for deadline-sensitive jobs
in large computing clusters.” In Proceedings of the twenty-fourth
annual ACM symposium on Parallelism in algorithms and architectures,
pp. 255-266. ACM, 2012.
[4] Brendan Lucier, Ishai Menache, Joseph Seffi Naor, and Jonathan
Yaniv. ”Efficient online scheduling for deadline-sensitive jobs.” In
Proceedings of the twenty-fifth annual ACM symposium on Parallelism
in algorithms and architectures, pp. 305-314. ACM, 2013.
[5] Yossi Azar, Inna Kalp-Shaltiel, Brendan Lucier, Ishai Menache,
Joseph Seffi Naor, and Jonathan Yaniv. ”Truthful online scheduling
with commitments.” In Proceedings of the Sixteenth ACM Conference
on Economics and Computation, pp. 715-732. ACM, 2015.
[6] Ishai Menache, Ohad Shamir, and Navendu Jain. ”On-demand,
Spot, or Both: Dynamic Resource Allocation for Executing Batch
Jobs in the Cloud.” In Proceedings of USENIX International Conference
on Autonomic Computing, 2014.
[7] Peter Bodı́k, Ishai Menache, Joseph Seffi Naor, and Jonathan Yaniv.
”Brief announcement: deadline-aware scheduling of big-data processing jobs.” In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures, pp. 211-213. ACM, 2014.
[8] Viswanath Nagarajan, Joel Wolf, Andrey Balmin, and Kirsten Hildrum. ”Flowflex: Malleable scheduling for flows of mapreduce
jobs.” In Proceedings of the 12th ACM/IFIP/USENIX International
Conference on Distributed Systems Platforms and Open Distributed
Processing (MiddleWare), pp. 103-122. Springer, 2013.
[9] J. Wolf, Z. Nabi, V. Nagarajan, R. Saccone, R. Wagle, et al. ”The
X-flex Cross-Platform Scheduler: Who’s the Fairest of Them All?.”
In Proceedings of the ACM/IFIP/USENIX 13th MiddleWare conference,
Industry Track. Springer, 2014.
[10] Eugene L. Lawler. ”A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of
late jobs.” Annals of Operations Research 26, no. 1 (1990): 125-133.
[11] D. Karger, C. Stein, and J. Wein. Scheduling Algorithms. In CRC
Handbook of Computer Science. 1997.
[12] James R. Jackson. ”Scheduling a Production Line to Minimize
Maximum Tardiness.” Management Science Research Project Research
Report 43, University of California, Los Angeles, 1955.
[13] W. A. Horn. ”Some Simple Scheduling Algorithms.” Naval Research Logistics Quarterly, 21:177-185, 1974.
[14] Eugene L. Lawler, and J. Michael Moore. ”A Functional Equation
and Its Application to Resource Allocation and Sequencing Problems.” Management Science 16, no. 1 (1969): 77-84.
[15] J. A. Stankovic, M. Spuri, K. Ramamritham, and G. Buttazzo,
Deadline Scheduling for Real-Time Systems: EDF and Related
Algorithms. Kluwer Academic, 1998.
[16] T. White. ”Hadoop: The definitive guide.” O’Reilly Media, Inc.,
2012.
[17] Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, and Joseph Seffi
Naor. ”Machine minimization for scheduling jobs with interval constraints.” In Foundations of Computer Science, 2004. Proceedings.
45th Annual IEEE Symposium on, pp. 81-90. IEEE, 2004.
[18] D. P. Williamson and D. B. Shmoys. The Design of Approximation
Algorithm. Cambridge University Press, 2011.

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

[19] Xiaohu Wu, and Patrick Loiseau. ”Algorithms for scheduling
deadline-sensitive malleable tasks.” In Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing
(Allerton), pp. 530-537. IEEE, 2015.
[20] Xiaohu Wu, and Patrick Loiseau. ”Algorithms for Scheduling Malleable Cloud Tasks (Technical Report).” arXiv preprint
arXiv:1501.04343v4 (2015).
[21] Longkun Guo, and Hong Shen. ”Efficient Approximation Algorithms for the Bounded Flexible Scheduling Problem in Clouds.”
IEEE Transactions on Parallel and Distributed Systems 28, no. 12
(2017): 3511-3520.
[22] G. Brassard, and P. Bratley. Fundamentals of Algorithmics.
Prentice-Hall, Inc., 1996.
[23] G. Even, Recursive greedy methods, in Handbook of Approximation Algorithms and Metaheuristics, T. F. Gonzalez, ed., CRC, Boca
Raton, FL, 2007, ch. 5.

A PPENDIX
Proof of Lemma 2. Before executing Fully-Utilize(i), the resource allocation to the previously allocated tasks S 0 satisfies Property 1. Its execution does not change the previous
allocation to S 0 . Let S 00 = S 0 ∪ {Ti }. Since di = τm ,
the workload of Ti can only be processed in [1, τm ]; the
maximum workload of S 00 that could be processed in
[τm +1, τL ] still equals its counterpart when S 0 is considered,
00
C
0
i.e., λC
L−m (S ) = λL−m (S ). Upon completion of FullyUtilize(i), if the total allocation to S 00 in [1, τm ] is C · τm , we
could conclude that Ti is the last task of S being considered
and all tasks in S have been fully allocated; otherwise,
S 00 ( S , which contradicts the fact that S and its subset
satisfy the boundary condition, which implies that after the
maximum workload of S 00 has been processed in [τm +1, τL ],
00
the remaining workload µC
m (S ) ≤ ·C · τm . Hence, we
conclude that
Proof of Lemma 3. During the execution of Fully-Utilize(i),
upon completion of the allocation to Ti at t ∈ [1, t1 ], if Ti
has not been fully allocated yet, it is allocated ki machines
at this slot. The allocations to Ti at slots t1 , · · · , 1 are nonincreasing, i.e.,

yi (1) ≤ yi (2) ≤ · · · ≤ yi (t1 ).
The reason for this is as follows: Fully-Utilize(i) allocates
machines to Ti from di towards earlier slots and, after the
allocation at every slot t ∈ [1, t1 ], yi (t) = min{ki , Di −
Pdi
y (t)} whose value is non-increasing with t. With
t=t+1 i
Property 2, before executing Fully-Utilize(i), the numbers of
idle machines have a stepped shape, i.e., W (1) ≥ · · · ≥
W (t0 ). The execution of Fully-Utilize(i) does not change
the previous allocation to S 0 and upon its completion the
number of available machines W (t) at every slot t ∈ [1, τm ]
will be no larger than its counterpart before executing
Fully-Utilize(i); we thus have t0 ≥ t1 . Upon completion
of Fully-Utilize(i), deducting the machines allocated to Ti ,
the numbers of idle machines still have a stepped shape in
[1, t1 ]. Hence, the lemma holds.
Proof of Lemma 5. Recall that W (t) is the sum of the allocations yj (t) of all tasks Tj ∈ S at t and W (t) + W (t) =
C . Initially, we have the inequality that W (t) − yi (t) >
W (t0 ) − yi (t0 ) due to the conditions (i)-(iii) of Lemma 5,
and, there exists a Ti0 such that yi0 (t0 ) < yi0 (t); otherwise,
that inequality would not hold. In the subsequent iteration
of Routine(·), W (t) becomes > 0 since partial allocation of

15

Ti0 is transferred from t to t0 ; however, it still holds that
W (t) < ∆ ≤ ki − yi (t). So, we have
W (t)−yi (t) = C−W (t)−yi (t) > W (t0 )−ki = W (t0 )−yi (t0 )
and such Ti0 can still be found like the initial case.
Proof of Lemma 6. If Ti has been allocated Di resource just
upon completion of Fully-Utilize(·), Fully-Allocate(i) does
nothing upon its completion and we have t2 = t1 and
the lemma holds. Otherwise, within [1, τm ], by Lemma 3,
only the time slots t in [1, t1 ] have available machines, i.e.,
W (t) > 0, and, at these time slots, yi (t) = ki ; for all
t ∈ [t1 + 1, di ], W (t) = 0. So, only for each t in [t1 + 1, di ]
and from di towards earlier time slots, Fully-Allocate(i)
will reduce the allocations of the previous tasks of S 0 at t
and transfer them to the latest time slot t0 in [1, t1 ] with
W (t0 ) > 0 (see the step 2 of Fully-Allocate(i)); then, all the
available machines at t will be re-allocated to Ti and W (t)
is still zero again (see the step 3 of Fully-Allocate(i)), and,
the number of available machines at t0 will be decreased to
zero one by one from t1 toward earlier time slots. Due to
Lemma 3, the lemma holds.
Proof of Lemma 7. The time complexity of Allocate-B(i) depends on Fully-Allocate(i) or AllocateRLM(·). In the worst
case, Fully-Allocate(i) and AllocateRLM(·) have the same
time complexity from the execution of Routine(·) at every
time slot t ∈ [1, di ]. In AllocateRLM(·) for every task Ti ∈ T ,
each loop iteration at t ∈ [1, di ] needs to seek the time slot
t0 and the task Ti0 at most Di times. The time complexities
of respectively seeking t0 and Ti0 are O(d) and O(n); the
maximum of these two complexities is max{d, n}. Since
di ≤ d and Di ≤ D, we have that both the time complexity
of Allocate-B(i) is O(dD max{d, n}). Since we assume that
d and k are finitely bounded where D ≤ d · k , we conclude
that O(dD max{d, n}) = O(n).
Proof of Lemma 8. Let us consider an optimal allocation to
A1 , R1 , · · · , AK , RK for the MSW-I problem. If we replace
an allocation to a task in Rm with the same allocation to
a task in R0m and do not change the allocation to Am , this
generates a feasible schedule for the MSW-II problem, which
yields at least the same social welfare since the marginal
value of the task in R0m is no smaller than the ones of the
tasks in Rm ; hence, Lemma 8 holds.
Proof of Lemma 9. We will show in an optimal schedule
of the MSW-II problem that (i) only the tasks of R0m ,
th
A1 , · · · , AK will be executed in [tth
m−1 + 1, tm ], and (ii) the
upper bound of the maximum workload of R0m that could
th
th
th
be processed in [tth
m−1 + 1, tm ] is (1 − r) · (tm − tm−1 ) · C . As
a result, the total value generated by executing all tasks of
th
A1 , · · · , AK and (1 − r) · (tth
m − tm−1 ) · C workload of each
0
+
Rm (m ∈ [K] ) is an upper bound of the optimal social
welfare for the MSW-II problem.
We prove the first point by contradiction. Given a
m ∈ [K]+ , if m ≥ 2, all tasks of R01 , · · · , R0m−1 could
th
not be processed in [tth
m−1 + 1, tm ] due to the deadline
constraint. If m ≤ K − 1, the marginal value of the task in
R0m is no smaller than the ones of R0m+1 , · · · , R0K ; instead
th
of processing R0m+1 , · · · , R0K in [tth
m−1 + 1, tm ], processing
0
Rm could generate at least the same value or even a higher
value. Hence, the first point holds.

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2015

We prove the second point also by contradiction. If there
th
exists a m0 ∈ [1, K] such that more than (1−r)·(tth
m0 −tm0 −1 )·
th
th
0
C workload of Rm0 is processed in [tm0 −1 + 1, tm0 ], let m
denote the minimum such m0 . In the case where m = 1,
due to Features 2 and 1, after the maximum workload of the
th
tasks of A1 has been processed in [tth
1 +1, tK ], the minimum
remaining workload that could be processed in [1, tth
1 ] is at
th
0
least r · tth
1 · C . If more than (1 − r) · t1 · C workload of R1
th
is processed in [1, t1 ], this means that the total amount of
th
workload of A1 processed in [1, tth
1 ] is smaller than r · t1 · C ;
in this case, we could always remove the allocation to R01
and add more allocation to A1 to increase the total value. As
a result, the second point holds when m = 1. In the other
case where m ≥ 2, since we are seeking for an upper bound,
we could assume that for all l ∈ [m − 1]+ , (1 − r) · (tth
l −
0
th
th
tth
)
·
C
workload
of
R
is
processed
in
[t
+
1,
t
]
.
Again
l−1
l
l−1
l
due to Features 2 and 1, similar to P
the case where m = 1, the
minimum available workload of Ti ∈∪m Al that could be
l=1
th
processed in [1, tth
m ] is at least r ·tm ·C . In this case, we could
stillPremove the allocation to R0m and add more allocation
to Ti ∈∪m Al to increase the total value, with the second
l=1
point holding when m ≥ 2.
Proof of Lemma 10. It suffices to prove that, the total alloth
cation to ∪m
l=1 Al in [1, tm ] could be divided into m parts
such that, for all l ∈ [1, m], (i) the l-th part has a size
th
r · (tth
l − tl−1 ) · C , and (ii) the allocation of the l-th part
is associated with marginal values no smaller than v 0l . Then,
the total value generated by executing the l-th part is no
times the total value generated by the
smaller than 1−r
r
th
allocation to R0l in [tth
l−1 + 1, tl ]. As a result, the value
th
generated by the total allocation to ∪m
l=1 Al in [1, tm ] is no
1−r
smaller than r times the value generated by the allocation
0
.
to T10 , · · · , Tm
Due to Feature 1, the allocation to A1 achieves a utilization r in [1, tth
1 ] and we could use a part of this allocation as
the first part whose size is r · tth
1 · C . Next, the allocation to
A1 ∪ A2 achieves a utilization r in [1, tth
2 ]; we could deduct
the allocation used for the first part and get a part of the
remaining allocation to A1 ∪ A2 as the second part, whose
th
size is r · (tth
2 − t1 ) · C . Similarly, we could get the 3rd,
· · · , m-th parts that satisfy the first point mentioned at the
beginning of this proof. Since the marginal value of the task
of R0l is no larger than the ones of the tasks in ∪ll0 =1 Al0
for all 1 ≤ l ≤ m, the second point mentioned above also
holds.
Proof of Proposition 6. We first show that the resource utilization of A1 ∪ · · · ∪ Am in [1, τm ] is r upon completion of the
m-th phase of GreedyRLM; then, we consider a task Ti ∈
∪m
l=1 Rl such that di = cm . Since
P Ti is not accepted when
being considered, it means that t≤di min{ki , W (t)} < Di
at that time and there are at most leni − 1 = d dsii e − 1 time
slots t with W (t) ≥ ki in [1, cm ]. Then, we assume that the
number of the time slots t with W (t) ≥ ki is µ. Since Ti isn’t
fully allocated, we have the current resource utilization of
A1 ∪ · · · ∪ Am0 in [1, cm ] is at least

Cdi − µC − (Di − µki )
Cdi − Di − (leni − 1)(C − ki )
≥
C · di
C · di
C(di − leni ) + (C − ki ) + (leni ki − Di )
s−1
≥
≥
≥ r.
C · di
s

16

We assume that Ti ∈ Rm0 for some m0 ∈ [m]+ . Now,
we show that, after Ti is considered and rejected, the subsequent resource allocation by Allocate-A(j ) to each task Tj of
∪L
l=m0 +1 Al doesn’t change the utilization in [1, τm ]. FullyUtilize(j ) does not change the allocation to the previous
accepted tasks; the operations of changing the allocation
to other tasks in AllocateRLM(j , 0, tth
m + 2) happen in its
th
call to Routine(∆, 0, 1, t) where we have cm0 ≤ tth
m0 ≤ tl
0
for all m + 1 ≤ l ≤ L. Due to the function of lines 68 of Routine(∆, 0, 1, t), in the l-th phase of GreedyRLM,
the call to any Allocate-A(j ) will never change the current
allocation of A1 ∪ · · · ∪ Am0 in [1, cm ]. Hence, if tth
m = cm ,
upon completion of GreedyRLM, the resource utilization of
A1 ∪· · ·∪Am where m0 ≤ m; if tth
m > cm , since each time slot
th
in [cm + 1, tth
m ] is fully utilized by the definition of tm , the
th
resource utilization in [cm + 1, tm ] is 1 and the final resource
utilization will also be at least r.
Proof of Lemma 12. Recall the process of defining µC
m (S)
where S = T . In Definition 1 that defines λm (T ), n
tasks are considered sequentially for each m ∈ [L]+ , leading to a complexity L · n. In Definition 2 that derives
C
C
C
λC
m (T ) from λm (T ), λ1 (T ), λ2 (T ), · · · , λL (T ) are considered sequentially,
leading
to
a
complexity
O(L). Finally,
P
C
µC
(T
)
=
D
−
λ
(T
)
.
Hence,
the
time
complexi
m
m
Ti ∈T
ity of determining the satisfiability of boundary condition
depends on Definition 1 and is O(L · n).

