流水作业调度

佚名 5年前 (2019-04-22) 算法 1660人围观抢沙发百度已收录

问题描述：

　　n 个作业 {1,2,...,n} 要在由 2 台机器 M₁ 和 M₂ 组成的流水线上完成加工。每个作业加工的顺序都是先在 M₁上加工，然后在 M₂上加工。M₁和 M₂ 加工作业 i 所需的时间分别为 a_i 和 b_i（1 <= i <= n）。流水作业调度问题要求确定这 n 个作业的最优加工顺序，使得从第一个作业在机器 M₁ 上开始加工，到最后一个作业在机器 M₂ 上加工完成所需的时间最少。
SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

算法分析：

　　一个最优调度应使机器 M₁ 没有空闲时间，且机器 M₂ 的空闲时间最少，则机器 M₂ 上会有机器空闲和作业积压两种情况。

算法描述：

令 N₁ = { i | a_i < b_i }，N₂ = { i | a_i >= b_i } ；

将 N₁ 中作业依ai的非减序排序，将 N₂ 中作业依 b_i 的非增序排序；

N₁ 中作业拼接 N₂ 中作业构成最优调度。

源代码:

//流水作业调度

/*测试数据
4
5 10 6 8
7 3 12 5
*/

#include<iostream>

using namespace std;

int k=0;  //定义全局变量 k：完成所有工作所需总时间

void FlowShop(int n,int *a,int *b,int *c)
{
    class Jobtype
    {
    public:
        int operator <= (Jobtype a) const { return (key <= a.key); }
        int key,index;
        bool job;
    };
    Jobtype *d = new Jobtype[n];
    for(int i=0;i < n;i++)
    {
        d[i].key = a[i]>b[i] ? b[i] : a[i];
        d[i].job = a[i] <= b[i];
        d[i].index = i;
    }

    //BubbleSort
    for(int i=0;i < n-1;i++)  //进行n-1趟排序
    {
        Jobtype temp;
        int Swap=0;  //设置未发生交换标志
        for(int j=0;j < n-i;j++)
            if(d[j].key > d[j+1].key)
            {
                temp=d[j];
                d[j]=d[j+1];
                d[j+1]=temp;
                Swap=1;  //有交换发生
            }
        if(Swap==0)
            break;  //已排好
    }

    int j = 0;
    k = n-1;
    for(int i=0;i < n;i++)
    {
        if(d[i].job)
            c[j++] = d[i].index;
        else
            c[k--] = d[i].index;
    }
    j = a[c[0]];
    k = j+b[c[0]];
    for(int i=1;i < n;i++)
    {
        j += a[c[i]];
        k = j<k ? k+b[c[i]] : j+b[c[i]];
    }
    delete[] d;
}

int main()
{
    int nn;  //工作总数
    int *aa,*bb,*cc;  //aa:分别在机器M1上的工作时间  bb:分别在机器M2上的工作时间  cc:流水作业调度表

    cout<<"工作总数："<<endl;
    cin>>nn;

    aa = new int[nn];
    bb = new int[nn];
    cc = new int[nn];

    cout<<"分别在机器M1上的工作时间："<<endl;
    for(int i=0;i < nn;i++)
        cin>>aa[i];
    cout<<"分别在机器M2上的工作时间："<<endl;
    for(int j=0;j < nn;j++)
        cin>>bb[j];

    FlowShop(nn,aa,bb,cc);

    //输出流水作业调度表
    cout<<endl;
    cout<<"流水作业调度表："<<endl;
    for(int i=0;i < nn;i++)
        cout<<cc[i]+1<<" ";
    cout<<endl;

    //完成所有工作所需总时间
    cout<<"总时间："<<endl;
    cout<<k<<endl;

    //释放空间
    delete[] aa;
    delete[] bb;
    delete[] cc;

    return 0;
}