Search/Scheduling Algorithm

For all coding issues - MODers and programmers, HTML and more.

Moderators: Jeff250, fliptw

Post Reply
User avatar
snoopy
DBB Benefactor
DBB Benefactor
Posts: 4434
Joined: Thu Sep 02, 1999 2:01 am

Search/Scheduling Algorithm

Post by snoopy » Fri Sep 21, 2012 5:53 am

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?
Arch Linux x86-64, Openbox
"We'll just set a new course for that empty region over there, near that blackish, holeish thing. " Zapp Brannigan
User avatar
Jeff250
DBB Master
DBB Master
Posts: 6386
Joined: Sun Sep 05, 1999 2:01 am
Location: ☃☃☃

Re: Search/Scheduling Algorithm

Post by Jeff250 » Fri Sep 21, 2012 2:07 pm

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.
User avatar
snoopy
DBB Benefactor
DBB Benefactor
Posts: 4434
Joined: Thu Sep 02, 1999 2:01 am

Re: Search/Scheduling Algorithm

Post by snoopy » Fri Sep 21, 2012 9:38 pm

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.
Arch Linux x86-64, Openbox
"We'll just set a new course for that empty region over there, near that blackish, holeish thing. " Zapp Brannigan
User avatar
Jeff250
DBB Master
DBB Master
Posts: 6386
Joined: Sun Sep 05, 1999 2:01 am
Location: ☃☃☃

Re: Search/Scheduling Algorithm

Post by Jeff250 » Sat Sep 22, 2012 1:05 pm

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.
User avatar
Foil
DBB Material Defender
DBB Material Defender
Posts: 4900
Joined: Tue Nov 23, 2004 3:31 pm
Location: Denver, Colorado, USA

Re: Search/Scheduling Algorithm

Post by Foil » Sat Sep 22, 2012 2:10 pm

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.
User avatar
snoopy
DBB Benefactor
DBB Benefactor
Posts: 4434
Joined: Thu Sep 02, 1999 2:01 am

Re: Search/Scheduling Algorithm

Post by snoopy » Sat Sep 22, 2012 6:15 pm

Foil wrote: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.
Arch Linux x86-64, Openbox
"We'll just set a new course for that empty region over there, near that blackish, holeish thing. " Zapp Brannigan
User avatar
snoopy
DBB Benefactor
DBB Benefactor
Posts: 4434
Joined: Thu Sep 02, 1999 2:01 am

Re: Search/Scheduling Algorithm

Post by snoopy » Sat Sep 22, 2012 6:48 pm

Jeff250 wrote: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.
Arch Linux x86-64, Openbox
"We'll just set a new course for that empty region over there, near that blackish, holeish thing. " Zapp Brannigan
User avatar
Jeff250
DBB Master
DBB Master
Posts: 6386
Joined: Sun Sep 05, 1999 2:01 am
Location: ☃☃☃

Re: Search/Scheduling Algorithm

Post by Jeff250 » Tue Sep 25, 2012 8:14 pm

snoopy wrote: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?
User avatar
snoopy
DBB Benefactor
DBB Benefactor
Posts: 4434
Joined: Thu Sep 02, 1999 2:01 am

Re: Search/Scheduling Algorithm

Post by snoopy » Wed Sep 26, 2012 5:11 pm

Jeff250 wrote:
snoopy wrote: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.
Arch Linux x86-64, Openbox
"We'll just set a new course for that empty region over there, near that blackish, holeish thing. " Zapp Brannigan
Post Reply