模拟退火算法解决作业车间调度问题（Job Shop Scheduling, JSP）

#include <bits/stdc++.h> #define mme(i,j) memset(i,j,sizeof(i))//新申请的内存做初始化工作 #define ll long long int #define maxs 202020 #define NUM 110 #define T 3000//系统的初始温度，需要达到一个高温的状态，保证粒子可以足够自由运动，放在组合优化中，就是我们的解的覆盖性尽可能全 #define EPS 1e-8 #define DELTA 0.98//温度衰减率，控制降温的快慢 //若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值 //所以一般的选取就是0.95--0.99 #define LIMIT 10000//概率选择上限 #define OUTLOOP 1000//内循环 #define INLOOP 15000//外循环 using namespace std; int tmp[20];//所有工序号的全排列 int lj,jq;//零件数量、机器数量 int vis[10][20],gt[15][20]; int k[10]; int num[6]; int matime[6];//数组为当前机器上次在工作的时间 int wktime[6];//为本任务上次执行的时间 int gx=0;//工序的总和 int finaltime = INT_MAX;//机器最长加工时间 int knum = 0; int temp; int flag = 0; struct work { int id;//工作号 int machine; int time; int num;//工序号 } a[100],b[100]; void Init()//定义初始解空间，解决编号问题，需要通过赋值写入的方式 { mme(matime,0); mme(num,0); mme(wktime,0); mme(vis,0); int id; for(int i=0; i<gx; i++) //gx为所有工序的总和 //wktime为本任务上次执行的时间 //wktime为本任务上次执行的时间 { id = a[tmp[i]].id;//当前任务所属标号 //如果现在排列的工序的前一个工序没有执行，直接跳出函数 if(num[id] != a[tmp[i]].num) return; //如果符合,则 num[id]++;//表示可进入目前工序的加工，用来下一次判断 if(matime[a[tmp[i]].machine] < wktime[a[tmp[i]].id])//机器在工作 { for(int kk=1; kk<=a[tmp[i]].time ; kk++) { if(vis[a[tmp[i]].machine][wktime[a[tmp[i]].id]+kk]==0)//状态数组未被写过，则赋值 vis[a[tmp[i]].machine][wktime[a[tmp[i]].id]+kk]=a[tmp[i]].id+1; } matime[a[tmp[i]].machine] = wktime[a[tmp[i]].id] = wktime[a[tmp[i]].id] + a[tmp[i]].time;// //机器本次工作的时间记录 } else//机器是空闲的 { for(int kk=1; kk<=a[tmp[i]].time; kk++) { vis[a[tmp[i]].machine][matime[a[tmp[i]].machine] + kk] = id+1; } matime[a[tmp[i]].machine] = wktime[a[tmp[i]].id] = matime[a[tmp[i]].machine] + a[tmp[i]].time; } } //所有序列组合判断结束，使用temp记录本次结果 temp=-1; for(int i=0; i<jq; i++) { temp=max(matime[i],temp);//总时间 } if(temp<finaltime) { finaltime=temp; mme(gt,0); for(int i=0; i<jq; i++) { for(int j=0; j<=finaltime; j++) { gt[i][j]=vis[i][j];//保存最优态 } } flag = 1; } } //搜索邻域解空间，这也就是刚才讲到的第一步，由当前解构造出新解，交换工序，之后就得在判断是不是合法的序列 int GetNext() {//使用随机数选择[1,cnt]之间的两个工序， int x = (int)(knum * (rand() / (RAND_MAX + 1.0))); int y = (int)(knum * (rand() / (RAND_MAX + 1.0))); while(x==y) { x = (int)(knum * (rand() / (RAND_MAX + 1.0))); y = (int)(knum * (rand() / (RAND_MAX + 1.0))); } swap(tmp[x],tmp[y]); mme(matime,0); mme(num,0); mme(wktime,0); mme(vis,0); //判断这个序列是否合法，合法则执行出结果temp，合法直接退出 int id; for(int i=0; i<gx; i++) { id = a[tmp[i]].id;//当前任务所属标号 if(num[id] != a[tmp[i]].num) return 0; num[id]++; if(matime[a[tmp[i]].machine] < wktime[a[tmp[i]].id])//machine is working { for(int kk=1; kk<=a[ tmp[i] ].time ; kk++) { if(vis[a[tmp[i]].machine][wktime[a[tmp[i]].id]+kk]==0) vis[ a[tmp[i]].machine][wktime[a[tmp[i]].id]+kk]=a[tmp[i]].id+1; } matime[a[tmp[i]].machine] = wktime[a[tmp[i]].id] = wktime[a[tmp[i]].id] +a[tmp[i]].time; } else//mathine is waiting { for(int kk=1; kk<=a[tmp[i]].time; kk++) { vis[a[tmp[i]].machine][matime[a[tmp[i]].machine]+ kk] = id+1; } matime[a[tmp[i]].machine] = wktime[a[tmp[i]].id] = matime[a[tmp[i] ].machine] + a[tmp[i]].time; } } temp=-1; for(int i=0; i<jq; i++) { temp=max(matime[i],temp);//总时间 } return temp; } //退火部分 int SA() { double t = T;//初始温度T srand(time(NULL)); int CurCost = temp; int NewCost = temp; int P_L = 0; int P_F = 0; while(1) {//外循环，主要更新参数t， for(int i=0; i<OUTLOOP; i++)//内循环，寻找一定温度的最优值，内循环则是用于决定在各温度下产生候选解的数目。 { //产生一个可行解 while(!GetNext()) { ; } NewCost = temp;//为新解赋值 double dE = NewCost - CurCost;//公式中的变化量 if(dE<0)//表达移动后得到更优解，则总是接受移动，如果找到更优解，直接更新//计算增量的好处 { CurCost = NewCost; finaltime = temp; //更新甘特图 for(int i=0; i<jq; i++) { for(int j=0; j<=finaltime; j++) { gt[i][j]=vis[i][j];//保存最优态 } } P_L = 0;P_F = 0; } else { double rd = rand() / (RAND_MAX + 1.0);//如果找到比当前更差的解，以一定概率接受该解，并且这个概率会越来越小 if(exp(dE/t)>rd&&exp(dE/t)<1) { CurCost = NewCost; } P_L++; } //内循环超限 if(P_L > LIMIT) { P_F++; break; } } //内循环条件判断，择机跳出退火过程 if(P_F > OUTLOOP || t < EPS) break; t *= DELTA; } } int main() {cout<<"#####机器编号从0开始#####"<<endl; cout<<"#####零件编号从1开始#####"<<endl; cout<<endl; cout<<"请输入零件数量和机器数量："<<endl; while(~scanf("%d%d",&lj,&jq)) { for(int i=0; i<lj; i++) {cout<<"请输入"<<i+1<<"号零件加工的工序数："; cin>>k[i]; knum+=k[i]; for(int j=0; j<k[i]; j++) {cout<<"请输入第"<<j+1<<"步工序加工机器的编号和加工时间："; cin>>a[gx].machine>> a[gx].time; a[gx].id=i;//属于哪个工作 a[gx].num=j;//第几个工序 gx++; } } for(int i=0; i<=gx; i++) tmp[i]=i; do { Init(); if(flag)break; } while(next_permutation(tmp,tmp+gx));//做全排列 SA(); cout<<"最优时间是 "<<finaltime; for(int i=0; i<jq; i++) {cout<<"\n"<<i<<"号机器"<<"的加工流程线："; for(int j=1; j<=finaltime; j++) { cout<<gt[i][j]; } } } }