流水作業(yè)調(diào)度問(wèn)題
描述:
N個(gè)作業(yè){1,2,………,n}要在由兩臺(tái)機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。
M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi，1≤i≤n。流水作業(yè)高度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在
機(jī)器M1上開(kāi)始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少。
可以假定任何任務(wù)一旦開(kāi)始加工，就不允許被中斷，直到該任務(wù)被完成，即非優(yōu)先調(diào)度。
輸入:
輸入包含若干個(gè)用例,第一行為一個(gè)正整數(shù)K(1<=K<=1000),表示用例個(gè)數(shù),接下來(lái)K個(gè)用例,每個(gè)用例第一個(gè)為作業(yè)數(shù)N(1<=N<=1000)，
接下來(lái)N行，每行兩個(gè)非負(fù)整數(shù)，分別表示在第一臺(tái)機(jī)器和第二臺(tái)機(jī)器上加工時(shí)間。
輸出:
每個(gè)用例用一行輸出采用最優(yōu)調(diào)度所用的總時(shí)間，即從第一臺(tái)機(jī)器開(kāi)始到第二臺(tái)機(jī)器結(jié)束的時(shí)間。
樣例輸入:
1
4
5 6
12 2
4 14
8 7
樣例輸出:
33

---

算法描述：

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

2 將n1中作業(yè)按ai的非減排序，n2 作業(yè)按bi非增排序

3 構(gòu)成滿(mǎn)足Johnson法則的最優(yōu)調(diào)度

#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;
}

運(yùn)行結(jié)果：

轉(zhuǎn)載于:https://www.cnblogs.com/xing901022/archive/2012/10/17/2728210.html

總結(jié)

以上是生活随笔為你收集整理的流水作业调度的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。