J. Software Engineering & Applications, 2009, 2: 323-329
doi:10.4236/jsea.2009.25042 Published Online December 2009 (http://www.SciRP.org/journal/jsea)
323
A Multi-Criteria Decision Making for the Unrelated
Parallel Machines Scheduling Problem
Wei-Shung CHANG, Chiuh-Cheng CHYU
Department of Industrial Engineering and Management, Yuan-Ze University, Taiwan, China.
Received August 6th, 2009; revised August 31st, 2009; accepted September 7th, 2009.
ABSTRACT
In this paper, we propose a multi-criteria machine-schedules decision making method that can be applied to a produc-
tion environment involving several unrelated parallel machines and we will focus on three objectives: minimizing
makespan, total flow time, and total number of tardy jobs. The decision making method consists of three phases. In the
first phase, a mathematical model of a single machine scheduling problem, of which the objective is a weighted sum of
the three objectives, is constructed. Such a model will be repeatedly solved by the CPLEX in the proposed
Multi-Objective Simulated Annealing (MOSA) algorithm. In the second phase, the MOSA that integrates job clustering
method, job group scheduling method, and job group – machine assignment method, is employed to obtain a set of
non-dominated group schedules. During this phase, CPLEX software and the bipartite weighted matching algorithm
are used repeatedly as parts of the MOSA algorithm. In the last phase, the technique of data envelopment analysis is
applied to determine the most preferable schedule. A practical example is then presented in order to demonstrate the
applicability of the proposed decision making method.
Keywords: Multi-Objective Optimization, Unrelated Parallel Machines Scheduling, Simulated Annealing Algorithm,
Integer Programming Models, Multi-Criteria Decision Making
1. Introduction
Parallel machine scheduling problems have been exten-
sively studied in the literature and widely used in many
manufacturing environments, such as the drilling opera-
tion in a PWB line [1] and glass etch polishing process in
the TFT-LCD manufacture. In many real-life situations,
the used machines are not always identical in perform-
ance. They are different because they were purchased at
different times or for different considerations. Some ma-
chines may spend much more time on a particular job
than others because of their age or design. Consequently,
the layout of unrelated parallel machines is more com-
mon than identical parallel machines in real manufactur-
ing environments. The unrelated parallel machine sched-
uling problem (UPMSP) is more difficult than the identi-
cal case. Since the latter belongs to NP hard [2], the
UPMSP is also NP hard. For further knowledge and re-
cent findings regarding the UPMSP, we refer to [3–4].
The problem solving approach to the UPMSP can be
classified into two categories: metaheuristics and exact
solution method. In metaheuristics, Hariri and Potts [5]
proposed a two-phase method to solve the UPMSP with
the objective of minimizing makespan (Cmax), where the
first phase applies an integer programming technique and
the second uses the earliest completion time rule to com-
plete the final schedule of the UPMSP. Weng et al. [6]
proposed seven heuristics for the UPMSP with job se-
quence dependent setup times and the objective of mini-
mizing the weighted mean flow time. Two priority rules,
shortest processing time (SPT) and the minimum sum of
setup time and processing time, are respectively em-
ployed in the heuristics. The numerical results indicated
that their algorithms are capable of finding quality solu-
tions to problems involving 120 jobs with 20 machines in
short computational times. Bank and Werner [7] devel-
oped a constructive and iterative algorithm to solve the
UPMSP with time window constraints on the job release
dates and with the objective of minimizing the total
weighted lateness.
Glass et al. [8] developed a genetic algorithm (GA),
simulated annealing (SA), and tabu search (TS) to solve
the UPMSP without the sequence dependent setup time
constraints. Their experiments conclude that GA per-
forms no better than the other two algorithms. Sirvastava
[9] proposed a TS algorithm that could find high quality
solutions in a short time for a part of the same instances.
Kim et al. [10–11] proposed an SA to solve the

A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem 324
UPMSP with a goal of total tardiness minimization, while
taking into consideration job sequence-dependent set up
times. Logendran et al. [4,12] developed a TS for the
same problem with additional considerations of dynamic
release dates and time window machine availability,
where the objective was to minimize the sum of weighted
tardiness jobs. Chen [13] presented a record-to-record
algorithm with tabu list to solve the UPMSP with the
goal of minimizing the maximum tardiness. This paper
also presented a threshold accepting algorithm with tabu
list to solve the UPMSP to minimize the total tardiness.
The branch and bound (B&B) methods are commonly
used to optimally solve the UPMSP in the literature
[14–18].
Most research on the UPMSP has been focused on a
single objective only and there have been comparatively
fewer studies on the multi-objective UPMSP. Suresh et
al. [19] developed a TS for UPMSP with two objectives:
minimizing the maximum makespan (Cmax) and the
maximum tardiness. The tabu list keeps the record of
newly found non-dominated solutions. Jansen et al. [20]
modified the TS by Suresh et al. and solve the UPMSP
with the objectives of minimizing Cmax and cost of
scheduling. In this paper, a simulated annealing that
interacts with the commercial software package CPLEX
is developed for solving the UPMSP with three objec-
tives – minimizing Cmax, total flow time, and total num-
ber of tardy jobs. Since only one schedule will be im-
plemented in a real situation, a decision procedure is
suggested to make the most preferable choice of the
candidate solutions.
Simulated annealing (SA) has been known as a com-
pact and robust technique to solve many NP-hard prob-
lems, including both single objective and multi-objective
ones. It can provide excellent solutions to these problems
with a substantial reduction in computational time. SA
was first introduced by [21]. We refer to [22–24] for sur-
veys on single objective SA, and [25] for surveys on
multi-objective SA.
The remainder of this paper is structured as follows.
Section 2 describes the problem under study. Section 3
presents the proposed solution approach. Section 4 pre-
sents the numerical results from the proposed method
used to solve a problem with real life data. Finally, Sec-
tion 5 concludes the paper with implications for future
research.
2. Problem Description
The aim of this study is to develop a systematic solution
method for determining the most preferred schedule
among a non-dominated set of schedules found by the
proposed hybrid simulated annealing algorithm. In this
section, first of all, notations used in this paper are intro-
duced; secondly, the studied problem is described, in-
cluding a multi-objective mathematical model.
2.1 Notations
Symbols:
i: machine index, i = 1,…, M
j: job index, j = 1,…, J
M: total number of machines used
J: total number of jobs to be processed
pij: processing time of job j performed by machine i
sij: set up time for job j on machine i
dj: due date of job j
Gm: set of jobs in group m, m = 1,…, M
Decision variables:
Cmax: maximum makespan (completion time) among
all machines
max
i
C: makespan of machine i
Cij: completion time of job j on machine i
Tij: tardiness of job j on machine i, Tij = max{0，Cij –
dj}
Uij: tardiness state of job j if it is processed on machine
i: value is 1 if tardy;otherwise value is 0; number of tardy
jobs for machine i
yij: value is 1 if job j is assigned to machine i; value is
0 otherwise
xijk: value is 1 if both jobs j and k are assigned to ma-
chine i and job j immediately precedes job k; value is 0
otherwise
2.2 Problem Definition
We consider the following manufacturing environment:
there are I different machines in parallel with a total
number of J jobs to be processed, and a job refers to a
customer’s order. The problem under study assumes that
each job may have different processing times depending
on the assigned machine, each machine will process one
job at a time, and the processing is non-preemptive. The
setup time of each job is assumed to be machine depend-
ent but not job sequence dependent; thus, the setup time
is included in the processing time. The scheduling prob-
lem considered in this study aims to minimize three ob-
jectives simultaneously: Cmax, total flow time, and total
number of tardy jobs.
2.2.1 Mathematical Formulation
max
11 11
(, ,
MJ MJ
ij ij
ijij
)
M
inimize CCU
 

 (1)
max max
. .
i
s
tC Ci
j
(2)
max ,
i
ij
CC i
(3)
max
1
J
i
ij ij
j
Cpy

i


 (4)
0; C ,
ijijij j
TT dij
(5)

A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem325
ijbig ij
TMU ,ij
(6)
(1 )
ik ikbigijkij
CpMx C  ,,ijk (7)
1,
,
J
ijk ij
kkj
x
yi


j
j
(8)
0 ,
ij
Ci ,
,0,1 ,
ij ij;
y
Ui j
0,1 ,,
ijk
x
ijk (9)
where Mbig is a big number.
In the model, Equation (1) presents the three objective
quality set (2) shows the first
ob
non-dominated schedules (or alternatives)
select the most
be adopted: 1)
se
lem solving method
as the
lowing strategy: 1)
pr
to represent a
nds to the set
gi
functions of the UPMSP; ine
jective is to minimize the maximin makespan of all
machines; constraint set (3) specifies the makespan of
each machine; constraint set (4) defines the makespan of
each machine; constraint set (5) defines the tardiness of
each job; constraint sets (5) and (6) together define the
number of tardy jobs; constraint set (7) specifies the
starting time relationships between jobs under a certain
processing sequence in the same group. Equation set (8)
ensures that each individual job will be processed by only
one machine.
2.2.2 Multi-Criteria Decision Making
Given a set of
to the problem under study, we seek to
preferable one. Various approaches can be applied to
solve this decision problem. Some well known methods
are as follows: 1) construct a multi-attribute utility func-
tion [26] which is defined on the objective space, and
then take the alternative with the maximum utility value;
2) assign priorities to objectives and take the alternative
with the best Lexicographic order; 3) select the alterna-
tive that has the maximum AP efficiency ratio in data
development analysis [27] or that has the maximum score
using principle component analysis [28].
In the case that there are too many non-dominated so-
lutions, a simple three-stage method will
lect a reasonable number of diversified solutions; 2)
decide what the inputs and the outputs should be; 3)
compute the AP efficiency ratio and choose the one
which ranks first.
3. Problem Solving Method
In this paper, we developed a prob
that uses the simulated annealing (SA) algorithm
main framework and employs the CPLEX optimizer to
solve the multi-objective scheduling problem with an
assigned weight vector. The acceptance probability takes
into account the upgrading or downgrading of each indi-
vidual objective function at each step of generating a
neighborhood solution, and is defined as the product of
each individual acceptance probability with respect to the
change of each objective at each step.
In order to produce an acceptable number of non-
dominated schedules, we adopt the fol
edetermine a set of weight vectors for the three- objec-
tive scheduling problem; 2) solve optimally or near opti-
mally the multi-objective scheduling problem with the
target of minimizing the weighted sum of the objectives
for each weight vector; 3) find higher quality diversified
solutions using different initial solution. In the study,
three priority rules, EDD (early due date), SPT (shortest
processing time), and CR (critical ratio) are used to gen-
erate an initial solution.
3.1 Encoding and Decoding Scheme
In the proposed SA, a job list is used
schedule of UPMSP. A sublist m correspo
of jobs assigned to group m. To generate an initial job list,
all jobs are first sorted first based on a priority rule, and
then placed one by one into each sublist according to the
order of the list. In doing so, a set of job groups is formed,
with the number of groups equal to the number of ma-
chines. Given a job list, a neighborhood solution will be
generated by performing a 3-opt operation on the list.
Figure 1 illustrates the decoding process using 15 jobs
and four machines. First, a weight vector (1, 2, 3) is
ven for the three objectives In step 1, 15 jobs are
grouped and sequenced according to the priority rule. In
the example, group 1 (sublist 1) contains jobs 2, 5, 6, and
13. In step 2, based on the results in step 1, we can obtain
an initial solution for each group-machine pair and fur-
ther improve it by single machine scheduling heuristic
(SMSH). Note that in this step the three objective values
are normalized using Equations (12)–(14). Since there are
four machines, a 4 by 4 yielding 16 group-machine pairs
are computed. Figure 2 displays the results of step 2.
Figure 1. Example of decoding scheme

A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem 326
332211
objective sum Weighted fff 
Figure 2. Applying SMSH to all group-machine pairs
Figure 3. Optimal group-machine matching by BWMA
Finally, the bipartite weighted matching algorithm (BW
MA) is applied to find the optimal group-machine mat-
ching and this concludes the decoding scheme (Figure 3).
3.1.1 Single Machine Scheduling Problem with a
Weighted Sum of Objectives
This section presents the mathematical model of the
weighted sum objectives of the single machine schedul-
ing problem, which will then be solved by the CPLEX
solver in the interactive SA algorithm. Given a weight
vector, (1, 2, 3) with 1 + 2 +3 = 1, 1, 2, 3  0,
and group Gm is assigned to machine i, the mathematical
model is as follows:
Min ,
3
,,
,123 123
12
(, , )imim im
im
F
ff     
s.t. (3), (4), (5), (6), (7) for ,m jk G
f
,,
m
ijk
jk Gjk
1x


m
0
ij m
CjG
0, 1
ijk
x ,m
jk G (11)
kG (10)
) (12)
where
,
max minmax 1()/(
im iiii
fCgg min g
,
minmax min 2()/()
m
imii i
j
jG
fChhh

 

(13)
,
minmax min
3()/()
m
imii i
ij
jG
fUuuu

 

(14)
and (min
i
g
,min
i
h,mi
i
u) and (max
i
g
,
n
i
max
h,max
i
u) are the
ideal solution and anti-ideal solution to the three-
obschedulin problem, re-
sp
3.1.2 Assignment Problems between J
Machines
Given an assigned weigt vector (1, 2, 3)
s {Gm, m = 1,…, M}, a total of M × M single
eduling solutions can be crea
which corresponds to a group of jobs being
a machine. The problem in this step is a bi
hted maching problem and will be solved by th
ian method. The mathematical model of the group-ma-
chine assignment problem is presented as follo
jective single machine g
ectively.
ob Groups and
hand a set of
job group
machine schted, each of
processed by
partite weig-
e Hungar-
ws:
,
1
(,
im i
i
123
1
, )
MM
m
m
M
in   F y


s .t.
M
im
y


1i
1

mM = 1，…，(15)
1
1
im
m
y

M

 i = 1，…，M (16)
0
im
y m, i = 1，…，M
3.2 MOSA Algorithm
The following presents the MOSA algorithm:
1) Select a wide diversified set  = {k

: k = 1,…,
K}, where each k

corresp the kth weight
vector of the three objectives. Choose a set of prior-
ity rules, Pr = {prl: l = 1, …, L}, which will subse-
be used to create the initial solutions. Set
the number of temperature levels = NTL, and the
number
level = ITN. k = 1; l = 1, ntl = 1, T = T1, itn = 1.
2) Apply priority rule prl to generate an initial parti-
tioned set of jobs, {Gm: m = 1,…, M}; Compute
onds to
quently
of maximum iterations at each temperature

A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem327
,1
(,,)
kkk
im
F23

 ; employ the Hunggorithm
the group jobs – machines assignment
arian al
to solve
problem; evaluate all objective functions and put
them
(z1(x), z2(x), z3(x)) be the cor-
alized objective values.
ted a new
m,
into a Pareto set of solutions. Let x = current
solution with Z(x) =
responding non-norm
3) Give a random perturbation and genera
partitioned set of jobs. {'
m
G: = 1,… M}; Com-
pute ,123 (, )
kkk
im
F,


; employ Hungarian algo-
rithm to solve the group jobs – machines assign-
ment problem and obtain a new solution y; evaluate
all objective values: Z(y) = (z1(y), z2(y), z3(y)).
Compare y with all solutions in the Pareto set and
update the Pareto set, if necessary.
If y is archived, make it the current solution by put-
4)
5)
probability to e
ting x = y and move on to step 7; otherwise compute
() ()
rr r
zzyzx , r = 1, 2, 3. Assign acceptance
ach of objective functions as fol-
lows:
pr = 1 if 0
r
z; pr = (exp(-/)
r
zT)k
r

if
0
r
z, r = 1, 2, 3;
Acceptance probability = 123
pp p
6) If y is accepted, then set x = y;
7) itn = itn + 1; if (itn > ITN), set ntl = ntl + 1;
1ntl ntl
TT


.
If (ntl ate and output the best solu-
tion; otherwise, go to step 2.
hoosing the Best Alternative
8) > NTL), termin
3.3 C
In
makipetitive alterna-
tiv
a hig
taken to complete the pr
of th
the t
schedese two arded as
the iomputing. On thot
hand, the num jobs represents the number of
unsae will instead be taken as
anf tardy jobs imply a
be
the ber of tardybs
m
th
that the setup time of a job is only ma-
job-sequence-dependent, and
time.
s are chosen to construct the initial
this paper, we will choose the AP efficiency ratio for
ng the best choice among many com
es. In the three objectives, a small Cmax usually implies
h utilization of machine(s), i.e., how much time is
oduction. Furthermore, the sum
e completion times of J jobs gives an indication of
otal holding or inventory costs incurred by the
le [29u]. Thobjectives will be reg
nputs when c the AP ratioe her
ber of tardy
tisfied customers. This valu
output. Since a small number o
tter performance, we use a total number of jobs minus
num jo in a schedule as the performance
easure to indicate the level of customers’ satisfaction of
at schedule.
4. Numerical Results
In this section, the computational characteristics and ef-
fectiveness of the proposed interactive SA algorithm are
evaluated via a practice example, which arises in the
glass etch polishing during the Cell manufacturing stage
of the TFT-LCD production process. The glass etch pol-
ishing operation is independent of the other manufactur-
ing processes, and is required only for some types of
TFT-LCD products.
In the example, a collection of real life data for four
different machines and 21 different products was made.
The data contains the information of the processing time
of each job (a batch of the same products) on each indi-
vidual machine. Our observation indicates that the setup
time of a job is approximately the same in each machine,
regardless of whichever its preceding job is. But the setup
time may be different in different machines. There- fore,
it is assumed
chine-dependent rather than
is included in the processing
In the experiment, the SA algorithm was coded in
Visual Studio C++. NET and executed on a computer
with Intel core dual, 1.8GHz and 2 GB DDR566, and
used the CPLEX 10.0 optimizer to solve the weighted
sum objective single machine scheduling problem. The
parameters setting of the SA is as follows: NTL = 20,
ITN = 5, T1 = 100, and  = 0.95.
Three priority rule
solutions. They are early due date (EDD), shortest proc-
ess time (SPT), and critical ratio (CR), where CR is de-
fined as the ratio of the due date over the average proc-
essing time. Table 1 displays the best solutions found
Table 1. Best solutions for various weight vector with EDD
initial solution
λ1 λ2 λ3Cmax Total flow time No. tardy jobs CPU (sec.)
0.1, 0.1, 0.84392105.9 2 201.5
* 0.1, 0.2,0.73441831.48 1 196.9
0.1, 0.3, 0.65562276.01 2 200.2
0.1, 0.4, 0.53671888.4 3 187
0.1, 0.5, 0.43721772.98 3 198.1
0.1, 0.6, 0.35882542.73 1 197.5
0.1, 0.7, 0.24501970.37 1 190.7
0.2, 0.1, 0.75962189.48 0 205.4
0.2, 0.2, 0.65982267.12 2 201.1
0.2, 0.3, 0.57262715.26
0.
1 194.5
0.3, 0.4, 0.33892241.87 3 196.9
1910.4 2 197.0
2, 0.4, 0.44272312.18 2 196.9
0.2, 0.5, 0.33821906.4 3 195.9
0.2, 0.6, 0.24002330.29 3 197.5
0.3, 0.1, 0.64752099.12 1 201.0
* 0.3, 0.2,0.53601774.87 2 203.4
0.3, 0.3, 0.45362103.48 1 210.9
0.3, 0.5, 0.27692890.04 1 194.0
0.4, 0.1, 0.53811924.4 1 199.8
0.4, 0.2, 0.4382
0.4, 0.3, 0.34792138.9 1 202.5
* 0.4, 0.4,0.25272019.48 0 200.1
* 0.5, 0.1,0.42551770.4 3 199.8
0.5, 0.2, 0.33672083.79 2 195.6
0.5, 0.3, 0.24502275.62 1 202.3
0.6, 0.1 ,0.3
0.6, 0.2, 0.2
389
663
1879.73
2471.01
2
1
206.7
197.8

A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem 328
Table 2. Nomutions fo in all t
max flow time No. tard
on-dinant solundrials
λ1 λ2 λ3CTotal y jobs
0.4, 0.4, 0.2 527 2019.48 0
0.3, 0.1, 0.6 304 1794.73 1
48.51 2
51 2
0.2, 0.3, 0.5 241 17
0.4, 0.4, 0.2 245 1746.
Tk theternativeased oAP
ra
1 Output CCR o
able 3. Rans of four als bn the
tio
Alternatives Input Input 2 AP rati
1 527 1.000 0.933 2019.48 0.933
2 304 0.952 1.000
0.905 1.000
0.905 0.999
1794.73 1.024
3 2411748.51 1.017
4 2451746.51 0.999
Nuesults ofENA
rCma flow time No. tard
Table 4.merical r AR
Dispatching ules x Total y jobs
SPT 262 2638 15
EDD 294 3391 20
CR 597 4926 21
wito eweighand the EDD initial
soldernd a limber of hi quality
non-domfor ght vector, the SA
ill output the solution with the minimum weighted ob-
observed from Table 1, only four local non-domi-
nns were fitDal .
Hen gln-
natedlutionsndAresin 2.
The first one wrodithDDl sn,
the second wite SPT, and tt tth .
Three local nomsos in Table re
emoved when compared with the second and third solu-
tions in Ta
mdule amse
four alhe pr6]
is applihen aing tdure, thelues of
Cmax anflow time are d as inputse value
of Cmax can be viewe the te of the equipments
nd schedule should be the most prefer-
ab
iding
quality
5.
-making process as to
e. In addition, for problems of large
onary algorithms will be more favor-
arlyle, and J. W.
h respect tach t vector
ution. In or to fimited nugh
inated solutions, each wei
w
jective value.
As
ated solutio
owever, th
ound w
otally o
h the ED
ly four
initi
obal
solution
on-domire are t
so fou by the S, as pented Table
as puced w the E initiaolutio
h thhe reswo withe CR
on-dinated lution1 we
r
ble 2.
To select the
ternatives, t
ost prefera
e ranki
ble sche
ng procedur
ong the
oposed by [2
ed. Wpplyhe proce va
d total treate
otal tim
. Th
d as
used in the production, and the flow time gives an indica-
tion of the total holding or inventory costs incurred in the
production. The number of tardy jobs occurs in a sched-
ule will be viewed as the output, since it represents the
number of customers who will not be satisfied with the
purchase service. The following scoring method for this
output is adopted:
(total no. of jobs – total no. of tardy jobs) /
(total no. of jobs)
Table 3 presents the ranks of the four non-dominated
schedules. Both the second and the third schedules have a
CCR ratio [30] of one, which implies both are effective.
However, a further comparison based on the AP ratio
indicates the seco
le. The proposed decision-making model is more pro-
per if it includes the consideration of the cost of sched-
ules. In unrelated parallel machine scheduling problems,
a job may take different processing times on different
machines, and thus its processing cost may also be dif-
ferent when processed by different machines.
Table 4 shows the numerical results by applying the
simulation software ARENA to the instance using three
different dispatching rules commonly used in industry.
Clearly, the SPT rule works much better than the other
two, but its solution is considerably dominated by the
second to fourth solutions in Table 2. The proposed algo-
rithm is superior to the professional software in prov
solutions for the instance.
Conclusions
In this paper, we proposed an interactive simulated an-
nealing algorithm aimed at searching for a set of near
Pareto optimal solutions to the unrelated parallel machine
scheduling problem with three objectives: minimizing
total completion time, total flow time, and total number
of tardy jobs. A commercial optimization software pac-
kage IILOG CPLEX is served as a function in the SA
algorithm, with the mission of solving optimally the sub-
problem - weighted sum objective single machine sched-
uling problems. To produce an acceptable number of high
quality non-dominated solutions, a unique best schedule
is found with respect to each weight vector. The ranking
procedure proposed by Andersen and Petersen is then
applied to select the most preferable schedule, using total
completion time and total flow time as the inputs, and
total number of tardy jobs as the output.
Further research would include the cost of schedules as
one of the inputs in the decision
select the best schedul
size, hybrid evoluti
able than the current method, in which the CPLEX opti-
mizer occupies a large percentage of computational time.
When solving large size problems, the number of
non-dominated solutions would be very large. An inter-
esting research direction may be focused on developing a
good method for making the best selection among the
huge number of near Pareto-optimal solutions.
6. Acknowledgments
This research was partially supported by the National
Science Council in Taiwan under grant NSC 95-2221-
E-155-045.
REFERENCES
[1] L. Yu, H. M. Shih, M. Pfund, W. M. C

A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem 329
nell, and B. Smucker, “Schedul-
Potts, “Heuristics for sched uling
unrelated paralers and Operations
Research, Vol. 1991.
226, 2001.
cal and Computer Modelling, Vol. 33,
heuristic for minim
ng, and F. F. Chen, “Unrelated
achine scheduling with auxiliar
llo, F. Soumis, and P. Toth, “Exact and approxi-
mation algorithms for makespan minimization on unre-
ake-
total
ti, G. R. Mateus, and P. M. Par-
ximation
tt, and M. P. Vecchi, “Opti-
bibliography,” American Journal
Devices Magazine (Janu-
Fowler, “Scheduling of unrelated parallel machines-An
application to PWB manufacturing,” IIE Transactions,
Vol. 34, No. 11, pp. 921–931, 2004.
[2] M. K. Richard, “Reducibility among combinatorial prob-
lems,” in R. E. Miller and J. W. Thatcher (editors): Com-
plexity of Computer Computations, pp. 85–103, Plenum,
New York, 1972.
[3] M. Pfund, J. W. Fowler, and J.N.D. Gupta, “A survey of
algorithms for single and multi-objective unrelated paral-
lel-machine deterministic scheduling problems,” Journal
of the Chinese Institute of Industrial Engineers, Vol. 21,
No. 3, pp. 230–241, 2004.
[4] R. Logendran, B. McDo
ing unrelated parallel machines with sequence-dependent
setups,” Computers and Operations Research, Vol. 34, No.
11, pp. 3420–3438, 2007.
[5] M. A. Hariri and C. N.
lel machines,” Comput
18, No. 3, pp. 323–331,
[19]
[6] M. Weng, J. Lu, and H. Ren, “Unrelated parallel machine
scheduling with setup consideration and a total weighted
completion time objective,” International Journal of Pro-
duction Economics, Vol. 70, pp. 215–
[7] J. Bank and F. Werner, “Heuristic algorithms for unre-
lated parallel machine scheduling with a common due
date, release dates, and linear earliness and tardiness pen-
alties,” Mathemati
pp. 363–383, 2001.
[8] A. Glass, C. N. Potts, and P. Shade, “Unrelated parallel
machine scheduling using local search,” Mathematical
and Computer Modeling, Vol. 20, No. 2, pp. 41–52, 1994.
[9] B. Srivastava, “An effectiveizing ary), pp. 19–26, 1989.
[24] R. W. Eglese, “Simulated annealing: A tool for opera-
tional research,” European Journal of Operational Re-
search Vol. 46, No. 3, pp. 271–281, 1990.
make- span on unrelated parallel machines,” Journal of
the Operational Research Society, Vol. 49, pp. 886–894,
1997.
[10] W. Kim, K. H. Kim, W. Ja
parallel machine scheduling with setup times using simu-
lated annealing,” Robotics and Computer Integrated
Manufacturing, Vol. 18, No. 3-4, pp. 223–231, 2002.
[11] W. Kim, D. G. Na, and F. F. Chen, “Unrelated parallel
machine scheduling with setup times and total weighted
tardiness objective,” Robotics and Computer Integrated
Manufacturing, Vol. 19, No.1-2, pp. 173–181, 2003.
[12] R. Logendran and F. Subur, “Unrelated parallel machine
scheduling with job splitting,” IIE Transactions, Vol. 36,
No. 4, pp. 359–72, 2004.
[13] J. F. Chen and T. H. Wu, “Total tardiness minimization
on unrelated parallel my
“M
equipment constraints,” Omega-International Journal of
Management Science, Vol. 34, pp. 81–89, 2006.
[14] J. F. Chen, “Minimization of maximum tardiness on un-
related parallel machines with process restrictions and
setups,” International Journal of Advanced Manufacturing
Technology, Vol. 29, No. 5, pp. 557–563, 2006.
[15] S. Marte
lated parallel machines,” Discrete Applied Mathematics,
Vol. 75, pp. 169–188, 1997.
[16] Lancia, “Scheduling jobs with release dates and tails on
two unrelated parallel machines to minimize the m
span,” European Journal of Operational Research, Vol.
120, pp. 277–288, 2000.
[17] C. F. Liaw, Y. K. Lin, C. Y. Cheng, and M. Chen,
“Scheduling unrelated parallel machines to minimize
weighted tardiness,” Computers and Operations Research,
Vol. 30, pp. 1777–1789, 2003.
[18] P. L. Rocha, M. G. Ravet
dalos, “Exact algorithms for a scheduling problem with
unrelated parallel machines and sequence and ma-
chine-dependent setup times,” Computers and Operations
Research, Vol. 35, No. 4, pp. 1250–1264, 2008.
V. Suresh and D. Chaudhuri, “Bicriteria scheduling prob-
lem for unrelated parallel-machines,” Computers and In-
dustrial Engineering, Vol. 30, pp. 77–82, 1996.
[20] K. Jansen and L. Porkolab, “Improved appro
schemes for scheduling unrelated parallel-machines,”
ACM Symposium on Theory of Computing, pp. 408–417,
1999.
[21] S. Kirkpatrick, Jr. C. D. Gela
mization by simulated annealing,” Science, Vol. 220, pp.
671–680, 1983.
[22] N. E. Collins, R. W. Eglese, and B. L. Golden, “Simulated
annealing—an annotated
of Mathematical and Management Sciences, Vol. 8, pp.
209–307, 1988.
[23] R. B. Rutenbar, “Simulated annealing algorithms: An
overview,” IEEE Circuits and
[25] B. Suman and P. Kumar, “A survey of simulated anneal-
ing as a tool for single and multiobjective optimization,”
Journal of the Operational Research Society, Vol. 57, No.
10, pp. 1143–1160, 2006.
[26] R. T. Clemen and T. Reilly, “Making hard decisions,”
Duxbury, Toronto, 2001.
[27] P. Andersen and N. C. Petersen, “A procedure for ranking
efficient units in data envelopment analysis,” Manage-
ment Science, Vol. 39, pp. 1261–1264, 1993.
[28] D. Slottje, G. W. Scully, J. G. Hirschberg, and K. J. Hayes,
easuring the quality of life across countries: A multi-
dimensional analysis,” Westview Press, Boulder, CO,
1991.
[29] M. Pinedo, “Scheduling theory: Algorithms and systems,”
Prentice-Hall, Inc., A Simon & Schuster Company Engle-
wood Cliffs, New Jersey, pp. 10, 1995.
[30] A. Charnes, W. W. Cooper, and E. Rhodes, “Measuring
the efficiency of decision making units,” European Jour-
nal of Operational Research, Vol. 2, pp. 429–444, 1978.