Consider the following problem:
Minimum Tardiness Seqaenclng (MTS)
Instance:
A
set
of
tasks
T
=
{ti,
t
1
,
...,
t,.}
each
requiring
one
unit of execution time, a set of deadlines
D
=
{d(ti),d(t;),
...,
d(t,.)},
a partial order
T
and an integer
K,
O
K
E;;
ITI,
Question:
Isthere a schedule (i.e.,an order of execution of the
ti)
such
that
if
t,
t
1
then
t,
is
executed
before
t
1
and
such
that
no more than
K
tasks are completed after their deadlines?
Given an instance of
CLIQUE, I,
we can construct an instance
F(I
)
of
MTS.
Let
I
consist of
G
=
(V,
E) and an integer
L. F(I )
then con
sists of:
T
=
{11:i,
"ii,
...,
v.,
e
1
,
e
1
,
...,
ei},
v,
e
V
and
e
1
e
E
v,
r
>
1
if
in
G,
v,
is
an
end-point
of
e
1
d(
vi
)
=
!L(
L+
1),
d(
e
,
)
= IVI+
IE
l
K
= IEl-(!L(L-1))
This construction can clearly be carriei.r out in polynomial time. Show that /has a clique of si7.e
L
ifand only if
F(I)
has no more than
K
tasks completed after their deadlines. This will prove that
MTS
is
NPC.
(The partial order requires that in every schedule any 'edge' task is com pleted after its own 'end-point' tasks. The deadlines are such that only 'edge' tasks can be late. Ifthe answer to
MTS
for
F(I)
is 'yes', then at least
!L(L-
2) of these tasks must be completed before their deadline, tL(L+2). In order that the schedule does not violate the partial ordering, the corresponding 'vertex' tasks must also beexecuted before this deadline. The
minimum
possible
number of these is
L
(when the corresponding vertices in
G
form a clique) so that the total number-of tasks now performed before the time
!L(L+
1) is
tL(L-l)+L = tL(L+l)
This just exhausts the available time before the 'edge'-task deadline.)