2
$\begingroup$

I am modeling a problem similar to the job shop problem (tasks with start times, duration, and predecessors) and my objective is to minimize the makespan, with Python and OR-Tools.

start[i] is an integer decision variable that shows the period when task $i$ starts

start[1] = 3 $\Rightarrow$ task 1 starts on period 3

duration[i] is a parameter that is the task $i$ duration (and is known)

duration [1] = 2 $\Rightarrow$ task 1 takes 2 period to be completed

Now I want to integrate a cost function where if a task $i$ starts on a specific period and ends on period start[i]+duration[i], the cost will be the sum of every period it's being worked on.

I have a cost matrix:

Cost[i,j] = [[ 1, 2, 3, 6, 8], 
             [5, 6, 7, 2, 1]]

cost[1,1] is the cost for task 1 if it's being worked on during period 1

So if task 1 has a duration of 2, and starts on period 1, then periods 1,2,3 will be the target periods, and the cost will be cost[1,1]+cost[1,2]+cost[1,3] = 1+2+3 from the cost matrix.

I tried creating a binary matrix BIN[i,start[i]:start[i]+duration[i]] that uses start[i] and duration[i] and returns a style matrix, where 1 if the task is in progress and 0 if not, so then I can pass the cost[i,j] and find the total cost for a scenario.

total_cost = model.NewIntVar(0,99999,'total_cost')
b = model.newboolvar('b')
    for i in range(alltasks):
        model.Add(start[i] != 0).OnlyEnforceIf(b)
        model.Add(start[i] == 0).OnlyEnforceIf(b.Not())

        model.Add(total_cost == sum(Cost*b)).OnlyEnforceIf(b)
        model.Add(total_cost == 0).OnlyEnforceIf(b.Not()) 

But that doesn't work at all...

If it can help in the understanding: My goal is to make the model choose the best period to start/end on a period knowing the duration is fixed and there is a cost to each period that this task will be worked on (so to reduce the cost)

$\endgroup$
2
  • $\begingroup$ "So if task 1 has a duration of 2, and starts on period 1, then periods 1,2,3 will be the target periods, and the cost will be cost[1,1]+cost[1,2]+cost[1,3] = 1+2+3 from the cost matrix.": since the duration is constant, couldn't you pre-compute $c_{jt}$ the total cost of task $j$ when starting at time $t$? $\endgroup$
    – fontanf
    Mar 21, 2022 at 7:20
  • 1
    $\begingroup$ @aczi0, welcome to OR.SE. Would you please, how do you calculate the cost function as long as it needs to solve the problem to determine the start/compilation time of each task? $\endgroup$
    – A.Omidi
    Mar 21, 2022 at 7:33

1 Answer 1

1
$\begingroup$

If the duration is fixed, then the cost is only a function of the start.

I recommend looking at this code sample on how to encode a step function. You can also just use an Element constraint.

$\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.