* FAQ    * Search  * Register * Login 
Active topics
Unanswered topics

All times are UTC-06:00



Post new topic  Reply to topic  [ 9 posts ] 
Author Message
 Post subject: Search/Scheduling Algorithm
PostPosted: Fri Sep 21, 2012 5:53 am 
Offline
DBB Benefactor
DBB Benefactor
User avatar

Joined: Thu Sep 02, 1999 2:01 am
Posts: 4428
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


Top
   
 Post subject: Re: Search/Scheduling Algorithm
PostPosted: Fri Sep 21, 2012 2:07 pm 
Offline
DBB Master
DBB Master
User avatar

Joined: Sun Sep 05, 1999 2:01 am
Posts: 6356
Location: ☃☃☃
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.


Top
   
 Post subject: Re: Search/Scheduling Algorithm
PostPosted: Fri Sep 21, 2012 9:38 pm 
Offline
DBB Benefactor
DBB Benefactor
User avatar

Joined: Thu Sep 02, 1999 2:01 am
Posts: 4428
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


Top
   
 Post subject: Re: Search/Scheduling Algorithm
PostPosted: Sat Sep 22, 2012 1:05 pm 
Offline
DBB Master
DBB Master
User avatar

Joined: Sun Sep 05, 1999 2:01 am
Posts: 6356
Location: ☃☃☃
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.


Top
   
 Post subject: Re: Search/Scheduling Algorithm
PostPosted: Sat Sep 22, 2012 2:10 pm 
Offline
DBB Material Defender
DBB Material Defender
User avatar

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


Top
   
 Post subject: Re: Search/Scheduling Algorithm
PostPosted: Sat Sep 22, 2012 6:15 pm 
Offline
DBB Benefactor
DBB Benefactor
User avatar

Joined: Thu Sep 02, 1999 2:01 am
Posts: 4428
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


Top
   
 Post subject: Re: Search/Scheduling Algorithm
PostPosted: Sat Sep 22, 2012 6:48 pm 
Offline
DBB Benefactor
DBB Benefactor
User avatar

Joined: Thu Sep 02, 1999 2:01 am
Posts: 4428
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


Top
   
 Post subject: Re: Search/Scheduling Algorithm
PostPosted: Tue Sep 25, 2012 8:14 pm 
Offline
DBB Master
DBB Master
User avatar

Joined: Sun Sep 05, 1999 2:01 am
Posts: 6356
Location: ☃☃☃
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?


Top
   
 Post subject: Re: Search/Scheduling Algorithm
PostPosted: Wed Sep 26, 2012 5:11 pm 
Offline
DBB Benefactor
DBB Benefactor
User avatar

Joined: Thu Sep 02, 1999 2:01 am
Posts: 4428
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


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 9 posts ] 

All times are UTC-06:00


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron



Descent'rs have piloted these pages
 
The layout and contents contained within this site are © DescentBB.net 1997-2006.
Descent, Descent II are © Parallax Software Corporation.
Descent III is Outrage Entertainment.
Descent is a Trademark of Interplay Productions.

Miner Wars™ is trademark of Keen Software House s. r. o.
.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group