欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

流水作业调度-算法设计

程序员文章站 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;
}

运行结果:流水作业调度-算法设计




相关标签: 算法设计