If you need any additional materials, please let me know.
Original Message:
Sent: Tue April 30, 2024 03:08 AM
From: Abbas Omidi
Subject: How to define an JIT objective besides Cmax
Dear Carlos,
Many thanks for your comments and insightful ideas. I have done what you proposed and I have encountered some issues.
1) As the first attempt, I added the new auxiliary variables into the model and then added the three constraints w.r.t the early/tardy part.
# The objective partmdl.add( mdl.minimize( mdl.sum( E[j] + T[j] + mdl.max([mdl.end_of(task_itv_vars[j])]) for j in range(len(p_time)) ) ))# The new constraintsfor j in range(len(p_time)): mdl.add(E[j] >= d_time[j] - (mdl.start_of(task_itv_vars[j]) + p_time[j])) mdl.add(T[j] >= (mdl.start_of(task_itv_vars[j]) + p_time[j]) - d_time[j]) (mdl.start_of(task_itv_vars[j]) + p_time[j]) + E[j] - T[j] == d_time[j]
In this way, the output shows that:
Model: parallel_Machine_Scheduling - source file: <ipython-input-3-314840e9531e> - modeling time: 24.25 sec - number of integer variables: 20 - number of interval variables: 50 - number of sequence variables: 4 - number of state functions: 0 - number of float variables: 0 - number of constraints: 49 - number of root expressions: 49 - number of expression nodes: 300 - operations: alternative: 10, endBeforeStart: 4, endOf: 10, greaterOrEqual: 30, minimize: 1, minus: 20, noOverlap: 4, plus: 40, startOf: 30, sum: 1 ! --------------------------------------------------- CP Optimizer 20.1.0.0 -- ! Minimization problem - 74 variables, 48 constraints ! Initial process time : 0.01s (0.01s extraction + 0.01s propagation) ! . Log search space : 1113.2 (before), 1113.2 (after) ! . Memory usage : 641.0 kB (before), 641.0 kB (after) ! Using parallel search with 8 workers. ! ---------------------------------------------------------------------------- ! Best Branches Non-fixed W Branch decision ! Using temporal relaxation. 0 74 1 - + New bound is 524 * 524 28 0.04s 1 (gap is 0.00%) ! ---------------------------------------------------------------------------- ! Search completed, 1 solution found. ! Best objective : 524 (optimal - effective tol. is 0) ! Best bound : 524 ! ---------------------------------------------------------------------------- ! Number of branches : 180 ! Number of fails : 72 ! Total memory usage : 5.2 MB (5.2 MB CP Optimizer + 0.1 MB Concert) ! Time spent in solve : 0.04s (0.04s engine + 0.01s extraction) ! Search speed (br. / s) : 5454.5 ! ----------------------------------------------------------------------------Optimal solution found with objective 524.
As the second attempt, I added the new term in the following form:
objective_1 = mdl.max([mdl.end_of(task_itv_vars[j]) for j in range(len(p_time))])objective_2 = sum(E[i] for j in range(len(p_time)))objective_3 = sum(T[i] for j in range(len(p_time)))mdl.add(mdl.minimize(objective_1 + objective_2 + objective_3))
And again the solver shows that:
Model: parallel_Machine_Scheduling - source file: <ipython-input-3-314840e9531e> - modeling time: 12.35 sec - number of integer variables: 20 - number of interval variables: 50 - number of sequence variables: 4 - number of state functions: 0 - number of float variables: 0 - number of constraints: 49 - number of root expressions: 49 - number of expression nodes: 286 - operations: alternative: 10, endBeforeStart: 4, endOf: 10, greaterOrEqual: 30, max: 1, minimize: 1, minus: 20, noOverlap: 4, plus: 22, startOf: 30, sum: 2 ! --------------------------------------------------- CP Optimizer 20.1.0.0 -- ! Minimization problem - 74 variables, 48 constraints ! Initial process time : 0.03s (0.01s extraction + 0.02s propagation) ! . Log search space : 1113.2 (before), 1113.2 (after) ! . Memory usage : 608.9 kB (before), 608.9 kB (after) ! Using parallel search with 8 workers. ! ---------------------------------------------------------------------------- ! Best Branches Non-fixed W Branch decision ! Using temporal relaxation. 0 74 1 - + New bound is 82 * 82 45 0.05s 1 (gap is 0.00%) ! ---------------------------------------------------------------------------- ! Search completed, 1 solution found. ! Best objective : 82 (optimal - effective tol. is 0) ! Best bound : 82 ! ---------------------------------------------------------------------------- ! Number of branches : 282 ! Number of fails : 72 ! Total memory usage : 5.2 MB (5.1 MB CP Optimizer + 0.1 MB Concert) ! Time spent in solve : 0.05s (0.04s engine + 0.01s extraction) ! Search speed (br. / s) : 8057.1 ! ----------------------------------------------------------------------------Optimal solution found with objective 82.
From the above both logs, it seems the solver was countering with two different models! (number of expression nodes: ...). Would you please, is there any reasonable reason to take such a difference?
2) As long as I added the following constraint, the model did not produce a solution:
for j in range(len(p_time)): mdl.add(mdl.end_of(task_itv_vars[j], d_time[j]) <= d_time[j])
when I remove this one, it seems the solver can make the solution space and the solving process is executing. Is it possible that the added new constraints can already take this into account? (to me, it somewhat weird)!
3) The optimal solution from the MIP model is:
obj_value = 212makespan = 82
In the first model, the objective value is too far from the expected value, and in the second it seems the only part that was participating is the makespan.
In addition, an editable MRE can be found here. I was wondering if, you could take a look at that and let me have your insights.
Best regards
------------------------------
Abbas Omidi
Original Message:
Sent: Mon April 29, 2024 10:53 AM
From: Carlos Ferreiro
Subject: How to define an JIT objective besides Cmax
Dear Abbas Omidi,
I hope this message finds you well. Your question about defining earliness/tardiness in Constraint Programming (CP) is quite interesting.
In CP, you can indeed model earliness and tardiness constraints. The key is to create additional variables that represent the earliness and tardiness of each task, similar to what you've done in the MIP version.
Here's a high-level idea of how you might do this:
Define two additional arrays of integer variables, E and T, each of the same length as your task_itv_vars array. These will represent the earliness and tardiness of each task.
For each task j, add constraints to define E[j] and T[j] in terms of the start time, due time, and processing time of task j. This would look something like:
E = [mdl.integer_var(name="E_{}".format(j)) for j in range(len(p_time))]T = [mdl.integer_var(name="T_{}".format(j)) for j in range(len(p_time))]for j in range(len(p_time)): mdl.add(E[j] >= d_time[j] - (mdl.start_of(task_itv_vars[j]) + p_time[j])) mdl.add(T[j] >= (mdl.start_of(task_itv_vars[j]) + p_time[j]) - d_time[j])
- You can then incorporate
E and T into your objective function as desired.
Please note that this is a high-level idea and the actual implementation might need adjustments based on the specifics of your problem.
I hope this helps! If you have further questions, feel free to ask.
------------------------------
Carlos Ferreiro
Original Message:
Sent: Fri April 26, 2024 12:32 PM
From: Abbas Omidi
Subject: How to define an JIT objective besides Cmax
Dear support team,
I hope you are doing well. I am currently working on a specific scheduling problem in the CP where I need to define a JIT, (earliness/tardiness), besides an existing makespan objective function. The way I have defined the model is:
# Defining the variablestask_itv_vars = [mdl.interval_var(optional=False, size=p_time[j], name="interval_job{}".format(j)) for j in range(len(p_time))]processing_itv_vars = [[mdl.interval_var(optional=True, size=p_time[j], name="interval_job{}_machine{}".format(j,m)) for m in range(len(machines))] for j in range(len(p_time))]#minimize makespanobjective = mdl.max([mdl.end_of(task_itv_vars[j]) for j in range(len(p_time))])mdl.add(mdl.minimize(objective))for j in range(len(p_time)): mdl.add(mdl.start_of(task_itv_vars[j], r_time[j]) >= max(1, r_time[j]))for j in range(len(p_time)): mdl.add(mdl.end_of(task_itv_vars[j], d_time[j]) <= d_time[j])
Now, I would like to create the related constraints to control the earliness/tardiness. The MIP version is something like this:
e1(task) E[task] =g= due(task)-(start(task)+p_time(task));e2(task) T(task) =g= (start(task)+p_time(task))-due(task);e3(task) (start(task)+p_time(task))+E(task)-T(task) =e= due(task);
In this case, task is an index the same as j.
Also, the added term in the objective function in the MIP version is:
sum((task), E(tast) + T(Tast));
I was wondering if, is it possible to define these kinds of earliness/tardiness by CP? If so, how can I do that?
All the best
------------------------------
Abbas Omidi
------------------------------