aco.rar_ACO_aco 调度_flow shop_零空闲

#include "tail20_5.h" //#include <afxwin.h> #include<iostream.h> #include<stdlib.h> #include<time.h> #include<iomanip.h> #include<fstream.h> #include<math.h> #define PL 0.75 #define MAX_MACHINES 20 #define MAX_JOBS 500 #define MAX_PSIZE 1000 #define START 1 #define END 120 double pheromone_trail[MAX_JOBS][MAX_JOBS]; int gjob,gmachine； short job_mach1; struct jobmac { int number;//工件序号 int timemac[MAX_MACHINES];//每一台机器上的运行时间 //int sche;//调用状态 int summac;//所有机器上的运行时间之和 }job[MAX_JOBS]; void SetPTime_Ta(int InstanceNo)/*Get the instance process time*/ { switch(InstanceNo/10) { case 0:gjob=20; gmachine=5;break; case 1:gjob=20; gmachine=10;break; case 2:gjob=20; gmachine=20;break; case 3:gjob=50; gmachine=5;break; case 4:gjob=50; gmachine=10;break; case 5:gjob=50; gmachine=20;break; case 6:gjob=100; gmachine=5;break; case 7:gjob=100; gmachine=10;break; case 8:gjob=100; gmachine=20;break; case 9:gjob=200; gmachine=10;break; case 10:gjob=200; gmachine=20;break; case 11:gjob=500;gmachine=20;break; } } void intial() { int i,j,k=0; for(i=0;i<gmachine;i++) { for(j=0;j<gjob;j++) job[j].timemac[i]=ch2[k++]; } for(i=0;i<gjob;i++) //job[i].sche=0; { job[i].number=0; job[i].summac=0; } } void mactime()//求解一个工件在所有机器上的运行时间之和 { int i,j; for(i=0;i<gjob;i++) { job[i].summac=0; for(j=0;j<gmachine;j++) job[i].summac+=job[i].timemac[j]; } } void jobsort()//按每个工件的运行时间降序排列 { int i,j,max,sort; for(i=0;i<gjob;i++) { max=0; for(j=0;j<gjob;j++) { if(job[j].number==0&&job[j].summac>max) //对当前工件序号为0的工件进行比较 { max=job[j].summac; sort=j; } } job[sort].number=i+1;//每次i值对应所选工件的序号 } } void copy(int sub[],int subpath[])//复制序列subpath->sub { int i; for(i=0;i<gjob;i++) sub[i]=subpath[i]; } int timemac1(int subpath[],int num)//求出所有工件在第一台机器上的运行时间之和 { int i,k; int sumtime=0; for(i=0;i<num;i++) { k=subpath[i];//数组值所对应的是工件的序号 sumtime+=job[k].timemac[0]; } return(sumtime); } int max(int f,int job)//比较f-job与0 的大小 { if(f-job>0) return(f-job); else return(0); } void fmach(int f[],int subpath[],int num)//求解相邻机器的最大完工时间差 { int i,j,k; for(i=0;i<num;i++) { k=subpath[i];//工件序号 if(i==0) { for(j=1;j<gmachine;j++) f[j]=job[k].timemac[j];//当只有一个工件时两相邻机器的完工时间差等于该工件在第二台机器的时间 } else for(j=1;j<gmachine;j++) f[j]=job[k].timemac[j]+max(f[j],job[k].timemac[j-1]); } } int cmax(int subpath[],int num)//求解一个序列的最大完工时间 { int j,f[MAX_MACHINES],cmax1=0; fmach(f,subpath,num); for(j=1;j<gmachine;j++) cmax1+=f[j]; cmax1+=timemac1(subpath,num); return(cmax1); } void initial_pheromonetrails(int zbest) { int i,j; for(i=0;i<gjob;i++) for(j=0;j<gjob;j++) pheromone_trail[i][j]=1/(PL*zbest);//将工件在每个位置上的信息素密度赋相等的初值 } int max_pheromonetrails(int sub[],int k) { int job,sit,line,maxline=0; double sum,max=0; for(job=0;job<5;job++)//对所选的5个工件求出它们每个在k位置的和，找出最大的工件的序号maxline { if(sub[job]==gjob) break; sum=0;line=sub[job]; for(sit=0;sit<=k;sit++) sum+=pheromone_trail[line][sit]; //sum=pheromone_trail[line][k]; if(sum>max) { max=sum; maxline=sub[job]; } } return(maxline); } void delet_maxline(int schejob[],int maxline,int k) { int i=0,j; for(i=0;i<gjob;i++) { if(schejob[i]==maxline) { for(j=i;j<gjob-1;j++) schejob[j]=schejob[j+1]; schejob[gjob-1]=gjob;break; } } } void print_sub(int sub[],int cmax[]) { int i; ofstream ofile; ofile.open("jieguo.txt",ios::app); for(i=0;i<gjob;i++) ofile<<setw(5)<<sub[i]+1; ofile<<endl; for(i=0;i<20;i++) ofile<<setw(5)<<cmax[i]; ofile<<endl; ofile<<"*********************"<<endl; } int max_select_p(double selectjob_p[],int p)//运用转轮法选择工件 { int i,maxline; double max=1,u; u=double(rand())/double(RAND_MAX); for(i=0;i<p;i++) { if(fabs(u-selectjob_p[i])<max) { max=fabs(u-selectjob_p[i]); maxline=i; } } return(maxline); } int _selectjobP(int sub[],int k) { int q,i,job,maxline,p=5; double sum=0,ssum=0,maxp=0,k1=0; double selectjob_p[5]; for(i=0;i<5;i++) { if(sub[i]==gjob) {p=i;break;} job=sub[i];sum=0; for(q=0;q<=k;q++) sum+=pheromone_trail[job][q]; ssum+=sum;selectjob_p[i]=sum; } for(i=0;i<p;i++) selectjob_p[i]=selectjob_p[i]/ssum; maxline=max_select_p(selectjob_p,p); return(sub[maxline]);//将选择概率最大的工件返回 } void update_pheromonetraila(int subpath[],int zbest)//更新信息素密度 { int i,j; for(i=0;i<gjob;i++) { for(j=0;j<gjob;j++) pheromone_trail[i][j]*=(1-PL); pheromone_trail[i][subpath[i]]+=1/zbest; if(pheromone_trail[subpath[i]][i]>1) pheromone_trail[subpath[i]][i]=1; if(pheromone_trail[subpath[i]][i]<0.2) pheromone_trail[subpath[i]][i]=0.2; } } void print(int subpath[],int cmax) { int i; ofstream ofile; ofile.open("jieguo.txt",ios::app); ofile<<"调度序列为："; for(i=0;i<gjob;i++) ofile<<subpath[i]+1<<" "; ofile<<endl; ofile<<"最大完工时间="<<cmax<<endl; } short neh(int subpath[])//运用NEH算法调度工件 { int i,j,k,p,num=0,sub[MAX_JOBS],best[MAX_JOBS],cma,max; jobsort(); for(i=0;i<gjob;i++) { k=0; while(job[k].number!=i+1) k++;//第i次选择工件 if(num==0) subpath[0]=k;//第一个时间和最大的工件放入数组中 else { max=9999; for(j=0;j<=num;j++)//所选工件有num+1个位置插入 { copy(sub,subpath); for(p=num-1;p>=j;p--)//移动工件，插入所选工件到当前位置 sub[p+1]=sub[p]; sub[j]=k; //对选择的工件进行位置选择，使最大完工时间最小 cma=cmax(sub,num+1); //计算该位置的最大完工时间 if(cma<max) { max=cma; copy(best,sub); } } copy(subpath,best); } num++; } print(subpath,max);return(max); } int position(int subpath[MAX_JOBS],int k) { int i; for(i=0;i<gjob;i++) if(k==subpath[i]) break; return(i); } void emach(int e[],int fe[],int subpath[],int num) { int i,j,k; for(i=num;i>0;i--) { k=subpath[i]; if(i==num) { for(j=1;j<gmachine;j++) { e[j]=job[k].timemac[j-1];//当只有一个工件时两相邻机器的开工时间差等于该工件在第一台机器的时间 fe[j]=job[k].timemac[j]; } } else for(j=1;j<gmachine;j++) { e[j]=job[k].timemac[j-1]+max(e[j],job[k].timemac[j]); fe[j]=fe[j]+max(job[k].timemac[j],e[j]); } } } int quickseach(int gbest[],int zbest)//对最佳微粒的位置进行邻域搜索 { int i,j,k,k1,ps,subpath[MAX_JOBS],fN[MAX_MACHINES],fNe[MAX_MACHINES],eN[MAX_MACHINES],F[MAX_MACHINES],cmax1; int e[MAX_MACHINES],fe[MAX_MACHINES],FF[MAX_MACHINES],sit,m,gsit=0; k=0; copy(subpath,gbest); while(k<gjob) { ps=position(subpath,k);//找到工件k的位置 gsit=ps; for(i=ps;i<gjob-1;i++) //从排列中取走工件k，形成新排列subpath[] subpath[i]=subpath[i+1]; fmach(fN,subpath,gjob-1);//计算N-1个工件相邻机器的完工时间差 emach(eN,fNe,subpath,gjob-1);//计算相邻机器的开工时间差 for(j=0;j<gjob;j++)//将K插入到序列j之后j+1之前(计算j+1序列的最大开工时间之差) { sit=j; cmax1=0; if(sit==0)//将工件k插入到n-1序列之前 { for(m=1;m<gmachine;m++) { eN[m]=job[k].timemac[m-1]+max(eN[m],job[k].timemac[m]); fNe[m]=fNe[m]+max(job[k].timemac[m],eN[m]); cmax1+=fNe[m]; } cmax1+=job_mach1; } else if(sit==gjob-1)//将工件K插入到n-1序列之后 { for(m=1;m<gmachine;m++) { fN[m]=job[k].timemac[m]+max(fN[m],job[k].timemac[m-1]); cmax1+=fN[m]; } cmax1+=job_