# Scheduling optimization problem, existing systems or software?
**URL:** https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274
**Category:** Algorithm
**Tags:** swish
**Created:** [May 4, 2020, 9:04pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274 "2020-05-04T21:04:13Z")
**Posts on this page:** 13
**Page:** 1
### Author:  [@sforman](https://swi-prolog.discourse.group/u/sforman)
#### Post date: [May 4, 2020, 9:04pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/1 "2020-05-04T21:04:14Z")
I hope it’s okay to [cross-post](https://groups.google.com/forum/#!msg/comp.lang.prolog/il4hqTJE3xg/nY9qeRpYAQAJ) this here from comp.lang.prolog? We’re
going to be using SWI Prolog and SWISH for this project.
Hi all! I hope you’re doing well.
I’m attempting to help with the design of a scheduling system to allow
for work at a site while maintaining social distancing and it seems like
a perfect job for Prolog. Before diving in, I thought it would be
prudent to ask if there are existing systems or software already that do
this. It doesn’t have to be polished, even a library or paper would be
appreciated.
Here’s the problem description.
1. Classes of information for the goals, input by the user at the beginning of a run:
2. Classes of information for the constraints, input by the user at the beginning of a run:
3. General constants
> given those data, the task is to output the top N scenarios for who
> goes in during what time of day and what day of week which optimally
> meets the constraints of #2 and satisfies the project activities in #1.
Any information would be greatly appreciated.
Warm regards, stay safe and be well,
~Simon Forman
---
### Author:  [@EricGT](https://swi-prolog.discourse.group/u/EricGT)
#### Post date: [May 4, 2020, 9:21pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/2 "2020-05-04T21:21:08Z")
> [@sforman](#):
>
> I hope it’s okay to cross-post this here from comp.lang.prolog?
It’s OK. Thanks for noting that it was cross-posed.
**EDIT**
A quick search turned up this
Solving Logical Business Problems Using Prolog: [Part Three](https://www.credera.com/blog/technology-insights/open-source-technology-insights/solving-logical-business-problems-using-prolog-part-3/)
which solves a similar variation using constraint satisfaction and notes that it was done with the help of [Markus Triska](https://www.metalevel.at/). I know Markus hangs out at comp.lang.prolog and StackOverflow but not here and StackOverflow would probably not allow that question as it is asking for to much.
---
### Author:  [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)
#### Post date: [May 4, 2020, 9:42pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/3 "2020-05-04T21:42:22Z")
Many years ago, I wrote a quick&dirty project scheduling program in Prolog. As you say, Prolog is very suitable - as I recall it was just a few hundred lines of code to handle some fairly fancy constraints. Sadly, I don’t have the code any more, so I can’t give it to you.
---
### Author:  [@sforman](https://swi-prolog.discourse.group/u/sforman)
#### Post date: [May 4, 2020, 9:57pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/4 "2020-05-04T21:57:46Z")
Oh awesome, that could be just the thing, eh? It links to [Nurse Scheduling using Constraint Logic Programming](https://www.researchgate.net/publication/221603658_Nurse_Scheduling_using_Constraint_Logic_Programming) which looks relevant.
I had a hunch Markus Triska would enter into the picture at some point… 🙂
---
### Author:  [@EricGT](https://swi-prolog.discourse.group/u/EricGT)
#### Post date: [May 4, 2020, 10:07pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/5 "2020-05-04T22:07:30Z")
Thanks for noting the paper ([PDF](https://www.aaai.org/Papers/IAAI/1999/IAAI99-118.pdf)). I have never heard of a PCSP.
A _partial constraint satisfaction problem_ (PCSP) (FW92) is a triple(V, C, _w_), where (V;C) is a CSP and _w_ maps constraints to weights.
---
### Author:  [@sforman](https://swi-prolog.discourse.group/u/sforman)
#### Post date: [May 4, 2020, 11:45pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/6 "2020-05-04T23:45:46Z")
> [@peter.ludemann](#):
>
> Prolog is very suitable - as I recall it was just a few hundred lines of code to handle some fairly fancy constraints. Sadly, I don’t have the code any more, so I can’t give it to you.
Ah, well.
I figured Prolog was the right tool for the job.
---
### Author:  [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)
#### Post date: [May 5, 2020, 12:17am UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/7 "2020-05-05T00:17:04Z")
My experience with constraint solvers is that using them can be tricky to debug – so I would suggest thinking first about how to solve the problem without a constraint solver (I didn’t use a constraint solver for my scheduler; it was easy enough to code up the rules without one). Also, some of your requirements are more of an optimization problem than constraint solver (the ones that say “the {greater,lesser} the better”) and those can quickly become intractable unless you use some heuristics.
Others might disagree with me on this; also, there might be tools for debugging with constraint solvers that I’m unaware of.
---
### Author:  [@EricGT](https://swi-prolog.discourse.group/u/EricGT)
#### Post date: [May 5, 2020, 12:37am UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/8 "2020-05-05T00:37:48Z")
While I am nothing more than a beginner with CLP, here are a few questions I answered at StackOverflow that gave me some insight in working with CLP.
[Understanding CLP(FD) Prolog code of N-queens problem](https://stackoverflow.com/questions/53406374/understanding-clpfd-prolog-code-of-n-queens-problem)
[SWI-Prolog reporting wrong answer with bitshifts CLPFD](https://stackoverflow.com/questions/60790266/swi-prolog-reporting-wrong-answer-with-bitshifts-clpfd)
[Hints to understand splendid program to solve Queens](https://stackoverflow.com/a/56227821/1243762)
As with most CLP problems I find that working a few example problems with only pen and paper to start is the best way to help understand the problem.
While I noted you can’t ask the entire question you asked at StackOverflow, you can ask for help on a specific part.
---
### Author:  [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)
#### Post date: [May 5, 2020, 9:06pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/9 "2020-05-05T21:06:52Z")
I noticed that Picat has some planner modules. They might help in developing heuristics for scheduling.
[http://picat.orgfree.com/picat\_guide/picat\_guide.html#chapter%3Aplanner](http://picat.orgfree.com/picat_guide/picat_guide.html#chapter%3Aplanner)
---
### Author:  [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)
#### Post date: [May 9, 2020, 5:34pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/10 "2020-05-09T17:34:51Z")
Also this thesis, which uses [CLP(FD)](https://www.swi-prolog.org/pldoc/man?section=clpfd) I think: [https://www.metalevel.at/mst.pdf](https://www.metalevel.at/mst.pdf)
---
### Author:  [@EricGT](https://swi-prolog.discourse.group/u/EricGT)
#### Post date: [May 9, 2020, 5:45pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/11 "2020-05-09T17:45:20Z")
> [@peter.ludemann](#):
>
> I think
Why do you say that?
The thesis notes:
> The goals of this thesis are:
>
> 1. to present and discuss the most prominent existing approaches towards
> solving SGP instances, which are:
> • design theoretic techniques
> • SAT encodings
> • constraint-based approaches
> • metaheuristic methods
> 2. to contribute, as far as possible, to each of these approaches
> 3. to go, where possible, beyond existing approaches, and obtain new
> results about the SGP
---
### Author:  [@sforman](https://swi-prolog.discourse.group/u/sforman)
#### Post date: [May 9, 2020, 5:59pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/12 "2020-05-09T17:59:28Z")
It looks like it could be useful, even though it’s not exactly the same problem.
I’m pretty sure that the right problem format or definition is out there already, and if it can be found the whole thing becomes really tractable (up to the limits of the problem domain that is. I mean that writing the rules for the scheduler should be straightforward.)
---
### Author:  [@peter.ludemann](https://swi-prolog.discourse.group/u/peter.ludemann)
#### Post date: [May 9, 2020, 6:02pm UTC](https://swi-prolog.discourse.group/t/scheduling-optimization-problem-existing-systems-or-software/2274/13 "2020-05-09T18:02:23Z")
> [@EricGT](#):
>
> Why do you say that?
(I haven’t read the thesis in detail. Also, my experience with finite-domain solvers is that they’re great when they work but not so great in figuring out what constraints need to be relaxed to get to a solution. Also, debugging them can be … interesting.)