首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >流水作业调度

流水作业调度

作者头像
用户1154259
发布2018-01-17 15:05:56
1K0
发布2018-01-17 15:05:56
举报

流水作业调度问题 描述: N个作业{1,2,………,n}要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工,然后在M2上加工。 M1和M2加工作业i所需的时间分别为ai和bi,1≤i≤n。流水作业高度问题要求确定这n个作业的最优加工顺序,使得从第一个作业在 机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少。 可以假定任何任务一旦开始加工,就不允许被中断,直到该任务被完成,即非优先调度。 输入: 输入包含若干个用例,第一行为一个正整数K(1<=K<=1000),表示用例个数,接下来K个用例,每个用例第一个为作业数N(1<=N<=1000), 接下来N行,每行两个非负整数,分别表示在第一台机器和第二台机器上加工时间。 输出: 每个用例用一行输出采用最优调度所用的总时间,即从第一台机器开始到第二台机器结束的时间。 样例输入: 1 4 5 6 12 2 4 14 8 7 样例输出: 33

算法描述:

1 令N1={i | ai < bi},N2={i | ai>=bi}

2 将n1中作业按ai的非减排序,n2 作业按bi非增排序

3 构成满足Johnson法则的最优调度

#include <iostream>
#include <algorithm>
using namespace std;
class JOB
{
public:
    int key,index;
    bool job;
};
bool cmp(JOB a,JOB b)
{
    return a.key<b.key;
}
int func(int n,int a[],int b[],int c[])
{
    int i,j,k;
    JOB *d =new JOB[n];
    for(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);
    j=0,k=n-1;
    for(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(i=1;i<n;i++)
    {
    j=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;
        for(i=0;i<m;i++)
        {
            cin>>a[i];
            cin>>b[i];
        }
        cout<<func(m,a,b,c)<<endl;
    }
    return 0;
}

运行结果:

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2012-10-17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档