wanted: algorithm for scheduling optimum capture list

[4evrplan]

Here's the problem:

I only have one capture card and can hence only capture one tv program at a time. Unfortunately, many of the programs I would like to record overlap each other chronologically, on different channels.

The solution I envision is to create a list of every tv program I would like to record, including reruns in case there are fewer conflicts with a later showing. The list would include the name of the program, the start time, the end time, and the duration and would be ordered by most preferred program to least preferred program. I would then feed this list into a software program of my own creation that would spit out a revised list of tv programs with all conflicts and and multiple airings removed. It would however, have to cull out shows in an intelligent way, taking into account my preferences, so that the revised list is the best possible one, given my preferences.

I'm comfortable programming, but I don't know how to approach creating an algorithm to do this. Hopefully, there already exists an algorithm that will fit this. I don't even know how to phrase a google search to get an algorithm that fits this exact challenge.

Any suggestions?

[4evrplan]

Me again. I had an idea. For each tv program in my list, if it conflicts with an item lower in the list (less preferred), simply remove the less preferred item. Once the conflicts for a program have been removed, I also check the rest of the list for reruns of this program and remove them as well.

I just realized though, that the order I put multiple airings in will change the results, since changing the show time of a preferred item changes what it will conflict with. Back to the drawing board.

[guns1inger]

You are talking about timetabling algorithms, which are incredibly complex the more variables you add in. Schools use these for creating teacher and class timetables, and shift managers use them to staff different time periods. I have yet to see one that wasn't difficult to use and/or still require a great deal of manual massaging to get right. Good luck.

[CogoSWSDS]

This might help. Let's say you've got the following schedule:

Title                    Time                     Channel                  Priority
CSI                      7:00-8:00                Spike                    1
Mythbusters              8:00-9:00                Discovery                2
CSI                      8:30-9:30                CBS                      1
CSI                     10:00-11:00               Spike                    1
Star Trek		         11:05-12:05               G4                       3
Mythbusters             11:00-12:00               Discovery                2
Star Trek                2:05-3:05                G4                       3
Everybody Loves Raymond  3:00-3:30                Fox                      3
Everybody Loves Raymond  6:00-6:30                Fox                      3

I'd do the following:
1. Make a list of all episodes which do not conflict with any other episode, regardless of priority, and remove them from the above list. The 7:00 and 10:00 showings of CSI don't conflict with anything else. We don't need both of them, so move 1 of them to the new list. Likewise with the 6:00 showing of Everybody Loves Raymond. This new list looks like this:

Title                    Time                     Channel                  Priority
CSI                      7:00-8:00                Spike                    1
Everybody Loves Raymond  6:00-6:30                Fox                      3

2. Now eliminate other episodes of the same shows from the first list. Your list now looks like this:

Title                    Time                     Channel                  Priority
Mythbusters              8:00-9:00                Discovery                2
Star Trek		         11:05-12:05               G4                       3
Mythbusters             11:00-12:00               Discovery                2
Star Trek                2:05-3:05                G4                       3

3. Repeat step 1 for the above list, making sure you do not select episodes which overlap with episodes already on the list generated in step 1. The 8:00 Mythbusters does not conflict with the already selected CSI or Everybody Loves Raymond, so add it to the list. Your list now looks like this:

Title                    Time                     Channel                  Priority
CSI                      7:00-8:00                Spike                    1
Mythbusters              8:00-9:00                Discovery                2
Everybody Loves Raymond  6:00-6:30                Fox                      3

4. Repeat step 2. The list of episodes with conflicts now looks like this:

Title                    Time                     Channel                  Priority
Star Trek		         11:05-12:05               G4                       3
Star Trek                2:05-3:05                G4                       3

5. Now I can pick either Star Trek episode, since neither of them conflict. I'll just pick the first one. My final schedule looks like this:

Title                    Time                     Channel                  Priority
CSI                      7:00-8:00                Spike                    1
Mythbusters              8:00-9:00                Discovery                2
Star Trek		         11:05-12:05               G4                       3
Everybody Loves Raymond  6:00-6:30                Fox                      3

If, after you've eliminated all the possible conflicts, you still have shows left you want to record, you then start using the priorities, and whichever one has the higher (lower numbered) priority is the one you would pick. In the event that two conflicting shows have the same priority, arbitrarily pick one. This may not have been a good example because I was already able to eliminate the conflicts, and was only intended to be some food for thought to get you started. Basically this is the old divide-and-conquer approach where you make the problem set smaller in an iterative fashion.

CogoSWSDS