Definition of disjunctions with restricted domain - Example 5

Example 5: A larger example using SUBSETS

The following example corresponds to a jobshop scheduling problem (Raman and Grossmann, 1994). In this problem, there is a set of jobs i E I that must be processed in a sequence of stages but not all jobs require all stages. Zero wait transfer policy is assumed between stages. To obtain a feasible solution is necessary to eliminate all clashes between jobs. It requires that no two jobs be performed at any stage at the same time. This is expressed by the following disjunction:

ex5

...where ti is the starting time of job i and tim the processing time of job i in stage j. The meaning of (1) is that either the job i precede job k or viceversa in the stage j where a clash can occur. The objective is to minimize the makespan.
The subset is used to prevent clashes at stage j between job i and k. In the following we include GAMS file for a jobshop scheduling problem to illustrate how to use a subset to control the disjunction domain.
The LogMIP input file corresponding to this example is the following:

SETS I jobs / A, B, C, D, E, F, G / ;
ALIAS(I,K);
SET J stages / 1*5 /;
ALIAS(J,M);
*
* Subset L to prevent clashes at stage j between stage i and k
*
SET L(I,K,J) /A.B.3, A.B.5, A.C.1, A.D.3, A.E.3, A.E.5, A.F.1, A.F.3, A.G.5,
     B.C.2, B.D.2, B.D.3, B.E.2, B.E.3, B.E.5, B.F.3, B.G.2, B.G.5,
     C.D.2, C.D.4, C.E.2, C.F.1, C.F.4, C.G.2, C.G.4,
     D.E.2, D.E.3, D.F.3, D.F.4, D.G.2, D.G.4, E.F.3, E.G.2, E.G.5, F.G.4 / ;

TABLE TAU(I,J) processing time of job i in stage j

  1 2 3 4 5  
A 3   5   2  
B   3 4   3  
C 6 3   6    
D   8 5 1    
E   4 6   2  
F 2   5 7    
G   8   5 4 ;


VARIABLES MS makespan ;
BINARY VARIABLES Y(I,K,J) sequencing variable between jobs i and k ;
POSITIVE VARIABLES T(I) ;>

EQUATIONS
   FEAS(I) makespan greater than all processing times
   NOCLASH1(I,K,J) when i precedes k
   NOCLASH2(I,K,J) when k precedes i
   DUMMY ;

FEAS(I).. MS =G= T(I) + SUM(M,TAU(I,M)) ;

NOCLASH1(I,K,J)$((ORD(I) LT ORD(K)) AND L(I,K,J)) ..
   T(I) + SUM(M$(ORD(M) LE ORD(J)), TAU(I,M)) =L=
   T(K) + SUM(M$(ORD(M) LT ORD(J)), TAU(K,M));

NOCLASH2(I,K,J)$((ORD(I) LT ORD(K)) AND L(I,K,J))..
   T(K) + SUM(M$(ORD(M) LE ORD(J)),TAU(K,M)) =L=
   T(I) + SUM(M$(ORD(M) LT ORD(J)), TAU(I,M));

DUMMY.. SUM(I, SUM(K,SUM(J, Y(I,K,J)))) =G= 0;

MODEL JOBSHOP / ALL / ;

$ONECHO > "%lm.info%"
DISJUNCTIOND1(I,K,J);
 D1(I,K,J) with ((ord(I) lt ord(K) and L(I,K,J)) IS
 IF Y(I,K,J) THEN
  NOCLASH1(I,K,J);
 ELSE
  NOCLASH2(I,K,J);
 ENDIF;
$OFFECHO
T.up(I)=100.;

OPTION MIP = LOGMIPM;
 OPTION OPTCR = 0.0 ;
 OPTION OPTCA = 0.0 ;
SOLVE JOBSHOP MINIMIZING MS USING MIP ;


In the example shown above note that in LogMIP section disjunction D1 is defined over sets I,K,J their domain is controlled by the clause WITH using ord and card operators and the subset L, this is done in the same way than the definition of NOCLASH1 and NOCLASH2 constraints in GAMS section.