流水作业调度--动态规划

时间：2021-07-04 11:30:03

问题描述：

n个作业{1，2，…，n},要在由机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi。

 要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

问题分析：
直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。
在一般情况下，机器M2上会有机器空闲和作业积压两种情况。
设全部作业的集合为N={1，2，…，n}。S是N的作业子集。
通常，机器M1开始加工S中作业时，机器M2还在加工其它作业，要等时间t后才可利用。
将这种情况下完成S中作业所需的最短时间记为T(S, t)。
流水作业调度问题的最优值为T(N, 0)。
处理过程：
1. 将｛a1，a2，…，an，b1，b2，…，bn｝排成非递减序列；
2. 依次从序列中抽出最小元素m，如果m ＝ aj且作业j还没有排入调度表，则把作业 j 安排在调度表可达的最左边一项空位上（设n个作业的调度表有n项，开始全部为空）。
3. 如果m = bj且作业j还没有排入调度表，则把作业j安排在调度表可达的最右边一项空位上。
4.如果作业j已排在调度表中，则取序列的下一个最小元素m，继续按上述方法调度，直到元素取完为止。
最后得到的调度表中的作业的顺序就是各作业的加工顺序。
例  设n ＝ 4，
（a1，a2，a3，a4）＝（3，4，8，10），
（b1，b2，b3，b4）＝（6，2，9，15），
经排序后为
（b2，a1，a2，b1，a3，b3，a4，b4）＝
           （2，3，4，6，8，9，10，15）。
设σ1，σ2，σ3，σ4是最优调度。

因为最小数是b2，故置σ4= 2。下一个次小的数是a1，置σ1= 1。接下去是a2，作业2已经被调度。再其次是b1作业1也已经被调度。下一个是a3，置σ2= 3，依次置σ3= 4。

算法复杂度分析：
算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为O(nlogn)。所需的空间为O(n)。

代码实现：

#include<iostream>
#include<algorithm>
using namespace std;

class Jobtype
{
public:
    int key;
    int index;
    bool job;

    int operator >(Jobtype a) const
    {
        return (key>a.key);
    }

};
void Shellsort(Jobtype *a,int n)
{
     for(int dk=n/2;dk>0;dk/=2)
    {
        for(int i=dk;i<n;i++)
        {
            for(int j=i-dk;j>=0 && a[j]>a[j+dk];j-=dk)
            {
                Jobtype t=a[j];
                a[j]=a[j+dk];
                a[j+dk]=t;
            }
        }
    }

}
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];
        d[i].job=(a[i]<=b[i]);
        d[i].index=i;
    }
    Shellsort(d,n);
    for(int i=0;i<n;i++)
    {
        cout<<"# "<<d[i].index<<"  "<<d[i].job <<endl;
    }
    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;
        }
    }
    for(int i=0;i<n;i++)
         cout<<"# "<<c[i]<<endl;
    int p=a[c[0]];
    int q=j+b[c[0]];
    for(int i=1;i<n;i++)
    {
        p+=a[c[i]];
        q= p<q? q+b[c[i]]:p+b[c[i]];
    }
    delete d;
    return q;
}

int main()
{
    int n;
    int a[100],b[100],c[100];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    int k=FlowShop(n,a,b,c);
    cout<<k;
    return 0;
}
样例及答案：

6
2 5 7 10 5 2
3 8 4 11 3 4
答案 15
5
2 4 3 6 1
5 2 3 1 7
答案 19




标签：

相关文章