#!/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" <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