carseq.gms : Car Sequencing

Description

A number of cars are to be produced; they are not identical, because
different options are available as variants on the basic model. The
assembly line has different stations which install the various options
(air-conditioning, sun-roof, etc.). These stations have been designed
to handle at most a certain percentage of the cars passing along the
assembly line. Furthermore, the cars requiring a certain option must not
be bunched together, otherwise the station will not be able to cope.
Consequently, the cars must be arranged in a sequence so that the capacity
of each station is never exceeded. For instance, if a particular station
can only cope with at most half of the cars passing along the line, the
sequence must be built so that at most 1 car in any 2 requires that option.
The problem has been shown to be NP-hard (Gent 1999).

This is the example given in Dincbas, et al. More instances can
be downloaded from CSPLib (problem prob001).


References

  • Kodratoff, Y, Ed, Proceedings of the 8th European Conference on Artificial Intelligence (ECAI 88), 1988.
  • Dincbas, M, Simonis, H, and Van Hentenryck, P, Solving the Car Sequencing Problem in Constraint Logic Programming. In Kodratoff, Y, Ed, Proceedings of the 8th European Conference on Artificial Intelligence (ECAI 88). Pitmann Publishing, 1988, pp. 290-295.

Large Model of Type : MINLP


Category : GAMS Model library


Main file : carseq.gms

$Title Car Sequencing  (CARSEQ,SEQ=407)
$ontext
A number of cars are to be produced; they are not identical, because
different options are available as variants on the basic model. The
assembly line has different stations which install the various options
(air-conditioning, sun-roof, etc.). These stations have been designed
to handle at most a certain percentage of the cars passing along the
assembly line. Furthermore, the cars requiring a certain option must not
be bunched together, otherwise the station will not be able to cope.
Consequently, the cars must be arranged in a sequence so that the capacity
of each station is never exceeded. For instance, if a particular station
can only cope with at most half of the cars passing along the line, the
sequence must be built so that at most 1 car in any 2 requires that option.
The problem has been shown to be NP-hard (Gent 1999).

This is the example given in Dincbas, et al. More instances can
be downloaded from CSPLib (problem prob001).


Dincbas et al., Dincbas, M., Simonis, H., and Van Hentenryck, P.
Solving the car-sequencing problem in constraint logic programming.
In 8th European Conference on Artificial Intelligence (ECAI 88) ,
Y. Kodratoff, Ed. Pitmann Publishing, London, Munich, Germany, 290-295, 1988

$offtext

Sets p  position
     o  options
     c  classes

Parameter
     maxc(o)        maximum number of cars with that option in a block
     bs(o)          block size to which the maximum number maxc refers
     classData(c,*) class data;

$if not set instance $set instance
$ifthen '%instance%'==''
Sets p  position  / pos1*pos10    /
     o  options   / opt1*opt5     /
     c  classes   / class1*class6 /

Parameter
     maxc(o) maximum number of cars with that option in a block /
                    (opt1,opt3,opt5) 1, (opt2,opt4) 2
                  /
     bs(o)   block size to which the maximum number maxc refers /
                     opt1 2, (opt2,opt3) 3, (opt4,opt5) 5
                  /
Table classData(c,*) class data
       numCars opt1 opt2 opt3 opt4 opt5
class1    1     1    0    1    1    0
class2    1     0    0    0    1    0
class3    2     0    1    0    0    1
class4    2     0    1    0    1    0
class5    2     1    0    1    0    0
class6    2     1    1    0    0    0;
$else

$onecho > cs.awk
BEGIN { nr=1 }
!/^#/ {
   if (nr==1) {
      o = $2;
      printf("set p /1*%d/, o /1*%d/, c /1*%d/\n", $1,o,$3)
   } if (nr==2) {
      printf("Parameter maxc(o) / 1 %d", $1);
      for (j=2; j<=o; j++) printf(", %d %d", j, $j);
      printf("/\n");
   } if (nr==3) {
      printf("Parameter bs(o) / 1 %d", $1);
      for (j=2; j<=o; j++) printf(", %d %d", j, $j);
      printf("/\n");
   } if (nr==4) {
      printf("Table classData(c,*)\n$ondelim\nclass,numCars");
      for (j=1; j<=o; j++) printf(",%d", j);
      printf("\n");
   } if (nr>3) {
      printf("%d,%d", $1+1, $2)
      for (j=1; j<=o; j++) printf(",%d", $(j+2));
      printf("\n");
   }
   nr++;
}
END { printf("$offdelim\n;") }
$offecho
$call awk -f cs.awk %instance% > "%gams.scrdir%csinst.%gams.scrext%"
$if errorlevel 1 $abort Problems running awk
$include "%gams.scrdir%csinst.%gams.scrext%"
$endif

abort$(card(p)<>sum(c, classData(c,'numCars'))) 'inconsistent number of cars';

alias (p,pp)
Sets blk(o,p)     blocks of positions to monitor
     blkc(o,p,pp) positions in the blocks;
blkc(o,p,pp)$(ord(p)<=card(p)-bs(o)+1) = ord(pp)>=ord(p) and ord(pp)<ord(p)+bs(o);
blk(o,p) = sum(pp$blkc(o,p,pp), 1);

Variable sumc(o,p);
Variables
     cp(c,p)  class k is scheduled at position p
     op(o,p)  option o appears at position p
     v(o,p)   violations in a block
     obj      sum of violations
     ;

Binary Variable cp;
$ifthen set MIP
  Positive variable v;
  Binary Variable op;
$endif

Equations
     defnumCars(c) exactly numCars of class c assigned to positions
     defoneCar(p)  one car assigned to each position p
     defop(o,p)    option o appears at position p
     defopLS(o,p)  option o appears at position p
     defviol(o,p)  violations in a block
     defviolLS(o,p) violations in a block
     defobj        minimize violations;

defnumCars(c)..     sum(p, cp(c,p)) =e= classData(c,'numCars');

defoneCar(p)..      sum(c, cp(c,p)) =e= 1;

defop(o,p)..        sum(c$classData(c,o),cp(c,p)) =l= op(o,p);

 Equation defsumc(o,p);
defsumc(o,p)..      sumc(o,p) =e= sum(c$classData(c,o),cp(c,p));
defopLS(o,p)..      op(o,p) =e= ifthen(sumc(o,p)>=0.5, 1, 0);
*defopLS(o,p)..      op(o,p) =e= ifthen(sum(c$classData(c,o),cp(c,p))>0.5, 1, 0);


defviol(blk(o,p)).. sum(blkc(blk,pp), op(o,pp)) =l= maxc(o) + v(o,p);
defviolLS(blk(o,p)).. v(o,p) =e= max(sum(blkc(blk,pp), op(o,pp)) - maxc(o), 0);

defobj..            obj =e= sum(blk(o,p), v(o,p));

model carseqMIP / all - defopLS - defviolLS - defsumc /
      carseqLS  / all - defop   - defviol /;

option optcr = 0;

$ifthen set MIP
  Positive variable v;
  Binary Variable op;
  solve carseqMIP min obj us mip;
$else
  solve carseqLS min obj us minlp;
$endif

Parameter rep(p,c,o);
rep(p,c,o)$(cp.l(c,p)>0.5) =  classData(c,o);
option rep:0:2:1; display rep;