基础NEH算法在流⽔车间调度问题（FlowShop）问题的应⽤（C++） 对于流⽔车间调度问题，基本的NEH不⼀定能给出最短或者最优的加⼯序列，但是他可以在⼀定程度上保证加⼯序列的局部最优性，所以它通常可以作为⼀些其他的算法（如IGA）的输⼊。 以下是启发式⽅法NEH的简介：
启发式算法利⽤问题特定知识和经验产⽣求解⽅案，能够在较短时间内得到次优解。研究表明，3台以上机器的PFSP即为NP-hard问题，⾄今没有⼀个多项式复杂性的全局优化算法。为了快速得到问题的次优解，研究⼈员提出了若⼲启发式算法。启发式⽅法有：Johnson算法、Campleu-Dudek-Smith⽅法、Palmer⽅法、Gupta⽅法、Rapid Access⽅法、Pour⽅法、Nawaz-Enscore-Ham⽅法、NEH_D⽅法、NEH-KK⽅法、Rajendran⽅法、B5Cmax⽅法、FRB⽅法等。 由Nawaz M, Enscore JEE, Ham I. 3位作者提出的启发式⽅法，命名为NEH，是解决 _ | | _ 最有效的启发式⽅
法之⼀。
NEH的⼤致流程为：
例如：⼀个6*3的基础调度问题
其中⾏数代表⼯件的个数，列数代表每⼀个⼯件需要加⼯的步骤数，某⾏某列填⼊的数字代表了某个⼯件在某个步骤的加⼯权值（时间） ⽐如：第⼀⾏第⼀列的19表⽰第⼀个⼯件需要加⼯19个单位的时间
在代码中⽤pai0 来表⽰结果所对应的加⼯序列
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
int times[105][105]= {{19,46,65},{44,63,12},{85,56,98},{59,68,25},{87,66,53},{51,4,63}}; static int num,prcs;
void InitTime()//初始化时间矩阵
{
高速路收费系统for(int i = 0; i < num; i++)
for(int j = 0; j < prcs ; j++)
scanf("%d",×[i][j]);
}
void PrintSquence(int Paitemp[],int k)//输出调度序列
{
if(k<=num)
for(int i = 0; i < k; i++)
cout<<Paitemp[i]<<" ";
}
void SquenceCopy(int a[],int b[])//复制加⼯序列
{
for(int i = 0 ; i < num ; i++)
a[i] = b[i];
}
void InsSort(int Pai[],int insLoc,int Loc)//插⼊操作
{
/
/加⼯序列数组插⼊的位置待插⼊元素的位置
//{2,1,5,4,3} InsSort(Pai,3,5) {2,1,3,5,4}
if(insLoc < Loc)
{
int temp = Pai[Loc-1];
for(int i = Loc-1; i > insLoc-1; i--)
Pai[i] = Pai[i-1];
Pai[insLoc-1] = temp;
}
else;
}
int CalcuTime(int num,int prcs,int Pai[])//计算加⼯时间
{
int pre[prcs] = {0};
int cur[prcs] = {0};
int sum = 0;
for(int i = 0; i < num ; i++)
{
for(int j = 0; j < prcs ; j++)
{
if(j == 0)
{
cur[j] += times[Pai[i]-1][0];
}
else
{
cur[j] = max(pre[j],cur[j-1]) + times[Pai[i]-1][j];
}
}
sum = cur[prcs-1];
for(int j = 0; j < prcs ; j++)
pre[j] = cur[j];
pre[j] = cur[j];
}
return sum;
}
int BasicNEH(int num,int prcs,int Pai0[])
{
int SumFroEach[num] = {0};
for(int i = 0; i < num; i++)// 对时间矩阵的每⼀⾏求和
for(int j = 0; j < prcs ; j++)
SumFroEach[i] += times[i][j];
int Pai[num];
for(int i = 0; i<num; i++)
Pai[i] = i+1;
for(int i = 0; i <num-1; i++)//双向冒泡排序
{ //最⼤值往左冒的同时，最⼩值往右冒。⽐传统的冒泡排序节省⼀些循环次数 if(i == num - 1 - i || i == num - i)
break;
int maxsum = SumFroEach[i];
int minsum = SumFroEach[num - 1 - i ];
if(maxsum < minsum)
{
swap(SumFroEach[i],SumFroEach[num - 1 - i ]);
swap(Pai [i], Pai[num - 1 - i ]);
}
for(int j = i+1; j < num -1- i ; j++)
{
if(SumFroEach[j] > maxsum)
{
swap(SumFroEach[j],SumFroEach[i ]);
maxsum = SumFroEach[i ];
swap(Pai[j],Pai[i]);
}
else if(SumFroEach[j] < minsum)
{
swap(SumFroEach[j],SumFroEach[num - 1 - i ]);
minsum = SumFroEach[num - 1 - i ];
swap(Pai[j],Pai[ num - 1 - i ]);
}
}
}
cout<<endl;//获得排序后的序列
cout<<"Sorted Sequence is: ";
PrintSquence(Pai,num);//输出检查⼀下
指纹识别模块
SquenceCopy(Pai0,Pai);//将排序好的加⼯顺序复制⼀份
cout<<endl;
cout<<endl;
int presum,sum;//上⼀次计算的加⼯时间本次加⼯时间
int Trytime = 1;//记录计算次数
for(int k = 1 ; k <= num; k++)
{
int insLoc = 1,Loc = k;
for(int j = 0; j <= k-1; j++)
{
int Paitemp[num];//建⽴加⼯序列副本
SquenceCopy(Paitemp,Pai);
if(insLoc < Loc)
{
if(j == 0);//第⼀次不进⾏插⼊操作
else
InsSort(Paitemp,insLoc++,Loc);
printf("Trial NO: %-4d ",Trytime++);
sum = CalcuTime(k,prcs,Paitemp);
sum = CalcuTime(k,prcs,Paitemp);
if(j == 0)
presum = sum;
else
{
切割环if(sum < presum)
{
SquenceCopy(Pai0,Paitemp);
presum = sum;
}
}
cout<<" Current Sequence : ";
PrintSquence(Paitemp,k);
cout<<endl;
cout<<"Current Procduce Time: "<<sum<<endl;
cout<<endl;
}染酸
else
break;
}
SquenceCopy(Pai,Pai0);
cout<<"Result NO: ";
printf("%-3d : ",k);
PrintSquence(Pai0,k);
cout<<endl<<"*****************************************************"<<endl;
}
return presum;
}
int main()
{
cout<<"Please Input the Numbers And Processes of Each Works "<<endl; cout<<"Numbers: ";
scanf("%d",&num);
cout<<"Processes:";
scanf("%d",&prcs);
// cout<<"Please Input Time Matrix :"<<endl;
//InitTime();
int Pai0[num];
int sum = BasicNEH(num,prcs,Pai0);
展频原理
cout<<"BEH Sequence:";
PrintSquence(Pai0,num);
cout<<endl;
cout<<" MakeSpan: "<<sum<<endl;
return 0;
}
氟苯尼考助溶剂
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议