Search/Scheduling Algorithm

[snoopy]

I'm starting to think about the algorithm that I'm going to need to write for my program to schedule recordings.

Assume you have the following "requests":

Some specific episodes that have manually been scheduled
Some "favorite" programs that have been defined, with an order of preference.

You now have a block listings for the next 14 days. These listings include:

Manually scheduled episodes
Some episodes of the favorite programs that appear only once
Some episodes of the favorite programs that appear multiple times


I want to figure out the most efficient way to create a schedule. My two main ideas are to either organize by chronology, and then schedule from earliest to latest accounting for conflicts or to organize by priority. What thoughts do you guys have on the matter?

[Jeff250]

There's a well known result in computer science that [edit: wrong, see post below].

If you had priorities and you wanted to ignore how choosing higher priority episodes conflicted with lower priority episodes, you could just repeat this process starting with the highest priority episodes and then working down.

But if you have conflicting high-priority episodes and want to choose the ones that also maximize the time on lower priority episodes, this is probably a hard problem. I'm a bit sleep deprived at the moment, so there might be something obvious that I'm not seeing.

[snoopy]

Right, here's an example of a harder scenario, assuming you organize from earliest to latest:

episode A with priority 3 runs at 4, 6, 8, 10
episode B with priority 2 runs at 6 and 8
episode C with priority 1 runs at 8 and 10
episode D with priority 0 runs at 4

If I just run in an order (either forward chronological or priority) D won't get recorded, even though there isn't any reason that it can't. At the same time, the algorithm to account for cases like this could end up getting really big, awkward, and time consuming.

I think I have the beginnings of a plan:

Create a list of everything to be recorded
Organize the entire list by priority, from highest to lowest and secondarily in chronologically (I guess by your recommendation, in reverse)
start running through the list:
a. if no conflict, schedule it & drop it & all duplicates from the list
b. if a conflict appears, just move on.

So, after one iteration, everything with a conflict-free instance is scheduled & gone.

run through the list again:
find all of the entries with only one possible schedule time:
create a list of all entries looking for that time.
a. For each conflicting entry: if another time for that entry has a conflict with a lower priority entry than itself, drop it from the conflict list & the master list
b. schedule the highest priority entry left in the conflict list & remove the conflicts & duplicates

This iteration should resolve all of the entries with a single time either by scheduling them or dropping them. It also will have eliminated time entries for episodes with multiple times

Run the one possible time section iteratively until the list is empty.

I need to think some about corner cases/etc, but this is the best solution I've come up with so far. Particularly, I'm not sure about step b in the single entry portion.

[Jeff250]

Correction to my earlier post (clearer head today): Ignoring priorities and maximizing number of *episodes*, you can sort by *end* time, starting at the *beginning* with the non-conflicting episodes that finish *earliest* OR sort by *start* time, starting at the *end* with the non-conflicting episodes that start the *latest*.

In your example, is priority 0 or priority 3 the highest priority? Do all episodes have unit duration? Note that in practice, shows can start and end at arbitrary times. Comedy Central, for example, is notorious for 35-minute episodes that do not start or end on the usual intervals.

[Foil]

While I'm intrigued conceptually by the problem, I have to ask: Are there really that many conflicts for your recording schedules?

My wife and I have a list of ~10 shows that we have scheduled for regular recording (Win7 MC with a couple of CableCard tuners). True conflicts (ones which can't be resolved by simply catching a later showing of one or more shows) are extremely rare, and with 2 weeks of lead programming, it's plenty of time for the system to prompt us to make a choice if needed.

[snoopy]

While I'm intrigued conceptually by the problem, I have to ask: Are there really that many conflicts for your recording schedules?

My wife and I have a list of ~10 shows that we have scheduled for regular recording (Win7 MC with a couple of CableCard tuners). True conflicts (ones which can't be resolved by simply catching a later showing of one or more shows) are extremely rare, and with 2 weeks of lead programming, it's plenty of time for the system to prompt us to make a choice if needed.

In practice, no I don't have that many. I do want to try to write this well, so in the future if the situation does arise, or someone else wants to use the program that does have a lot of conflicts, the program can handle all of the conflict resolution without any need for user intervention.

[snoopy]

In your example, is priority 0 or priority 3 the highest priority? Do all episodes have unit duration? Note that in practice, shows can start and end at arbitrary times. Comedy Central, for example, is notorious for 35-minute episodes that do not start or end on the usual intervals.

3 is the highest priority
The programs have unit duration

Yeah, the code will have to account for varying lengths and odd start/stop times.

[Jeff250]

If I just run in an order (either forward chronological or priority) D won't get recorded, even though there isn't any reason that it can't.

I don't understand this concern then--why would you expect episode D to get recorded when there is a higher priority episode at the same time?

[snoopy]

If I just run in an order (either forward chronological or priority) D won't get recorded, even though there isn't any reason that it can't.

I don't understand this concern then--why would you expect episode D to get recorded when there is a higher priority episode at the same time?

If the schedule is correctly shuffled, everything can get recorded. If you aren't sophisticated about shuffling duplicates, you potentially will skip lower priority programs when you could postpone higher priority programs to a different time, but don't.