//Machine Scheduling Problem
//Compiled by Microsoft Visual C++6.0
//Written by Yuan Gao in 2009
//Copyright by Uncertainty Theory Laboratory
#include<iostream>
#include<cmath>
#include<ctime>

using namespace std;

const int M=3;  // number of machines
const int N=7;  // number of jobs
const double pi=3.1415926;
const double e=2.7182818;

const int TYPE=-1; // 1=max;-1=min
const int GEN=1000; // maximum generation number
const int POP_SIZE=30; // population size 
const double P_MUTATION=0.2; // probablity of mutation 
const double P_CROSSOVER=0.7; // probablity of crossover


int CHROMOSOME[POP_SIZE+1][N+1];
double OBJECTIVE[POP_SIZE+1];
double q[POP_SIZE+1];
double temp[POP_SIZE+1][N+1];
double info[1+N][1+M][100];


static void  initialization(void);
static void  evaluation(int gen);
static void  selection(void);
static void  crossover(void);
static void  mutation(void);
static void  objective_function();


void constructinfo() //construct the 99 table of each variable
{
	double a[M][N]={{1,2,3,4,5,6,7},{1,2,3,4,5,6,7},{1,2,3,4,5,6,7}};
	double b[M][N]={{2,3,4,5,6,7,8},{3,4,5,6,7,8,9},{4,5,6,7,8,9,10}};
	int i,j,h;
	for(i=1;i<=N;i++){
		for(j=1;j<=M;j++){
			for(h=1;h<=99;h++){
				info[i][j][h]=a[j-1][i-1]+(b[j-1][i-1]-a[j-1][i-1])*h/100.;
			}
		}
	}
}



int main()
{
	constructinfo();
	srand((int)time(0));

	int i,j;
	double a;
	
	q[0]=0.05; a=0.05;
	for(i=1; i<=POP_SIZE; i++){
		a=a*0.95; q[i]=q[i-1]+a;
	}
	
	initialization();
	evaluation(0);
	for(i=1;i<=GEN;i++){
		selection();
		crossover();
		mutation();
		evaluation(i);
	}
	
	cout<<"The Machine Scheduling should be"<<endl;
	for(j=1;j<=M;j++){
		cout<<"The "<<j<<" machine processes: " ;
		for(i=1;i<=N;i++){
			if(CHROMOSOME[0][i]==j){
				cout<<" "<<i;
			}
		}
		cout<<endl;
	}
	cout<<"The expected makespan is: "<<OBJECTIVE[0]<<endl;
		
	return 1;
}


static void objective_function()
{
	int i,j,k,h;double a;
	double table[1+M][100];
	for(i=1;i<=POP_SIZE;i++){
		for(k=0;k<=M;k++)
			for(h=0;h<=99;h++)table[k][h]=0;
		for(j=1;j<=N;j++){
			k=CHROMOSOME[i][j];
			for(h=1;h<=99;h++){
				table[k][h]+=info[j][k][h];
			}
		}
		for(h=1;h<=99;h++){
			a=0;
			for(k=1;k<=M;k++){
				if(a<table[k][h])a=table[k][h];
			}
			table[0][h]=a;
		}
		a=0;
		for(h=1;h<=99;h++){
			a+=table[0][h];
		}
		OBJECTIVE[i]=(double)a/99.;
	}
}


static void  initialization()
{
	int i,j;
	for(i=1;i<=POP_SIZE;i++){
		for(j=1;j<=N;j++){
			CHROMOSOME[i][j]=rand()%M+1;
		}
	}
}
	
static void evaluation(int gen)
{
	double a;
	int i,j,k,label;
	objective_function();
	if(gen==0){
		OBJECTIVE[0]=OBJECTIVE[1];
		for(j=1;j<=N;j++)CHROMOSOME[0][j]=CHROMOSOME[1][j];
	}
	for(i=1;i<POP_SIZE;i++){
		label=0;a=OBJECTIVE[i];
		for(j=i+1;j<=POP_SIZE;j++){
			if((TYPE*a)<(TYPE*OBJECTIVE[j])){
				a=OBJECTIVE[j];
				label=j;
			}
			if(label!=0){
				a=OBJECTIVE[i];
				OBJECTIVE[i]=OBJECTIVE[label];
				OBJECTIVE[label]=a;
				for(k=1;k<=N;k++){
					a=CHROMOSOME[i][k];
					CHROMOSOME[i][k]=CHROMOSOME[label][k];
					CHROMOSOME[label][k]=a;
				}
			}
		}
	}
	if(TYPE*OBJECTIVE[0]<TYPE*OBJECTIVE[1]){
		OBJECTIVE[0]=OBJECTIVE[1];
		for(j=1;j<=N;j++)
			CHROMOSOME[0][j]=CHROMOSOME[1][j];
	}
}


static void selection()
{
	double r;
	int i,j,k;
	for(i=1;i<=POP_SIZE;i++){
		r=q[POP_SIZE]*(rand()/RAND_MAX);
		for(j=0;j<=POP_SIZE;j++){
			if(r<=q[j]){
				for(k=1;k<=N;k++) temp[i][k]=CHROMOSOME[j][k];
				break;
			}
		}
	}
	for(i=1;i<=POP_SIZE;i++)
		for(k=1;k<=N;k++)
			CHROMOSOME[i][k]=temp[i][k];
}

static void crossover()
{
	int i,j,jj,k,pop,r;
	int x[N+1],y[N+1];
	pop=POP_SIZE/2;
	for(i=1;i<=pop;i++) {
		if((double)rand()/RAND_MAX>P_CROSSOVER) continue;
		j=1+rand()%POP_SIZE;
		jj=1+rand()%POP_SIZE;
		r=1+rand()%N;
		for(k=1;k<=N;k++){
			if(k<=r){
				x[k]=CHROMOSOME[j][k];
				y[k]=CHROMOSOME[jj][k];
			}
			if(k>r){
				x[k]=CHROMOSOME[jj][k];
				y[k]=CHROMOSOME[j][k];
			}
		}
	}
}

static void mutation()
{	
	int i,r;
	for(i=1;i<=POP_SIZE;i++) {
		if((double)rand()/RAND_MAX>P_MUTATION) continue;
		r=1+rand()%N;
		CHROMOSOME[i][r]=rand()%M+1;
	}
}