[Openpvr-devel] scheduling algorithms

[Brian J. M. <317...@in...>]

Hello folks,

Let me first appologize for the length of this message.  It is
messages this long on most other lists that hit 'D' when starting to
read.  I hope I can be (much!) more brief in the future, but I felt
that the issue at heart in this message required some background.  If
you want to just get to the heart of this issue and decide from there
if you want to go back and read the background, skip down to paragraph
9

Sorry about the lack of progress here on OpenPVR but the last month or
two has been quite event filled.  Of course there were the holidays,
which when you are single are a great time to catch up on some
hacking, but when you have a family it has exactly the opposite
effect.

That leads me to the other thing that has been occupying my time since
starting OpenPVR.  At the beginning of Dec, my son was born and that
event had and continues to still occupy a lot of my time.  I am
fitting in stuff where I can though.

I don't know how many of you have looked at the program recording
scheduling prototype that I wrote and is in CVS right now, so I will
give a brief overview of what it does.

It's goal is to simply record as much programming as you are
interested in seeing based on program names (i.e. "ER", or "Survivor:
Africa", etc.).  In order to meet that goal the scheduler uses the
XMLTV project to get a two week schedule of programming.  Using that
programming information, the scheduler tries to search out your
programs, when they are on and if they are repeated.  This latter item
is used to try to schedule as much programming as possible.

For instance, if program A is on in timeslot 1 and so is program B,
but program A is also shown in timeslot 2, program B will be recorded
in timeslot 1 and program A will be recorded in timeslot 2.

To determine the best schedule to record as much as possible, I simply
try out every combination of programming until I get the schedule that
records the most episodes for the two weeks.  This is a brute-force
search.  The mathematics of it are of course exponential.  If you have
two programs you want to record and each of those two programs is
repeated twice, you have to try 4 different scheduling combinations in
order to determine which one is best.

The numbers of schedules gets very high very fast when you include
heavily syndicated programs like "Frasier", and "Friends" (and here in
Canada, "Law & Order" and "All in the Family" the latter of which is
shown 6 times a day -- 2 episodes back to back, 3 times a day).

So I have been thinking about how to reduce the numbers of schedules
that need to be "brute-force" searched.  I thought, if I can identify
programming that will neither cause a conflict or help resolve one
(i.e. a program that is repeated during the scheduling cycle but never
on at the same time as something else), I can schedule that and remove
it from the brute-force scheduling algorithm.  That could have
dramatic effects at reducing the number of scheduling combinations
that needs to be brute-force searched.

So in application of this thought, I decided that a list of everything
I want to record, sorted by showing time and traversed from beginning
to end should identify conflicts (adjacent items whose start time +
duration overlap with each other, as well as programs that do not
conflict.  I can then put the conflicts in one schedule to be searched
further and the non-conflicting (easy ones) programs into the
recording schedule.

But then it occurred to me, do I even have to brute force search for
the best possible conflict resolution?

What if given the above sorted list of programs, I just schedule
everything that does not have a conflict (removing repeated
programming from the list as I schedule the earliest showing of it)
and then treat conflicting programs in the following manner, assuming
the programs that are conflicting (showing in overlapping time
windows) are "A" and "B":

1. if either "A" or "B" is repeated, defer scheduling the one that
   repeats and record the other

2. if neither repeat, use a scoring mechanism to choose the one to
   record
   - if the scores are equal, choose one randomly

3. if they both repeat... what?

In the case of #1, the repeated program will continue to be deferred
until it becomes case #2, or it can be recorded without conflict.
This seems like a good scenario.  Deferring repeated programming in
favour of non-repeated programming is good.

In the case of 2, hopefully the user has set up scoring of his
programs to be sure that he gets the one he wants.  Perhaps some kind
of "schedule review" could be set up to show him what he will be
missing because of the conflicts and his scoring on his wanted
programming.  He should be allowed to adjust scores to get the
schedule to record what he wants most and sacrifices what he wants
least.

I think case #3 is what my current "brute-force" search is supposed to
work ideally with.  If both "A" and "B" repeat, then when choosing
which one to record first and which one to defer, one has to look at
all of the conflicts to decide if deferring either "A" or "B" helps
out in resolving other conflicts and which to defer to help reduce
further conflicts to their minimum.  Either choice can have (deep)
ripple and/or circular effects on further conflict resolution.  I see
no other way (as good anyway) to resolve the real conflicts than to
brute-force search for the best combination of recording.

Or am I missing something much more simple here?

b.

-- 
Brian J. Murrell