Scheduling issue with program that starts one minute early

[johnsta]

Fox has launched a new show called "Pitch," and the first two episodes
are scheduled for 20:59 for length=1:01. This obnoxious scheduling
decision is causing an issue with npvr scheduling.

The following is a listing of how npvr schedules the shows at 8pm
and 9pm. I've listed these shows below in priority order within each
of these hours:

Code:

Time                    Channel  Device   Program
--------------------    -------  ------   -------------------
Thu-10/27-20:00:00+0:31:   4      24      The Big Bang Theory
Thu-10/27-20:00:00+0:59:  13      23      Rosewood
Thu-10/27-20:00:00+0:30:   7      22      Superstore
Thu-10/27-20:00:00+1:00:   5      21      Grey's Anatomy

Thu-10/27-20:30:00+0:30:   7      22      The Good Place
                    
Thu-10/27-21:00:00+1:00:   7      24      Chicago Med
Thu-10/27-21:01:00+0:29:   4      23      Mom
Thu-10/27-21:00:00+1:00:   5      22      Notorious

Thu-10/27-20:59:00+1:01:  13       0 CONF Pitch

So what happens is that npvr successfully schedules all the shows in
the 8-9 hour. It schedules the first three shows in the 9-10 hour, but
when it gets to Pitch it fails because all the devices have been used
up for the one-minute period from 8:59-9:00pm. As a result, the
program is assigned a "conflict" status and not scheduled.

This is the case even though there are four devices available for four
channels. The problem arose because Pitch is a new program, therefore
had the lowest priority (highest priority value). I'm going to guess
that other people are having the same issue.

*** Suggestion

If I could make a suggestion for your scheduling algorithm, it would
be the following: You have a Settings|Devices dialog that allows the
user to specify the order in which devices should be allocated.

My suggestion would be have a setting that overrides the order, and causes
the scheduling algorithm to give highest priority to a device already
being used for the same channel.

In the above case, this modified algorithm would have assigned Chicago Med
to device 22, Mom to device 24, and Notorious to device 21. That would
have left device 23 free to schedule Pitch.

*** Workaround

I tried various things to trick npvr into scheduling all the 9pm
shows. The thing that finally worked is that I changed the priority
of Pitch so that it was just one greater than the priority of
Rosewood. That way, Pitch was scheduled right after Rosewood, and
they used the same device.

I don't believe that this workaround will work 100% of the time, even
though only four channels are involved with four devices. In some
cases it would be necessary to change the priorities of both Pitch and
Rosewood so that they're together at a higher priority than the other
shows. This is something I'll have to watch on a case by case basis.


One thing I might try is to enhance my priority algorithm. I
currently group programs into three groups. All the programs in Group
1 are "must record" and have the highest priority, and group 3 have
the lowest priority. I have a script that generates sql update
statements to assign priorities correctly in all three groups.

I'm thinking of enhancing this algorithm so that the programs in group
1 are sorted by channel, and therefore are assigned priorities so that
those on same channel are all grouped together (similar to
prioritizing Rosewood and Pitch together above). The combinatorics of
this are a little complicated, so I'd have to test to see if this
would work with nprv's scheduling algorithm.

*** One more request

While I'm posting a message, I'd like to make one more request.

When a series program is not scheduled because of a conflict, you can
tell because it appears in the scheduled_recording table with a
status of 3.

But when a program is "Manually scheduled" and has a conflict, then it
doesn't appear in the scheduled_recording table at all, and also
doesn't appear on NextPVR UI "Conflicts" screen, so there's no easy
way to detect that it had a conflict. So my request would be that
when a manually scheduled program is not scheduled because of a
conflict, then it appear in the scheduled_recording table with a
status of 3.

Thanks. I hope you're doing well.

[sub]

You could try setting your padding on that recording to -1 minute, which may help.

The app does it's best with scheduling, and usually does a pretty decent job, but that's not to say a user couldn't do a better job at working out how to squeeze a tight recording schedule in the available amount of tuners. In reality, if you've got multiple tuners, and lots of recordings going on, the easiest fix is probably adding another tuner to the system.

[johnsonx42]

If I could make a suggestion for your scheduling algorithm, it would
be the following: You have a Settings|Devices dialog that allows the
user to specify the order in which devices should be allocated.

My suggestion would be have a setting that overrides the order, and causes
the scheduling algorithm to give highest priority to a device already
being used for the same channel.

In the above case, this modified algorithm would have assigned Chicago Med
to device 22, Mom to device 24, and Notorious to device 21. That would
have left device 23 free to schedule Pitch.

Just to give you a little more understanding of the situation: behind the scenes we've actually talked about this exact scenario before, and the conclusion was always that it wouldn't be worth the limited benefit and we found reasons not to do it as it would cause undesired results for some users. I've studied the scheduler's operation in detail over the years, I think I know how it works about as well as sub does, and I can tell you that actually implementing what you suggest would be difficult and would open up numerous avenues for weird bugs. The short version is that because the scheduler processes the recordings in priority order, not chronologically, it generally doesn't know which tuners will be in use on which channels chronologically. Everyone always thinks of scheduling programs in this timeslot or that timeslot (as evidenced by the way you listed your recording schedule) because that's what makes sense for us humans, but the NextPVR recurring scheduler doesn't work that way.

As you've already found, adjusting the recurring priority is the solution. That's why sub added the ability to change the recurring priority, to deal with these exact sorts of issues.

[BrettB]

The short version is that because the scheduler processes the recordings in priority order, not chronologically, it generally doesn't know which tuners will be in use on which channels chronologically.

In addition, just because the scheduler originally scheduled (or rather reserved) a particular recording to use a particular tuner doesn't guarantee that the recording will actually end up using that tuner at record time. Factors like a user watching live tv, another app/device using a network tuner, a tuner no longer being available/active, and (probably) an earlier recording being extended can cause a recording to get moved to a different tuner when the recording actually begins.

[johnsta]

Thanks to everyone for your responses and for the information.

I just wanted to clarify what I was suggesting. The scheduling would
still be done in priority order (not chronological order). The only
thing that would change is that tuner devices would be assigned in a
different way. Also, I was suggesting that this be a user setting,
rather than something that would be done for everyone.

There's a more complicated algorithm that I didn't mention. This is
in the category of "backtracking algorithms." (I assume you must have
considered this, but Google the phrase if you're not familiar with
it.) In the case I described, once the scheduling algorithm had
failed to schedule Pitch at 9 pm, it would go back (backtrack) to
previous scheduling decisions (e.g., 8pm and 7pm) to see if changing
those schedules would allow Pitch to be scheduled. A backtracking
scheduling algorithm can be quite difficult (NP-complete), but it can
be simplified considerably by changing the way that tuners are
assigned, as described above (give preference to tuner already being
used for the same channel).

I would encourage you to consider a backtracking algorithm since (I
believe) both of the systems that I used previously -- Beyond TV and
Media Center -- used backtracking algorithms, and quickly recomputed
the entire schedule whenever an event occurred (change in schedule,
live tv, etc.) They never ran into the Pitch problem I described.

Npvr actually has a very big advantage over Beyond TV and WMC because,
unlike them, Npvr can overlap recordings by using the same tuner for
two recordings for the same channel at the same time. This greatly
simplifies the backtracking scheduling algorithm.

As a further update to my own situation, I tried the idea that
I mentioned -- I changed all the priorities so that all the CBS
programs are done first, then all the NBC programs, then all
the ABC programs, and then all the Fox programs.

I was VERY pleasantly surprised by the result. Not only was the Pitch
problem completely resolved, but some of my "Group 3" programs that
had not previously been scheduled suddenly were scheduled, indicating
that the assignment of tuners was being done much more efficiently.
This was spectacularly great, and it worked so well that I really hope you'll
try some version of this.

Thanks again for the help, and I hope everyone is doing well.

[johnsonx42]

@sub,

actually as I think about the way the scheduler operates, a simple change does occur to me that would probably make it work better for some users. add an option to disregard the recurring recording priority and instead process the recurring recordings by channel_oid (or channel_oid combined with the priority if you need something unique for each recording). this would tend to result in more efficient tuner allocation, and more likely accommodation of padding, at the expense of being unable to change relative priorities. This way the user can pick the scheduling order: by channel for more efficient tuner allocation but less control, or by priority for possibly less efficient tuner allocation but more control.

[scJohn]

Where is this 'recurring recording priority' field? When setting up a recording I only see Recording Type, Pre-Padding, Post-Padding, Directory and Keep.

[johnsonx42]

it's in the database. you can change the relative priorities through the UI (as you've apparently done already), but the priority field itself isn't exposed directly. normally the scheduler iterates through the recurring recording table in order of the priority, which is how NextPVR and GB-PVR before it have always done it. I'm suggesting to sub that iterating through the recurring recording table in order of channel_oid would be a better option for a lot of users, and I know it'd be relatively simple to implement with the existing scheduling logic vs. your suggesting of a backtracking algorithm which would be great and wonderful I'm sure but a major new layer of logic to add which I strongly suspect sub is disinclined to consider. (the work/benefit ratio is not favorable... if sub's not keen on an idea, or sees limited benefit, it's a lot easier to get him to do it anyway if it's not time consuming to implement and isn't likely to break anything)

[BrettB]

it's in the database. you can change the relative priorities through the UI (as you've apparently done already), but the priority field itself isn't exposed directly. normally the scheduler iterates through the recurring recording table in order of the priority, which is how NextPVR and GB-PVR before it have always done it. I'm suggesting to sub that iterating through the recurring recording table in order of channel_oid would be a better option for a lot of users, and I know it'd be relatively simple to implement with the existing scheduling logic vs. your suggesting of a backtracking algorithm which would be great and wonderful I'm sure but a major new layer of logic to add which I strongly suspect sub is disinclined to consider.

I think that Johnsonx42 got scJohn confused with the OP--johnsta.

To further answer scJohn's question: you can change the priority order of Recurring Recordings in the GUI by:

1. Go to the Recordings screen
   
2. Use the left/right arrow to get to the Recurring list
   
3. Press the stop button until the sort order is listed as "Sorting By Priority" (or "Sorting By Priority Descending")
   
4. Use the up/down arrows to select the recording whose priority you want to change
   
5. Use the Next Chapter/Previous Chapter (or Ctrl-right arrow/Ctrl-left arrow) to move the recurring recording up or down the list
   

[johnsta]

> @sub, actually as I think about the way the scheduler operates, a
> simple change does occur to me that would probably make it work
> better for some users. add an option to disregard the recurring
> recording priority and instead process the recurring recordings by
> channel_oid (or channel_oid combined with the priority if you need
> something unique for each recording). this would tend to result
> in more efficient tuner allocation, and more likely accommodation
> of padding, at the expense of being unable to change relative
> priorities. This way the user can pick the scheduling order: by
> channel for more efficient tuner allocation but less control, or
> by priority for possibly less efficient tuner allocation but more
> control.

Based on my experience, I believe that something like this could be
extremely effective. But take care -- what I did was not a "pure"
case of scheduling by channel. I also broke the programs up into
three priority groups, and mainly applied the scheduling-by-channel
change to Group 1 -- the "must record" programs. I believe that to be
effective, some combination of scheduling by priority and scheduling
by channel would have to be used. But as I said, I was really
surprised by how well it worked for me.