Decision Optimization

Originally posted by: bgokgur

Hi all,

I wonder that is there any way to access position member of sequence variable ?

I can access them after solution is obtained. However, I want to use position element of sequence variable while I am writing a constraint.
Thank you for your support,

Burak.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: rdumeur

Dear bgokgur,

There is no direct way to access the position of a sequence var member. But depending on what you wish to do with this positional information, we can advise you on the best way to compute and use it. So, could you please give more details about your model and what is the intended use of sequence member positions?

Cheers,
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: bgokgur

Thank you for your reply.

My problem briefly is:

There are set of jobs to be processed on parallel machines. For each job, there are set of tools required to be loaded before processing the job. Required set of tools of each job may vary. Also, processing of each job may vary on different machines.

I just want to write a constraint for each tool such that

in what sequence it is used and on which machine ? and I want to say that if that tool used on different machines on consecutive positions by jobs, then say a binary variable takes value 1.

To be able to this, I thought that I need to access position element of sequence variable. In my CP model, tools and machines are unary resources.

Again, thank you for your help,

Burak.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: rdumeur

Dear bgokgur,

The model given at the end of the message shows how to use transition costs to model the fact that a tool moves between machines. Basically, you only need to create:
- job interval vars
- alternatives for machine usage associated to each job.
- a noOverlap constraint on a sequence made from these jobs
- one sequence per tool associated with a transition cost matrix. Each member of this sequence is one of each job/machine alternative member requiring the tool.
- applying the noOverlap constraint on each sequence with the associated cost matrix will introduce delays between consecutive intervals of the sequence corresponding to the change of tool.
At the beginning of the constraint declaration ("subject to") a couple of constraints are introduced that force a tool to be moved between two machines, hence introducing a delay between job #1 and job #2. Without them, the optimizer manages to group jobs on machine so that no tool motion is required (and thus no extra delay is introduced).

I hope this helps.

Cheers,

/********************************************* * OPL 12.5 Model * Author: R_Dumeur * Creation Date: 20 mars 2013 at 14:26:17 *********************************************/ using CP;   tuple JobDurationTuple 
{ string name; 

int duration; 
};   tuple JobMachineTuple 
{ string job; string machine; 
}   tuple ToolTransitionCostTuple 
{ string tool; string before; string after; 

int cost; 
}   tuple JobToolTuple 
{ string job; string tool; 
} 
// problem data   
{string
} JobSet = 
{ 
"j1", 
"j2", 
"j3", 
"j4", 
"j5" 
}; 
// { j | <j,d> in JobDurationSet }; 
{string
} MachineSet = 
{ 
"m1", 
"m2" 
}; 
// { m | <j,m> in JobMachineSet };   
{JobMachineTuple
} JobMachineSet = 
{ <j,m> | j in JobSet, m in MachineSet 
}; 
{JobDurationTuple
} JobDurationSet = 
{ <j,10> | j in JobSet 
}; 
{JobToolTuple
} JobToolSet = 
{ <
", "t1
">, <", 
"t1">, <
", "t1
">, <",
"t2">, <
","t2
"> };   
{ToolTransitionCostTuple
} ToolTransitionCostSet = 
{ <
","m1
","m2
",10>, <
","m2
","m1
",10> 
};   
// entities 
{string
} ToolSet = 
{t | <j,t> in JobToolSet 
};   

int JobDuration[j in JobSet] = first(
{d | <j,d> in JobDurationSet 
}); 

int MachineIndex[m in MachineSet] = ord(MachineSet, m); range MachineIndices = 0..card(MachineSet); dvar interval job[j in JobSet] size JobDuration[j]; dvar interval job_machine[JobSet][MachineSet] optional ; dvar sequence machine_job[m in MachineSet] in all(<j,m> in JobMachineSet) job_machine[j][m]; dvar sequence tool_machine[t in ToolSet] in all(<j,t> in JobToolSet, m in MachineSet) job_machine[j][m] types all(<j,t> in JobToolSet, m in MachineSet) MachineIndex[m]; tuple TransitionCostTuple 
{ 

int m1; 

int m2; 

int value; 
} 
{TransitionCostTuple
} ToolMachineTransitionCost[t in ToolSet] = 
{ <a,b,c> | a,b in MachineIndices, <t,sa,sb,c> in ToolTransitionCostSet : a == MachineIndex[sa] && b == MachineIndex[sb] 
};   minimize max(j in JobSet) endOf(job[j]);   subject to 
{ 
// To show transition cost, force presence of job #2 on machine #2 
// this will force requirement of tool #2 on this machine 
// and introduce a transition cost. presenceOf(job_machine[
"j2"][
"m2"]) == 

true; presenceOf(job_machine[
"j1"][
"m1"]) == 

true; endBeforeStart(job[
"j1"],job[
"j2"]); forall(j in JobSet) 
{ alternative(job[j], all(<j,m> in JobMachineSet) job_machine[j][m]); 
} forall(m in MachineSet) 
{ noOverlap(machine_job[m]); 
} forall(t in ToolSet) 
{ noOverlap(tool_machine[t], ToolMachineTransitionCost[t]); 
} 
}

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: bgokgur

dear rdumeur,

Thanks for your support. I forgot to mention about tool switches in my problem.

There is also tool switches(independent from jobs and it has constant time) and tool magazine capacity in my problem. A tool switch can occur in two ways:

1) when a tool is moved to different machines
2) if the number of required set of tools of two consecutive jobs exceeds tool magazine capacity
I can't reflect these situations into my model.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: bgokgur

Because of tool switches, I want to access position element of sequence variable.

Again, thank you for your support.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: rdumeur

Hi,

As shown in the attached model, you can model tool changes with transition costs between jobs for a given machine. So, again, you can avoid knowing the position of the interval in a sequence.
In the attached file, we specify, for the sake of the example, the transition delay between two job to be the absolute value of the difference of the job indices.
This is done with:

{TransitionCostSymbolicTuple
} JobTransitionCostSet = 
{ <m,j1,j2,c> | m in MachineSet, j1,j2 in JobSet, c in 0..card(JobSet) : c == abs(JobIndex[j1]-JobIndex[j2]) 
};

We generate the tuple set specifying integer indices required by the noOverlap method:

{TransitionCostTuple
} MachineJobTransitionCost[m in MachineSet] = 
{ <a,b,c> | a,b in JobIndices, <m,sa,sb,c> in JobTransitionCostSet : a == JobIndex[sa] && b == JobIndex[sb] 
};

And eventually we pass this transition matrix to the noOverlap constraint on the machine_job sequence:

forall(m in MachineSet) 
{ noOverlap(machine_job[m], MachineJobTransitionCost[m]); 
}

Naturally, you can define any kind of transition delay introduced by the fact that a machine switches from a job to another. It could depend on the number and nature of tools that need to be changed in the machine during two consecutive jobs.

I hope it helps,

Cheers,
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: bgokgur

dear rdumeur,

That is exactly what I need. I should have thought that I could develop right tuples for transition matrix without trying to access position element of sequence variable.

Thank you for your support.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: bgokgur

dear rdumeur,

I made a mistake in explaining my problem.

In 2nd case of tool switching, considering two consecutive jobs whether the number of required set of tools of them exceeds tool magazine capacity will not be enough.

I have to consider all assigned jobs for each machine.

For example,
Assigned jobs for machine 1 -> J1-J5-J4-J6-J10
Each combination of subset of consecutive jobs must be checked for tool magazine capacity such as
(J1-J5), (J1-J5-J4), (J1-J5-J4-J6), (J1-J5-J4-J6-J10)

I first thought that I could generate tuple for each possible combination of jobs sequence but the number of instance of all tuples is too much.

Is there a more intelligent way to check cumulatively subset of jobs for tool magazine capacity ?

Thank you for your help,
Burak.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,
I think that you should formalize more what happens when the capacity of the machine magazine is exceeded. What happens then ? Let's assume that if the maximal capacity of the magazine is reached and a new tool needs to be installed on the machine, then at least one of the current tools in the machine magazine needs to be removed (and stored somewhere else) and that this operation will require some time. So if a given tool Ti cannot stay in the machine magazine, it need to be removed from the magazine and will not be able to be available again before some minimal time has elapsed.

For instance, with your example of sequence on machine 1: J1-J5-J4-J6-J10. If the capacity of the magazine is 2, we have 4 tools T1..T4 and if we have the following tool requirements by jobs: J1:{T1,T2}, J5:{T2,T3}, J4:{T1,T3}, J6:{T3,T4}, J10:{T1,T4}. Let's suppose the jobs are all 10 and that when the magazine capacity is exceeded it requires 30 units of time to install a new tool. A solution could be:

J1 executes on [0,10) with T1 and T2, magazine usage is 2
J5 executes on [10,20) with T2 and T3, T1 needs to be removed from the magazine in order not to exceed the capacity so it won't be available until 10+30=40
J4 executes on [40,50) with T1 (that has been put back in the magazine which explains the delay) and T3 (already in magazine), magazine is full, so T1 needs to be removed again from the magazine in order not to exceed the capacity, it won't be available until 50+30=80
J6 executes on [50,60) with T3 and T4 (installed in place of T1)
J10 executes on [80,90) with T1 (that has been put back in the magazine which explains the delay) and T4 (already in magazine)

You could model this with a model like the one attached. For simplicity, I considered a single machine but it can easily be extended to alternative machines, the only difference will be that the job intervals are optional. The model introduces some additional interval variables (optional interval variables occupyMagazine) to represent the contiguous occupation of the machine magazine by a particular tool. We do not know the number of these intervals a priori (that's why they are optional) but we know their number cannot exceed the number of jobs requiring the tool on the machine and we can break evident symmetries in the problem by adding precedence and implication constraints between these intervals. Then the constraints state that:
1- during the execution of a job the required tools need to be installed in the magazine (alwaysIn constraint)
2- there is a minimal delay that must elapse between two consecutive presences of the tool in the magazine (delay in the endBeforeStart constraints)
The maximal capacity of the magazine is then modeled as a limit on a global cumul function on the machine.

This model can be adapted if you have a slightly different definition for what happens when the magazine is full. Note also that finding an initial feasible solution may not be trivial for CP Optimizer on this type of model. If constraints on the magazine capacities are not real bottlenecks in your problem, it could be a good idea to first solve the problem with a relaxation or an approximation of this constraint (for instance the relaxation only considering pairs of consecutive jobs) and then, once a solution has been found, re-optimize it by considering those magazine capacities. For that you can use the notion of "starting point" in CP Optimizer.

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: bgokgur

Dear Philippe,

First of all, thank you for your help.

I did not understand one point in the model that you attached. "Horizon" is defined and optional size of tool interval variable is set to minduration to horizon.

What is the reason of defining horizon and setting optional size of tool interval variable such as minduration..Horizon ?

Also, I might miss some crucial points in the model but when I check the starting and ending time of jobs in the solution of the model, there is no transition time between jobs even if switching must occurs because of tool magazine capacity between some subset of consecutive jobs.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,

"Horizon" is not really important in the model. It could be any large value. It is used in the definition of interval variables occupyMagazine to define the domain of the size of the interval. The maximum size ("Horizon") is not really important. what is more important is the minimal size. Interval variable occupyMagazine represents the time interval during which a given tool stays in the magazine of a machine. It would be sufficient to set a minimal size of 1 for such an interval. In the attached model, it is slightly optimized by the fact that if a tool is in the magazine of a machine for performing a job, the duration of such an interval of time will be at least the minimal duration of all jobs requiring this tool on the machine. This is why the min size is stated to be minJobDuration[tj.tool]. As the OPL syntax for defining a min size also requires a value for the max, that's the reason for introducing "Horizon".

In the model I attached there is no transition time on the machine beside the tool transition constraint. And a transition between tools does not necessarily imply a transition between consecutive jobs on the machine (but this is because of the interpretation I did of your description of the tool change constraint). Look at the example I gave:


There is indeed no transition time between the first two jobs J1 and J5. It is because in my interpretation, if the capacity of the magazine is 2, switching from {T1,T2} to {T2,T3} does not require any delay between the jobs: moving T1 out of the magazine can be done in parallel with installing T3. It is only when T1 will have to be re-installed in the magazine that it will require some time, but this re-installation can be done without interrupting the machine, it will only delay the time a new job requiring tool T1 can start (like the subsequent job J4 in the above example).

Your question when looking at the solution shows that my interpretation of the tool change constraint is probably not the right one. This is why I asked if you can formalize this tool change constraint so that there is no ambiguity about its possible interpretation. Note that the attached model with cumul function can be adapted to other interpretations of the tool change constraint. The chain of intervals occupyMagazine really represent the set of time intervals during which the tool needs to stay in the machine magazine in order to perform some jobs. You can for instance add addition intervals in the chain of intervals occupyMagazine to represent activities related with tool removal/installation in the machine magazine. These interval variables could require the machine and even, why not, other resources.
Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: bgokgur

Dear Philippe,

I appreciate your help.

I understood your point. I will try to make some change by adding some additional interval variables as you mentioned. After that, If I again have any questions, I will post it to here.

Thank you,

Burak.
#DecisionOptimization
#OPLusingCPOptimizer