DueDate objective CP SAT

Rick Tielen

unread,

Jul 7, 2021, 8:13:32 AM7/7/21

to or-tools-discuss

Hi all,

I am using the CP SAT solver to optimize my job shop scheduling problem. I added an extra input in the jobs_data which contains the due date of the job just as in https://github.com/google/or-tools/issues/2352. In this example the deadline is set as an constraint.

I've read that it is not possible for the CP SAT solver to solve for 2 objectives. And that it is better to first solve for 1 objective and give this solution as a hint. For the first solver I want to minimize the lateness of orders (deadline - end) as an objective instead of the makespan objective. I've already searched the internet for similar problems but have not found a solution yet. My knowledge on the CP SAT solver is not enough to come with a solution. I've tried something as given below, without result...

# DueDate objective.

obj_var = model.NewIntVar(0, horizon, 'dueDate')

model.AddMaxEquality(obj_var, [all_tasks[job_id, len(job) - 1].deadline - all_tasks[job_id, len(job) - 1].end for job_id, job in enumerate(jobs_data)])

Help would be appreciated!

Laurent Perron

unread,

Jul 7, 2021, 8:26:27 AM7/7/21

to or-tools-discuss

AddMaxEquality() expects an array of variables, not an array of expressions. Please create intermediate variables for each .all_tasks[job_id, len(job) - 1].deadline - all_tasks[job_id, len(job) - 1].end.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/ce60ce6c-d186-4039-8590-b44d2eb43537n%40googlegroups.com.

Message has been deleted

Priidik Vilumaa

unread,

Jul 8, 2021, 10:00:31 AM7/8/21

to or-tools...@googlegroups.com

Skimmed through and not tested, but should work:

1.

intArr = []

for job_id, job in enumerate(jobs_data):

new_var = model.NewIntVar(all_tasks[job_id, len(job) - 1].end - all_tasks[job_id, len(job) - 1].deadline)

intArr.append(new_var)

# now intArr contains variables not expressions (multiple variables with some operations between them)

2.1 This is a Python thing, tuples can't be changed after creation. Up to you to find a workaround.

2.2 You are attempting to get values of variables before they are being calculated by the solver. You should do

lateness_var = model.NewIntVar(........)

model.Add(lateness_var == end_var - deadline_var)

Best,

Priidik

On Thu, Jul 8, 2021 at 12:47 PM Rick Tielen <tiele...@gmail.com> wrote:

Hi Laurent,

Thank for your response. I indeed see that AddMaxEquality() expects an array of variables.

I don't know if I am asking stupid questions, but I really don't know how to implement this. I've tried several 'solutions'.

1: By creating the array called intArr which will serve as an input for the AddMaxEquality.
# DueDate objective.
obj_var = model.NewIntVar(0, 100000, 'dueDate')
intArr = [all_tasks[job_id, len(job) - 1].end - all_tasks[job_id, len(job) - 1].deadline for job_id, job in enumerate(jobs_data)]
print(intArr)
model.AddMaxEquality(obj_var, intArr)
When I print intArr i get an array which contains SumArray(end_0_1(0..10151), ProductCst(deadline_0_1(28800), -1), 0)
When I do the same thing without the enumeration i get: (end_49_0 + -deadline_49_0)

2.1 : Adding a lateness_var
for job_id, job in enumerate(jobs_data):
for task_id, task in enumerate(job):
machine = task[0]
duration = task[1]
deadline = task[2]
suffix = '_%i_%i' % (job_id, task_id)
start_var = model.NewIntVar(0, horizon, 'start' + suffix)
end_var = model.NewIntVar(0, horizon, 'end' + suffix)
interval_var = model.NewIntervalVar(start_var, duration, end_var,
'interval' + suffix)
deadline_var = model.NewIntVar(deadline, deadline,
'deadline' + suffix)
lateness_var = model.NewIntVar(0, 100000,
'lateness' + suffix)
all_tasks[job_id, task_id] = task_type(start=start_var,
end=end_var, deadline=deadline_var,
interval=interval_var, lateness=lateness_var)
machine_to_intervals[machine].append(interval_var)

And trying to calculate the lateness using:

all_tasks[job_id, len(job) - 1].lateness = all_tasks[job_id, len(job) - 1].end - all_tasks[job_id, len(job) - 1].deadline

This gives AttributeError: can't set attribute

2.2: Adding a lateness_var
for job_id, job in enumerate(jobs_data):
for task_id, task in enumerate(job):
machine = task[0]
duration = task[1]
deadline = task[2]
suffix = '_%i_%i' % (job_id, task_id)
start_var = model.NewIntVar(0, horizon, 'start' + suffix)
end_var = model.NewIntVar(0, horizon, 'end' + suffix)
interval_var = model.NewIntervalVar(start_var, duration, end_var,
'interval' + suffix)
deadline_var = model.NewIntVar(deadline, deadline,
'deadline' + suffix)
#lateness_var = model.NewIntVar(0, 100000, 'lateness' + suffix)
lateness_var = end_var - deadline_var
all_tasks[job_id, task_id] = task_type(start=start_var,
end=end_var, deadline=deadline_var,
interval=interval_var, lateness=lateness_var)
machine_to_intervals[machine].append(interval_var)

This gives TypeError: NotSupported: model.GetOrMakeIndex((end_0_1 + -deadline_0_1))

I've tried more than this but still did not come up to a working solution. Help would be appreciated again.

Op woensdag 7 juli 2021 om 14:26:27 UTC+2 schreef Laurent Perron:

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/1cf9a98e-2d7a-4e3f-8648-56e118ae25f1n%40googlegroups.com.

Laurent Perron

unread,

Jul 8, 2021, 11:24:16 AM7/8/21

to or-tools-discuss

Model.NewIntVar has signature (lb, ub, name)

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CAN-_P7ct6MCsbcxjgLH9DLwsj9bMdr1k_3YxifFO3UPxZa2S6g%40mail.gmail.com.

Priidik Vilumaa

unread,

Jul 8, 2021, 3:50:17 PM7/8/21

to or-tools...@googlegroups.com

Correct, my bad. So I believe the following should work in point 1:

1.

intArr = []

for job_id, job in enumerate(jobs_data):

new_var = model.NewIntVar(0,99999999,'')

model.Add(all_tasks[job_id, len(job) - 1].end - all_tasks[job_id, len(job) - 1].deadline==new_var)

intArr.append(new_var)

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/CABcmEea1k9DQ6YfOY7YxLHNx1Wj9scbUChBkoP31Zvb095bACQ%40mail.gmail.com.

Islem Benmahammed

unread,

Jul 9, 2021, 3:33:27 PM7/9/21

to or-tools-discuss

Hello,

You can do that as folowing :

The aim is to minimize the time (absolute value) between the due date (idx_date) and the start of each task.

diff_time = self._model.NewIntVar(0, 300, "{}_diff_time".format(order_id))

model.Add(diff_time >= -(start_master_task - idx_date))

model.Add(diff_time >= start_master_task - idx_date)

...

objectifs.append(LinearExpr.Sum([i for i in self._diff_time.values()]))

...

and then minimize objectifs :

model.Minimize(LinearExpr.Sum(self._objectifs))

You can find more information about scheduling using or tools in this article :

Scheduling optimization in blending plants

blind.line

unread,

Jul 10, 2021, 1:42:52 AM7/10/21

to or-tools...@googlegroups.com

Nice writeup!

James

On Jul 9, 2021, at 12:33, Islem Benmahammed <benmaham...@gmail.com> wrote:

Hello,

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/9b6c7358-e3d6-4809-bb67-935bd42c2b7cn%40googlegroups.com.

Rick Tielen

unread,

Jul 14, 2021, 11:52:09 AM7/14/21

to or-tools-discuss

Hi all,

Thanks for the replies. After the answer of Laurent I've implemented different objectives which can be seen below:

# Objectives

latenessAllJobs = [model.NewIntVar(0, 500000, 'lateness_%i' % i) for i in range(len(jobs_data))]

cycleTimeAllJobs = [model.NewIntVar(0, 500000, 'cycleTime_%i' % i) for i in range(len(jobs_data))]

costAllJobs = [model.NewIntVar(0, 500000, 'cost_%i' % i) for i in range(len(jobs_data))]

startAllJobs = [all_tasks[job_id, 0].start for job_id, job in enumerate(jobs_data)]

endAllJobs = [all_tasks[job_id, len(job) - 1].end for job_id, job in enumerate(jobs_data)]

deadlineAllJobs = [all_tasks[job_id, len(job) - 1].deadline for job_id, job in enumerate(jobs_data)]

for i in range(len(jobs_data)):

latenessJob = model.NewIntVar(0,500000,"latenessJob")

model.Add(latenessJob == endAllJobs[i] - deadlineAllJobs[i])

model.AddAbsEquality(latenessAllJobs[i], latenessJob)

cycleTimeJob = model.NewIntVar(0,500000,"cycleTimeJob")

model.Add(cycleTimeJob == endAllJobs[i] - 0)#startAllJobs[i])

model.AddAbsEquality(cycleTimeAllJobs[i], cycleTimeJob)

costJob = model.NewIntVar(0,500000,"costJob")

model.Add(costJob == cycleTimeAllJobs[i] + latenessAllJobs[i])

model.AddAbsEquality(costAllJobs[i], costJob)

model.Minimize(sum(cycleTimeAllJobs))

I can easily change the input for the Minimize function.

However, I have a new question regarding the job shop problem. Currently I am updating my model with machine availability. Therefore I used the Job shop with maintenance from Laurent (https://github.com/google/or-tools/blob/master/examples/python/jobshop_with_maintenance_sat.py). I want jobs to be able to end processing in the evening and start processing in the morning again. For this I have implemented job splitting which I found via (https://groups.google.com/g/or-tools-discuss/c/KMK8ywapy2A/m/oj6Hcg_sAAAJ and https://groups.google.com/g/or-tools-discuss/c/DA_4Pniwhn8/m/moLYiJpWAgAJ) Again great thanks to Laurent!

The problem that arises is that e.g. machine A starts processing Job 1, then processes Job 2 and then continues with Job 1 again. I have to implement a certain constraint that makes sure that no other job can interrupt between operations of the same job. Only an Interval can occure between two operations of the same job. However, then the problem that arises is that if a job needs to go from Machine A to Machine B to Machine A there is no processing of jobs allowed when the job is at machine B. How can we solve this?

Should I open a new chat for this or can we continue on this chat?

Thanks in advance!

Op zaterdag 10 juli 2021 om 07:42:52 UTC+2 schreef blind.lin...@gmail.com:

Reply all

Reply to author

Forward