制造業(yè)流水作業(yè)計劃(編輯修改稿)
2025-01-24 14:29 本頁面
【文章內容簡介】 排列排序問題 ， 可以用分支定界法 。 求一般 n/m/P/ Fmax問題近優(yōu)解 (Near optimal solution)的啟發(fā)式算法 ? 關鍵零件法 ? CDS法 ? 關鍵零件法求近優(yōu)解舉例 表 11 5 加工時間矩陣 i 1 2 3 4 P i1 1 2 6 3 P i2 8 4 2 9 P i3 4 5 8 2 表 11 － 6 用關鍵零件法求解 i 1 2 3 4 P i1 1 2 6 3 P i2 8 4 2 9 P i3 4 5 8 2 p i 13 11 16 14 CDS法 ? CampbellDudekSmith 三人提出了一個啟發(fā)式算法 ,簡稱 CDS法。他們把Johnson算法用于一般的 n/m/P/Fmax問題，得到 (ｍ－ 1)個加工順序，取其中優(yōu)者 ? 當ｌ＝ 1時，按 Johnson算法得到加工順序 (1，2， 3， 4)； 當ｌ＝ 2時，得到加工順序 (2， 3， 1， 4)。對于順序 (2， 3， 1， 4)，相應的Fmax＝ 29。所以，取順序 (1， 2， 3， 4)。我們已經(jīng)知道，這就是最優(yōu)順序。 表11－7 用CDS法求解 i 1 2 3 4 P i1 1 2 6 3 l=1 P i3 4 5 8 2 P i1 +p i2 9 6 8 12 L=2 P i2 +p i3 12 9 10 11 單件作業(yè)排序問題 ? 加工描述矩陣和加工時間矩陣 1,1,1 1,2,3 1,3,2 2 4 1 D＝ T＝ 2,1,3 2,2,1 2,3,2 3 4 5 無延遲作業(yè)計劃 (nondelay schedule)的構成 ? 我們稱每安排一道工序稱作一 “ 步 ” ，設 ? {St}──t 步之前已排序工序構成的部分作業(yè)計劃； ? { Ot }── 第 t步可以排序的工序的集合； ? Tk ──{ Ot }中工序 Ok的最早可能開工時間； ? Tk’ ──{ Ot }中工序 Ok的最早可能完工時間 。 無延遲作業(yè)計劃的構成步驟 : ? ① 設 t＝ 1， {S1}為空集， {O1}為各工件第一道工序的集合。 ② 求 T*＝ min{Tk}，并求出 T*出現(xiàn)的機器M*。如果 M*有多臺，則任選一臺。 ③ 從 {Ot}中挑出滿足以下兩個條件的工序 Oj：需要機器 M*加工，且 Tj＝ T*。 ④ 將確定的工序 Oj放入 {St}，從 { Ot }中消去 Oj，并將 Oj的緊后工序放入 { Ot }，使 t＝ t＋ 1。 ⑤ 若還有未安排的工序，轉步驟②；否則，停止。 表 11 11 無延遲計劃的構成 t { O t } T k T k T* M* O j 1 0 0 2 3 0 0 M 1 M 3 2 2 0 6 3 0 M 3 3 3 3 7 7 3
教學課件相關推薦
鄂ICP備17016276號-1