車間作業(yè)計劃與控制(編輯修改稿)
2024-11-17 22:48 本頁面
【文章內(nèi)容簡介】 SOT）規(guī)則]，則平均流程時間最小。 [定理2] 對于單機進度計劃問題，如從交貨期最短的工件開始順序進行排序[最早交貨期（EDD）規(guī)則]，則最大交貨期延遲Lmax或最大交貨期延誤Tmax最小。,?,8.2.5 n個作業(yè)兩臺工作中心排序,n/2/A/B，即 n/2問題。,?,8.2.5 n個作業(yè)兩臺工作中心排序,n個作業(yè)在兩臺機器上排序的目標是使最大完成時間（總加工周期）最短。 對于n/2問題，Johnson算法。,?,8.2.5 n個作業(yè)兩臺工作中心排序,Johnson法則： 如果以pi1表示零件Ji機器M1上加工時間，以pi2表示上M2加工時間，每個零件都按照M1→ M2的路線加工， 如果min(pi1, pj2) min(pj1, pi2), 則零件Ji應該排在工件Jj之前。如果中間是等號，則可以隨意安排。,?,8.2.5 n個作業(yè)兩臺工作中心排序,Johnson算法： （1）從加工時間矩陣中找出最短的加工時間。 （2）若最短的加工時間出現(xiàn)在M1上，則對應的工件盡可能往前排；若最短加工時間出現(xiàn)在M2上，則對應工件盡可能往后排。然后，從加工時間矩陣中劃去已排序工件的加工時間。若最短加工時間有多個，則任挑一個。 （3）若所有工件都已排序，停止。否則，轉(zhuǎn)步驟（1）。,?,8.2.5 n個作業(yè)兩臺工作中心排序,例8.2 現(xiàn)有5個訂單，每個訂單在兩臺工作中心上的作業(yè)時間如表所示，求5/2/F/Fmax問題的最優(yōu)解。,?,8.2.5 n個作業(yè)兩臺工作中心排序,2,,2,4,2,2,2,4,4,4,1,1,1,3,3,5,?,8.2.5 n個作業(yè)兩臺工作中心排序,?,8.2.5 n個作業(yè)兩臺工作中心排序,n/2問題，需注意以下問題： （1）M1為連續(xù)安排作業(yè)，無須等待時間，故閑置時間為零； （2）M1的排序結(jié)果和M2的排序結(jié)果相同； （3）M2的閑置時間是造成總時間增加的因素，應盡量縮短這種閑置浪費時間； （4）最小所有作業(yè)完成總時間有時不一定是唯一的一中排序結(jié)果。,?,8.2.6 n個作業(yè)m臺工作中心排序,如果需要n個作業(yè)在m臺工作中心上加工，就是“n/m”排序問題。 當m大于2時，就很難找到最優(yōu)解，計算也比較復雜，計算量也大，往往要借助計算機計算。 “n/m/F/Fmax”排序問題啟發(fā)式算法： Palmer算法、 CDS算法。 “n/m/P/Fmax”排序問題可用分支定界法得到最優(yōu)解。,?,8.2.6 n個作業(yè)m臺工作中心排序,Palmer算法 Palmer于1965年對流水作業(yè)排序問題提出了按斜度指標排列工件的啟發(fā)式算法，該算法先定義工件的斜度指標，然后將各工件按其斜度指標不增進行排序。,?,8.2.6 n個作業(yè)m臺工作中心排序,例8.3 有一個4/3/F/Fmax問題，其加工時間如表所示，試用Palmer法求解。,?,8.2.6 n個作業(yè)m臺工作中心排序,解：計算λ ， 按照λ不增進行排序，得到最優(yōu)順序為：（1,2,3,4）或（2,1,3,4），F(xiàn)max=28。,?,8.2.6 n個作業(yè)m臺工作中心排序,CDS算法 Campbell等人于1970年對流水作業(yè)排序問題提出了一個基于Johnson算法的啟發(fā)式算法，該算法先產(chǎn)生m1個排列，然后從中選優(yōu)。 依次令j=1,2,3,.,m1,，可以得到m1組αj和βj，將每一組值看成是分別在兩個機器上的加工時間，根據(jù)Johnson算法可以求得一個排序，共可得到m1個排序，從中選優(yōu)。,?,8.2.6 n個作業(yè)m臺工作中心排序,例8.4 有一個4/3/F/Fmax問題，其加工時間如表所示，試用CDS法求解。,?,8.2.6 n個作業(yè)m臺工作中心排序,解：首先求 αj和βj ，結(jié)果如表下表所示,,,,,,?,8.2.6 n個作業(yè)m臺工作中心排序,當j=1時，根據(jù)Johnson算法得到加工順序（1,2,3,4）；當j=2時，得到加工順序（2,3,1,4）,這時Fmax為29；所以，取順序（1,2,3,4）。,?,8.2.6 n個作業(yè)m臺工作中心排序,加工周期的計算 “n/m”排序問題的加工周期（最長流程時間），是指從第一個零件在第一臺機器上開始加工算起，直到最后一個零件在最后一臺機器上完成加工時所經(jīng)過的時間。 假設零件到達時間ri=0，所以Fmax等于排在末位加工的零件在車間的停留時間，也等于一批零件的最長完工時間Cmax。,?,8.2.6 n個作業(yè)m臺工作中心排序,加工周期的計算 設n個零件的加工順序為S=（S1, S2, ., Sn）,其中Si為排在第i位的零件代號。以Cksi表示零件Si在機器Mk上的完工時間，PSik表示零件Si在機器Mk上的加工時間，k=1, 2, ., m；i=1, 2, ., n；則Cksi可以按以下公式計算：,?,8.2.6 n個作業(yè)m臺工作中心排序,例8.5 有一個4/3/F/Fmax問題，其加工時間如表所示，得到最優(yōu)順序為：（1,2,3,4） ，求加工周期。,?,8.2.6 n個作業(yè)m臺工作中心排序,解：按（1,2,3,4）順序列出加工時間矩陣，按公式遞推計算，將每個零件的完工時間列在加工時間的右上角。,,,,?,8.2.7 指派法：任務分配,指派問題：也稱為“任務分配”，將n個零件安排在n各機器上的加工的問題。 問題的關鍵：n個零件如何在n個機器上分配，而不是加工的先后順序。 求解的目標：使任務和資源得到最佳
公司管理相關推薦
鄂ICP備17016276號-1