jberger@asterix.drev.dnd.ca (Jean Berger) (08/01/90)
Hey folks,
Two questions:
1) NP-Complete for a variant of a well-known problem
2) Well-known heuristics in scheduling (one, multi-processor) wanted!
(Refs wanted)
1) NP-Complete for a variant of a well-known problem
From the book Computer and intractability (A Guide to NP Completeness)
from Garey & Johnson is mentioned a NP-Complete problem regarding
the sequencing on one processor (p. 236):
A5 Sequencing and Scheduling
Problem A5.1 Sequencing on one processor
[SS1] Sequencing with release times and deadlines
Instance: Set T of tasks, for each task t in T, a length l(t) in Z+,
a release time r(t) in Z+ U {0}, and deadline d(t) in Z+
Question: Is there a one-processor schedule for T that satisfies the
release time constraints and meets all deadlines.(No preemptions
initially assumed)
From Garey & Johnson if r(t) = 0 the general problem can be solved in poly
time.
MY QUESTION: Now if we relax the condition on l(t) as follows:
We introduce a new variable called time (real time variable) such that
l(t) = l(t; time) = a(t) - b(t)*time (a,b in R+)
In other words if the length of the task t is linearly decreasing as
time goes by, is that problem still NP-Complete ??????
2) Well-known heuristics in scheduling (one, multi-processor) wanted
I am looking for heuristics for similar problems in tasks scheduling
for one/multiple processor. Would you know a repertory/collection of
efficient heuristic for scheduling resolution problems ?
(Basically the idea is to schedule n tasks on m processors with
constraints mentioned previously: l(t), d(t), r(t) for all t in T)
Thank a million. E-mail: ARPA: jeanb@quebec.drev.dnd.ca
--
-- Great Minds Think Alike
==========================================================================
jean berger Eng. Defence Research Establishment
Command and Control Division