Begrænsnings-programmering til vagtplanlægning med Google OR-Tools

I tidligere indlæg har jeg allerede introduceret Google OR-tools til lineær programmering. I dette indlæg vil jeg demonstrere funktionerne i Google OR-tools til begrænsningsprogrammering. Mere specifikt vil jeg løse et jobplanlægningsproblem ved hjælp af begrænsningsprogrammering med Google OR-tools.

I modsætning til lineær programmering tillader begrænsningsprogrammering modelleringen af vilkårlige typer af begrænsningsfunktioner. Desuden fokuserer begrænsningsprogrammering ofte på at identificere en tilladt løsning snarere end en optimal løsning. Det vil sige: I begrænsningsprogrammering har modellen, som løses, ofte ikke en målfunktion.

Jobplanlægning er et godt eksempel på begrænsningsprogrammering. I dette eksempel ønsker en fabrik at lave en arbejdsplan for en uge. Vagtplanen giver mulighed for 3 vagter på alle ugens 7 dage, med 24 timers drift pr. dag.

# importer Google eller værktøjer og erklærer modelskabelon
from ortools.sat.python import cp_model
model = cp_model.CpModel()
# erklær en tom liste, der vil blive brugt til lagring af indekser til kombination af arbejdstager-skift-dag
shiftoptions = {}

# sæt antal arbejdstagere, dage og tidsplaner samt maksimale tidsplaner pr. dag,
# samt maks. forskydning i skift pr. arbejdstager
workers = 5
shifts = 3
days = 7
maxshiftsperday = 1
maxdifference = 1

# Opret en tuple som et listeindeks for skiftmuligheder for hver kombination af arbejdstager, skift og dag
# brug google eller værktøjer til at oprette en boolsk variabel, der angiver, om den givne arbejdstager arbejder den dag i det skift
for x in range(workers):
    for y in range(days):
        for z in range(shifts):
            shiftoptions[(x,y,z)] = model.NewBoolVar("shift with id" + str(x) + " " + str(y) + " " + str(z))

# nu tilføjer vi begrænsningen af skift, der kun tildeles en arbejdstager
for y in range(days):
    for z in range(shifts):
        model.Add(sum(shiftoptions[(x, y, z)] for x in range(workers)) == 1)
# nu tilføjer vi begrænsningen for, at en arbejdstager kun arbejder et skift om dagen
for x in range(workers):
    for y in range(days):
        model.Add(sum(shiftoptions[(x,y,z)] for z in range(shifts)) <= 1)
# nu tilføjer vi begrænsningen for alle arbejdere, der har samme antal skift, med nogle afvigelser tilladt med en maksimalt tilladt forskel
minshiftsperworker = (shifts * days) // workers
print(minshiftsperworker)
maxshiftsperworker = minshiftsperworker + maxdifference
for x in range(workers):
    shiftsassigned = 0
    for y in range(days):
        for z in range(shifts):
            shiftsassigned += shiftoptions[(x,y,z)]
    model.Add(minshiftsperworker <= shiftsassigned)
    model.Add(shiftsassigned <= maxshiftsperworker)

# før jeg løser problemet, tilføjer jeg en løsningsprinter (denne kode hentes direkte fra Googles dokumentation)
class SolutionPrinterClass(cp_model.CpSolverSolutionCallback):
    def __init__(self, shiftoptions, workers, days, shifts, sols):
        val = cp_model.CpSolverSolutionCallback.__init__(self)
        self._shiftoptions = shiftoptions
        self._workers = workers
        self._days = days
        self._shifts = shifts
        self._solutions = set(sols)
        self._solution_count = 0
    def on_solution_callback(self):
        if self._solution_count in self._solutions:
            print("solution " + str(self._solution_count))
            for y in range(self._days):
                print("day " + str(y))
                for x in range(self._workers):
                    is_working = False
                    for z in range(self._shifts):
                        if self.Value(self._shiftoptions[(x,y,z)]):
                            is_working = True
                            print("worker " +str(x) +" works day " + str(y) +" shift " + str(z))
                    if not is_working:
                        print('  Worker {} does not work'.format(x))
            print()
        self._solution_count += 1
    def solution_count(self):
        return self._solution_count

# løs problemet
solver = cp_model.CpSolver()
solver.parameters.linearization_level = 0
# løs det og kontroller, om løsningen var mulig
solutionrange = range(1) # we want to display 1 feasible results (the first one in the feasible set)
solution_printer = SolutionPrinterClass(shiftoptions, workers,
                                        days, shifts, solutionrange)
solver.SearchForAllSolutions(model, solution_printer)

4
solution 0
day 0
  Worker 0 does not work
worker 1 works day 0 shift 0
  Worker 2 does not work
worker 3 works day 0 shift 2
worker 4 works day 0 shift 1
day 1
  Worker 0 does not work
  Worker 1 does not work
worker 2 works day 1 shift 0
worker 3 works day 1 shift 2
worker 4 works day 1 shift 1
day 2
  Worker 0 does not work
  Worker 1 does not work
worker 2 works day 2 shift 0
worker 3 works day 2 shift 1
worker 4 works day 2 shift 2
day 3
worker 0 works day 3 shift 2
  Worker 1 does not work
  Worker 2 does not work
worker 3 works day 3 shift 1
worker 4 works day 3 shift 0
day 4
worker 0 works day 4 shift 0
worker 1 works day 4 shift 2
worker 2 works day 4 shift 1
  Worker 3 does not work
  Worker 4 does not work
day 5
worker 0 works day 5 shift 0
worker 1 works day 5 shift 1
worker 2 works day 5 shift 2
  Worker 3 does not work
  Worker 4 does not work
day 6
worker 0 works day 6 shift 1
worker 1 works day 6 shift 2
worker 2 works day 6 shift 0
  Worker 3 does not work
  Worker 4 does not work

Dette var blot én af de gennemførlige arbejdsplaner som blev identificeret af cp-løseren. Og det er et eksempel på, hvordan begrænsningsprogrammering kan bruges til at søge efter mulige løsninger snarere end “optimale” løsninger.

Jeg har skrevet en række indlæg om optimering i både Python og R, der f.eks. dækker: