问题

我希望你今天过得很愉快。

当我尝试使用Google OR-Tools编写CP-SAT来实现调度中的序列依赖设置时间时，我找不到以布尔变量形式表示两个区间之间的优先关系的方法。例如，如果作业1直接在作业2之前（作业1 -> 作业2），我想将布尔变量强制为1。原因是，使用二进制变量（命名为lit），我想添加一个考虑序列依赖设置时间的约束，如下所示。

model.Add(start_vars[m][j2] >= end_vars[m][j1] + setup_matrix[m][j1[j2]).OnlyEnforceIf(lit)

区间定义如下：

processing_itv_vars = [
    [model.NewOptionalIntervalVar(start=start_vars[m][j], end=end_vars[m][j], size=processingTimes[m][j], is_present=presence_vars[m][j], name="interval_machine{}_job{}".format(m, j))
     for j in jobs] for m in machines]

我将其声明为可选区间变量，因为我现在正在考虑并行机器调度问题，其中作业可以由任何机器处理。

是否有一种方法可以将两个区间之间的优先关系表示为布尔变量？

供您参考，我附上了完整的代码如下：

def cp_scheduling_ortools(prob:Instance):
    jobs = [*range(0, prob.numJob)]
    machines = [*range(0, prob.numMch)]
    setup_matrix = prob.setup
    processingTimes = prob.ptime
    H = 100000

    model = cp_model.CpModel()
    presence_vars = [[model.NewBoolVar(name="presence_machine{}_job{}".format(m, j)) for j in jobs] for m in machines]
    start_vars = [[model.NewIntVar(0, H, name="start_machine{}_job{}".format(m, j)) for j in jobs] for m in machines]
    end_vars = [[model.NewIntVar(0, H, name="end_machine{}_job{}".format(m, j)) for j in jobs] for m in machines]
    processing_itv_vars = [
        [model.NewOptionalIntervalVar(start=start_vars[m][j], end=end_vars[m][j], size=processingTimes[m][j], is_present=presence_vars[m][j], name="interval_machine{}_job{}".format(m, j))
         for j in jobs] for m in machines]
    for m in machines:
        model.AddNoOverlap(processing_itv_vars[m])

    presence_lit = [[[model.NewBoolVar('%i and %i in %i' % (j1, j2, m)) for j2 in jobs] for j1 in jobs] for m in machines]
    precedence = [[[model.NewBoolVar('%i -> %i in %i' % (j1, j2, m)) for j2 in jobs] for j1 in jobs] for m in machines]
    for m in machines:
        for j1 in jobs:
            for j2 in jobs:
                if j1 != j2:
                    lit = ?
                    model.Add(start_vars[m][j2] >= end_vars[m][j1] + setup_matrix[m][j1][j2]).OnlyEnforceIf(lit)

    for j in jobs:
        alt_intvs = []
        for m in machines:
            alt_intvs.append(presence_vars[m][j])
        model.Add(cp_model.LinearExpr.Sum(alt_intvs) == 1)

    objective = cp_model.LinearExpr.Sum([end_vars[m][j] for j in jobs for m in machines])
    model.Minimize(objective)

    solver = cp_model.CpSolver()

    # solver.parameters.enumerate_all_solutions = True
    solver.parameters.log_search_progress = True
    status = solver.Solve(model)

    for m in machines:
        for j in jobs:
            if solver.Value(presence_vars[m][j]) == 1:
                print('%i in %i, from %i to %i (ptime: %i)' % (j, m, solver.Value(start_vars[m][j]), solver.Value(end_vars[m][j]), processingTimes[m][j]))

提前感谢您，祝您愉快。


<details>
<summary>英文:</summary>

I hope you are having a great day.

When I tried to code CP-SAT by using Google OR-Tools for implementing sequence-dependent setup times in scheduling, I couldn&#39;t find the way to present the precedence between two intervals as a boolean variable. For example, if Job 1 precedes Job 2 directly (Job 1 -&gt; Job 2), I would like to force a boolean variable into 1. The reason is that, with the binary variable (named lit), I want to add a constraint for considering sequence-dependent setup time as shown below.

    model.Add(start_vars[m][j2] &gt;= end_vars[m][j1] + setup_matrix[m][j1[j2]).OnlyEnforceIf(lit)

The intervals are defined as follows:

    processing_itv_vars = [
        [model.NewOptionalIntervalVar(start=start_vars[m][j], end=end_vars[m][j], size=processingTimes[m][j], is_present=presence_vars[m][j], name=&quot;interval_machine{}_job{}&quot;.format(m, j))
         for j in jobs] for m in machines]

I declared it as an optional interval variable because I am now considering parallel machine scheduling problem that a job can be processed by any machine.

Is there any way to present a precedence between two intervals as a boolean variable&gt;

For your information, I have attached a full code as shown below.

    def cp_scheduling_ortools(prob:Instance):
    jobs = [*range(0, prob.numJob)]
    machines = [*range(0, prob.numMch)]
    setup_matrix = prob.setup
    processingTimes = prob.ptime
    H = 100000

    model = cp_model.CpModel()
    presence_vars = [[model.NewBoolVar(name=&quot;presence_machine{}_job{}&quot;.format(m, j)) for j in jobs] for m in machines]
    start_vars = [[model.NewIntVar(0, H, name=&quot;start_machine{}_job{}&quot;.format(m, j)) for j in jobs] for m in machines]
    end_vars = [[model.NewIntVar(0, H, name=&quot;end_machine{}_job{}&quot;.format(m, j)) for j in jobs] for m in machines]
    processing_itv_vars = [
        [model.NewOptionalIntervalVar(start=start_vars[m][j], end=end_vars[m][j], size=processingTimes[m][j], is_present=presence_vars[m][j], name=&quot;interval_machine{}_job{}&quot;.format(m, j))
         for j in jobs] for m in machines]
    for m in machines:
        model.AddNoOverlap(processing_itv_vars[m])

    presence_lit = [[[model.NewBoolVar(&#39;%i and %i in %i&#39; % (j1, j2, m)) for j2 in jobs] for j1 in jobs] for m in machines]
    precedence = [[[model.NewBoolVar(&#39;%i -&gt; %i in %i&#39; % (j1, j2, m)) for j2 in jobs] for j1 in jobs] for m in machines]
    for m in machines:
        for j1 in jobs:
            for j2 in jobs:
                if j1 != j2:
                    lit = ?
                    model.Add(start_vars[m][j2] &gt;= end_vars[m][j1] + setup_matrix[m][j1][j2]).OnlyEnforceIf(lit)

    for j in jobs:
        alt_intvs = []
        for m in machines:
            alt_intvs.append(presence_vars[m][j])
        model.Add(cp_model.LinearExpr.Sum(alt_intvs) == 1)

    objective = cp_model.LinearExpr.Sum([end_vars[m][j] for j in jobs for m in machines])
    model.Minimize(objective)

    solver = cp_model.CpSolver()

    # solver.parameters.enumerate_all_solutions = True
    solver.parameters.log_search_progress = True
    status = solver.Solve(model)

    for m in machines:
        for j in jobs:
            if solver.Value(presence_vars[m][j]) == 1:
                print(&#39;%i in %i, from %i to %i (ptime: %i)&#39; % (j, m, solver.Value(start_vars[m][j]), solver.Value(end_vars[m][j]), processingTimes[m][j]))

Thank you in advance and have a nice day.




</details>


# 答案1
**得分**: 2

你将需要两个布尔变量，因为时间间隔可以不存在或存在。

通常的技巧如下：

布尔变量 a_before_b
model.Add(start(b) >= end(a)).OnlyEnforceIf(a_before_b, present(a), present(b))

布尔变量 b_before_a
model.Add(start(a) >= end(b)).OnlyEnforceIf(b_before_a, present(a), present(b))

model.AddBoolOr(a_before_b, b_before_a, present(a).Not(), present(b).Not())

<details>
<summary>英文:</summary>

You will need two bool_vars as the intervals can be absent/present.

The usual trick is the following:

bool_var a_before_b
model.Add(start(b) &gt;= end(a)).OnlyEnforceIf(a_before_b, present(a), present(b))

bool_var b_before_a
model.Add(start(a) &gt;= end(b)).OnlyEnforceIf(b_before_a, present(a), present(b))

model.AddBoolOr(a_before_b, b_before_a, present(a).Not(), present(b).Not())

</details>