Google OR-Tools를 사용한 작업 스케줄링을위한 제약 프로그래밍

이전 게시물에서 선형 프로그래밍을위한 Google OR 도구를 이미 소개했습니다. 이 게시물에서는 제약 프로그래밍을위한 Google OR 도구의 기능을 보여주고 싶습니다. 보다 구체적으로 Google OR 도구로 제약 프로그래밍을 사용하여 작업 일정 문제를 해결합니다. 선형 프로그래밍과 달리 제약 프로그래밍은 임의 유형의 제약 함수를 허용합니다. 더욱이 제약 프로그래밍은 종종 최적의 솔루션이 아닌 실행 가능한 솔루션을 식별하는 데 중점을 둡니다. 즉, 제약 프로그래밍에서 해결되는 문제는 종종 최적화 할 목적 함수가 없을 수 있습니다. 작업 스케줄링은 제약 프로그래밍의 좋은 예입니다. 이 예에서 공장은 일주일 동안 작업 일정을 만들고자합니다. 교대 모델은 주 7 일 모두 3 교대를 허용하며 하루 24 시간 작동합니다. 공장에는 5 명의 노동자가 있습니다. 근로자는 주어진 날에 2 교대로 연속해서 일해서는 안됩니다. 또한 근로자 1 인당 교대조의 차이가 1 교대를 넘지 않아야합니다. 근무조는 한 명의 작업자에게만 할당 될 수 있습니다. 근로자는 같은 날 2 교대로 일해서는 안됩니다. 제약 프로그래밍에 Google OR 도구를 사용하여 아래 코드에서 실행 가능한 작업 일정을 찾습니다.

# Google 또는 도구 가져 오기 및 모델 템플릿 선언
from ortools.sat.python import cp_model
model = cp_model.CpModel()
# 근무 교대 근무일 조합에 대한 색인을 저장하는 데 사용할 빈 목록을 선언합니다.
shiftoptions = {}

# 일일 최대 일정뿐만 아니라 작업자 수, 날짜 및 일정 설정,
# 및 작업 자당 최대 교 대량 차이
workers = 5
shifts = 3
days = 7
maxshiftsperday = 1
maxdifference = 1

# 작업자, 근무조 및 요일의 각 조합에 대해 근무조 옵션 목록 인덱스로 튜플을 만듭니다.
# Google 또는 도구를 사용하여 주어진 작업자가 해당 근무일에 근무하는지 나타내는 부울 변수를 만듭니다.
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))

# 이제 우리는 한 명의 작업자에게만 할당되는 교대 제약을 추가합니다.
for y in range(days):
    for z in range(shifts):
        model.Add(sum(shiftoptions[(x, y, z)] for x in range(workers)) == 1)
# 이제 우리는 하루에 한 교대로 일하는 작업자의 제약을 추가합니다.
for x in range(workers):
    for y in range(days):
        model.Add(sum(shiftoptions[(x,y,z)] for z in range(shifts)) <= 1)
# 이제 우리는 최대 허용 차이로 허용되는 일부 편차와 함께 동일한 교 대량을 가진 모든 작업자의 제약 조건을 추가합니다.
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)

# 문제를 해결하기 전에 솔루션 프린터를 추가합니다 (이 코드는 Google 문서에서 직접 가져옴).
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

# 모델 해결
solver = cp_model.CpSolver()
solver.parameters.linearization_level = 0
# 해결하고 해결책이 타당한 지 확인
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

이것은 cp 솔버에 의해 식별 된 실행 가능한 작업 일정 중 하나 일 뿐이며,“최적”솔루션이 아닌 실행 가능한 솔루션을 검색하는 데 제약 조건 프로그래밍을 사용하는 방법의 예입니다. Python과 R 모두에서 최적화에 대한 일련의 게시물을 작성했습니다. R에서 lpSolve를 사용한 간단한 선형 최적화 R에서 lpSolve를 사용한 선형 정수 프로그래밍 R에서 lpSolve로 운송 문제 해결 Python에서 Pulp를 사용한 선형 최적화 Python에서 SciPy를 사용한 선형 최적화 R에서 nloptr을 사용한 비선형 최적화 Python에서 Google OR 도구를 사용한 간단한 선형 최적화 Google OR 도구의 추가 예제를 계속 다루겠습니다. 운송 네트워크의 라우팅 문제.