OR-Tools Cost Function Integration

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)

• "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$? Mar 21 at 7:20
• @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? Mar 21 at 7:33

1 Answer

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.