Available online at www.sciencedirect.

com

Expert Systems
with Applications
Expert Systems with Applications 34 (2008) 2071–2081
www.elsevier.com/locate/eswa

Multiprocessor system scheduling with precedence and

resource constraints using an enhanced ant colony system
Shih-Tang Lo a, Ruey-Maw Chen b, Yueh-Min Huang a,*
, Chung-Lun Wu c

a
Department of Engineering Science, National Cheng-Kung University, Tainan 701, Taiwan, ROC
b
Department of Computer Science and Information Engineering, National Chin-yi Institute of Technology, Taichung 411, Taiwan, ROC
c
Department of Electronic Engineering, National Chin-yi Institute of Technology, Taichung 411, Taiwan, ROC

Abstract

This study presents and evaluates a modified ant colony optimization (ACO) approach for the precedence and resource-constrained
multiprocessor scheduling problems. A modified ant colony system is proposed to solve the scheduling problems. A two-dimensional
matrix is proposed in this study for assigning jobs on processors, and it has a time-dependency relation structure. The dynamic rule
is designed to modify the latest starting time of jobs and hence the heuristic function. In exploration of the search solution space, this
investigation proposes a delay solution generation rule to escape the local optimal solution. Simulation results demonstrate that the pro-
posed modified ant colony system algorithm provides an effective and efficient approach for solving multiprocessor system scheduling
problems with resource constraints.
 2007 Elsevier Ltd. All rights reserved.

Keywords: Ant colony optimization; Scheduling; Multiprocessor

1. Introduction Many different schemes have been presented for solving

scheduling problems. In practice, multiprocessor schedul-
1.1. Scheduling problem ing problems only consider the precedence constraint
and finding the minimum of maximum complete time. In
Job scheduling problems are typically considered to this study, an ACO approach for the precedence and
involve executing a set of jobs satisfying given constraints resource-constrained multiprocessor scheduling problem
and optimizing given criteria. Jobs are assigned timing con- is presented and evaluated.
straints such as ready time, due date, and a processing time
(Cardeira & Mammeri, 1996). There are also some other 1.2. Multiprocessor scheduling problems using genetic
constraints, like setup time between two jobs, job prece- algorithm
dence, and resource requirements. Scheduling has many
applications in commercial, industrial and academic fields, In a multiprocessor scheduling problem, given programs
including avionics, communications, signal processing, (tasks) with precedence relation within tasks are scheduled
routing, industrial control, operations research, production in a given multiprocessor system, such that the program’s
planning, project management, process scheduling in oper- execution time is minimized. Such problems are the same
ating systems, class arrangement and grid computing. as the task-scheduling problem. This problem is extremely
difficult to solve precisely, and many heuristic methods for
*
finding a suboptimal or optimal schedule exist. Most
Corresponding author.
E-mail addresses: [email protected] (S.-T. Lo), raymond@
scheduling problems are confirmed to be NP-complete
mail.ncit.edu.tw (R.-M. Chen), [email protected] (Y.-M. Huang), problems. The traveling salesman problem (TSP) is a typi-
[email protected] (C.-L. Wu). cal NP-complete problem, for which obtaining an optimal

0957-4174/$ - see front matter  2007 Elsevier Ltd. All rights reserved.
doi:10.1016/j.eswa.2007.02.022
2072 S.-T. Lo et al. / Expert Systems with Applications 34 (2008) 2071–2081

solution for a tour with a minimum distance is quite time- (ACS) to solve TSP. Simulation results indicate that ACS
consuming. Liu and Leyland pioneered real-time schedul- outperforms other nature-inspired algorithms, such as sim-
ing algorithms for mono-job or scheduling of independent ulated annealing and evolutionary computation. Applica-
and periodic tasks (Liu & Layland, 1973). The genetic algo- tions of the ACO algorithm are also involved in solving
rithm (GA) is the most popular and widely used technique job shop scheduling problems (Pierucci, Brandani, & Sog-
for several kinds of multiprocessor scheduling problem aro, 1996). Besten, Sttzle, and Dorigo (2000) presented an
(Correa, Ferreira, & Rebreyend, 1996; Hou, Ansari, & application of the ACO meta-heuristic to the single
Ren, 1994). Crossover, mutation and selection operators machine total weighted tardiness problem. Gajpal, Rajen-
are applied to create for the new generation of schedules dran, and Ziegler (2004) adopted ACO to solve the prob-
and find the solution with GA. Hou et al. (1994) developed lem of scheduling in flowshop with sequence-dependent
an efficient method, the height value of each job in graph, setup times of jobs. Rajendran and Ziegler (2004) devel-
based on a genetic algorithm to solve the multiprocessor oped two ant colony optimization algorithms for
scheduling problem. Correa, Ferreira, and Rebreyend solving the permutation flowshop scheduling problem.
(1999) proposed a novel combined approach, in which a Merkle, Middendorf, and Schmeck (2002) presented an
genetic algorithm is enhanced with the introduction of ACO approach for the resource-constrained project sched-
some knowledge about the scheduling problem represented uling problem (RCPSP), which is a schedule problem to
by the use of a list heuristic in the crossover and mutation find the minimum makespan with resource and precedence
genetic operations. Zomaya, Ward, and Macey (1999) constraints. These studies indicate that ACO can work suc-
studied an alternative paradigm, based on genetic algo- cessfully in many different scheduling applications about
rithms, to solve the parallel processor scheduling problem combination problems.
efficiently without the need to apply any restrictive prob-
lem-specific assumptions. The above studies focused only 1.4. Artificial neural networks
on multiprocessor scheduling without resource constraints.
Some works focus on finding the minimum processors or Hopfield and Tank first adopted artificial neural net-
the heterogeneous processors scheduling problems. Oh works, called Hopfield neural networks (HNN), to solve
and Wu (2004) presented a multi-objective genetic algo- optimization problems. In the HNN (Hopfield & Tank,
rithm, which aims to minimize the number of processors 1985), the state input information from a community of
required and the total tardiness of tasks. Topcuoglu, neurons is received to determine the neuron output state
Hariri, and Wu (2002) presented two novel scheduling information. Each neuron exchanges information with
algorithms for a bounded number of heterogeneous proces- other neurons in the network. These neurons apply this
sors, aiming to meet high performance and fast scheduling information to move the network cooperatively, thus
time simultaneously. achieving convergence. A competitive Hopfield neural net-
A GA generates a high quality of output schedules in work (CHNN) utilizes a competitive learning mechanism
homogeneous or heterogeneous systems, but the scheduling to update the neuron states in the Hopfield neural network.
times are generally much higher than with the heuristic- In our previous work, a multi-constraint schedule problem
based schemes. Additionally, several control parameters for a multiprocessor system was solved by HNN (Huang &
in a genetic algorithm need to be determined appropriately. Chen, 1999). Chen et al. also presented a modified neural
Hence, GA along with simulated annealing (SA) and local network to solve the multiprocessor scheduling problem
search methods, called guided random search techniques, with inequality constraints (Chen, Lo, & Huang, 2007).
have been presented (Kwok, Ahmad, & Gu, 1996; Topcuo- A series of studies has been conducted using HNN and
glu et al., 2002; Wu, Shu, & Gu, 1997). mean field annealing. These schemes are adopted for mul-
tiprocessor scheduling problems, and a modified cooling
1.3. Ant system for job scheduling problems schedule has been developed to accelerate the convergence
rate for the problem investigated (Chen & Huang, 1998). A
In ACO, a set of ant-like agents or software ants solve typical CHNN scheme has also been applied to the same
the problem under consideration cooperatively. This effort problem (Chen & Huang, 2001). Most of these works con-
is mediated by exchanging information based on the prob- centrate on the specific multiprocessor scheduling situa-
lem structure collected concurrently by the agents, while tions in which each resource type has one resource
building solutions stochastically. Similarly, an ACO sched- available.
uling algorithm, consisting of concurrent distributed
agents, which discovers a feasible solution, is presented. 1.5. Resource-constrained multiprocessor scheduling
ACO is a class of constructive meta-heuristic algorithms problems
that share the common approach of building a solution
on the basis of information provided by both a standard This work attempts to find optimal or near-optimal
constructive heuristic function and previously constructed solutions to multiprocessor schedule problems with re-
solutions (Maniezzo & Carbonaro, 1999). Dorigo and source and precedence constraints and restricted schedul-
Gambardella (1997) first applied the ant colony system ing times, known as resource-constrained multiprocessor
 S.-T. Lo et al. / Expert Systems with Applications 34 (2008) 2071–2081 2073

scheduling problems, and denoted by RCMPSP in this Initialize

study. The traditional multiprocessor scheduling problems Loop
only consider the precedence constraint, and do not Each ant is positioned on a starting node
address the resource requirement problem while executing. Loop
However, RCMPSP has some processors available in
Each ant applies a state transition rule to incrementally build a
scheduling problems, not only with the precedence relation
solution and a local pheromone update rule
between jobs, but also with the resource requirement con-
Until all ants have built a complete solution
straints. This work not only meets the job precedence
and resource requirement, but also minimizes the make- A global pheromone updating rule is applied
span. The proposed algorithm enables fast optimal or Until End_condition is reached
near-optimal solutions to be found, and is useful in indus-
trial environments where computational resources and time Fig. 1. ACS for TSP.
are restricted.
RCPSP using ACO algorithms has recently been studied Normally, each edge (i, j) is associated with one value rep-
(Brucker, Drexel, Möhring, Neumann, & Pesch, 1999; Her- resenting a distance or cost. Each ant establishes a com-
roelen, Reyck, & Demeulemeester, 1998; Merkle et al., plete tour in a graph (i.e., a feasible solution to the TSP)
2002). These scheduling problems have been demonstrated by repeatedly applying a stochastic greedy rule (the state
to be NP-hard. The ACO has been successfully applied to transition rule) to choose nodes to visit. Ants choose the
RCPSP, combined with the different heuristics, easily next node to visit using a combination of heuristic and
obtaining a near-optimal solution. The RCMPSP is a gen- pheromone information. Ant k at node vi selects the next
eral scheduling problem. Therefore, the concept can be node vj to move based on Eq. (1) when q 5 q0:
adopted to solve project scheduling, job-shop, flow-shop, n o
open-shop problems and grid computing problems. Hence, ½sði; jÞa ½gði; jÞb ¼ max ½sði; lÞa ½gði; lÞb ð1Þ
vl 2J k ðiÞ
the RCMPSP is of interest in this investigation.
The rest of this study is organized as follows. Section 2 where q is a random number uniformly distributed in [0, 1],
reviews the ant colony system in the TSP problem and the and 0 5 q0 5 1 is an predetermined parameter that deter-
constraints of RCMPSP. Section 3 describes the proposed mines the relative importance of exploitation versus explo-
ACO algorithm, which combines the delay solution gener- ration. s(i, j) denotes the pheromone level on edge (i, j). And
ation rule and dynamic rule for the scheduling problem. g(i, j) represents a heuristic function defined as the recipro-
The simulation examples and experimental results are pre- cal of cost. Jk(i) denotes the set of nodes to be visited by ant
sented in Section 4. Conclusions and discussions are given k at node vi, and parameter a, b determines the relative
in Section 5. importance between the pheromone level and the edge cost.
If q > q0, vj is randomly selected from Jk(i) according to
2. Ant colony system and scheduling problem the probability distribution given by the following
equation:
2.1. Ant colony system 8 a b
< P ½sði;jÞ ½gði;jÞ ; if j 2 J k ðiÞ;
½sði;lÞa ½gði;lÞb
The ACO algorithm has been demonstrated to be an pk ði; jÞ ¼ vl 2J k ðiÞ ð2Þ
:
effective means of solving complex combinatorial optimiza- 0; otherwise:
tion problems. In ACO, the positive feedback of phero- After an ant has completed its tour, the pheromones on
mone deposits on arcs comprising more optimal node-arc the edges of that tour are updated using the local updating
tours (paths), allows the next cycle (iteration) to progress rule. The ACS uses the following local updating rule to pre-
toward an optimal solution (Stützle & Hoos, 2000). ACO vent succeeding ants from searching in the neighborhood
mimics the behavior of foraging ants. Ants deposit phero- of the current best tour. The rule is defined as
mones on the paths that they move along. The pheromone
level deposited on a particular path increases with the num- sði; jÞ ¼ ð1  qÞsði; jÞ þ qDsði; jÞ; ð3Þ
ber of ants passing along it. Ants adopt pheromones to where q (0 < q < 1) is a parameter representing the local
communicate and cooperate with each another in order pheromone evaporation rate, and Ds(i, j) = s0 is the initial
to identify the shortest paths to a destination. ACO is pheromone level.
applied to the TSP first, since it enables an efficient evolu- Once all the ants have completed their tours, the phero-
tion toward quality sub/optimal solutions. Dorigo et al. mones on all edges of the graph are updated using the glo-
proposed the ACO algorithm to solve the well-known bal updating rule. The ACS uses the global updating rule
TSP, which evolved into the ant colony system (ACS) as to accelerate searching for the best solution. The global
shown in Fig. 1 (Dorigo & Gambardella, 1997; Dorigo, updating rule enhances the edges discovered in the globally
Maniezzo, & Colorni, 1996). best tour and is defined as
A graph G = (V, E) comprises a set of nodes (vertex)
V = {v1, v2, . . ., vn} and a set of edges E = {(i, j)jvi, vj 2 V}. sði; jÞ ¼ ð1  dÞsði; jÞ þ dsgb ði; jÞ; ð4Þ
2074 S.-T. Lo et al. / Expert Systems with Applications 34 (2008) 2071–2081

where d (0 < d < 1) is a parameter representing the global investigates a job scheduling problem involving non-pre-
pheromone evaporation rate, and emptive multitasking with processing time, precedence
( and resource constraints conditions. However, meta-heu-
L1
gb ; if edgeði; jÞ 2 the global best tour; ristic methods such as genetic algorithms, artificial neural
sgb ði; jÞ ¼
0; otherwise; networks, and simulated annealing are time-consuming.
ð5Þ However, the ACO has been demonstrated to have a fast
convergence rate in many applications. A modified ACO
where Lgb represents the globally best tour in the current has been built to solve defined scheduling problems. The
iteration. major difference between RCMPSP and RCPSP is that
The ACO algorithm has recently been applied to sched- RCMPSP has a special resource type – processors (or
uling problems, such as job-shop, flow-shop, and single machines), and one processor can only process one job
machine tardiness problems (Bauer et al. 1999; Dorigo & (activity) at a time. The studied multiprocessor system
Gambardella, 1997; Iredi, Merkle, & Middendorf, 2001; comprises a number of identical (homogeneous) proces-
Merkle & Middendorf, 2001). Traditionally, the phero- sors. In other words, this study focuses on homogeneous
mone matrix s = [sij], where the pheromone is added to processors only, while the number of processors can be limi-
an element sij of the pheromone matrix, finds a good solu- ted or unlimited.
tion where job j is the ith job on the machine. The following The formal assumptions of the scheduling problem
ants of the next generation directly use the value of sij and domain are introduced in advance. Suppose that there
heuristic function to estimate the desirability of placing job are N jobs and M machines in a scheduling system. First,
j as the ith job on the machine when obtaining a new solu- a job cannot be both segmented and preemptive. Second,
tion (Merkle et al., 2002). Bauer, Bullnheimer, Hartl, and a job cannot be assigned to different machines, which
Strauss (1999) proposed ACO algorithms using a conven- implies that no job migration is allowed between machines.
tional pheromone matrix [sij] to solve the single machine Based on these assumptions, a set of job schedules is
total tardiness problem and the flow-shop problem. This sought. Let J = {1, . . ., N} denote the set of jobs, and
study adopts a modified pheromone matrix [stj], in which m = {1, . . ., M} represent the set of machines. Q denotes a
the element stj, denoting the pheromone value of job j is set of resource totals of g types, and Ri = 0 is the resource
processed at time t on a specific machine. Restated, the quantity for resource type i, i 2 Q. Each job j, j 2 J, has a
two-dimensional grid for assigning jobs on processors is a duration pj and resource requirements rj, 1, . . ., rjg, where rj, i
time-dependent relation structure for scheduling jobs. denotes the requirement for a resource type i when process-
The element stj is similar to sij, which is designed to suit ing job j. The value of rj, i does not change with time (Mer-
a dynamic environment. kle et al., 2002). There are precedence relations between the
jobs, and setup time is assumed to zero from one job switch
2.2. Scheduling problem to the next job. The precedence relations between the jobs
can be represented by an acyclic activity-on-vertex (AOV)
Most scheduling problems focus on minimizing either network. A job schedule list is mapping a set of tasks to
the maximum complete time (makespan) or the tardiness. a set of processors to meet the job precedence relations
However, maximizing performance, and minimizing make- and resource requirements.
span and scheduling time are the major issues in multipro- Fig. 2 shows a basic example of the problem domain
cessor scheduling problems. Examples of such problems studied, including a precedence graph and resources con-
include scheduling jobs onto a fixed set of machines in a straint with six jobs and four resource types on two
manufacturing plant, scheduling aircraft takeoffs and land- machines. The total utilized resources can not be more than
ings onto one or more landing strips, and scheduling meet- the total available resources for each resource type at a cer-
ing rooms for multiple events of varying size and length. tain time. A two-dimensional matrix (T · N) is adopted to
Solving multiprocessor scheduling problems containing denote the scheduling result. The axes of the matrix are job
precedence and resource constraints is similar to the above and time, as denoted by j and t, respectively. The state of a
examples, and is the major concern in this study. This work coordinate is represented by Vtj.The value of Vtj is set to

Fig. 2. Simulation cases for six jobs with precedence and resource constraints and one solution matrix.
 S.-T. Lo et al. / Expert Systems with Applications 34 (2008) 2071–2081 2075

one (Vtj = 1) if job j is processed at time t, otherwise average quality of the solutions found by the ants of a gen-
Vtj = 0. Every Vtj is associated with one stj and one gtj. eration is unchanged for several generations.
Thus, unlike other approaches, the stj and gtj in the pro- The state transition rules are governed by Eqs. (6) and
posed approach is time-dependent. (7) (Park et al., 1994). The next job j is chosen from Jk(t)
when q 5 q0, which flavors the choices for the next job with
3. Modified ACO algorithm for RCMPSP the highest pheromone times heuristic value, where the g
function is defined in Eq. (8):
n o
Fig. 3 displays the steps of the scheduling algorithm for a b
j ¼ arg max ½sðt; lÞ  ½gðt; lÞ ð6Þ
the resource-constrained multiprocessor scheduling prob- l2J k ðtÞ
lem by modified ACS, which combines the dynamic rule
If q > q0, then job j is randomly selected from Jk(t) accord-
and delay solution generation rule, and is called a dynamic
ing to the probability distribution given by the following
and delay ant colony system (DDACS). DDACS begins
equation:
with a partial schedule containing no jobs at time 0. At 8
each stage, a set of all eligible jobs Jk(t), comprising all can- > ½sðt;jÞa ½gðt;jÞb
< P ½sðt;lÞa ½gðt;lÞb
; j 2 J k ðtÞ;
didates for successors at time t. The initial jobs in Jk(0) P k ðt; jÞ ¼ l2J k ðtÞ ð7Þ
have in-degree = 0 which refers to the number of eligible >
:
0; otherwise;
jobs at time 0. The following jobs selected from Jk (t) are
applied until m = M or not satisfying resource constraints. where a, b denote the parameters correlating to the impor-
A job is selected by the ant from Jk(t) if it satisfies resource tance of the pheromone and heuristic, respectively. Con-
and processor constraints. The processor constraint defines cerning heuristics, this study adopts the adaptations of
the most M jobs that can be assigned to M processors. priority heuristics known as the critical path method to
After allocating one job to one processor so as to satisfy determine the earliest/latest starting process time; Ej/Lj
the resource constraints, C and Jk(t) are then updated, for job j, j 2 J. The Ej and Lj are initially computed under
where C denotes the set of already scheduled jobs. The no resource considerations, hence there is a conservative
algorithm runs until a stopping criterion is met, e.g., a cer- value for each job. However, the actual starting process
tain number of generations have been performed or the time of some jobs is behind the Lj when involving resource

Fig. 3. DDACS algorithm.

2076 S.-T. Lo et al. / Expert Systems with Applications 34 (2008) 2071–2081

constraints. The Lj is used in the g function to build the ini-

tial solution. The Lj from the best solution of all ants is
adopted in every iteration. Finally, the Lj is changed
dynamically in the coming iteration according to dynamic
rules given in Section 3.3. Eq. (8) shows the g function of
the modified ACO:
8 1 ffiffiffiffiffiffiffi
< ðd j þ1Þp
c p þ1
; if Ej 6 t < Lj ;
j Fig. 4. Simulation result of another ant after the previous ant using the
gðt; jÞ ¼ ; j 2 J k ðtÞ ð8Þ local update rule.
: 1 pffiffiffiffiffiffiffi
; if t P Lj ;
ð2d =c Þ c p þ1
j 1 j

where dj = jLj  tj and c, c1 are large enough constant 3.2. Global update rule
values.
Eq. (8) demonstrates that job j with the shortest process After all ants have built all feasible schedules, the global
time (shortest pj) and nearest to Lj (minimum dj) obtains update rule, Eq. (10), is used to increase the pheromone stj
the highest g value. Job j with the highest probability by applying the best solution so far. For all stj, the phero-
(Pk(t, j)) is selected from Jk(t) at time t. Hence, the job with mone is increased by the global update rate if Vtj = 1,
minimum dj and shortest pj is first when Ej 5 t < Lj, or the where t = Sj, and is otherwise evaporated by global phero-
job with maximum dj and shortest pj is maximum first when mone evaporation rate, as shown in Eq. (10). This is an elit-
t = Lj.Once one job j is selected according to the state tran- ist strategy that leads ants to search near the best-found
sition rule Eq. (6), then Vtj = 1, t 2 [Sj, fj], where Sj = t and solution:
fj = t + pj  1. Restated, Sj (fj) is the starting (finish) pro-
cess time of job j in the current solution. Thus this setting sðt; jÞnew ¼ ð1  dÞ  sðt; jÞ þ d  Dsgb ðt; jÞ; t ¼ Sj ð10Þ
ensures that the non-preemptive requirement is satisfied. where 0 < d < 1 denotes a parameter representing the glo-
Restated, Vtj is set to one during the time period of Sj to bal pheromone evaporation rate, and
fj. An unassigned job has high g value (>1/2) when the time 
t > Lj, and low g value (<1/2) when t < Lj for jobs in Jk(t). Dms; if V tj ¼ 1;
Dsgb ðt; jÞ ¼ and
A job with a g value of 0 is not a member of Jk(t). The g 0; if V tj ¼ 0
value of a job is close to 1/2 when Lj = t. However, the g 1 þ maxf0; msold  msgb g
value of a job is always between 0 and 1. Dms ¼ ð11Þ
msgb

3.1. Local update rule where Dsgb(t, j) is computed by the best schedule in the cur-
rent iterations, and the amount of pheromone added is
The pheromones stj are updated by the local updating dDsgb(t, j) when job j is assigned to run in time period [Sj, fj].
rule after an ant has built one RCMPSP solution. The The msold and msgb denote the makespan of the best sche-
modified ACS adopts the following local updating rule to dule in the previous and current iterations, respectively.
prevent succeeding ants from searching in the neighbor- For each job, pheromone is added when a job is being pro-
hood of the current schedule of the current ant. The ants cessed in the job schedule list of the best solution obtained
select job j at time t, and then modify their pheromone in the current generation. Otherwise, the pheromone is
levels: evaporated if Vtj = 0.
sðt; jÞnew ¼ ð1  qÞ  sðt; jÞ þ q  Dsðt; jÞ; t ¼ Sj; ð9Þ
3.3. Dynamic rule
where 0 < q < 1 denotes the evaporation rate as an input
parameter, where job j progresses from Sj to fj. Ds(t, j) = The studied multiprocessor scheduling system with
s0 is set in the proposed ACO method. If the pheromone resource constraints combines the RCPSP and task assign-
stj is set to a low value, then job j has a lower probability ment. One job’s earliest starting and latest starting time is
of being chosen by another ant at time t. computed by the critical path. The makespan is first
In Fig. 2, job 1 2 Jk(1) is the first job in the schedule at assumed to be equal to the critical path length without con-
time 1, where Jk(1) = {1, 5}. Thus, s11 evaporates some sidering the resource constraints. Owing to the resource
pheromone lower than s15, according to the local update constraints, the makespan may be larger than the critical
rule. At time 3, Jk(3) = {2, 3, 5}. If jobs 2 and 3 are selected, path in the optimal solution. That is, the value of Lj
the related s value (s32 and s33) is decreased. Fig. 4 shows increases along with the makespan. A schedule may contain
another feasible solution for the next ant, while job 5 is some jobs that start to run behind Lj, which is a conserva-
the first job to be assigned to the processor with the highest tive value and is initially determined under no resource
s value. Such a solution has the smallest makespan, i.e. considerations, while the g function is based on the latest
makespan = 11. The local update rule adopted to select starting time, as shown in Eq. (8). If the Lj cannot reflect
another job is a strategy to avoid being trapped in a local the actual latest starting time, then the Lj is an excessively
maximum (or minimum). conservative value for the state transition rule. Therefore, a
 S.-T. Lo et al. / Expert Systems with Applications 34 (2008) 2071–2081 2077

rule is designed to refine the latest starting time by feedback mines the probability of changing the influence on the deci-
of the best solution found in each iteration. This rule is sions of the ants. The rules in Eqs. (6) and (7) are adopted
called a ‘‘dynamic’’ rule. If the job is processed before the when q 5 q1. Otherwise, this delay strategy is applied when
Lj, then the Lj does not need to be extended later. For those q > q1 and t < Lj. The q1 value increases along with the iter-
jobs that have been processed later than the Lj, the new Lj ation. The q1 value is close to one after certain iterations.
is replaced by the Sj. Restated, this replacement is used to Restated, the possibility of delaying jobs is decreased as
acquire the most accurate value for Lj. This rule is adopted the iteration increase.
in step 22 of the DDACS procedure in Fig. 3. The accuracy The DDACS combines the above described rules to
of estimation of the g function value rises as the accuracy explore the search space of a feasible solution. The follow-
of Lj increases. The Lj dynamic adjustment rule is defined ing simulations indicate these rules are suitable for
as follows: resource-constrained multiprocessor problems.

Lj ; if Ej < S j 6 Lj ;
Lj ¼ ð12Þ
S j ; if Lj < S j : 4. Experimental simulations

The simulations involved different sets of scheduling

3.4. Delay solution generation rule problems with different jobs, from 10 to 30 jobs on different
processors, then later with 30–120 jobs. All simulation
The delay solution generation rule (called the delay rule cases assumed that three or four different resource types
for short) is indicated in step 11 of DDACS. This rule were available and 10 ants were adopted. The simulations
enables some jobs to be assigned later on purpose to escape used various set of weighting factors. The q0 value was
the local optimal solution. The delayed job is excluded from set in the range of [0.8, 0.95]. The initial q1 value was set
in Jk(t) for a certain delay length, which is a uniform distri- in the [0.7, 0.95] range. Other settings were: iterationmax =
bution of [0, Lj  t] as demonstrated in Eq. (13). The delay is 1000, s0 = 0.01, c = 10 and c1 = 50. Moreover, d = 0.1,
not later than Lj, hence theSj of job j cannot be greater than q = 0.1, a = 1, b = 1, q0 = 0.9 and q1 = 0.95 were set in
Lj. One job can be processed later to let the other jobs be the simulation, if no other values are mentioned.
processed ahead to yield global optimal solution under Fig. 5 shows the simplest case. This case involves 10
the resource constraints. For instance, if one job requiring jobs, two or three processors with the given precedence
many resources at time t is selected and added into C, then and resource constraints. Figs. 6 and 7 indicate the sched-
some other jobs requiring same resources are prohibited uling results for two processors. Figs. 8 and 9 display the
from being processed for some time. Accordingly, these jobs simulation results of three processors. Figs. 6 and 8 show
result in a larger makespan than the optimal solution. the results of the no-delay rule used in the modified
Fig. 6 depicts an example of this situation. Based on the ACO. Figs. 7 and 9 display scheduling results of using
proposed method without delay strategy, two jobs in the delay rule in the algorithm.
Jk(1) = {1, 2, 3} are schedule to run when two processors The makespan of the optimal solution in the two proces-
exist at t = 1. Suppose that jobs 1 and 2 are assigned for sors case is ten; thus the proposed approach with the delay
processing, and Jk(2) = {3, 4, 5} at time 2. In this case, rule can obtain the optimal solution in less than 10 itera-
job 2 needs two R3 resources and job 5 needs three R3 tions. Meanwhile, the simulation results of using three pro-
resources. The total amount of R3 resources available is cessors indicate that more processors do not improve the
4, which is not sufficient for processing jobs 2 and 5 concur- makespan, due to the resource constraints and because
rently at t = 2. The solution is never optimal if job 2 is the jobs would be completely finished with two processors.
scheduled at t = 1. If jobs 2 and 3 are delayed to process, The following simulation cases are PSLIB cases, which
then the other jobs (jobs 4 and 5) can be executed earlier, are one special problem case of the studied RCMPSP.
and the successor jobs of jobs 4 and 5 can start to run as The PSLIB library has cases with 30–120 jobs; each case
soon as possible. Hence, an optimal solution is obtained,
since job 7 is a critical path job and processed earlier.
The comparison between cases without delay strategy
and with delay strategy is shown in Figs. 6 and 7.
The ‘‘delay’’ rule deliberately delays an eligible job, as
shown in Eq. (13). This rule enables an undiscovered solu-
tion to be found. The delay time is defined as follows:

q  ðLj  tÞ; if q > q1 and t 6 Lj
delay time ¼
0; otherwise
ð13Þ
where q is a random number uniformly distributed in [0,1]. Fig. 5. Simulation cases for 10 jobs with precedence and resource
The q1 (0 < q1 < 1) is a predetermined parameter that deter- constraint.
2078 S.-T. Lo et al. / Expert Systems with Applications 34 (2008) 2071–2081

Fig. 9. The simulation result by Gantt chart with delay rule for three
processors.

resource-constrained multiprocessor problems that assume

the processors are unlimited. Thus, suggested DDACS can
be directly applied to solve the PSLIB problems. The fol-
lowing simulations were used to test the proposed DDACS
to check whether the optimal solutions can be found as
Fig. 6. The solution matrix and Gantt chart with no delay rule for two
processors. listed in PSLIB. The other purpose of solving PSLIB using
DDACS is to verify the designed dynamic rule and delay
solution generation rule in obtaining a near-optimal (opti-
mal) solution. The following simulation results indicate
that the DDACS finds a near-optimal (optimal) solution
under a certain number of iterations.
Table 1 shows the simulation results (job number, pro-
cessor number, average, best, worst makespan, standard
deviation of makespan and execution time) by proposed
scheme. Each case was simulated 10 times; each simulation
was set to run for 20 iterations. These simulation cases were
set from 30 jobs to 120 jobs with intervals of 30 jobs and
with different numbers of processors. All simulations were
run on a Pentinum4 2.8 GHz PC using the C language.
Fig. 10 illustrates the simulation results of PSLIB for
cases of 30 jobs with 480 instances. Simulation results indi-
cate that the DDACS found more optimal solutions for
Fig. 7. The solution matrix and Gantt chart with delay rule for two PSLIB problems.
processors. Fig. 11 shows the difference between computed make-
span and optimal makespan for cases of 30 jobs with 480
instances. The total number of near-optimal solutions with
dynamic and delay solution generation rules were greater
than that obtained when no rule was employed. For
instance, DDACS obtained about 93.3% (=448/480) cases
with near-optimal solutions, in which the difference
between the computed makespan and optimal makespan
was no more than 2, as in Fig. 11c.
Fig. 8. The simulation result by Gantt chart with no delay rule for three The q1 value indicates the probability of not adopting
processors. the delay rule. Fig. 12 shows the numbers of optimal solu-
tions found for different no delay probabilities q1 with dif-
is with at least 480 instances. The PSLIB includes project ferent q0 values. Simulation results reveal that more
scheduling problems with no processor constraints. This optimal solutions found as high probability q1 was set.
work studies RCMPSP which has resources constraints. Restated, a low delay probability (higher q1 value) is
Restated, the PSLIB problems are special cases of suggested.

Table 1
Execution summary of one instance for 30–120 jobs
job Processor MS_avg MS_best MS_worst MS_stdevp Execution time
j30 4 44.2 43 45 0.5386 0.29
j60 5 96.3 95 98 0.9078 1.01
j90 6 121.8 120 123 0.6353 2.52
j120 11 92.3 91 94 1.0450 4.83
 S.-T. Lo et al. / Expert Systems with Applications 34 (2008) 2071–2081 2079

80.00% 350

# of optimal solutions
287 273
300 q0=0.8
222 226
Percentage(no/480)

60.00% 250 q0=0.9

DDACS 200 147
40.00% ACS 120
difference
150
81 84
100
20.00% 26 22
50
0
0.00% q1=0.7 q1=0.8 q1=0.85 q1=0.9 q1=0.95

0
1

0
10

0
=<5

0
0
-20.00%
=<5

0
0

0
=<1
Fig. 12. The number of optimal solutions found for 30 jobs/480 different
<=

=<2

=<4
=<3

=<5
Iterations instances after 20 iterations with different delay probability.

Fig. 10. Probability of finding optimal solutions comparison with ACS

and DDACS.
200
30 jobs
150 60 jobs

Makespan
500
100
450
# of solutions

50
400
DDACS 0
350 2 3 4 5 6 7 8 9
ACS
Processors
300
Fig. 13. The makespan for one 30 jobs and 60 jobs case after 100
250 iterations.
0 <
= 1 <
= 2 <
= 3 <
=4
Difference between computed makespan and optimal makespan
Most of the simulations assumed that the number of pro-
500
cessors in the multiprocessor system was sufficient. The
450 simulation results easily reveal the requisite number of pro-
# of solutions

cessors. The case with 60 jobs required about 5 processors,

400
while that with 30 jobs needed 4 processors. If only 2 or 3
DDACS
350
ACS
processors were available, then the makespan increased
300
when the number of processors was not enough to process
jobs simultaneously.
250 To better understand how a, b values affect optimal
0 <
= 1 <
= 2 <
= 3 <
= 4 solutions obtained by proposed DDACS. Different a, b
Difference between computed makespan and optimal makespan values were tested in simulation. Fig. 14 shows that a lower
500
a value applied in DDACS is better than a high value.
Restated, a lower a value yields more optimal solutions.
450 Below, an a value that is equal to 1 and 2 under 500 itera-
# of solutions

400 tions is shown. The best a, b values are set case by case
DDACS based on the scheduling considerations of the real case.
350 ACS The best a and b values of this study are all set to 1.
300

250 500
0 <
= 1 <
= 2 <
= 3 <
=4 α =1
450
Difference between computed makespan and optimal makespan α =2
400
# of optimal solutions

Fig. 11. The number of near-optimal solutions for 480 different instances 350
with different iterations: (a) 20 iterations; (b) 100 iterations and (c) 500 300
iterations. 250
200
Fig. 13 depicts the makespan of the simulation results of 150
cases with 30 and 60 jobs with different numbers of proces- 100
sor simulations. These two cases show that increasing the 50
number of processors may not improve the schedule when 0
β =1 β =2 β =3 β =4 β =5
precedence constraints are adopted. Different numbers of
processors were set in the simulation. The minimum num- Fig. 14. The number of optimal solutions, found for one 30 jobs case after
ber of required processors was not considered in this study. 500 iterations with different a, b values.
2080 S.-T. Lo et al. / Expert Systems with Applications 34 (2008) 2071–2081

5. Conclusions and discussion and with the changes in available resources. Moreover,
the makespan is considered in this work, but tardiness is
This study presents a modified ACO approach named allowed in other scheduling problems, such as job-shop,
DDACS for a multi-constraint (precedence and resource flow-shop and industry production plans. Heuristic func-
constraints) multiprocessor scheduling problem. A two tions and how to generate better solutions can also be fur-
dimension (time and job) matrix graph is adopted to repre- ther discussed, and future research endeavors should
sent the scheduling problem. This graph is used to resolve address these issues more thoroughly.
the minimum makespan schedule. The proposed DDACS
algorithm modifies the latest starting time of each job in References
the dynamic rule for each iteration. The latest starting time
of a job is used in the heuristic influence, as listed in Eq. (8). Bauer, A., Bullnheimer, B., Hartl, R. F., & Strauss, C. (1999). An ant
The latest starting time amendment provides an appropri- colony optimization approach for the single machine total tardiness
ate feedback to find the optimal solution. Moreover, a problem. In Proceedings of the 1999 Congress on Evolutionary
Computation, 1999 (pp. 1445–1450).
delay solution generation rule is applied to allow the solu-
Besten, M. D., Sttzle, T., & Dorigo, M. (2000). Ant colony optimization
tion to escape from the local minimum. The delay solution for the total weighted tardiness problem. Lecture notes in computer
generation rule is a good strategy to search for a better science (Vol. 1917, pp. 611–620). Berlin, Germany: Springer-Verlag.
solution, as revealed by the simulation results, as shown Brucker, P., Drexel, A., Möhring, R. H., Neumann, K., & Pesch, E.
in Fig. 10. (1999). Resource-constraint project scheduling: Notation, classifica-
tion, models, and methods. European Journal of Operation Research,
The proposed DDACS scheme provides an efficient
112(1), 3–41.
method of finding the optimal schedule of the multi-con- Cardeira C., & Mammeri, Z. (1996). Neural network versus max-flow
straint multiprocessor system. However, the simulation algorithms for multi-processor real-time scheduling. Real-time sys-
results demonstrated some significant consequences for this tems. In Proceedings of the Eighth Euromicro Workshop (pp. 175–180).
study when applied to the scheduling domain. These were Chen, R. M., & Huang, Y. M. (1998). Multiconstraint task scheduling in
as follows: multiprocessor system by neural network. In Proceedings of the IEEE
10th international conference on tools with artificial intelligence, Taipei
(pp. 288–294).
1. The resource-constrained project scheduling problem is Chen, R. M., Lo, S. T., & Huang, Y. M. (2007). Combining competitive
a special RCMPSP scheduling problem. Therefore, the scheme with slack neurons to solve real-time job scheduling problem.
proposed method can be applied to solve RCPSP Expert Systems with Applications, 33(1), 75–85.
Chen, R. M., & Huang, Y. M. (2001). Competitive neural network to
directly without modification. Processors crashing or
solve scheduling problem. Neurocomputing, 37(1–4), 177–196.
changing of available resources is an important consid- Correa, R. C., Ferreira, A., & Rebreyend, P. (1996). Integrating list
eration in multiprocessor systems. However, the pro- heuristics into genetic algorithms for multiprocessor scheduling. In
posed DDACS method is an adaptable scheme for Parallel and distributed processing, eighth IEEE symposium (pp. 462–
such variable resource situations. 469).
2. This method can be adopted to predict the minimum Correa, R. C., Ferreira, A., & Rebreyend, P. (1999). Scheduling
multiprocessor tasks with genetic algorithms. IEEE Transactions on
number of processors required in the multiprocessor sys- Parallel and Distributed Systems, 10(8), 825–837.
tem, as the results shown in Fig. 13, which indicates that Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: A
increasing the number of processors to more than the cooperative learning approach to the traveling salesman problem.
required number do not improve the solution. IEEE Transactions on Evolutionary Computation, 1(1), 53–66.
3. An important feature of the scheduling algorithm is its Dorigo, M., Maniezzo, V., & Colorni, A. (1996). The ant system:
Optimization by a colony of cooperating agents. IEEE Transaction on
efficiency or performance, i.e., how its execution time System, Man and Cybernetics, 26(1), 1–13.
increases with the problem size. A fast convergence rate Gajpal, Y., Rajendran, C., & Ziegler, H. (2004). An ant colony algorithm
is a significant characteristic of an ant colony system. for scheduling in flowshops with sequence-dependent setup times of
The execution time of the DDACS algorithm is propor- jobs. European Journal of Operational Research, 155(2), 426–438.
Herroelen, W. B., Reyck, D., & Demeulemeester, E. (1998). Resource-
tional to O(N · T · ant) for one iteration instead of
constrained project scheduling: A survey of recent developments.
O(N · M · T · ant) if three dimensions matrix used. Computers & Operations Research, 13(4), 279–302.
Restated, the execution time of DDACS is linear pro- Hopfield, J. J., & Tank, D. W. (1985). Neural computation of decision in
portional to ant number and matrix size. optimization problems. Biological Cybernetics, 52, 141–152.
Hou, E. S. H., Ansari, N., & Ren, Hong. (1994). A genetic algorithm for
This work focuses on investigating multiprocessor sys- multiprocessor scheduling. Systems. IEEE Transactions on Parallel and
Distributed, 5(2), 113–120.
tem scheduling with precedence and resource constraints. Huang, Y. M., & Chen, R. M. (1999). Scheduling multiprocessor job
The scheduling processors in this investigation are homo- with resource and timing constraints using neural network. IEEE
geneous processors. However, the more complex condi- Transactions on System, Man and Cybernetics, Part B, 29(4), 490–
tions, such as set-up time between jobs on a particular 502.
Iredi, S., Merkle, D., & Middendorf, M. (2001). Bi-Criterion Optimization
machine, and the communication cost of jobs running on
with Multi Colony Ant Algorithms. In Proceedings of the first
different processors and heterogeneous processors, should international conference on evolutionary multi-criterion optimization
be further studied. Meanwhile, a dynamic situation can (EMO’01). Lecture notes in computer science (Vol. 1993, pp. 359–372).
be studied, with emergency jobs arriving at a certain time Springer-Verlag.
 S.-T. Lo et al. / Expert Systems with Applications 34 (2008) 2071–2081 2081

Kwok, Y. K., Ahmad, I., & Gu, J. (1996). FAST: A low-complexity Pierucci, P., Brandani, E. R., & Sogaro, A. (1996). An industrial
algorithm for efficient scheduling of DAGs on parallel processors. In application of an on-line data reconciliation and optimization prob-
Proc. int’l conf. parallel processing (ICPP) (vol. II, pp. 150–157). lem. Computers & Chemical Engineering, 20, S1539–S1544.
Liu, C., & Layland, J. (1973). Scheduling algorithms for multiprogram- Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permu-
ming in a hard real-time environment. Journal of the ACM, 20(l), tation flowshop scheduling to minimize makespan/total flowtime of
46–61. jobs. European Journal of Operational Research, 155(2), 426–438.
Maniezzo, V., & Carbonaro, A. (1999). Ant colony optimization: An Stützle, T., & Hoos, H. H. (2000). MAX–MIN ant system. Future
overview. In Proceedings of MIC’99, III metaheuristics international Generation Computer Systems, 16(9), 889–914.
conference, Brazil. Topcuoglu, H., Hariri, S., & Wu, M. Y. (2002). Performance-effective and
Merkle, D., & Middendorf, M. (2001). A new approach to solve low-complexity task scheduling for heterogeneous computing. IEEE
permutation scheduling problems with ant colony optimization. In Transactions on Parallel and Distributed Systems Publication, 13(3),
Proceedings of the EvoWorkshops 2001, Lecture notes in computer 260–274.
science (vol. 2037, pp. 484–494). Wu, M. Y., Shu, W., & Gu, J. (1997). Local search for DAG scheduling
Merkle, D., Middendorf, M., & Schmeck, H. (2002). Ant colony and task assignment. In 1997 international conference on parallel
optimization for resource-constrained project scheduling. IEEE Trans- processing (ICPP ’97) (pp. 174–180).
actions on Evolutionary Computation, 6(4), 333–346. Zomaya, A. Y., Ward, C., & Macey, B. (1999). Genetic scheduling for
Oh, J., & Wu, C. (2004). Genetic-algorithm-based real-time task sched- parallel processor systems: Comparative studies and performance
uling with multiple goals. Journal of Systems and Software, 71(3), issues. IEEE Transactions on Parallel and Distributed Systems, 10(8),
245–258. 795–812.
Park, J. G., Park, J. M., Kim, D. S., Lee, C. H., Suh, S. W., & Han, M. S.
(1994). Dynamic neural network with heuristic. IEEE International
Conference on Neural Networks, 7, 4650–4654.