Benchmarks Library ballred.gif (861 bytes) Transfer Line Balancing Problem
line.jpg (1129 bytes)

 GAMS-model         

ballred.gif (861 bytes)  Transfer Line Balancing Problem 

ballred.gif (861 bytes)  Benchmarks

ballred.gif (861 bytes)  GAMS-model


$offsymxref

$offsymlist

 

$include "problem.GMS"

 

$setglobal CPU_TIME_CPLEX 90

* CPU time limit for CPLEX

 

$setglobal ABS_ERROR_CPLEX 0

* Absolute error limit for CPLEX

 

scalar r temporary value;

 

*========================================== calculated sets and parameters

 

set QQ(j,q) "set of indices q of blocks to which operation j can be assigned";

loop((j,q)$((ord(q) ge a(j)) and (ord(q) le b(j))), QQ(j,q)=yes);

 

set KK(j,k) "set of indices k of stations to which operation j can be assigned";

loop((j,k)$((ord(k) ge AA(j)) and (ord(k) le BB(j))), KK(j,k)=yes);

 

set SS(k,q) the set of block indices q for the stations k;

loop(k,

  loop(q$((ord(q) > (ord(k)-1)*n_0) and (ord(q) le ord(k)*n_0)),

    SS(k,q)= yes;

  );

);

 

parameters

  IS_size(IS_name) sizes of station inclusion subsets e,

  XS_size(XS_name) sizes of station exclusion subsets e,

  XB_size(XB_name) sizes of block exclusion subsets e

;

 

set je_IS(j,IS_name) je is some fixed operation from the set IS_name;

set KK_IS(k,IS_name) the set of stations where all operations of IS_name can be placed;

KK_IS(k,IS_name)=yes;

 

loop(IS_name,

  r=smin(IS(IS_name,j),ord(j));

* choose the operation with minimal index in IS_name as je_IS for IS_name

  loop(j$(ord(j)=r), je_IS(j,IS_name)=yes);

  IS_size(IS_name)=sum(IS(IS_name,j),1);

  loop((j,k)$(IS(IS_name,j) and not(KK(j,k))),

    KK_IS(k,IS_name)=no;

  )

);

 

set je_XS(j,XS_name) je is some fixed operation from the set XS_name;

loop(XS_name,

  r=smin(XS(XS_name,j),ord(j));

* choose the operation with minimal index in XS_name as je_XS for XS_name

  loop(j$(ord(j)=r), je_XS(j,XS_name)=yes);

  XS_size(XS_name)=sum(XS(XS_name,j),1);

);

 

set je_XB(j,XB_name) je is some fixed operation from the set XB_name;

loop(XB_name,

  r=smin(XB(XB_name,j),ord(j));

* choose the operation with minimal index in XB_name as je_XB for XB_name

  loop(j$(ord(j)=r), je_XB(j,XB_name)=yes);

  XB_size(XB_name)=sum(XB(XB_name,j),1);

);

 

parameter

  t(i,j) supplementary parameter to compute the block time t_b

;

loop((i,j),

  t(i,j)=max(l(i),l(j))/min(s(i),s(j));

);

 

display t;

 

parameter

 min_num_st "minimal number of stations (computed on the basis of AA)"

;

 

min_num_st=smax(j,AA(j));

 

scalar UseEq7Prime the flag to use (7') if not all s_j are identical;

UseEq7Prime=0;

loop(j$(ord(j)>1),

  if(not(s(j)=s(j-1)),

    UseEq7Prime=1;

  );

);

 

*======================================== end of calculated sets and parameters

alias (q, qprime);

alias (j,je);

alias (q,qminus1);

alias (k,kminus1);

 

*======================================== Model

 

Binary Variables

        Z(k) "indicates if the station k exists or not"

        Y(q) "indicates if the block q exists or not"

;

Positive Variables

        F(q) "the time of block q"

;

Binary Variables

        X(j,q) "decision variable: equals to 1 iff operation j is assigned to block q"

 

Variables

        cost "the overall cost, to be minimized"

;

 

Equations

         obj

         cone_block_op(j)

         cpreced2(i,j)

         cincusion_st(IS_name,k,je)

         cexclusion_bl(XB_name,q)

         cexclusion_st(XS_name,k)

         clb_block_time1(i,q)

         clb_block_time2(i,j,q)

         cub_station_time(k)

         cexist_block(q,j)

         cexist_station(q,k)

         ccont_block(q,k,qminus1)

         ccont_station(k,kminus1)

         cut_station(k)

         cut_block(q)

;

 

* (1) Objective function (minimization)

obj..

  cost =e= C_1 * sum(k, Z(k)) + C_2 * sum(q, Y(q));

 

* (2") Precedence constraint

cpreced2(i,j)$(Pred(i,j))..

  sum(q$QQ(j,q), (ord(q)-1)*X(j,q)) =g= sum(q$QQ(i,q), (ord(q)-1)*X(i,q));

 

* (3) Each operation is assigned only to one block

cone_block_op(j)..

  sum(q$(QQ(j,q)), X(j,q))=e= 1;

 

* (4) Inclusion constraint for stations

cincusion_st(IS_name,k,je)$(KK(je,k) and je_IS(je,IS_name))..

  sum(j$(IS(IS_name,j) and not je_IS(j,IS_name)),

    sum(q$(SS(k,q) and QQ(j,q)), X(j,q))

  )

  =e=(IS_size(IS_name)-1) * sum(q$SS(k,q), X(je,q));

 

* (5) Exclusion constraint for blocks

cexclusion_bl(XB_name,q)$

    ( sum(j$(XB(XB_name,j) and QQ(j,q)),1) = XB_size(XB_name) )..

  sum(j$XB(XB_name,j), X(j,q)) =l= XB_size(XB_name)-1;

 

* (6) Exclusion constraint for stations

cexclusion_st(XS_name,k)$

    ( sum(j$(XS(XS_name,j) and KK(j,k)),1) = XS_size(XS_name) )..

  sum(j$XS(XS_name,j),

    sum(q$(SS(k,q) and QQ(j,q)),

      X(j,q)

    )

  ) =l= XS_size(XS_name)-1;

 

* (7) lower bound on block time

clb_block_time1(i,q)$(QQ(i,q))..

  F(q) =g=t(i,i)* X(i,q);

 

* (7') lower bound on block time

clb_block_time2(i,j,q)$(ord(i)<ord(j) and QQ(i,q) and QQ(j,q))..

  F(q) =g= t(i,j)*(X(i,q)+X(j,q)-1) - (1-UseEq7Prime)*T_0;

 

* (8) the station time does not exceed the cycle time T_0

cub_station_time(k)..

  tau_s+sum(q$SS(k,q), F(q)) =l= T_0;

 

* (9) existence of block q

cexist_block(q,j)$QQ(j,q)..

  Y(q) =g= X(j,q);

 

* (10) existence of station k

cexist_station(q,k)$(ord(q)=(ord(k)-1)*n_0+1)..

  Z(k) =e= Y(q);

 

* (11) block q can be created only if block q-1 exists in station k

ccont_block(q,k,qminus1)$(SS(k,q) and not(ord(q)=(ord(k)-1)*n_0+1) and ord(qminus1)=ord(q)-1)..

  Y(qminus1) - Y(q) =g= 0;

 

* (12) staion k can be created only if station k-1 exists

ccont_station(k,kminus1)$(ord(k)>1 and ord(kminus1)=ord(k)-1)..

  Z(kminus1) - Z(k)=g= 0;

 

* Additional constraint that serves as a cut

cut_station(k)..

  Z(k) =l= sum(q$SS(k,q), Y(q));

 

* Additional constraint that serves as a cut

cut_block(q)..

  Y(q) =l= sum(j$QQ(j,q), X(j,q));

 

*Bounds on variables

Y.up(q)= 1;

Z.up(k)= 1;

Y.lo(q)= 0;

Z.lo(k)= 0;

F.up(q)=T_0-tau_s-tau_b;

 

* Eliminate/fix unnecesary binary variables

loop((j,q)$(not(QQ(j,q))), X.up(j,q)=0);

loop((j,k)$(not(KK(j,k))),

  loop(q$SS(k,q),X.up(j,q)=0);

);

loop(k$(ord(k) le min_num_st),

         Z.fx(k)=1;

         loop(q$(ord(q) = (ord(k)-1)*n_0+1), Y.fx(q)=1);

);

 

 

Model MIP2

        /

         obj

         cone_block_op

         cpreced2

         cincusion_st

         cexclusion_bl

         cexclusion_st

         clb_block_time1

         clb_block_time2

         cub_station_time

         cexist_block

         cexist_station

         ccont_block

         ccont_station

         cut_station

         cut_block

        /;

 

MIP2.NodLim = 1e09;

MIP2.holdfixed = 1;

 

option mip = CPLEX;

option optcr = 0.0;

option optca = %ABS_ERROR_CPLEX%;

option reslim = %CPU_TIME_CPLEX%;

option iterlim = 1e08;

option solprint = off;

 

file series_report / results.csv /;

series_report.ap=1;

put series_report;

put " ";

 

Solve MIP2 using MIP minimizing cost;

 

put series_report;

put "f best found  , CPLEX CPU time (sec), CPU time given (sec) , modelstat flag;

put solvestat flag, variables, LB, Use (7')? " /;

 

if(not(execerror) and (MIP2.modelstat=1  or MIP2.modelstat=8 ),

  put cost.l, " , ", MIP2.resusd, " , ", %CPU_TIME_CPLEX% , " , ",MIP2.modelstat;

 put " , ", MIP2.solvestat , " , ", MIP2.numvar , " , ", MIP2.objest, ", ",UseEq7Prime;

else

  put "NOT FOUND", " , ", " , ", %CPU_TIME_CPLEX% , " , ", MIP2.modelstat;

put " , ", MIP2.solvestat , " , ", MIP2.numvar, ", ", " , ", UseEq7Prime;

);

 

display X.l;