#!/usr/local/bin/perl -w
use List::Util qw(shuffle);
@a = 1..4;
@b = 1..4;
for $i (@a){
for $j (@b){
push @team, $i.$j;
$N++; # number of combinations
}
}
$m = @a; # size of a group
$d = int $N/$m; # distance OK
$penalty[0]=0;
for $i (1..$N){
if ($i < $d){
$penalty[$i] = 3**($d-$i);
}else{
$penalty[$i]=0;
}
}
$min=9e99;
while(1){
@steam = shuffle(@team);
%hash=();
$count=0;
for $i (@steam){
$count++;
$hash{$i}=$count;
}
$err=0;
for $k (@steam){
($i,$j) = split "", $k;
for $z (@a){
$dist = abs($hash{$k} - $hash{$z.$j});
$err += $penalty[$dist];
}
for $z (@b){
$dist = abs($hash{$k} - $hash{$i.$z});
$err += $penalty[$dist];
}
}
if ($err<=$min){
$min=$err;
print "$err) @steam\n";
}
}
__END__
#From saravanan.vsn@gmail.com Tue Apr 20 16:22:38 2010
#Date: Tue, 20 Apr 2010 09:22:38 -0700 (PDT)
#From: "saravanan.vsn@gmail.com"
#Newsgroups: sci.op-research
#Subject: Sequence Problem
Hi All,
I have been working on a sequencing/matching problem,
Problem Description:
I have two groups of people who have to attend trainings as a pair in
the weekend (only one pair taken for training for a weekend), now with
each group having 4 people each, so there will be 16 combinations ,
added to that I would need to balance the distance between the
trainings for each of the trainees.Example (a1,a2,a3,a4) belong to
group A and (b1,b2,b3,b4) belong to group B, then the sequence of
training schedule for each of the trainees has to get balanced
( number of weeks in between the trainings) and ofcourse all the
combinations between groupA and groupB are to be met (this has a
structure of scheduling matches between teams in round-robin fashion).
I modelled this as math program and solved with Cplex, but the
combinations /no. of constraints/variables are very exhaustive, due to
this combinatorial nature. I wonder what would happen if I have to
expand to may groups/trainees.
Any better algorithm/meta heuristic, I should look into ?. Thanks in
advance.
Regards,
Saravanan.V
60) 31 42 23 34 12 21 43 14 32 41 13 22 44 11 33 24