Originally posted by: AndyHam

Dear IBM,

I am working on a material transfer problem in semiconductor industry. In particular, there is an auxiliary resource called reticle. The auxiliary resource must be present with a machine for job processing. Furthermore, the auxiliary resource needs to be transferred by vehicles to other machines. The enclosed code and figure illustrate the problem and my concern.

The upper figure shows job-machine schedule with auxiliary resources. The lower figure shows reticle schedule which is derived from the upper based model. I need this derived reticle schedule in order to model the reticle transfer. For instance, pick up R2 from M2 after 10 and drop it off to M1 by 18. Then, pick up R2 from M1 after 28 and drop it off to M2 by 30. The question is how to create intervals like this. I have tried "typeOfNext" and "SPAN", but failed. Any help will be appreciated. Thanks, Andy

 

using CP;
int nj=5;
int nm=2;
int nr=2;
int StkIdx=3;

range Machines = 1..nm; 
range Reticles = 1..nr; 

tuple par_Job {
  int job;   
  int pt;   
  int release;  
  };
{par_Job} par_Jobs ={
<1,5,0>,
<2,5,18>,
<3,5,0>,
<4,5,18>,
<5,5,0>,
<6,5,18>
};

tuple par_J2M2R {
  int job; 
  int mch; 
  int ret;   
};
{par_J2M2R} par_J2M2Rs = {
<1,2,1>,
<2,1,2>,
<3,2,1>,
<3,1,1>,
<4,2,2>,
<5,2,2>,
<6,1,2>
};

int t[1..StkIdx][1..StkIdx]=[ 
[0,    2,    2],
[2,    0,    2],
[2,    2,    0]
];

tuple t_D {
    key int m1;
    key int m2;
    int dist;
}; {t_D} D;
execute {
for(var m2 in  Machines) 
    D.add(StkIdx, m2, t[StkIdx][m2]);
for(var m1 in  Machines) for(var m2 in Machines) 
    D.add(m1, m2, t[m1][m2]);
};

dvar interval itvJob[j in par_Jobs] size j.pt; 
dvar interval itvMach[j2m in par_J2M2Rs] optional;

dvar sequence seqMach[m in Machines]
  in    all(j2m in par_J2M2Rs: j2m.mch==m) itvMach[j2m]
  types all(j2m in par_J2M2Rs: j2m.mch==m) j2m.ret; 
dvar sequence seqRet[r in Reticles] 
  in    all(j2m in par_J2M2Rs: j2m.ret==r) itvMach[j2m]
  types all(j2m in par_J2M2Rs: j2m.ret==r) j2m.mch; 

                                                  
dexpr int Cmax = max(j in par_Jobs) endOf(itvJob[j]);

execute {
  cp.param.LogVerbosity=21;  
  cp.param.LogPeriod = 1000000;
  cp.param.TimeLimit = 2;
}

minimize  Cmax;

subject to {
 forall(j in par_Jobs)
    startOf(itvJob[j]) >= j.release;

 forall (j in par_Jobs)
    alternative(itvJob[j], all(j2m in par_J2M2Rs: j2m.job==j.job) itvMach[j2m]);  
 forall(m in Machines) 
    noOverlap(seqMach[m]); 
 forall(r in Reticles) 
    noOverlap(seqRet[r],D);     
}

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi Andy

 

The issue you have is clearly not knowing the reticle route makes impossible to model the transportation (the vrp model would be far from too huge)

That is a typical case for which successive model usually work very well.

 

The first model relax the vehicle routing and its side constraints problem :

be the jobs  and their locations  and the transition time matrix between 2 locations D.

• Each reticle is a unary resource containing the related jobs at the location var sequence reticle([itsJobs, [their locations])
• tell the constraint noOverlap(reticle, D)
• If the transportation time are very small wrt the job processing time, (which is usually the case in semiconductor fabs) you can even ignore all that stuff and only schedule the jobs. I strongly invite you to try this relaxation first
• elsewhere
  • if there is one vehicle (or the reticle are pre affected to a vehicle) each vehicle  is a non overlapping sequence noOverlap(alljobs, allocation, D)
  • If there is several vehicle, the right relaxation depends upon how the transportation system is organised and how much it is critical.

The second model add the vehicle routing model 

• As warm start, keep the allocation and sequence of jobs on each machines (use precedences constraints) and the sequence of jobs on each reticle. You know have fixed the route (jobs, location) for each reticle 
• A move between two location is an interval variable
  • of length the transition time between the two job locations,
  • that follows and precedes the two successive jobs at locations
• tell the transportation model on the moves  vehicle alternative,  their capacity and the secondary resources  model 

Hope that helps

 

 

If there is several vehicle, let's say n, the situation is more complicated.

be a cumulative function of level n, for each job, create a new activity that start at the end of the job

of same presence status the one of the job

of duration : if for the reticle, (1 - (location[jobs] = location[nextOf(vehicle, job))*averD

Where averD is the average transition time in D

Note tha

 

Second Problem : 

The warn start consist in the allocation and sequence of jobs. add this constraint and the sequence of 

 

The reticle is a state function whose state is the location of the machine and transition distance the time spent by the vehicle from location to location.

 

That is the job execution tell an alwaysEqual constraint(job, location).

 

The second model includes the vehicle

keeping the job resource allocation and the job sequence of task :

 

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: AndyHam

Thanks for the feedback.

I was working on two models: exact and decomposed (based on warm-start; similar to the one you suggested).

Decomposed model:
At 1^st stage, machines, jobs, and vehicles for job-delivery are modeled. A buffer time is added to ensure a feasibility after adding vehicles for reticle-delivery at 2^nd stage.

At 2^nd stage, machines, jobs, vehicles for job-delivery, reticles, and vehicles for reticle-delivery are modeled.

The decomposed model generates a solution within 60 s up to the following size:

  nj=100; //number of jobs

  nm=15; //number of machines

  nr=30; //number of reticles

  nLotBot=10; //number of vehicles for lot delivery

  nRetBot=5; // number of vehicles for reticle delivery

 

An exact model is needed to understand the quality of the decomposed model. So, I developed a semi-exact model with an assumption that all jobs are available at time 0. So, I was able to prevent a reticle from being delivered to a same machine multiple times during a planning horizon. Namely, jobs using a same reticle are processed consecutively on a machine, leading to one-time same reticle transfer on a machine. I used SPAN to capture the consecutive jobs on machine with a same reticle and used the intervals to initiate the reticle transfer by vehicle.

 

In a semiconductor, the material transfer takes few mins and the job process takes 10~180 mins. The material transfer often causes machine idles so unlimited capacity of material transfer is not realistic.

 

I still want to see if we can model the multi-visit on a machine by a same reticle to handle the dynamic job arrival as depicted on the figure earlier.

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: GGR

Hi Andy

 

Please ignore the last part of my message, (after the hope that's help). If you discover the relaxation of the transportation model is too weak, do not hesitate to contact us.

#DecisionOptimization
#OPLusingCPOptimizer