【正文】 間。 i 1 2 3 4 pi1 1 9 5 4 pi2 5 7 6 3 pi3 4 6 3 5 pi4 6 2 3 7 四、相同零件、不同移動方式下加工周期的計算 ? 排序問題針對的是不同零件，如果 n個零件相同，則沒有排序問題。 i 1 2 3 4 pi1 1 9 5 4 pi2 5 7 6 3 pi3 4 6 3 5 pi4 6 2 3 7 i 1 2 3 4 pi1 1 9 5 4 pi2 5 7 6 3 pi3 4 6 3 5 pi4 6 2 3 7 pi 16 24 17 19 （三） CDS法 ? 康坎貝爾 杜德克 史密斯三人提出了一個啟發(fā)式算法，簡稱 CDS法。在最優(yōu)順序下， F max =28。 ? （ 2）機器 1共需工作多長時間？ ? （ 3）機器 2應該在機器 1開始工作后多長時間開始運轉(zhuǎn)？ 任務(wù) 在機器 1上加工所需時間（小時） 在機器 2上加工所需時間（小時） A B C D 0 任務(wù) 在機器 1上加工所需時間（小時） 在機器 2上加工所需時間（小時） A B C D 0 B, A, C, D, B, A, C, 機器 1 機器 2 三、一般 n/m/P/Fmax問題的啟發(fā)式算法 ? 啟發(fā)式算法是一個基于直觀或經(jīng)驗構(gòu)造的算法，在可接受的花費 (時間、占用空間等 )下給出待解決組合優(yōu)化問題的可行解 。 【例】求如表所示的 6/2/F/Fmax問題的最優(yōu)解。 ? 例 有一個 6/4/P/Fmax問題，其加工時間如下表所示。 ? MWKR法則使不同工作量的工件的完工時間盡量接近。 流程時間 =等待時間 +加工時間 平均在制品庫存 =各工件流程時間之和247。 ? LWKR規(guī)則 優(yōu)先選擇余下加工時間最短的工件。 五、優(yōu)先調(diào)度規(guī)則 ? 調(diào)度方法： ? 所謂調(diào)度方法，就是運用若干預先規(guī)定的優(yōu)先順序規(guī)則，順次決定下一個應被加工的工件的排序方法。在 A的位置若標以標以“ P”，則表示 流水作業(yè)排列排序 問題；若標以“ G”，則表示一般單件作業(yè)排序問題。 ? ，即當上一道工序完工后，立即送下道工序加工。醫(yī)院要安排病人手術(shù)，為此要安排手術(shù)室，配備手術(shù)器械、手術(shù)醫(yī)師和護士。第十一章 制造業(yè)作業(yè)計劃與控制 ? 引言 ? 通過 MRP確定各車間的零部件投入出產(chǎn)計劃，從而將全廠性的產(chǎn)品出產(chǎn)計劃變成了各車間生產(chǎn)作業(yè)計劃，將車間的生產(chǎn)任務(wù)變成各個班組、各個工作地和各個工人的任務(wù)。 ? 編制作業(yè)計劃要解決先加工哪個工件、后加工哪個工件的加工順序問題 ? 確定機器加工每個工件的開始時間和完成時間 ? 例如 。零件可以是單個零件，也可以是一批相同的零件 ? “加工順序”則表示每臺機器加工 n個零件的先后順序，是排序和編制作業(yè)計劃要解決的問題 二、假設(shè)條件和符號說明 ? 假設(shè)條件： ? 。 ? 根據(jù)工件到達系統(tǒng)的情況 – 靜態(tài)排序 – 動態(tài)排序 ? 根據(jù)參數(shù)的性質(zhì) – 確定型排序 – 隨機型排序 4參數(shù)法 ? n/m/A/B ? 其中， n為工件數(shù) ? m為機器數(shù) ? A車間類型。 ? ? 用一臺機器或一個工人的有效生產(chǎn)時間占總工作時間的百分比來表示。 ? MWKR規(guī)則 優(yōu)先選擇余下加工時間最長的工件。 發(fā)動機機殼 所需標準加工時間 （包括機器調(diào)整） 預計顧客取貨時間 （從現(xiàn)在開始算起的所需工作時間） 機殼 1 8 10 機殼 2 6 12 機殼 3 15 20 機殼 4 3 18 機殼 5 12 22 機殼加工次序 開始 工作 加工 時間 結(jié)束 工作 流程 時間 預計顧客 取貨時間 顧客實際取貨時間 提前 小時數(shù) 拖延 小時數(shù) 機殼 4 0 3 3 3 18 18 15 機殼 2 3 6 9 9 12 12 3 機殼 1 9 8 17 17 10 17 7 機殼 5 17 12 29 29 22 29 7 機殼 3 29 15 44 44 20 44 24 總數(shù) 102 120 18 38 平均數(shù) 平均在制品庫存 =102/44= 平均總庫存 =120/44= SPT規(guī)則排序結(jié)果 顧客實際取貨時間基于以下假設(shè)：顧客不會在預定取貨時間之前來取貨；如果有拖延發(fā)生，他們將在加工結(jié)束時馬上取走。 ? EDD法則可使工件延誤時間最小。 ? 最長流程時間 又稱加工周期，它是從第一個零件在第一臺機器開始加工時算起，到最后一個零件在最后一臺機器上完成加工時為止所經(jīng)過的時間。 ? （ 4）對于剩余的作業(yè)重復第二步和第三步，直到整個排序完成。 ? （ 1）安排生產(chǎn)順序，使得在最短時間內(nèi)完成生產(chǎn)。如不是這樣，則從中挑選較優(yōu)者。 ? 解：總加工時間最長的為 2號零件， pi1≤p i4的零件為1和 3，按 pi1不減的順序排成 sa=（ 1， 4）； pi1＞ pi4的零件為 4號零件， sb=（ 3），這樣得到的順序為（ 1， 4，2， 3）。 用 Palmer法、關(guān)鍵工件法和 CDS法求以下 4/4/P/Fmax問題的最優(yōu)解，并比較三種方法的結(jié)果。 時間 工序 1 2 3 4 加工 周期 （ 1）當 titi+1時，零件按平行移動方式轉(zhuǎn)移； （ 2）當 ti≥t i+1時，以i工序最后一個零件的完工時間為基準，往前推移（ n1） ti+1作為零件在（ i+1）工序的開始時間。 問應如何分配才能使總效率 （ 時間或費用 ） 最高 ？ )..,1(0)..( 1)..( 1min111 1njixnjxnixxcZijniijnjijninjijij????????????? ???? ?或指派問題模型 （ The Model for Assignment Problem） ??????項任務(wù)個人取完成第不分配第項任務(wù)個人取完成第分配第ji0ji1ijx 典型問題 例 1：有一份說明書，要分別譯成英、日、德、俄四種文字，交與甲、乙、丙、丁四個人去完成，因各人專長不同，他們完成翻譯不同文字所需要的時間（小時）如表所示。若 m n, 則轉(zhuǎn)入下一步。 （ i， j， k）表示工件 i的第 j道工序在機器 k上進行。 ? （ 3）從 {Ot}中選出滿足以下兩個條件的工序 Oj：需要 M*加工，且 Tj T* 。 ? （ 5）若還有未安排的工序，轉(zhuǎn)步驟（ 2）；否則，停止。假定車子在重新噴漆前要經(jīng)過重新整修的步驟，南希廠可以滿足時間要求并且得到合同嗎？ 汽車 整修時間（小時） 重新噴漆時間（小時） A 6 3 B 0 4 C 5 2 D 8 6 E 2 1 ? 2/3/G/Fmax問題，其加工描述矩陣 D和加工時間矩陣 T分別為： ? 試構(gòu)成一個能動作業(yè)計劃和無延遲作業(yè)計劃。 生產(chǎn)作業(yè)控制 三、生產(chǎn)作業(yè)控制的主要工具 ? 實際生產(chǎn)中，有不少工具可以用來進行生產(chǎn)作業(yè)控制，這些工具容易通過運用適當?shù)能浖砩?，主要包括? ? 調(diào)度單 ? 日報、月報 ? 例外報告、異常報告 ? 輸入 /輸出 （ I/O） 報告 日常調(diào)度單 ? 它告訴主管哪些工件要被加工，這些工件的優(yōu)先級以及加工時間。 ③ 若希望平均通過時間在所控制的范圍內(nèi)，則適當調(diào)整平均在制品庫存與生產(chǎn)率的比例。 注：曲線圖的垂直段表示到達或完成的工作量；水平段表示相鄰到達或完成的任務(wù)之間的時間間隔。 ? 生產(chǎn)運作控制的受控客體是生產(chǎn)運作過程，其預定目標是主生產(chǎn)計劃與生產(chǎn)作業(yè)計劃的目標值。 練 習 ? 交易所提供全部客戶服務(wù)的合同。 ? （ 2）求 T* = min{Tk},并求出 T*所出現(xiàn)的機器 M*。 ? 符號說明 – 每安排一道工序稱為一“步” – {St}:t步之前已排序工序構(gòu)成的部分作業(yè)計劃； – {Ot}:t步可排序工序的集合； – Tk為 {Ot}中工序 Ok的最早可能開始時間； – T’ k為 {Ot}中工序 Ok的最早可能完成時間。轉(zhuǎn)回第 2步。 4 2 ????????????00102350960607130 在變化后的效率矩陣中找盡可能多的獨立 0元素，若能找出 n個獨立 0元素，就以這 n個獨立 0元素對應解矩陣 (xij)中的元素為 1，其余為 0，這就得到最優(yōu)解。 ? 解： T順 =4（ 10+5+15+10） =160分鐘 ? T平 =（ 10+5+15+10） +（ 41） 15=85分鐘 ? T平順 =4（ 10+5+15+10） （ 41）（ 5+5+10） =100分鐘 比較項目 平行移動 平行順序移動 順序移動 生產(chǎn)周期 短 中 長 運輸次數(shù) 多 中 少 設(shè)備利用 差 好 好 組織管理 中 復雜 簡單 零件三種移動方式的比較 ? 已知 m=5,n=4,t1=10,t2=4,t3=8,t4=12,t5=6,分別求在順序移動、平行移動和平行順序移動方式下，這批零件的加工周期。 分鐘101 ?t 分