#include <iostream>	
#include<time.h>
#include<vector>

#define Times 80000			//循环次数
#define Job 70				//工件数 
#define Stg 6					//阶段数
#define Tim 2					//重入次数
#define Machine 18	//机器数
int stage_m[Stg] = { 2,3,4,2,3,4 };		//表示一次完整过程中，各个阶段的机器数

#define random(X) (rand()%X)
double job_time[Job][Stg];					//表示工件各个阶段的加工时间,注意！是各个阶段，因为每个阶段的机器加工时间相等
int summ = 0;    //记录次数
double value[10] = { 0 };  //记录值
double total_time[10] = { 0 };	//记录时间
double best_value;
double worst_value;
double average_value;
double average_time;

clock_t start, finish;

using namespace std;

struct individual
{
	int seq[Job*Tim];  //工件序列
	double val;        //最大加工时间
};


//填上工件在每个阶段的时间信息
void set_job_time()
{
	for (int i = 0; i < Job; i++)
	{
		for (int j = 0; j < Stg; j++)
		{
			job_time[i][j] = 1 + (double)random(20);
		}
	}
}

//初始化种群
void Creat_Pop(individual & solution)
{
	/*srand((int)time(NULL));*/
	int tmp[Job*Tim] = { 0 }, flag[Job*Tim] = { 0 };
	int m = 0;
	for (int i = 1; i <= Job; i++)
	{
		for (int j = 0; j < Tim; j++)
		{
			tmp[m++] = i;
		}
	}

	int num = 0, index = 0;
	while (num < Job*Tim)
	{
		int X = Job*Tim;
		index = random(X);
		while (flag[index] == 1)
			index = random(X);
		flag[index] = 1;
		solution.seq[num++] = tmp[index];
	}

}


//随机选两点互换
void Variation1(individual &solution)
{
	/*srand((int)time(NULL));*/
	int point1, point2, tmp, L = Job*Tim;
	point1 = random(L);
	point2 = random(L);
	while (point2 == point1 || solution.seq[point1] == solution.seq[point2])
		point2 = random(L);
	tmp = solution.seq[point1];
	solution.seq[point1] = solution.seq[point2];
	solution.seq[point2] = tmp;
}


//随机选一点(point1)重新插入位置point2
void Variation2(individual &solution)
{
	int point1, point2, L = Job*Tim;
	/*srand((int)time(NULL));*/
	point1 = random(L);
	point2 = random(L);
	while (point2 == point1)
		point2 = random(L);
	if (point1 > point2)
	{
		int tmp = point1;
		point1 = point2;
		point2 = tmp;
	}

	//往后插入
	if (point1 < point2)
	{
		int tmp = solution.seq[point1];
		for (int i = point1; i < point2; i++)
		{
			solution.seq[i] = solution.seq[i + 1];
		}
		solution.seq[point2] = tmp;
	}

	//往前插入
	if (point1 > point2)
	{
		int tmp = solution.seq[point1];
		for (int i = point1; i > point2; i--)
		{
			solution.seq[i] = solution.seq[i - 1];
		}
		solution.seq[point2] = tmp;
	}
}

//解码,传过来一个引用,
void Encode(individual &tmp)
{
	summ++;

	double M[Machine] = { 0 };									//所有机器上时间标志
	int j = 0, job, index, max_m, min_m, now_m;  //index：该阶段的第一台机器号；job：当前加工的工件号
	double min, max, min2, last, now;				//last：工件在上一阶段的完成时间；now：当前阶段的开始时间；
													//min：当前阶段的最早开始时间 max：当前阶段的最晚开始时间
	double job_infm[Job] = { 0 };		//存储每一个工件的时间信息



	while (j <(Job*Tim))
	{
		index = 0;
		job = tmp.seq[j++] - 1;
		for (int stage = 0; stage < Stg; stage++)   //stage：工件加工的当前阶段
		{
			min = 10000, max = -2, min2 = 10000;
			if (stage == 0)
			{
				last = job_infm[job];
			}
			if (stage_m[stage] == 1)
			{
				now = (M[index]>last) ? M[index] : last;
				now_m = index;
			}
			else
			{
				for (int i = index; i < (index + stage_m[stage]); i++)
				{
					if (M[i] < min)
					{
						min = M[i];
						min_m = i;
					}
					if (M[i] > max)
					{
						max = M[i];
						max_m = i;
					}
				}
				if (last <= min)
				{
					now = min;
					now_m = min_m;
				}
				else if (last >= max)
				{
					now = last;
					now_m = max_m;
				}
				else
				{
					for (int i = index; i < (index + stage_m[stage]); i++)
					{
						if (M[i] <= last && (last - M[i]) < min2)
						{
							now_m = i;
							min2 = (last - M[i]);
						}
					}
					now = last;
				}
			}
			index += stage_m[stage];
			last = now + job_time[job][stage];
			M[now_m] = last;
			job_infm[job] = last;
		}
	}



	tmp.val = 0;
	for (int i = 0; i < Machine; i++)
	{
		if (tmp.val < M[i])
			tmp.val = M[i];
	}


}

int main()
{
	srand(0);
	set_job_time();

	cout << "no-insert VNS" << endl;
	cout << "\nrepeat_times is: " << Times << "    ;Job is: " << Job << "    ;Stage is:  "
		<< Stg << endl;
	for (int circle = 0; circle < 10; circle++)
	{
		rand();
		summ = 0;
		start = clock();
		individual m1;  //定义一个个体
		Creat_Pop(m1);  //初始化该个体
		Encode(m1);
		individual tmp1 = m1;
		while (1)
		{
			if (summ >= Times)
			{
				value[circle] = m1.val;
				/*for (int z = 0; z < Job*Tim; z++)
				cout << m1.seq[z] << " ";
				cout << "\n";*/
				finish = clock();
				total_time[circle] = (double)(finish - start) / CLOCKS_PER_SEC;

				//cout << "value:" << m1.val << "\ntime:" << total_time[circle] << endl;
				break;
			}

			tmp1 = m1;
			Variation1(tmp1);
			Encode(tmp1);
			if (tmp1.val <= m1.val)
			{
				m1 = tmp1;
				continue;
			}
			else
			{
				tmp1 = m1;
				Variation2(tmp1);
				Encode(tmp1);
				if (tmp1.val <= m1.val)
				{
					m1 = tmp1;
				}
			}

		}
	}

	double maxx = -1, minn = 10000;
	for (int i = 0; i < 10; i++)
	{
		if (value[i] > maxx)
		{
			maxx = value[i];
			worst_value = maxx;
		}
		if (value[i] < minn)
		{
			minn = value[i];
			best_value = minn;
		}
		average_value += value[i];
		average_time += total_time[i];
	}
	cout << "\n the best value of every round is:" << endl;
	for (int i = 0; i < 10; i++)
		cout << value[i] << " ";

	cout << "\n the best value is:" << best_value;
	cout << "\n the worst value is:" << worst_value;
	cout << "\n the average value is:" << average_value / 10;
	cout << "\n the average  program's runing time:" << average_time / 10;
	return 0;


}