Scheduling optimization problem, existing systems or software?

Help! Algorithm
1

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

2

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.

3

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.

4

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… :slight_smile:

1 Like
5

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.

6

Ah, well.

I figured Prolog was the right tool for the job.

7

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.

8

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
SWI-Prolog reporting wrong answer with bitshifts CLPFD
Hints to understand splendid program to solve Queens

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.

9

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

10

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

2 Likes
11

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
12

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.)

13

(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.)