Information Technology Reference
In-Depth Information
in polynomial time. For the remaining ones, the
only way to secure optimal solutions is usually by
enumerative methods, requiring exponential time.
The investigation has focused on two approaches:
developing approximation algorithms, and opti-
mally solving restricted, more tractable, cases.
Thus, heuristic methods have been developed,
some of them showing an acceptable performance.
Many real life problems can be modeled as
permutation flow-shop scheduling ones. On pro-
duction lines, it is common to find multi-purpose
machines carrying out different products. Our
experience has been with the ceramic tile manu-
facturing sector, however many problems could be
mentioned when we speak about scarce resources,
or machines, dedicated to the production of some
goods, or jobs.
We will use the three-parameter notation,
α β γ
/ /
, introduced by Graham et al. (1979),
and extended by T'kindt & Billaut (2006) to
multicriteria scheduling problems. The first field
specifies the machine environment (
F
represents
general permutation flow-shop); the second, job
characteristics; and the third refers to the chosen
optimality criterion for single criteria models, and
it extends to cover multicriteria as well as meth-
odology.
definitions
Consider a set of
n
independent jobs
J
i
(
i
=1,...,
n
)
to be processed, each of them on a set of
m
ma-
chines
M
j
(
j
=1,...,
m
), that represent the
m
stages
of the production process. Every job requires a
known, deterministic and non-negative process-
ing time, denoted as
p
ij
, for completion at each
machine. Each machine processes the jobs in the
same order, thus knowing the order of jobs the
resulting schedule is entirely fixed. Any feasible
solution is then called a
permutation schedule
or
a
sequence
.
In a single-criterion problem, we look for the
permutation of jobs from set
J
that would optimize
the performance criterion while for more than
one criterion the objective is to find out the set of
Pareto optimal solutions. French (1982) presents
the following classification:
notation
We will use the notation that follows:
•
J
: set of
n
jobs
J
i
(
i
=1,...,
n
)
•
M
: set of
m
machines
M
j
(
j
=1,...,
m
)
•
p
ij
: processing time of job
J
i
on machine
M
j
•
d
i
: due date of job
J
i
, time limit by which
J
i
should be completed
•
r
i
: time at which the job
J
i
is ready to be
processed
•
w
i
: priority or weight of job
J
i
•
C
i
: completion time of job
J
i
•
C
max
: the maximum completion time of all
jobs
J
i
(this is the schedule length, which is
also called
makespan
)
•
F
i
: flow time of job
J
i
,
F
i
=
C
i
-
r
i
, if
r
i
= 0,
then
F
i
=
C
i
•
L
i
: lateness of job
J
i
,
L
i
=
C
i
-
d
i
•
T
i
: tardiness of job
J
i
,
T
max
= max{
L
i
, 0}
•
E
i
: earliness of job
J
i
,
E
max
= max{-
L
i
, 0}
Criteria based upon completion time measures:
◦
F
max
= max{
F
1
, F
2
,..., F
n
}, the maxi-
mum flow time
◦
C
max
= max{
C
1
, C
2
,..., C
n
}, the maxi-
mum completion time
F
å
F
å
mean flow time or
◦
or
i
n
total flow time, respectively
C
å
C
å
mean completion
The optimal value of any criterion is denoted
with an asterisk,
e.g.
C
max
◦
or
i
n
*
denotes the optimal
time or total completion time,
respectively
makespan value.
Search WWH ::
Custom Search