流水作業(yè)的排序問題-加微信Q763433542有更新會在微信朋友圈通知

第九章流水作業(yè)的排序問題

9.1排序問題概述9.2流水作業(yè)排序問題9.1排序問題概述一、排序問題的基本概念排序是確定工件（零部件）在一臺或一組設備上加工的先后順序。在一定約束條件下，尋找總加工時間最短的安排產(chǎn)品加工順序的方法，就是生產(chǎn)作業(yè)排序。例如，考慮32項任務（工件），有32！2.61035種方案,假定計算機每秒鐘可以檢查1billion個順序,全部檢驗完畢需要8.41015個世紀.如果只有16個工件,同樣按每秒鐘可以檢查1billion個順序計算,也需要2/3年.以上問題還沒有考慮其他的約束條件,如機器、人力資源、廠房場地等，如果加上這些約束條件，所需要的時間就無法想象了。所以，很有必要去尋找一些有效算法，解決管理中的實際問題。假設條件1.一個工件不能同時在幾臺不同的機器上加工。2.工件在加工過程中采取平行移動方式，即當上一道工序完工后，立即送下道工序加工。3.不允許中斷。當一個工件一旦開始加工，必須一直進行到完工，不得中途停止插入其它工件。4.每道工序只在一臺機器上完成。5.工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關。6.每臺機器同時只能加工一個工件。排序常用的符號

Ji---工件i，i=1,2,..n。Mj----

機器j，j＝1，2，…，m.

pij----工件Ji在機器Mj上的加工時間,j=1,…,m

Pi----工件Ji的加工時間；di----工件Ji的完工期限；Ci----工件Ji的完成時間；Fi----工件Ji的流程時間，即工件在車間的實際停留時間，在工件都已到達的情況下,Fi=Pi+Wi

Wi----工件Ji在加工過程中總的等待時間Li----工件Ji的延誤時間,Li=Ci-di,Li<=0按期或完成提前；Li>0延誤

Fmax----最長流程時間，F(xiàn)max＝max{Fi}二、排序問題的分類和表示法1、排序問題的分類：

(1)根據(jù)機器數(shù)的多少單臺機器的排序問題多臺機器的排序問題

(2)根據(jù)加工路線的特征單件作業(yè)排序(JobShop)：工件加工路線不同

流水作業(yè)排序(FlowShop)：所有工件加工路線完全相同

(3)根據(jù)工件到達系統(tǒng)的情況靜態(tài)排序：進行排序時，所有工件都已到達，可以一次對他們排序動態(tài)排序：工件陸續(xù)到達，要隨時安排他們的加工順序（4）根據(jù)參數(shù)的性質確定型排序：指加工時間和其他參數(shù)是已知確定的量隨機型排序：指加工時間和有關參數(shù)為隨機變量（5）根據(jù)要實現(xiàn)的目標單目標排序多目標排序2、排序問題的表示法排序問題常用四個符號來描述:

n/m/A/B其中,n-----工件數(shù)；

m-----機器數(shù)；

A----車間類型；F－流水作業(yè)排序，

P－流水作業(yè)排列排序

G－一般類型,即單件型排序

B-----目標函數(shù)9.2流水作業(yè)排序問題一、最長流程時間Fmax的計算

工件

Si在機器MK上的完工時間為CKSi工件

Si在機器MK上的加工時間為PSiK

C1Si=C1Si-1+PSi1

CKSi=max｛C(k-1)Si,CkSi-1

｝+PSik舉例：有一個6/4/p/Fmax問題，其加工時間如下表所示。當按順序S＝（6，1，5，2，4，3）加工時，求Fmax。i123456Pi1Pi2Pi3pi4423142456745587555424331i615243Pi1Pi2Pi3pi4224641021211331657411415520727633512517522830535742

113421325232338446二、兩臺機器排序問題兩臺機器排序的目標是使最大完成時間（總加工周期）Fmax最短。實現(xiàn)兩臺機器排序的最大完成時間Fmax最短的目標，一優(yōu)化算法就是著名的約翰遜法(Johnson’sLaw)。其具體求解過程如下例所示。約翰遜－貝爾曼法則約翰遜法解決這種問題分為4個步驟：(1)列出所有工件在兩臺設備上的作業(yè)時間。(2)找出作業(yè)時間最小者。(3)如果該最小值是在設備1上，將對應的工件排在前面，如果該最小值是在設備2上，則將對應的工件排在后面。(4)排除已安排好的工件，在剩余的工件中重復步驟(2)和(3)，直到所有工件都安排完畢。

舉例AB兩臺設備完成6個零件的加工任務，每個工件在設備上的加工時間如下表所示。求總加工周期最短的作業(yè)順序。

J1J2J3J4J5J6機器A518534機器B722474機器工件編號求解過程由約翰遜法可知，表中最小加工時間值是1個時間單位,出現(xiàn)在設備1上，根據(jù)約翰遜法的規(guī)則，應將對應的工件2排在第一位，即得：

J2-*-*-*-*-*

去掉J2，在剩余的工件中再找最小值，最小值是2個時間單位，它是出現(xiàn)在設備2上，所以應將對應的工件J3排在最后一位，即：

J2-*-*-*--*J3

再去掉J3，在剩余的J1、J4、J5、J6中重復上述步驟，求解過程為：

J2－J5-*-*-*-J3J2–J5－J6

-*-*–J3J2–J5－J6

-*-J4–J3J2–J5－J6

–J1--J4–J3當同時出現(xiàn)多個最小值時，可從中任選一個。

J2–J5–J6-J1-J4－J3

或J2–J5–J1-J6-J4－J3

i256143Pi1Pi211344851351882623711415722426228i251643Pi1Pi211345941351882623711718422426228求得最優(yōu)順序下的Fmax＝28

Johnson算法的改進1.將所有ai≤

bi的工件按ai值不減的順序排成一個序列A；2.將ai＞bi的工件按bi值不增的順序排成一個序列B；3.將A放到B之前，就構成了一個最優(yōu)加工順序。

J1J2J3J4J5J6機器A518534機器B722474○○○○○○ai≤bi工件按ai值不減的順序（由小到大）排列：

J2–J5–J6-J1；ai＞bi的工件按bi值不增的順序（由大到?。┡帕校篔4－J3

最后排序J2–J5–J6-J1-J4－J3三、m(m≥3)臺機器排序問題的算法

一般采用啟發(fā)式算法解決這類問題。斜度指標法關鍵工件法CDS法（一）Palmer（斜度指標法）

工件的斜度指標計算公式k＝1，2，……m式中，m機器數(shù)；Pik為工件i在Mk上的加工時間。按照各工件λi不增的順序排列工件，可得出令人滿意的順序。λi=舉例有一個4/3/F/Fmax問題，其加工時間如下表所示，用Palmer法求解。i1234Pi1Pi2Pi3126384294582λi＝＝-Pi1+Pi3λ1＝-P11+P13=-1＋4＝3λ2＝-P21+P23=-2+5=3λ3＝-P31+P33=-6+8=2λ4＝-P41+P43=-3+2=-1按λi不增的順序排列工件，得到加工順序（1，2，3，4）或（2，1，3，4）k=1，2，3i1234Pi1Pi2Pi3112369312

89413215924

413518826228

Fmax=28i2134Pi1Pi2Pi3221369312

46814216925

511418826228

Fmax=28加工順序（1，2，3，4）或（2，1，3，4）

（二）關鍵工件法

1、計算Pi=,找出其中最大者，定義為關鍵工件Jc。2、除Jc外，將滿足Pi1≦Pim的工件，按Pi1值的大小，從小到大排在Jc的前面。3、除Jc外，將滿足pi1>pim的工件，按Pim值的大小，從大到小排在Jc的后面。i1234Pi1Pi2Pi312638429582Pi13111614（1）工件3加工時間最長，作為關鍵工件。（2）滿足Pi1<Pi3的工件有1、2，按Pi1值由小到大排在3的前面，1-2-3。（3）滿足pi1>pi3的工件是4，將4排在3的后面。所以加工順序為（1，2，3，4）。i1234Pi1Pi2Pi3112369312

89413215924

413518826228

舉例J1J2J3J4J5J6機器1pi15541210機器2pi25553610機器3pi3833474機器4pi4282156機器5pi55212810總和252315112840具體過程（1）找出關鍵工件：工作負荷最大的40，對應的是工件6，Jc=J6

（2）滿足Pi1≦Pi5的工件有J1、J4、J5,按Pi1值由小到大排在關鍵工件前面，所以有J4–J5–J1-J6

（3）滿足pi1>pi5的工件有J2、J3，按Pi5值由大到小排在關鍵工件的后面,所以有–J6–J2–J3

J4–J5–J1–J6–J2–J3Fmax=51（三）CDS法Campbell,Dudek,Smith三人于1970年共同提出了一個啟發(fā)式算法，簡稱CDS法。他們把Johnson算法用于一般的n/m/P/Fmax問題，得到（m一1)個加工順序，取其中優(yōu)者。具體做法是，對加工時間和（l=1，2，…，m-1），用Johnson算法求（m-1)次加工順序，取其中最好的結果。i1234l=1Pi11263Pi34582l=2Pi1+Pi296812Pi2+Pi31291011舉例

當l＝1時，按Johnson算法得到加工順序（1，2，3，4）i1234Pi1Pi2Pi3112369312

89413215924

413518826228

Fmax=28當l=2時，得到加工順序(2，3，1，4)對于順序（2，3，1，4）i2314Pi1Pi2Pi3226819312

46210818927

511819423229

Fmax=29所以，取順序（1，2，3，4）四、相同零件、不同移動方式下加工周期的計算1、順序移動

一批零件在上道工序全部加工完畢后才整批轉移到下道工序繼續(xù)加工。一批零件的加工周期為：例：已知n=4,t1=10分，t2＝5分鐘，t3＝15分鐘，t4＝10分鐘，求T順

t1t4t2t3工序4060120160T順＝4×(10+5+15+10)=160（分鐘）2、平行移動方式

每個零件在前道工序加工完畢后，立即轉移到下道工

序繼續(xù)加工，形成前后交叉作業(yè)。一批零件的加工周期為：

T平＝（10＋5＋15＋10）＋（4-1)×15

=85(分鐘）

t1t3時間t4t23075853、平