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?

Would you see the resources-constraint project schedule or other related scheduling problem such as flowshop? They contain task precedence constraints (using binary variables) which you could benchmark. — A.Omidi, Nov 28 '19 at 14:48
Your preced_task keys are (1, 2, ..) and I assume X index starts from 0. Are you sure then you're correctly indexing X? Also, this is just a suggestion about implementing your constraint. You have 5 loops and you only have a handful of values in preced_task. So, I suggest changing the order of your loops. Loop over your preced_task which gives you only those keys and values that you need and then for the desired j1 and j2 indices coming from preced_task, you can create your constraint. — EhsanK, Nov 28 '19 at 15:56
@A.Omidi, thanks for replying. I took a look at the references you suggested me in another post (https://or.stackexchange.com/questions/3055/scheduling-with-transition-costs-docplex/3064#3064), but I was looking for some code examples. In the tutorial of Philippe Laborie he used interval variables to establish precedence constraints... — campioni, Dec 01 '19 at 13:41
@EhsanK I'm not sure I understood your answer. X is a decision variable and its index is based on t, w and j. All of them start from 1. — campioni, Dec 01 '19 at 13:42
@campioni I didn't know how you defined x. That was just a check to make sure the index problem is not coming from x being defined on a different range. Anyway, it seems you figured out a solution. — EhsanK, Dec 01 '19 at 14:56

campioni · Accepted Answer · 2019-12-01T14:13:45.443

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.

Precedence constraints using binary variables - DOCPLEX

1 Answers1