If I understand your problem correctly, I don't think that
you've given enough information to come up with pseudocode
so I'll just try to give a general overview.
Maybe another analogy would help make things clearer.
Think of set A as a group of jobs that need to be run and
you have:
Set A Job TimeFrame Priority
1 TFa 2
2 TFa 1
3 TFa 1
Think of set B as a series of job queues waiting to run
Set A jobs:
Set B Queue TimeFrame UnitsAvail
X TFb 10u
Y TFb 8u
Z TFb 4u
Then you have a table that defines the amount of time it
takes for each queue in Set B to run each job in set A:
Set X Queue Job RunTime
X 1 3
X 2 5
X 3 2
Y 1 2
Y 2 3
Y 3 1
Z 1 2
Z 2 1
Z 3 2
You can represent the schedule by keeping a separate table
for each job queue where each row represents the smallest
time unit necessary (with appropriate beginning and ending
time frame values).
The last step is to sort your jobs by priority, time and
dispatch them. This is the trickiest part since you have to
make a decision on how to process the incoming jobs, insure
that a queue can process a given job A in the time frame
necessary using only X time units.
I would approach this by trying to resolve all jobs with
the same priority. There are at least two approaches you
can take from here:
- Brute Force -- assign the jobs to queues based on
first job first queue fit. If not all of the jobs can be
scheduled, start again trying the fit the second job of the
same priority first.
- Best Fit -- start with the first job, look at each of
the available queues and select the tightest fit (time
frame-wise).
Once all jobs of the highest level priority are assigned,
process the next group and so on. Each time you make a
successful assignment, decrement the corresponding queue's
available time units and make assignments to the queue's
schedule table (for each row of the job's duration).
There are whole books, dissertations, etc. on scheduling
theory. A Google search on the keywords "scheduling
theory algorithms" turned up over 100K matches. HTH.
--Jim
Update: One of the things you didn't mention was
what to do if it is impossible to schedule all jobs of one
priority given the constraints. This is bound to happen and
could cause infinite loops if you don't allow for it in
your code.
|