Precedence constraints using binary variables - DOCPLEX

Question

I would like to establish a precedence constraint to ensure the precedence relation of tasks. I have a set of tasks available, but required tasks are not always the same. It means, the tasks executed will depend of the demand.

When I searched for examples of precedence constraints in CPLEX/DOCPLEX and also OR-TOOLS, all examples I found use interval variables for establishing precedence constraints. In my case, I don't have interval variables, just binary ones.

I tried to implement the following precedence constraint:

  for t1 in required_tasks:
        for t2 in required_tasks:
            for w in range(1, len(task_cost) + 1):
                for j1 in range(1, number_tasks + 1):
                    for j2 in range(1, number_tasks + 1):
                        if j1 < j2:
                             if t2 in preced_task[t1]:
                                  opt_model.add(
                                        X[t1, w, j1] *
                                        precedence[t1, t2]
                                        >= X[t2, w, j2]
                                    )

Some definitions:

• X is a binary variable

• w is the worker index

• t1 and t2 are task indexes

• j1 and j2 are the positions of the tasks in the sequence

• preced_task is a dictionary containing the precedence relation.

Example: In this case, task 2 must be done after task 1, task 3 must be done after task 2. Task 1, 4, etc do not require any tasks before them.

preced_task = {1: [], 2: [1], 3: [2], 4: [], 5: [], 6: [], 7: []}

When I consider j1 and j2 in range(1, number_tasks + 1) it does not return a solution. However, if I consider j1 and j2 in range(2, number_tasks + 1) it returns a solution respecting precedence for one task (2, for example), but not for task 3.

Could someone help me with that?

Answer 1

After a while, I finally found a way to establish a precedence constraint using binary variables. It was hard to find examples of precedence constraints that do not use time as a parameter in both theoretical models and also code implementation tutorials.

Anyway, I am sharing here the code I used in DOCPLEX to establish the precedence constraint with binary variable without using time, but just process plan position as a parameter. I hope it will help other people dealing with similar problems.

for t1 in required_tasks:
    for t2 in required_tasks:
        for j2 in range(1, number_tasks + 1):
            opt_model.add(
                opt_model.sum(
                    X_var[t1, w1, j1]
                    for w1 in range(1, len(workers) + 1)
                    for j1 in range(1, j2)
                )
                 >= opt_model.sum(
                    X_var[t2, w2, j2] * precedence[t1,t2]
                    for w2 in range(1, len(workers) + 1)

                )
            )

PS: precedence is a dictionary showing the precedence relation between t1 and t2. If t1 must be done before t2, precedence[t1, t2] = 1, and 0 otherwise.