流水作业调度-算法设计
程序员文章站
2022-03-24 15:25:12
...
由于本人懒得敲题目,于是乎拍照代替^o^
问题描述:
算法描述:
具体代码:
#include <stdio.h>
#include <iostream>
using namespace std;
class Jobtype
{
public:
int operator <=(Jobtype a) const //重载<=
{
return(key<=a.key);
}
int key,index; //key为机器所用时间,index为作业序号
bool job; //job为1表示M1,0表示M2
};
void Sort(Jobtype *d,int n) //采用冒泡排序将d中元素按升序排列
{
int i,j,flag;
Jobtype temp;
for(i=0;i<n;i++){
flag = 0;
for(j=n-1;j>i;j--){
if(d[j]<=d[j-1]){
temp = d[j];
d[j] = d[j-1];
d[j-1] = temp;
flag = 1;
}
}
if(flag == 0){
break;
}
}
}
int FlowShop(int n,int a[],int b[],int c[])
{
Jobtype *d = new Jobtype[n];
for(int i=0; i<n; i++)
{
d[i].key = a[i]>b[i]?b[i]:a[i];//按Johnson法则分别取对应的a[i]或b[i]值作为关键字
d[i].job = a[i]<=b[i];//给符合条件a[i]<b[i]的放入到N1子集标记为true
d[i].index = i;
}
Sort(d,n);
int j = 0,k = n-1;
for(int x=0; x<n; x++)
{
if(d[x].job)
{
c[j++] = d[x].index;
}
else
{
c[k--] = d[x].index;
}
}
j = a[c[0]];
k = j+b[c[0]];
for(int z=1; z<n; z++)
{
j += a[c[z]];
k = j<k?k+b[c[z]]:j+b[c[z]];//消耗总时间的最大值
}
delete d;
return k;
}
int main()
{
int a[100],b[100],n;
int c[100];
cout<<"请输入作业个数:"<<endl;
cin>>n;
cout<<"请输入m1的时间"<<endl;
for(int i=0;i<n;i++)
cin>>a[i];
cout<<"请输入m2的时间:"<<endl;
for(int j=0;j<n;j++)
cin>>b[j];
int minTime = FlowShop(n,a,b,c);
cout<<"完成作业的最短时间为:"<<minTime<<endl;
cout<<"作业调度的顺序为:"<<endl;
for(int y=0; y<n; y++)
{
cout<<c[y]+1<<" ";
}
cout<<endl;
return 0;
}
运行结果:
上一篇: dw怎么运行php程序?
下一篇: python如何提取PDF文本