Einschränkungs-programmierung für die Arbeitsplanung mit Google OR-Tools

In früheren Beiträgen habe ich bereits Google OR-Tools für die lineare Programmierung eingeführt. In diesem Beitrag möchte ich die Funktionen von Google OR-Tools für die Einschränkungsprogrammierung demonstrieren. Insbesondere werde ich ein Problem bei der Auftragsplanung mithilfe der Einschränkungsprogrammierung unter Verwendung von Google OR-Tools lösen.

Im Gegensatz zur linearen Programmierung ermöglicht die Einschränkungsprogrammierung beliebige Arten von Einschränkungsfunktionen. Darüber hinaus konzentriert sich die Einschränkungsprogrammierung häufig darauf, eine realisierbare Lösung zu finden und nicht auf optimale Lösungen. Das heißt: Bei der Einschränkungsprogrammierung hat das zu lösende Problem häufig keine zu optimierende Zielfunktion.

Die Auftragsplanung ist ein gutes Beispiel für die Einschränkungsprogrammierung. In diesem Beispiel möchte ich in einer Fabrik einen Arbeitsplan für eine Woche erstellen. Das Schichtmodell ermöglicht 3 Schichten an allen 7 Tagen der Woche mit einem 24-Stunden-Betrieb pro Tag.

Die Fabrik hat 5 Arbeiter. Ein Arbeiter sollte an einem bestimmten Tag nicht zwei Schichten hintereinander arbeiten. Außerdem sollte der Unterschied in der Anzahl der Schichten pro Arbeitnehmer 1 Schicht nicht überschreiten.

Eine Schicht kann nur einem Arbeiter zugewiesen werden.

Ein Arbeiter sollte nicht zwei Schichten am selben Tag arbeiten.

Mit Google OR-Tools für die Einschränkungsprogrammierung finde ich im folgenden Code einen realisierbaren Arbeitsplan:

# Google oder Tools importieren und Modellvorlage deklarieren
from ortools.sat.python import cp_model
model = cp_model.CpModel()
# deklarieren Sie eine leere Liste, die zum Speichern von Indizes für die Kombination aus Arbeiter und Schichttag verwendet wird
shiftoptions = {}

# Anzahl der Arbeiter, Tage und Zeitpläne sowie maximale Zeitpläne pro Tag festlegen,
# sowie maximale Schichtbetragdifferenz pro Arbeiter
workers = 5
shifts = 3
days = 7
maxshiftsperday = 1
maxdifference = 1

# Erstellen Sie ein Tupel als Index für die Liste der Schichtoptionen für jede Kombination aus Arbeiter, Schicht und Tag
# Verwenden Sie Google oder Tools, um eine boolesche Variable zu erstellen, die angibt, ob ein bestimmter Mitarbeiter an diesem Tag in dieser Schicht arbeitet
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))

# Jetzt fügen wir die Einschränkung hinzu, dass die Schicht nur einem Mitarbeiter zugewiesen wird
for y in range(days):
    for z in range(shifts):
        model.Add(sum(shiftoptions[(x, y, z)] for x in range(workers)) == 1)
# Jetzt fügen wir die Einschränkung hinzu, dass ein Arbeiter nur eine Schicht pro Tag arbeitet
for x in range(workers):
    for y in range(days):
        model.Add(sum(shiftoptions[(x,y,z)] for z in range(shifts)) <= 1)
# Jetzt fügen wir die Einschränkung hinzu, dass alle Arbeitnehmer die gleiche Anzahl von Schichten haben, wobei einige Abweichungen mit einer maximal zulässigen Differenz zulässig sind
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)

# Bevor ich das Problem löse, füge ich einen Lösungsdrucker hinzu (dieser Code stammt direkt aus der Google-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öse das Modell
solver = cp_model.CpSolver()
solver.parameters.linearization_level = 0
# Lösen Sie es und prüfen Sie, ob eine Lösung möglich war
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

Dies war nur einer der realisierbaren Arbeitspläne, die vom cp-Solver identifiziert wurden, und ein Beispiel dafür, wie die Cosntraint-Programmierung für die Suche nach realisierbaren Lösungen anstelle von „optimalen“ Lösungen verwendet werden kann.

Ich werde weitere Beispiele in Google OR-Tools behandeln, z. für Routingprobleme in Transportnetzen.