流水作業(yè)調度問題

1、精選優(yōu)質文檔-傾情為你奉上流水作業(yè)調度問題描述:N個作業(yè)1,2,n要在由兩臺機器M1和M2組成的流水線上完成加工。每個作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時間分別為ai和bi，1in。流水作業(yè)高度問題要求確定這n個作業(yè)的最優(yōu)加工順序，使得從第一個作業(yè)在機器M1上開始加工，到最后一個作業(yè)在機器M2上加工完成所需的時間最少?？梢约俣ㄈ魏稳蝿找坏╅_始加工，就不允許被中斷，直到該任務被完成，即非優(yōu)先調度。輸入:輸入包含若干個用例,第一行為一個正整數(shù)K(1<=K<=1000),表示用例個數(shù),接下來K個用例,每個用例第一個為作業(yè)數(shù)N(1<=N&l

2、t;=1000)，接下來N行，每行兩個非負整數(shù)，分別表示在第一臺機器和第二臺機器上加工時間。輸出:每個用例用一行輸出采用最優(yōu)調度所用的總時間，即從第一臺機器開始到第二臺機器結束的時間。樣例輸入:145 612 24 148 7樣例輸出:33假定直接按順序進行完成，則機器1可以不用考慮，因為作業(yè)1完成后就可以完成作業(yè)2,直到作業(yè)n，需要的時間為所有作業(yè)在機器1上的時間總和。但是，機器2上完成的時間呢？機器2上完成的時間顯示除了作業(yè)在機器2上完成的時間總和，還要加上等待時間，即要求先在機器1上完成后，才能在機器2上開始。例如5 612 2兩個作業(yè)，順序如下：按順序，則在機器1上進行作業(yè)1需要5小時

3、，后進行作業(yè)2,需要12小時，和為17小時；機器2上，作業(yè)1只能從第5小時開始，第11小時完成，等待了5小時，等到作業(yè)2在機器1上完成后（已經(jīng)是第17時），再完成2小時，共19小時。機器2的等待時間總計為11小時。逆序，在機器1上進行作業(yè)2需要12小時，后進行作業(yè)1需要5小時，和為17小時，和前面一樣；機器2上，作業(yè)2完成后開始，等待了12小時，然后再等3小時開始作業(yè)1的6小時，共計21小時，共等待了15小時。圖如下：512625651262123從剛才的分析可知，主要考慮機器2的等待時間，越少越好！如何做到呢？仔細分析可知，在機器1上需要的時間越少的，應該越早開始進行，這樣才能保證機器2盡早

4、開始。但真是這樣嗎？如：5 64 2按順序需要共13小時，等待5小時；逆序需要共15小時，等待7小時。那怎么辦呢？根據(jù)相關解題思路及教材上Johnson法則，在此采用的方法簡述如下：在機器1上需要時間比在機器2是需要時間少的先開始，且按時間從小到大開始進行；在機器1上需要時間比在機器2上需要時間多的后開始，按按時間從大到小開始進行；解題思路（簡略版）：a與b分別表示在第一臺機器和第二臺機器所用時間a51248b62147d為一結構體，key為短時間，job為是否可先做,index為作業(yè)號key5247job1010index0123對d依時間排序key2457job0110index1203能安排的先安排，不能安排的置最后key4572job1100index2031得到順序為2 0 3 1順序，即先安排第3個工作，再安排第1個，再安排