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

f-myth-users at media.mit.edu f-myth-users at media.mit.edu
Fri Sep 9 20:20:07 UTC 2011


    > Date: Fri, 9 Sep 2011 19:54:23 +0000
    > From: Gary Buhrmaster <gary.buhrmaster at gmail.com>

    > On Fri, Sep 9, 2011 at 18:59,  <f-myth-users at media.mit.edu> wrote:
    > ...
    > > 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.]

    > Not exactly sure what an optimal fit would be, but it may
    > approach the complexity of the optimal traveling salesman
    > solution.  In other words, NP-hard.  The heuristics used
    > to avoid the O(n!) brute force search in both the TSP
    > and the MythTV scheduling problem will not produce the
    > optimal solution some of the time.

Yes, my guess would be NP-hard, but I'm not willing to claim that
without a proof that this reduces to TSP or 3SAT or whatever and
even with one, if the chances of a stochastic fit are good enough,
that would bypass NP with high-enough probability that we'd never
see the failure.  (After all, large-number primality testing is also
probabalistic, but you run even a few tests and the chances are better
than the chances your CPU has a fault... :)

So stochastic nudges to the existing scheduler code seems easier.
I'm thinking here of well-known polytime approximations to the
knapsack problem (even though it's NP-complete if you insist on
exactness) and the dynamic programming literature is -huge- and
maybe some CS theory type would like to write a thesis on using
DP to accelerate Myth scheduling decisions... :)  [And then ITA
or some airline-scheduling outfit would hire him or her.]

I keep mentioning things like TMS's because at least that way the
workfactor is (usually) small per-step---adding one more rule or one
more program doesn't necessarily imply redoing all the work.  OTOH,
in a conflict, we might have to backtrack all assumptions to the root,
at which point we -do- have a lot of work, and nobody is going to
seriously propose that radical a change to the scheduler, I suspect.
[And if it runs slower in the whole-new-day-of-guide-data or in the
14-new-days case, it's cooked and nobody will use it anyway.]

    > I suspect that if someone wishes to contribute optional
    > alternative scheduling code(s) to the project that use
    > some of the alternative heuristics for such problems that
    > might be interesting (and most likely hard to accomplish).

Yeah.  And the problem with -optional- is that it runs into the
"minimize configuration buttons to ease diagnosis and setup"
goal that Myth is currently pursuing.


More information about the mythtv-users mailing list