【正文】 鐘104t 設(shè)零件批量為 n（件），工序數(shù)目為 m，一批零件不計算工序間運輸時間，只考慮加工時間，設(shè)其加工的周期為 T（分鐘），零件在 i道工序的單件工時為 ti （分鐘 /件）， i=…n 。和 1m21pml1mkik1????????lplkik 。 ? （ 3）順序（ Sa， C， Sb）即為所求順序。 ? 工件的斜度指標(biāo)可按下式計算： ? k=l， 2， … ， m ? 式中， m為機器數(shù)； pik為工件 i在 Mk上的加工時間。 任務(wù) ai bi A 9 6 B 7 2 C 10 3 D 8 1 E F G H 2 1 5 4 5 8 7 4 ? 1. 將所有 ai ≤ bi的工件按 ai值不減的順序排成一個序列 A； ? 2. 將 ai＞ bi的工件按 bi值不增的順序排成一個序列 B； ? 3. 將 A放到 B之前，就構(gòu)成了一個最優(yōu)加工順序。約翰遜算法包括以下幾個步驟： ? （ 1）列出每個作業(yè)在兩臺機器上的加工時間。 ? 加工路線一致，是指工件的流向一致，并不要求每個工件必須經(jīng)過加工路線上每臺機器加工。 比較 SPT規(guī)則和 EDD規(guī)則的排序結(jié)果，用 SPT規(guī)則排序，其平均流程時間更短，在制品庫存更少。 一般作業(yè)排序的目標(biāo) ?滿足顧客或下一道工序的交貨期要求 ?流程時間最短 ?準(zhǔn)備時間最短或成本最小化 ?在制品庫存最低 ?機器設(shè)備或勞動力利用最大化 ? [例 ] 一個加工車間負(fù)責(zé)加工發(fā)動機機殼，現(xiàn)在共有 5個機殼等待加工。 ? EDD規(guī)則 優(yōu)先選擇完工期限最緊的工作。 ? 2. 加工周期 ? 完成一組工作所需的全部時間。 ? 。通常情況下都是按最早可能開（完）工時間來編制作業(yè)計劃。 ? 作業(yè)計劃問題的基本概念 ? 流水作業(yè)排序問題 ? 單件作業(yè)的排序問題 ? 生產(chǎn)作業(yè)控制 11 收入、費用和利潤 要求掌握： 3種啟發(fā)式算法 4. 相同零件的 3種移動方式下機器加工周期的計算方法 學(xué)習(xí)目的與要求 重點 最長流程時間的計算 約翰遜算法 相同零件的 3種移動方式下機器加工周期的計算方法 難點 一般流水作業(yè)排序問題的啟發(fā)式算法 教學(xué)重點與難點 生產(chǎn)任務(wù)的最終落實 ? MRP確定各車間的零部件投入出產(chǎn)計劃，將全廠性的產(chǎn)品出產(chǎn)計劃變成了各車間的生產(chǎn)任務(wù)。 ? 各車間要將車間的生產(chǎn)任務(wù)變成各個班組、各個工作地和各個工人的任務(wù)。 ? 派工：按作業(yè)計劃的要求，將具體生產(chǎn)任務(wù)安排到具體的機床上加工。 ? 、機器數(shù)和加工時間已知，加工時間與加工順序無關(guān)。它是從第一個工件在第一臺機器上開始加工時算起，到最后一個工件在最后一臺機器上完工時為止所經(jīng)過的時間。 ? SPT規(guī)則 優(yōu)先選擇加工時間最短的工件。只有一名技工在崗，做此項工作。用 EDD規(guī)則，可以給顧客提供更好的服務(wù)（平均延遲時間較少），它也提供了更低的總庫存水平。 ? 對于流水作業(yè)排序問題，工件在不同機器上的加工順序不盡一致。 ? （ 2）選擇最短的加工時間，如果有兩個相同的值，則任選一個。 改進(jìn)算法 工件號 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 4 工件最優(yōu)順序： 2 5 6 1 4 3 1 3 4 5 5 8 2 7 4 7 4 2 1 4 8 13 18 26 3 11 15 22 26 28 ai bi 最優(yōu)順序下的加工周期為 28 練 習(xí) ? 某公司要生產(chǎn) 4種產(chǎn)品，需要兩臺機器 1和 2。 ? 按照各工件 λ i不增 的順序排列工件，可得出令人滿意的順序。 i 1 2 3 4 pi1 1 2 6 3 pi2 8 4 2 9 pi3 4 5 8 2 pi 13 11 16 14 例 有一個 4/3/F/Fmax問題，其加工時間如下表所示，試用關(guān)鍵零件法求最優(yōu)順序。和 1m21pml1mkik1????????lplkikm=2時， l=1,加工時間分別為 pi1和 pi2； m=3時， l=1,2,加工時間分別為 ： （ 1） l=1， pi1和 pi3 （ 2） l=2,pi1+pi2和 pi2+pi3 m=4時， l=1， 2， 3，加工時間分別為： （ 1） l=1,pi1和 pi4 （ 2） l=2， pi1+pi2和 pi3+pi4 （ 3） l=3， pi1+pi2+pi3和 pi2+pi3+pi4 l A 加工時間 B 加工時間 1 t 1 t m 2 t 1 +t 2 t m1 +t m 3 t 1 +t 2 +t 3 t m2 +t m1 +t m … …… …… m1 t 1 +t 2 + … +t m1 t 2 + … +t m 1 +t m i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 2)1(pml1mkik1，和 ??????lplkiki 1 2 3 4 l=1 pi1 1 2 6 3 pi3 4 5 8 2 l=2 pi1+pi2 9 6 8 12 pi2+pi3 12 9 10 11 i 1 2 3 4 l=1 pi1 1 2 6 3 pi3 4 5 8 2 l=2 pi1+pi2 9 6 8 12 pi2+pi3 12 9 10 11 當(dāng) l=1時，按（ Johnson）算法得到加工順序（ 1， 2， 3，4）； 當(dāng) l=2時，得到加工順序（ 2， 3， 1， 4）。 則該批零件的加工周期為： 121... mimiT nt nt nt n t?? ? ? ? ? 已知 n=4， t1=10分鐘， t2=5分鐘， t3=15分鐘，t4=10分鐘，則 T順 =4（ 10+5+15+10） =160分鐘 （二）平行移動方式 分鐘101 ?t 分鐘52t 分鐘153 ?t工序 1 2 3 4 時間 加工周期 每個零件在前道工序加工完畢后，立即轉(zhuǎn)移到后道工序去繼續(xù)加工，形成前后工序交叉作業(yè)。 第三節(jié) 單件作業(yè)排序問題 ? 指派問題 ? 單件作業(yè)排序問題的描述 ? 兩種作業(yè)計劃的構(gòu)成 ? 求解一般 n/m/G/Fmax問題的啟發(fā)式方法 ? 指派問題的形式表述 ? 給定了一系列所要完成的任務(wù)（ tasks）以及一系列完成任務(wù)的被指派者（ assignees），所需要解決的問題就是要確定出哪一個人被指派進(jìn)行哪一項任務(wù) 指派問題的假設(shè) ?被指派者的數(shù)量和任務(wù)的數(shù)量是 相同的 ?每一個被指派者只完成 一項任務(wù) ?每一項任務(wù)只能由 一 個被指派者 來完成 ?每個被指派者和每項任務(wù)的組合有一個相關(guān)成本 ?目標(biāo)是要確定怎樣進(jìn)行指派才能使得總成本最小 指派問題 設(shè) n 個人被分配去做 n 件工作 ， 每人只能完成一項任務(wù) ， 每項任務(wù)只能由一人完成 。 第 2步：進(jìn)行試指派，即確定獨立零元素 （ 1）從有唯一的零元素的行或列開始確定獨立零元素，并用 表示，并劃掉其所在行或列的其他零。 2142 289541013895421176)(?????????????????ijc????????????0673390245100954????????????017340201004545 √ √ ????????????????1062340240101343??????????????0062440250100343???????????????0100001000011000ijx√ 問題的描述 加工描述矩陣 D為 D= 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2 對于一般單件作業(yè)排序問題，每個工件都有其獨特的加工路線，工件沒有一定的流向。 （一）能動作業(yè)計劃的構(gòu)成步驟 ? （ 1）設(shè) t=1,{S1}為空集， {O1}為各工件第一道工序的集合。 如果 M*有多臺，則任選一臺。