3 ms·
Does anyone know if Prolog is useful for creating a schedule for workers with many constraints? I have a comment somewhere where I included the constraints but
by johnisgood 2y ago
Does anyone know if Prolog is useful for creating a schedule for workers with many constraints? I have a comment somewhere where I included the constraints but I have forgotten most of it by now. Constraints like minimum of 2 workers for both morning and night shifts, all workers must have 2 days off at least in a week, so no consecutive 3 days work, etc. The number of workers would be defined with names as well, etc. The goal would be to create a monthly schedule. I tried to come up with one but I may have messed up the constraints because it took too long (it got stuck, actually), maybe the constraints were too tight, I don't remember. If not Prolog, then what would be the best way to do this? I am interested in FOSS.
I wish there was a way to search for my comments, it sucks that I would have to paginate. I left a lot of comments.
- Entze 2y agoYou could have a look at the potassco suite[0]. It is a grounder and solver for Answer Set Programming (ASP). ASP is a form of Logic Programming. [0] https://potassco.org/ https://potassco.org/
- johnisgood 2y agoI will take a look at it. Are you familiar with it, an example or a snippet would come in handy, but I may just ask Claude (if it even knows about Potassco).
- Entze 2y agoASP is optimized for combinatorial problems. Basically, you list the parts that are variable, and the constraints, the answers are given by the solver. Have a look at the documentation[0]. Here is an example: % Each shift needs a nurse). 1 { shift_nurse(Shift, Nurse): nurse(Nurse) } 1 :- shift(shift). % It cannot be that a nurse does two shifts in a row. :- nurse(Nurse), shift_nurse(Shift1,Nurse),shift_nurse(Shift2,Nurse), Shift1 + 1 = Shift2. [0] https://potassco.org/doc/start/ https://potassco.org/doc/start/
- johnisgood 2y agoThanks. Found the original comment: https://news.ycombinator.com/item?id=41756679 https://news.ycombinator.com/item?id=41756679 Would this still work with ASP?
- rscho 2y agoYes, but honestly if you can use specialized software instead of writing your own, do so. Scheduling problems become very hairy quite quickly. For ASP, there is also sCASP that is the current flagship application of SWI Prolog.
- cess11 2y agoYes, you could do this and it's likely it'll turn out as rather nice and decently performant code. You would, however, most likely run into the problem of finding people to maintain it that are willing to learn. Most Prolog teaching material is quite abstract in the sense that it mainly teaches the language and its tricks, not so much applications, though there are of course a lot of FOSS and example applications to look at. In practice you would have to write documentation that basically turns into a course on constraint solving in Prolog. There are footguns and somewhat advanced techniques involving control over the execution strategy that are going to trip up newcomers. You'll also have to figure out how to interface with a Prolog implementation. A compromise might be to use bindings for Z3 or something like the Timefold solver, https://timefold.ai/open-source-solver https://timefold.ai/open-source-solver. Either way it's a good idea to spend some time playing around with Scryer, https://www.scryer.pl/ https://www.scryer.pl/, and Markus Triska's crash course, https://www.metalevel.at/prolog https://www.metalevel.at/prolog. SWI-Prolog has more conveniences that might make it more suitable for practical applications, but being used to them might make it harder to adapt to e.g. Scryer, Tau or some other implementation. There's also the Mercury language, it's weirder but also very interesting, https://mercurylang.org/ https://mercurylang.org/. Edit: Some people swear by Picat but I have very little experience with it, http://picat-lang.org/ http://picat-lang.org/.
- deleted 2y ago[deleted]
- nurettin 2y agoProlog is definitely the tool for this. I created an entire year's schedule for teachers a decade ago without a sweat. Maybe remove some constraints and try to debug which one is causing the problem.
- johnisgood 2y agoIs it open source? Is the code available anywhere?
- nurettin 2y agoOh no, it is in an undergrad thesis probably rotting in some library.
- Q6T46nT668w6i3m 2y agoTry Z3
- upghost 2y agoyes[1][2]. You can write Prolog schedulers with arbitrary constraints. [1]: https://www.metalevel.at/prolog/timetabling/ https://www.metalevel.at/prolog/timetabling/ [2]: https://github.com/mthom/scryer-prolog/discussions/2519 https://github.com/mthom/scryer-prolog/discussions/2519
- johnisgood 2y agoSo something like this: https://news.ycombinator.com/item?id=41756679 https://news.ycombinator.com/item?id=41756679 can be created using this?