Information Technology Reference
In-Depth Information
å
completed, lateness measures are appropriate. In
the case where all the due dates are zero,
d
i
=0,
◦
w
i
weighted completion time
i
i
,
tardiness or lateness are identical to completion
time functions.
All of the above mentioned criteria are regular
in the sense that they are non-decreasing functions
of job completion times. French's classification
includes some non-regular criteria, such as mea-
sures based upon the inventory and utilization
costs. For example, to measure the idle time of a
machine, the following criterion is used:
∀
å
◦
w F
i
weighted flow time
i
Flow time is applied as a criterion when the
cost function is related to the job standing time.
Completion time reflects a criterion where the
cost depends on the finish time. In the event of all
ready times being zero,
r
i
=0,
i
, completion time
and flow time functions are identical. Maximum
criteria should be used when interest is focused
on the whole system. When some jobs are more
important than others, weighted measures could
be considered.
∀
n
∑
1
•
I
j
=
C
max
-
p
ij
total time during which
i
=
machine
M
j
is waiting for a job or has fin-
ished processing jobs, but the total process
of jobs has not finished jet.
Criteria based upon due date measures:
◦
L
max
= max{
L
1
, L
2
,..., L
n
}, maximum
lateness
◦
T
max
= max{
T
1
, T
2
,..., T
n
}, maximum
tardiness
In the literature, the most common criterion is
the makespan. Only a relative few published works
are devoted to flow time and tardiness measures.
L
å
L
å
mean lateness or
◦
or
i
n
total lateness, respectively
computational complexity
T
å
T
å
mean tardiness or
◦
or
i
n
Since the early algorithm presented by Johnson
(1954), which solves
F2//C
max
in polynomial time,
only a few restricted cases have been shown to
be efficiently solvable. Minimizing the sum of
completion times is still NP-complete for two
machines (Garey & Johnson, 1979).
The following cases have been shown to be
NP-hard:
total tardiness, respectively
å
◦
w L
i
weighted lateness
i
å
◦
w
i
weighted tardiness
i
U
å
total tardy jobs. The indicator
function
U
i
denotes whether the job
J
i
is tardy, then
U
i
= 1, or on time, then
U
i
= 0.
◦
•
F
/
p
ij
=1,
intree
,
r
i
/
C
max
•
F
/
p
ij
=1,
prec
/
C
max
•
F2
/
chains
/
C
max
•
F2
/
chains
,
pmtn
/
C
max
•
F2
/
r
i
/
C
max
•
F2
/
r
i
,
pmtn
/
C
max
•
F3
//
C
max
•
F3
/
pmtn
/
C
max
•
F
/
p
ij
=1,
outtree
/
L
max
•
F2
//
L
max
When maintaining customer satisfaction by
observing due dates, or any other
just in time
concept has to be considered, measures related
to the notion of how much is lost by not meet-
ing the due dates are applied. If the penalty is
applied only to the delays, tardiness measures
are used. When there is a positive reward, or
penalization, for completing a job early and that
reward/penalization is larger the earlier a job is
Search WWH ::
Custom Search