Shortest time scheduling for twoprocessors
A complicated task can be broken down into a number of subtasks, s" i = 1, 2, ..., n, each requiring a unit of processing time. Two processors are available and can operate simultaneously. There exists a
partial
ordering
'
'
for
the
s,,
such
that
s,
s
1
means
that
s,
must
be
completed
before
s
1•
G
is
a
digraph
in
which
each
vertex
represents
some
s,
and
there
is
an
edge
(s,,
s
1)
for
each
relation
s,
s
1•
An
undirected
graph G* = (V, E*) is constructed as follows. G* has the same vertex
set as
G
and
(s,,
s
1)
e
E*
if
and only
if
there is no directed path
from
s,
to
s
1
or
from
s
1
to
s,
in
G.
Such
a
construction
is
shown
below.
Justify
the statement that if M is a maximum-cardinality matching in G*, then a lower bound in the computation time for the overall task is given by (n-lMI).
(Such a matching for the problem is said to be feasible if it describes a
possible
scheduling
sequence.
For
example,
matching
{
(
si.
sJ
,
(
s
1
,
s
a
)
}
describes
a
feasible
schedule:
(
s
1
and
sJ
being
executed
simultaneously,
followed
by
(
s
1
and
s
,
),
and
finally
s
1
is
executed.
However,
the
matching
{(si.
sJ ,
(s
1
,
s
1
)}
is not feasible. Fujii et
a1.no1
have shown that a
feasible
matching always exists which is of maximum cardinality and that this
can be found in O(n8)-time. See also Coffman & Graham.[111)