Originally posted by: Kyle_Wang

I have a Main tool with 20 sub tool installed on it .

• Main Tool will have a maintenance window from t0-t1 , for example 10-1-2016  to 10-10-2016, which means I can do main tool maintenance any time in this time frame
• Main Tool has 20 socket B1 to B20, where we can install Sub tool.  There is a sub tool pool from a1---a25. there are 5 more sub tools as buffer. Each of the sub tool has its maintenance window t'0-t'1, t'2-t'3 etc……
• Main tool maintenance will cause 100% capacity loss, but each of the sub tool  online maintenance will cause 5% (1/20) capacity loss. The rest of the 5 buffer sub tool offline maintenance work cause 0% capacity loss.
• Here I want to utilize main tool maintenance time to perform sub tool maintenance to save the capacity.

in this case i created a 1D 1*25 0-1 matrix represent the sub tool and Main tool mapping relation. but i get confused how to constraint  "if main tool maintenance window overlap with sub tool maintenance window, then let them happen together."   can some help me on that?  thanks alot!

Originally posted by: Petr Vilím

Hello,

if you want to force all sub tool maintenance to happen only during main tool maintenance then you can use span constraint, see e.g. here: http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.3/ilog.odms.ide.help/refcppopl/html/constraints_groups.html

Or it is just a preference? What are another constraints on the main tool and subtools? Maybe cumulative function(s)?

Petr

Originally posted by: Kyle_Wang

Hi Vilim

   thanks so much for your help.  seems like synchronize is the feature i am looking for.  but i am still a bit confused.

1. if i treat interval a as the main tool maintanence, interval b1 ... b25 is my sub tool maitanence.   but here only 20 of the total 25 subtool is installed on main tool.  in this case how to synchronize?
2. main tool maitanence time is longer than sub tool maintanence.  not possible to set s(a)=s(bi) and e(a)=e(bi)
3. my objective to maximize main tool utilization. may need a cumlfunction to show the availability of main tool.  for example when   between s(a) and e(b) main tool availability is 0%.   during s(a) and e(b) sub tool maintanece will keep availablity 0%. periods <s(a) or period > e(a), sub tool maitance will cause 5% of availability loss.thanks again! 

Originally posted by: PhilippeLaborie

Hello,

Could you try formalizing your problem with maths so that we have better grasp on what you are trying to solve?

In particular: what are the decision variables of the problem, what are the parameters/constants already known, what are the constraints and which criterion do you want to optimize?

Originally posted by: Kyle_Wang

Hi Let me explain the problem.

1. I have 1 main tool A and 25 sub tool. main tool requires 20 sub tools installed to keep it fully run.
2. both main tool and sub tool has their maintenance task with earliest start date and due day and different maintenance time  ( maintenance time window) showed  in previous picture
3. main tool maintenance will cause machine availability 100% loss, if sub tool is installed on main tool, it will cause 5% availability loss, but if the sub tool is not installed on main tool (5 buffer sub tool), it will has 0% availability impact. and also , if sub tool installed on main tool and their maintenance work happen together, trigger 0% availability impact
4. my objective to schedule main tool maintenance tasks and sub tool maintenance task to maximize main tool availability

please let me know if i explained it clearly. thanks!

Originally posted by: PhilippeLaborie

So I'll then formalize the problem myself. Let me know if I get it well:

Let A denote your main tool and A1,..., AN denote your available sub-tools

Here are the known parameters of the problem:

- Number of available sub-tools: N=25

- For main tool A you know:
  o A set of time-windows W were you can perform the maintenance activity W = { [Sj,Ej] } where Sj (resp Ej) is the start (resp. end) time of the jth time window
  o The duration D of the maintenance activity

- For each sub-tool Ai, you know similar information as for main tool:
  o A set of time-windows Wi were you can perform the maintenance activity Wi = { [Sij,Eij] } where Sij (resp Eij) is the start (resp. end) time of the jth time window for maintenance of subtool Ai
  o The duration Di of the maintenance activity

- The number M of subtools Ai that needs to be installed on main tool A (M=20)
  
The decision variables of your problem are:

1- A Boolean decision variable bi for each sub-tool Ai, bi==1 if and only if you decide to install sub-tool Ai on main tool A

2- A set of time variables t, t1, ... ti ...,tN where t (resp. ti) denotes the time you start the maintenance task for the main tool (resp. for sub-tool i in case sub-tool i is installed on the main tool) 

The constraints of your problem are:

1- You need to select M subtools so: sum_i b_i == M

2- If a subtool is selected, the date of its maintenance should be in a time window of the subtool:

   ( b_i == 1 ) => there exists a time window j in Wi such that : Sij <= ti  and ti+Di <= Eij
 

The objective is:
minimize the non-availability of the main tool which can be formalized as:

D + 0.05 * sum_i { (b_i==1) *  outside( [ti,ti+Di], [t,t+D] ) }

Where outside(U, V) is the length of interval U outside of interval V, that is :
outside(U,V) = card ( U \ V )

Do I get it right ?

Originally posted by: Kyle_Wang

Hi Philippe

   thanks so much for your much elegant model description.   your description is what i want.

Originally posted by: PhilippeLaborie

Then if you have no other constraints in the problem I think it can be solved in polynomial time.

For a fixed value t at which to start the maintenance on the main tool A, you can easily compute for each sub-tool Ai an "optimal" maintenance date with respect to main tool maintenance [t,t+D] if sub-tool Ai is installed, this is just the position [ti, ti+Di] that is inside the time windows of Ai and overlaps [t, t+D] as much as possible. Let OUTi(t) be the part outside  [t, t+D] for this optimal position. For a given t, you can sort the sub-tools Ai by increasing OUTi(t) and select the M sub-tools with the smallest OUTi(t) value, this way you get an optimal sub-toll selection and maintenance schedule with respect to main tool maintenance interval [t,t+D]. Then you can compute this for all t and select the t minimal objective function. And you can use some consideration on the variation of the objective function to show that it should be enough to consider a limited number of values for t related with the durations D, Di and the start end of time-windows W and Wi.

Of course if you have additional constraints, the problem may turn out to be more complex to solve.

If you want to use CP Optimizer, you could think of using the overlapLength expression. The value of overlapLength(U,V,absVal) if U and V are two interval variables is the length of the intersection between U and V if the two intervals are present and absVal otherwise. So , if you have an interval variable T=[t,t+D] for the maintenant of the main tool and and optional interval TSi=[ti,ti+Di] for the subtool Ai (present if Ai is installed), then in the mathematical formulation outside( [ti,ti+Di], [t,t+D] ) } is Di - overlapLength(STi,T,Di).

So your problem could be formulated as:

dvar interval T size D;
dvar interval ST[i in ...] optional size D[i];
minimize sum(i in .. ) ( D[i] - overlapLength(ST[i], T, D[i]) );
subject to {
  forbidExtent(T, W);
  for (i in ...) forbidExtent(ST[i], SW[i]);
  sum(i in ...) presenceOf(ST[i]) == M;
}

Where W (resp. SW[i] ) is a step function with value 1 during the allowed time-window for maintenance on main tool A (resp. sub-tool Ai) and value 0 on forbidden maintenance time-window.

For this problem if you do not have additional constraints like precedence relations or production activities and/or resource constraints, I'm not sure a CP Optimizer model will bring a lot compared for instance to an Integer Linear Programming model.

Originally posted by: Kyle_Wang

that is great. let me try this out :)  will update in the weekend. thank you have good night !

Originally posted by: Kyle_Wang

This works perfect now! i even expand this to 20 main tool and 200 sub tool scheduling.. :)    thank you so much for your help!

Originally posted by: Kyle_Wang

Hi Dear Philippe

  i have expand the model to 4 main tool, 130 sub tools and try to arrange the scheduling for year 2016 and year 2017. total, ~400 tasks need to scheduling.  and decision variable matrix[main tool] [Sub tool]  range(0,1) to represent the mapping was added in. the scheduling time unit is "Hour". 

   {
                for (int j = 0; j < main_tools_tasks[i].Count; j++)
                {
                    foreach (IIntervalVar main_tools_pm in main_tools_tasks[i])  // main_tools ID is i
                    {
                        int main_tools_pm_tpt = 12;
                        int sub_tool_pm_tpt = 6;
                        for (int k = 0; k < sub_tool_count; k++)  //sub_tool ID is k
                        {
                            foreach (IIntervalVar sub_tool_pm in sub_tool_tasks[k])
                            {
                               
                                Overlap = cp.Sum(Overlap, cp.Sum( cp.Prod(dvar_module_cell_matrix[i][k], cp.Diff(cp.LengthOf(main_tools_pm), cp.Prod(dvar_module_cell_matrix[i][k], cp.OverlapLength(main_tools_pm, main_tools_pm, main_tools_pm_tpt)))),cp.Prod(cp.Diff(1, dvar_module_cell_matrix[i][k]), 12)));
                                
                            }

                        }

                    }

                }

            }

now the problem now is the model are 1) memory usage easily rise up to >20G. 2) memory overflow at

   i is the index of main tool, k is the index of sub tool.  do you have any tips to solve the memory overflow issue?  (i can get the result when setting to shorter time frame, but business need require to look at yearly schedule. )  thanks!

Originally posted by: Petr Vilím

Hello,

it seems to me that there are duplicate cycles on both main and sub tools. Lets consider this:

for (int j = 0; j < main_tools_tasks[i].Count; j++)
{
   foreach (IIntervalVar main_tools_pm in main_tools_tasks[i])  // main_tools ID is i

This is a nested loop on main_tools_task[i]. I.e. if main_tools_task[i].Count is 4 then the outer cycle has 4 iterations and the inner cycle also 4 iterations what results in 4x4=16 iterations.

I guess that you wanted to write instead:

for (int j = 0; j < main_tools_tasks[i].Count; j++)
{
   IIntervalVar main_tools_pm = main_tools_tasks[i][j]

And similarly for the inner cycles on k and sub_tool_pm. It should dramatically decrease the size of the expression "Overlap" and also the memory usage.

Finally I noticed that sub_tool_pm is not used at all in the expression. I suspect that the following expression:

cp.OverlapLength(main_tools_pm, main_tools_pm, main_tools_pm_tpt)

was actually meant to be:

cp.OverlapLength(main_tools_pm, sub_tool_pm, main_tools_pm_tpt)

Best regards, Petr

Originally posted by: Kyle_Wang

1) yeah. here is duplicate cycles there. after i make change the memory usage reduced to <1G for 2 years scheduling tasks

2) i just corrected the typo. 

thank you for your help!  good day! :)