# Scheduling optimization problem, existing systems or software?

I hope it’s okay to cross-post 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:

• project activities, rated 1-10 in terms of priority
• people associated with each project activity
• those people’s transportation options (car, public)
• equipment needed for each activity, labeled by name
• schedule for such activities during the week (some activities have a prescribed timing each day)
• site map - a geometric schematic of the rooms of work area, and the equipment placed in the correct rooms (include bathroom)
• location of people’s home desks/workstations in the site(s)
• specific personal constraints on when each person can’t be onsite.
2. Classes of information for the constraints, input by the user at the beginning of a run:

• limit on # of people onsite at any one time (the smaller the better)
• limit on hours site can be open (the fewer the better)
• how many hours of empty time between shifts (the greater the better)
• max distance allowable between people as they work (the greater the better)
• no. of people allowed passing in a hallway at any one time (the fewer the better)
3. General constants

• speed of people walking

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

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

which solves a similar variation using constraint satisfaction and notes that it was done with the help of Markus Triska. 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.

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.

Oh awesome, that could be just the thing, eh? It links to Nurse Scheduling using Constraint Logic Programming which looks relevant.

I had a hunch Markus Triska would enter into the picture at some point…

1 Like

Thanks for noting the paper (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.

Ah, well.

I figured Prolog was the right tool for the job.

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.

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.

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.

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

Also this thesis, which uses CLP(FD) I think: https://www.metalevel.at/mst.pdf

2 Likes

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