The problem is that when the tab could be most useful is when it's hardest to create it. With an instrument like the guitar, tab tells you which of a few alternate strings to use to get a particular note. Choosing the best alternative depends on the context; you want to minimize hand and finger movement, so you want to tab whole phrases, not individual notes.

Laurie Griffiths (a very knowledgeable guitarist with a background in mathematical physics) put this sort of intelligent tab generation into his ABC processor Muse, but was killed by a thug in a posh car just before he could release it. He said that in the most pathological cases, changing a note at one or other end of a tune could force a change in the tab that would propagate all the way to the other end.

I suspect that the definitive answer to this problem would have to use Dmitri Tymoczko's orbifold models of voice leading; he has a theorem which constructs voices moving by the minimum number of steps, with no crossings, for any specified chord progression. That isn't quite the same as the tab creation problem, but you should be able to use similar constructions to minimize finger position movement rather than to avoid unsingable jumps. The relevant articles:

"The Geometry of Musical Chords", Science, 7 July 2006, pp.72-4 (see Theorem 1 in the supplement you can download from the Science website)

"Generalized Voice-Leading Spaces", Science, 18 April 2008 (which also has a supplement detailing the nitty-gritty)

Tymoczko has a book about all this, The Geometry of Music, which has all sorts of neat ideas about music history but less about algorithms. And lots of demos, as downloadable software or videos.