Resumen
This article extends the scheduling problem with dedicated processors, unit-time tasks, and minimizing maximal lateness ??max
L
max
for integer due dates to the scheduling problem, where along with precedence constraints given on the set ??={??1,??2,??,????}
V
=
{
v
1
,
v
2
,
?
?
,
v
n
}
of the multiprocessor tasks, a subset of tasks must be processed simultaneously. Contrary to a classical shop-scheduling problem, several processors must fulfill a multiprocessor task. Furthermore, two types of the precedence constraints may be given on the task set ??
V
. We prove that the extended scheduling problem with integer release times ????=0
r
i
=
0
of the jobs ??
V
to minimize schedule length ??max
C
max
may be solved as an optimal mixed graph coloring problem that consists of the assignment of a minimal number of colors (positive integers) {1,2,??,??}
{
1
,
2
,
?
?
,
t
}
to the vertices {??1,??2,??,????}=??
{
v
1
,
v
2
,
?
?
,
v
n
}
=
V
of the mixed graph ??=(??,??,???)
G
=
(
V
,
A
,
?
E
)
such that, if two vertices ????
v
p
and ????
v
q
are joined by the edge [????,????]???
[
v
p
,
v
q
]
?
E
, their colors have to be different. Further, if two vertices ????
v
i
and ????
v
j
are joined by the arc (????,????)???
(
v
i
,
v
j
)
?
A
, the color of vertex ????
v
i
has to be no greater than the color of vertex ????
v
j
. We prove two theorems, which imply that most analytical results proved so far for optimal colorings of the mixed graphs ??=(??,??,???)
G
=
(
V
,
A
,
?
E
)
, have analogous results, which are valid for the extended scheduling problems to minimize the schedule length or maximal lateness, and vice versa.