5
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – A.Omidi
    Nov 28, 2019 at 14:48
  • $\begingroup$ 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. $\endgroup$
    – EhsanK
    Nov 28, 2019 at 15:56
  • $\begingroup$ @A.Omidi, thanks for replying. I took a look at the references you suggested me in another post (or.stackexchange.com/questions/3055/…), but I was looking for some code examples. In the tutorial of Philippe Laborie he used interval variables to establish precedence constraints... $\endgroup$
    – campioni
    Dec 1, 2019 at 13:41
  • $\begingroup$ @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. $\endgroup$
    – campioni
    Dec 1, 2019 at 13:42
  • $\begingroup$ @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. $\endgroup$
    – EhsanK
    Dec 1, 2019 at 14:56

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.