動态規劃---->流水線排程問題

問題的描述：

n個作業{1，2，…，n}要在由2台機器M1和M2組成的流水線上完成加工。每個作業加工的順序都是先在M1上加工，然後在M2上加工。M1和M2加工作業i所需的時間分别為ai和bi。

流水作業排程問題要求确定這n個作業的最優加工順序，使得從第一個作業在機器M1上開始加工，到最後一個作業在機器M2上加工完成所需的時間最少。

排程規則

(1 ) 把全部ai和bi分類成非降序列，ai和bi分别是第i個作業在兩個機器上所需要的時間。

(2 ) 按照這一分類次序考察此序列: 如果序列中下一個數是aj 且作業j還沒排程,那麼在還沒使用的最左位置排程作業j ; 如果下個數是bj 且作業j還沒排程,那麼在還沒使用的最右位置排程作業j ; 如果已經排程了作業j,則轉到該序列的下一個數。

算法主要利用Johnson不等式原理，對于所有的a步驟和b步驟的時間從小到大排序。如果合并序列中拿出的元素屬于a集合，則将其所屬的job作為第一個job執行；如果屬于b集合，則将其所屬的job作為最後一個job執行。進行下一個元素的判斷，分别作為第二、倒數第二，依次類推；直到所有job被标記之後退出，獲得的job數組就是job的執行序列。

例子1

設 n=4,( a1,a2,a3,a4 ) =( 3,4,8,10 ) 和( b1,b2,b3,b4 ) =(6,2,9,15 ),對這些a和b分類後的序列是( b2,a1,a2,b1,a3,b3,a4,b4 ) =( 2,3,4,6,8,9,10,15),

設σ1,σ2,σ3,σ4是最優排程。            最小數是b2,  置σ4 = 2。 下一個最小數是a1,  置σ1 = 1。 接着的最小數是a2,由于作業2已被排程,轉向再下一個數b1 。 作業1已被排程,再轉向下一個數a3,置    σ2 = 3。 最後剩σ3 是空的,而作業4還沒排程,進而σ3= 4

例子2：