当前位置:   article > 正文

流水作业调度问题

作业调度问题

问题描述:
n个作业{0,1,2,…,n}在2台机器上M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工,后在M2上加工。在两台机器上加工的时间分别为ai和bi。
目标:确定这n个作业的加工顺序,使得从第一台作业开始加工,到最后一个作业完成加工所需要的时间最少。
题目类型:动态规划
算法描述:
流水作业调度问题的Johnson算法:
(1) 令 这里写图片描述
(2)将N1 中作业依t[i,1]的非减序排列;将N2中作业依t[i,2]的非增序排列;
问题分析:
当输入的作业数目为6时:
每个作业在M1上执行的时间为t[i,1],在M2上执行的时间为t[i,2],输入的数据为:

这里写图片描述

算法按照先执行这里写图片描述的作业,保证M2机器上没有等待,本例中作业1、4、5满足条件,被选择先执行。当选择第一个作业时,算法选择让M2第一次等待时间最少的那个,本例中作业1的t[i,1]最小,这样就可以让M2第一次等待最少。所以在这里写图片描述的集合中,t[i,1]越小越靠前执行。
当执行这里写图片描述的作业时,要保证最后一个作业在M2上的执行时间最短,所以作业2,6,3是按照t[i,2]非增序排列,保证了作业3的t[i,2]是它们三个当中最小的一个。
算法在计算执行时间的过程如下图所示:
这里写图片描述

作业执行次序为:1,4,5,2,6,3

1)执行1时:M1上运行2个时间后交给M2,这时M2空闲了2个时间并开始工作。
所以此时要想将1做完需要7(2+5)个时间。
2)执行4时:M1上运行4个时间后,M2还在继续运行1,并没有结束。M1结束时间为6,而M2结束1的时间为7,即<6,7>。
所以此时要想把1,4做完,需要14(7+7)个时间。
3)执行5时:M1上运行6个时间后,M2还在继续运行4,并没有结束。M1的结束时间为12,而M2结束4的时间为14,即<12,14>
所以此时要想把1,4,5做完,需要23(14+9)个时间。
4)执行2时:M1上运行7个时间后,M2还在继续运行5,并没有结束。M1的结束时间为19,而M2结束5的时间为23,即<19,23>.
所以此时要想把1,4,5,2做完,需要26(23+3)个时间。
5)执行6时:M1上运行8个时间后,M2已经不在继续运行2。M1的结束时间为27,而M2结束2的时间为26,即此时M2已经空闲了一个时间,即<27,26>.
所以此时要想把1,4,5,2,6完成,需要29(27+2)个时间。
6)执行3时:M1上运行6个时间后,M2已经不在继续运行6。M1的结束时间为33,而M2结束6的时间为29,即此时M2已经空闲了3个时间,即<33,29>.
所以此时要把1,4,5,2,6,3完成,需要35(33+2)个时间。

所以,根据运行结果,作业执行时间为35.

代码如下:

/*
1)先执行t[i,1]<t[i,2],保证M2上没有等待。选择第一个作业时,让M2选择第一次等待时间最少的,
即t[i,1]越小,越靠前执行;
2)执行t[i,1]>=t[i,2]时,要保证最后一个作业在M2上执行时间最短,所以按照减序排列 
*/
#include<stdio.h>
#include<string.h>
#include<algorithm> 
#define N 100
using namespace std;

struct node {
    int time;//执行时间 
    int index;//作业序号
    bool group;//1代表第一个机器,0代表第二个机器 
};

bool cmp(node a,node b)
{//升序排序 
    return a.time<b.time; 
}
int main()
{
    int i,j,k,n;
    int a[N]={0},b[N]={0};
    int best[N];//最优调度序列 
    node c[N];
    scanf("%d",&n);
    for(i=0;i<n;i++) {
        scanf("%d%d",&a[i],&b[i]);
    }
    for(i=0;i<n;i++) {  //n个作业中,每个作业的最小加工时间 
        c[i].time=a[i]>b[i]?b[i]:a[i];
        c[i].index=i;
        c[i].group=a[i]<=b[i];

    }
    sort(c,c+n,cmp);//按照c[]中作业时间增序排序
    j=0,k=n-1;
    for(i=0;i<n;i++) {
        if(c[i].group) { //第一组,从i=0开始放入到best[]中 
            best[j++]=c[i].index;
        }
        else {
            best[k--]=c[i].index;
        }
    }
    j=a[best[0]];//最优调度序列下的消耗总时间 
    k=j+b[best[0]];
    for(i=1;i<n;i++) {
        j+=a[best[i]];
        k=j<k?(k+b[best[i]]):j+b[best[i]];//消耗总时间的最大值 
    }
    printf("%d\n",k);
    for(i=0;i<n;i++) {
        printf("%d ",best[i]+1); 
    }
    printf("\n");
    return 0;
} 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

运行结果:
这里写图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/890985
推荐阅读
相关标签
  

闽ICP备14008679号