脚本宝典收集整理的这篇文章主要介绍了动态规划 --- 例题8. 同顺序流水作业调度问题，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

一.题目描述

设有m种加工用的机器：M1, M2, …, Mm 所谓同顺序流水作业是指它的加工顺序是相同的，不妨为M1 -> M2 ->… -> Mm 即先通过M1加工，然后依次为M2 ，等等。 现有n项任务．其加工顺序一样，设为: J1, J2, …, Jn 已知矩阵 T=(tij)m*n 其中 tij ＝作业Jj在机器Mi上的加工时间,求所用时间最短的作业加工顺序及时间.

下面仅就m=2的情形讨论。 S0={J1, J2, …, Jn}, N={1, 2, …, n} 若n个任务的加工顺序不同，从第一个任务在机器M1上加工开始，到最后一个任务在机器M2上加工完毕为止，所需的时间也不同。从直观上知道最佳的安排是使得机器M2的空闲时间达到最少，而对机器M1不存在空闲问题。当然M2也存在任务等机器的状况，即M1加工完毕，而M2还在加工前面一个任务。

二.解题思路

设M1、M2加工作业i分别需要时间 ai 和 bi 设全部作业的集合问题为N ={1,2,...,n}. S是N的作业子集,在一般情况下,机器M1开始加工S中作业时,机器M2还在加工其他作业,要等时间t后才可以利用.将这种情况下完成S中作业所需的最短时间记为T(S, t).流水作业调度问题的最优值为T(N, 0).

1.最优子结构性质

2.递归计算最优值

以上两步略去,因为数学推导太难懂了,我们只需要记住结论: 先把所有作业的ai和bi放在一起,在这之中选择一个最小的,如果是bi的话,这个作业i就放在最后,如果是ai的话,这个作业就放在最前面.把这个已经安排好的作业从作业集中删除,重复上述步骤即可.

用更规范的语言总结出来就是,就是流水作业调度问题的Johnson算法:

• 令n1 = {i | ai<bi}, N2 = {i | ai>=bi}
• 将N1中作业依ai的非降序排列,将N2中作业依bi的非增序排列
• N1中作业接N2中作业构成满足Johnson法则的最优调度

参考回答:博客园优质文章.

代码如下:

// 流水作业调度问题
// 结论:
// 1. 令N1 = {i|ai<bi}, N2 = {i|ai>=bi};
// 2. 将N1中作业依ai的非降序排列,将N2中作业依bi的非增序排列
#include<bITs/stdc++.h>
using namespace std;
class JOB
{
    public:
        int key, index;
        bool job;
};
bool cmp(JOB a, JOB b)
{
    return a.key < b.key;
}
int JobSort(int n, int a[], int b[], int c[])
{
    JOB *d = new JOB[n];
    for(int i=0; i<n; i++)
    {
        if(a[i]<b[i])
        {
            d[i].job = true;
            d[i].key = a[i];
        }
        else
        {
            d[i].job = false;
            d[i].key = b[i];
        }
        d[i].index = i;
    }
    sort(d, n+d, cmp);
    int j=0, k=n-1;
    for(int i=0; i<n; i++)
    {
        if(d[i].job == true)
        {
            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;
    return k;
}
int main()
{
    int i, n, m, a[100], b[100], c[100];
    cin>>n;
    while(n--)
    {
        cin>>;m;
        cout<<"请输入每个作业用时: "<<endl;
        for(int i=0; i<m; i++)
        {
            cout<<"作业编号"<<i<<": ";
            cin>>a[i];
            cin>>b[i];
        }
        cout<<JobSort(m, a, b, c)<<endl;
    }
    System("pause");
    return 0;
}

参考例子:

运行结果:

参考毕方明老师《算法设计与分析》课件.

如果觉得本篇文章对你有所帮助,欢迎大家来到我的个人博客网站---乔治的编程小屋逛一逛.

脚本宝典总结

以上是脚本宝典为你收集整理的动态规划 --- 例题8. 同顺序流水作业调度问题全部内容，希望文章能够帮你解决动态规划 --- 例题8. 同顺序流水作业调度问题所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。