[mythtv-users] scheduler settling with conflicts where they are resolvable
gary.buhrmaster at gmail.com
Fri Sep 9 19:54:23 UTC 2011
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.
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).
More information about the mythtv-users