利用Google OR-Tools进行工作安排的约束编程。

在之前的文章中，我已经介绍了Google OR工具用于线性编程。在这篇文章中，我想展示Google OR工具在约束编程方面的能力。更具体地说，我将使用约束编程与Google OR工具解决一个作业调度问题。

与线性编程不同，约束编程允许使用任意类型的约束函数。此外，约束编程通常侧重于确定一个可行的解，而不是最优的解。也就是说，在约束编程中，正在解决的问题可能经常没有目标函数需要优化。

作业调度是约束性编程的一个很好的例子。在这个例子中，一个工厂想制定一个星期的工作计划。轮班模型允许一周7天3班倒，每天24小时工作。

该工厂有5名工人。一个工人不应该在某一天连续上2班。同时，每个工人的班次相差不能超过1班。

一个班只能分配给一个工人。

一个工人不应该在同一天上两班。

使用谷歌OR工具进行约束编程，我在下面的代码中找到了一个可行的工作时间表。

#导入谷歌或工具，并声明模型模板。
from ortools.sat.python import cp_model
model = cp_model.CpModel()
#声明空列表，用于存储工人-班-日组合的指数。
shiftoptions = {}

设置工人数量、天数和时间表，以及每天的最大时间表。
＃以及每个工人的最大班次差额
workers = 5
shifts = 3
days = 7
maxshiftsperday = 1
maxdifference = 1

# 为每个工人、班次和日期的组合创建一个元组作为班次选项列表索引。
# 使用谷歌或工具创建一个布尔变量，表明如果给定的工人在当天工作，在该班次
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) #我们要显示1个可行的 
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求解器确定的可行工作计划之一，也是cosntraint编程如何用于搜索可行解而非 “最优 “解的一个例子。

我已经写了一系列关于Python和R的优化的文章，包括例如。

在R中使用lpSolve进行简单的线性优化
在R中使用lpSolve进行线性整数编程。
在R中用lpSolve解决运输问题。
在Python中使用Pulp进行线性优化
在Python中使用SciPy进行线性优化
在R中使用nloptr进行非线性优化。
在Python中使用Google OR-tools进行简单的线性优化。

我将继续在Google OR-tools中介绍更多的例子，例如用于交通网络中的路由问题。