Dear support team,

I am working on an identical parallel machine scheduling problem that needs to take into consideration release time, (SD) setup time, and precedence relation. The problem is classified as (Pm | rj, perc, Sij | Cmax). The model was written as a MILP and was solved optimality. Now, to check and compare the provided solution from MIP, I would like to develop a CP model to see how it performs well on such a problem. As I am pretty new to CP optimizer, I defined the following interval variable based on a template.

processing_itv_vars = [[mdl.interval_var(optional=True, size=processingTimes[j], name="interval_job{}_machine{}".format(j,m)) for m in machines] for j in jobs] 

Also, I am not aware of how to define the precedence relation in the model, and after running the model, despite it showing no error, the problem was not solved, and the log file is as follows:

 ! --------------------------------------------------- CP Optimizer 22.1.1.0 -- ! Minimization problem - 44 variables, 54 constraints ! Initial process time : 0.01s (0.00s extraction + 0.01s propagation) !  . Log search space  : 213.3 (before), 213.3 (after) !  . Memory usage      : 367.7 kB (before), 367.7 kB (after) ! Using parallel search with 2 workers. ! ---------------------------------------------------------------------------- !          Best Branches  Non-fixed    W       Branch decision                        0         44                 - + New bound is 74 ! ---------------------------------------------------------------------------- ! Search completed, model has no solution. ! Best bound             : 74 ! ---------------------------------------------------------------------------- ! Number of branches     : 0 ! Number of fails        : 0 ! Total memory usage     : 806.6 kB (749.3 kB CP Optimizer + 57.4 kB Concert) ! Time spent in solve    : 0.03s (0.03s engine + 0.00s extraction)

Please, find a minimum reproducible example (MRE) in this link. 

I was wondering if, how can I fix the code to capture release time, setup time, and already precedence relation in the right way?

Best regards

Dear Abbas,

First, many thanks for sharing a MRE. This helps a lot for analyzing your issue.
The infeasibility is caused by the following constraint:

The `start_of` function "returns an integer expression that is equal to start of the interval variable interval if it is present. If it is absent, then the value of the expression is absentValue (zero by default)." (see: https://ibmdecisionoptimization.github.io/docplex-doc/cp/docplex.cp.modeler.py.html#docplex.cp.modeler.start_of)

Since the returned value of this function is involved in a constraint which enforces a value that is strictly positive in some cases, this means this constraint is actually enforcing all optional intervals associated with the job to be 'present' (which contradicts the: "each job should be assigned to a machine" constraint).

The proper way to formulate this constraint is as follows:

With this formulation, for optional intervals that are not present, the `start_of` function will return a value that satisfies the constraint.
This use of the `absentValue` parameter is a common pattern when using functions on intervals that are involved in a constraint.
Best regards,

Dear support team,

I am working on an identical parallel machine scheduling problem that needs to take into consideration release time, (SD) setup time, and precedence relation. The problem is classified as (Pm | rj, perc, Sij | Cmax). The model was written as a MILP and was solved optimality. Now, to check and compare the provided solution from MIP, I would like to develop a CP model to see how it performs well on such a problem. As I am pretty new to CP optimizer, I defined the following interval variable based on a template.

processing_itv_vars = [[mdl.interval_var(optional=True, size=processingTimes[j], name="interval_job{}_machine{}".format(j,m)) for m in machines] for j in jobs] 

Also, I am not aware of how to define the precedence relation in the model, and after running the model, despite it showing no error, the problem was not solved, and the log file is as follows:

 ! --------------------------------------------------- CP Optimizer 22.1.1.0 -- ! Minimization problem - 44 variables, 54 constraints ! Initial process time : 0.01s (0.00s extraction + 0.01s propagation) !  . Log search space  : 213.3 (before), 213.3 (after) !  . Memory usage      : 367.7 kB (before), 367.7 kB (after) ! Using parallel search with 2 workers. ! ---------------------------------------------------------------------------- !          Best Branches  Non-fixed    W       Branch decision                        0         44                 - + New bound is 74 ! ---------------------------------------------------------------------------- ! Search completed, model has no solution. ! Best bound             : 74 ! ---------------------------------------------------------------------------- ! Number of branches     : 0 ! Number of fails        : 0 ! Total memory usage     : 806.6 kB (749.3 kB CP Optimizer + 57.4 kB Concert) ! Time spent in solve    : 0.03s (0.03s engine + 0.00s extraction)

Please, find a minimum reproducible example (MRE) in this link. 

I was wondering if, how can I fix the code to capture release time, setup time, and already precedence relation in the right way?

Best regards

Dear Hugues,

Many thanks for your informative comments. It seems the method you pointed out can solve my first issue. Now, I am trying to define the precedence relations in the following forms and based on the documentation here on page 38:

# the first formfor i in jobs:  for j in jobs:    if (i, j) in Precedence:      for m in machines:        mdl.add(mdl.end_of(processing_itv_vars[i][m]) <= mdl.start_of(processing_itv_vars[j][m]))

# the second formfor i in jobs:  for j in jobs:    if (i, j) in Precedence:      for m in machines:        mdl.add(mdl.end_before_start(processing_itv_vars[i][m],processing_itv_vars[j][m]))

But, neither of them can produce a correct solution. Also, the constraint in the MIP form would be something like ( end(i) <= start(j)  ,forall i,j in precedence).
I was wondering if, how can I fix that?

Regards

Dear Abbas,

First, many thanks for sharing a MRE. This helps a lot for analyzing your issue.
The infeasibility is caused by the following constraint:

The `start_of` function "returns an integer expression that is equal to start of the interval variable interval if it is present. If it is absent, then the value of the expression is absentValue (zero by default)." (see: https://ibmdecisionoptimization.github.io/docplex-doc/cp/docplex.cp.modeler.py.html#docplex.cp.modeler.start_of)

Since the returned value of this function is involved in a constraint which enforces a value that is strictly positive in some cases, this means this constraint is actually enforcing all optional intervals associated with the job to be 'present' (which contradicts the: "each job should be assigned to a machine" constraint).

The proper way to formulate this constraint is as follows:

With this formulation, for optional intervals that are not present, the `start_of` function will return a value that satisfies the constraint.
This use of the `absentValue` parameter is a common pattern when using functions on intervals that are involved in a constraint.
Best regards,

Dear support team,

I am working on an identical parallel machine scheduling problem that needs to take into consideration release time, (SD) setup time, and precedence relation. The problem is classified as (Pm | rj, perc, Sij | Cmax). The model was written as a MILP and was solved optimality. Now, to check and compare the provided solution from MIP, I would like to develop a CP model to see how it performs well on such a problem. As I am pretty new to CP optimizer, I defined the following interval variable based on a template.

processing_itv_vars = [[mdl.interval_var(optional=True, size=processingTimes[j], name="interval_job{}_machine{}".format(j,m)) for m in machines] for j in jobs] 

Also, I am not aware of how to define the precedence relation in the model, and after running the model, despite it showing no error, the problem was not solved, and the log file is as follows:

 ! --------------------------------------------------- CP Optimizer 22.1.1.0 -- ! Minimization problem - 44 variables, 54 constraints ! Initial process time : 0.01s (0.00s extraction + 0.01s propagation) !  . Log search space  : 213.3 (before), 213.3 (after) !  . Memory usage      : 367.7 kB (before), 367.7 kB (after) ! Using parallel search with 2 workers. ! ---------------------------------------------------------------------------- !          Best Branches  Non-fixed    W       Branch decision                        0         44                 - + New bound is 74 ! ---------------------------------------------------------------------------- ! Search completed, model has no solution. ! Best bound             : 74 ! ---------------------------------------------------------------------------- ! Number of branches     : 0 ! Number of fails        : 0 ! Total memory usage     : 806.6 kB (749.3 kB CP Optimizer + 57.4 kB Concert) ! Time spent in solve    : 0.03s (0.03s engine + 0.00s extraction)

Please, find a minimum reproducible example (MRE) in this link. 

I was wondering if, how can I fix the code to capture release time, setup time, and already precedence relation in the right way?

Best regards

Dear Abbas,
I think the right way to model your scheduling problem is by using the "alternative" constraints.

This facilitates a lot the management of precedence constraints.
I tried to quickly rewrite your model to illustrate the modelling approach:

I subtracted 1 to the indexing from the Precedence list, otherwise I was getting an index out of range exception.
Precedence constraints are defined on the "parent" tasks (task_itv_vars ), while machine-level constraints are using the processing_itv_vars  intervals.

I hope I haven't made any error in the above code... Anyway, I encourage to have a look at: https://github.com/IBMDecisionOptimization/docplex-examples/blob/master/examples/cp/jupyter/scheduling_tuto.ipynb
This may give you some insights on the modelling approach for this kind of scheduling problem.
Best regards,

Dear Hugues,

Many thanks for your informative comments. It seems the method you pointed out can solve my first issue. Now, I am trying to define the precedence relations in the following forms and based on the documentation here on page 38:

# the first formfor i in jobs:  for j in jobs:    if (i, j) in Precedence:      for m in machines:        mdl.add(mdl.end_of(processing_itv_vars[i][m]) <= mdl.start_of(processing_itv_vars[j][m]))

# the second formfor i in jobs:  for j in jobs:    if (i, j) in Precedence:      for m in machines:        mdl.add(mdl.end_before_start(processing_itv_vars[i][m],processing_itv_vars[j][m]))

But, neither of them can produce a correct solution. Also, the constraint in the MIP form would be something like ( end(i) <= start(j)  ,forall i,j in precedence).
I was wondering if, how can I fix that?

Regards

Dear Abbas,

First, many thanks for sharing a MRE. This helps a lot for analyzing your issue.
The infeasibility is caused by the following constraint:

The `start_of` function "returns an integer expression that is equal to start of the interval variable interval if it is present. If it is absent, then the value of the expression is absentValue (zero by default)." (see: https://ibmdecisionoptimization.github.io/docplex-doc/cp/docplex.cp.modeler.py.html#docplex.cp.modeler.start_of)

Since the returned value of this function is involved in a constraint which enforces a value that is strictly positive in some cases, this means this constraint is actually enforcing all optional intervals associated with the job to be 'present' (which contradicts the: "each job should be assigned to a machine" constraint).

The proper way to formulate this constraint is as follows:

With this formulation, for optional intervals that are not present, the `start_of` function will return a value that satisfies the constraint.
This use of the `absentValue` parameter is a common pattern when using functions on intervals that are involved in a constraint.
Best regards,

Dear support team,

I am working on an identical parallel machine scheduling problem that needs to take into consideration release time, (SD) setup time, and precedence relation. The problem is classified as (Pm | rj, perc, Sij | Cmax). The model was written as a MILP and was solved optimality. Now, to check and compare the provided solution from MIP, I would like to develop a CP model to see how it performs well on such a problem. As I am pretty new to CP optimizer, I defined the following interval variable based on a template.

processing_itv_vars = [[mdl.interval_var(optional=True, size=processingTimes[j], name="interval_job{}_machine{}".format(j,m)) for m in machines] for j in jobs] 

Also, I am not aware of how to define the precedence relation in the model, and after running the model, despite it showing no error, the problem was not solved, and the log file is as follows:

 ! --------------------------------------------------- CP Optimizer 22.1.1.0 -- ! Minimization problem - 44 variables, 54 constraints ! Initial process time : 0.01s (0.00s extraction + 0.01s propagation) !  . Log search space  : 213.3 (before), 213.3 (after) !  . Memory usage      : 367.7 kB (before), 367.7 kB (after) ! Using parallel search with 2 workers. ! ---------------------------------------------------------------------------- !          Best Branches  Non-fixed    W       Branch decision                        0         44                 - + New bound is 74 ! ---------------------------------------------------------------------------- ! Search completed, model has no solution. ! Best bound             : 74 ! ---------------------------------------------------------------------------- ! Number of branches     : 0 ! Number of fails        : 0 ! Total memory usage     : 806.6 kB (749.3 kB CP Optimizer + 57.4 kB Concert) ! Time spent in solve    : 0.03s (0.03s engine + 0.00s extraction)

Please, find a minimum reproducible example (MRE) in this link. 

I was wondering if, how can I fix the code to capture release time, setup time, and already precedence relation in the right way?

Best regards