Benchmarks Library Transfer Line Balancing Problem

 GAMS-model Benchmarks   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;