問題描述
n個作業{1,2,…,n}要在由2台機器M1和M2組成的流水線上完成加工。每個作業加工的順序都是先在M1上加工,然後在M2上加工。M1和M2加工作業i所需的時間分别為a[i]和b[i]。流水作業排程問題要求确定這n個作業的最優加工順序,使得從第一個作業在機器M1上開始加工,到最後一個作業在機器M2上加工完成所需的時間最少。
基本思路
-
将每個作業按照加工時間分組
對于作業i,若a[i]<=b[i],則分到N1組。若a[i]>b[i],則分到N2組。
-
進行加工排序
所有N1組(a[i]<=b[i])的作業都在N2組之前加工,對于N1組(a[i]>b[i])的作業,按照b[i] (在M2上加工時間)升序排列。對于N2組的作業,按照a[i] (在M1上加工時間)降序排列。排列完成即得到加工順序
示例
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5yM1MzMzE2YlZmNyMmMhNmZyYzX2QTMxYTM3EzLchDMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
N1按b[i]升叙排列:0、5、1、3
N2按a[i]降叙排列:2、4
最優加工順序:0、5、1、3、2、4
代碼
如果想要了解程式設計思路,好好看注釋
//3d9 動态規劃 流水作業排程問題
#include <iostream>
using namespace std;
const int N = 6;
class Jobtype
{
public:
int key;//key記錄a[i]、b[i]的較大者
int index;//作業的編号
bool job;//作業的分組
};
int FlowShop(int n,int a[],int b[],int c[]);
void BubbleSort(Jobtype *d,int n);
int main()
{
int a[] = {2,5,7,10,5,2};
int b[] = {3,8,4,11,3,4};
int c[N];//c[]記錄加工順序
int minTime = FlowShop(N,a,b,c);
cout<<"作業在機器1上的運作時間為:"<<endl;
for(int i=0; i<N; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"作業在機器2上的運作時間為:"<<endl;
for(int i=0; i<N; i++)
{
cout<<b[i]<<" ";
}
cout<<endl;
cout<<"完成作業的最短時間為:"<<minTime<<endl;
cout<<"編号從0開始,作業排程的順序為:"<<endl;
for(int i=0; i<N; i++)
{
cout<<c[i]<<" ";
}
cout<<endl;
return 0;
}
int FlowShop(int n,int a[],int b[],int c[])
{
Jobtype *d = new Jobtype[n];//總共有n個作業
for(int i=0; i<n; i++)
{
d[i].key = a[i]>b[i]?b[i]:a[i];//按Johnson法則分别取對應的b[i]或a[i]值作為關鍵字,關鍵字是記錄加工順序的标準
d[i].job = a[i]<=b[i];//分組,給符合條件a[i]<=b[i]的放入到N1子集标記為true
d[i].index = i;
}
BubbleSort(d,n);//對數組d按關鍵字升序進行排序
int j = 0,k = n-1;
/*
如果作業分在N1集合中(說明a[i]<=b[i]),按b[i]進行升序排列
如果作業分在N2集合中(說明a[i]>b[i]),按a[i]進行降序排列
*/
for(int i=0; i<n; i++)
{
if(d[i].job)//c[]記錄加工順序
{
c[j++] = d[i].index;//将排過序的數組d,取其中作業序号屬于N1的從前面進入
}
else
{
c[k--] = d[i].index;//屬于N2的從後面進入,進而實作N1的非減序排序,N2的非增序排序
}
}
//下面構造最優值(最短加工時間)
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]];
/*
M1在執行c[i]作業的同時,M2在執行c[i-1]号作業,最短執行時間取決于M1與M2誰後執行完。
隻有M1将第i個作業加工完且M2将第i-1個作業加工完,M2才能加工第i個作業。
是以k取j和k中的較大者+第i個做的在M2上的加工時間
*/
}
delete d;
return k;
}
/*
按關鍵字key升序排列
在N1集合(a[i]<=b[i])中,key=b[i]
在N2集合(a[i]>b[i])中,key=a[i]
*/
void BubbleSort(Jobtype *d,int n)
{
int i,j,flag;
Jobtype temp;
for(i=0;i<n;i++)
{
flag = 0;
for(j=0;j<n-i;j++)
{
//如果前一個數大于後一個數,則交換
if(d[j].key>=d[j+1].key)
{
temp = d[j];
d[j] = d[j+1];
d[j+1] = temp;
flag = 1;
}
}
//如果本次循環沒有進行一次交換,則break,減少了執行時間。
if(flag == 0){
break;
}
}
}