[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