Indeed, some of the early history of Prolog is in Hewitt's PLANNER: https://en.wikipedia.org/wiki/Planner_(programming_language)... .
If you have such constraints, why not use a proper constraint system? Prolog is in a (sometimes not so) sweet spots in terms of exploring search spaces.
For a problem like you've described, just write a SAT instance and be done with it. And if you don't know how large your solution/search space is (even a bound), then there's no alternative to creating lists and giving recursion hints.
I forget the specifics but every implementation of such a schedule tends up using lists and explicit recursion, (which I think is unpleasant in Prolog) In fact, most moderately complex solutions of any problem I’ve seen fall back on lists and explicit recursion. (I thought I was using Prolog to avoid all that!) That’s probably a shortcoming of the language.