[mythtv-users] scheduler settling with conflicts where they are resolvable

[f-myth-users at media.mit.edu]

    > Date: Fri, 09 Sep 2011 14:25:51 -0400
    > From: "Brian J. Murrell" <brian at interlinx.bc.ca>

    > What is really strange is that without my doing anything between
    > yesterday and today the scheduler is now using the additional idle
    > tuners that it was not using yesterday.  That it's using them today and
    > wasn't yesterday, without any intervening mucking with any config at all
    > smells kind of fishy, yes?

What's changed is that time has advanced, and even if you don't have
new guide data, Myth has probably recorded something and rerun the
scheduler a few times.

I wrote a couple years ago about problems I'd had with the scheduler
magically -causing- conflicts in schedules that had been conflict-free
and which had had no user input nor updated scheduling input---in other
words, no one had touched the box, the next MFDB run was 12 hours away,
Mythweb had shown a conflict-free schedule, and then as the scheduler
ran at the conclusion of recording something, the new schedule it worked
out had a conflict for something airing an hour later, and so it dropped
it.  I keep extensive logging data, so this was easy to see, even in
retrospect.

This happened often enough to me (e.g., more than once) that I wrote
code that monitored the logging output and alerted me whenever a new
conflict was detected, so if I actually -did- happen to be somewhere I
could talk to Myth, I could manually push things around ("no, record
-that- one instead") and hence change the situation enough that the
schedule would realize it -did- have the tuners to execute the
schedule---the one it had enough tuners for two hours earlier.
It turns out that this is most likely to happen during primetime
(when the most tuners are in use), and that I'm most likely to be
around at that time (though usually not watching TV), and so having
the alert has actually saved some only-shown-once recordings.

This code fires maybe every 6 months for me, but it -does- fire.
[Note that I'm not running the most up-to-date scheduler, which will
probably behave slightly differently, but the general idea is there
---the scheduler does not spend what I'm guessing would be exponential
time (in its current algorithm, anyway) getting an optimal fit.]

Here's my suggestion for a "quick" (ha!) fix, in the absence of a
total rewrite (such as using a truth-maintenance system or something
in place of giant database joins).  If and only if a conflict is
detected, add noise and rerun---AKA stochastic optimization, or
simulated annealing, or however you want to think about it.

It's not clear to me how exactly to inject this noise---perhaps by
sorting or permuting the ordering of one of the lists of things the
scheduler is chewing on---but the basic idea is to jiggle things and
hope they settle out in a different configuration.  You'd want to only
jiggle a time or two, though, because otherwise you could spend
literally forever randomly trying permutations of a schedule that
absolutely cannot be conflict-free no matter what you do, and the
scheduler has no way of knowing that a priori.

Extra credit:  Remember, for any given scheduler run,
(a) whether it was conflict-free
(b) whether it was prompted by a recording ending,
    or was instead prompted by something that might
    have changed guide data (MFDB run) or rules (user input).

If the last run was conflict-free, but the current run must by
definition be using the same data (no user input or MFDB),
-then- run the jiggle-until-it-fits algorithm, or run it
harder, since it -must- work somehow if it worked last time.

All of this is still a fair amount of code that may be hard to test,
but at least the stochastic-randomness approach won't change anyone's
existing scheduler behavior -unless- a conflict is detected, and then
it may improve it.