【正文】 相同零件的 3種移動(dòng)方式下機(jī)器加工周期的計(jì)算方法 難點(diǎn) 一般流水作業(yè)排序問(wèn)題的啟發(fā)式算法 教學(xué)重點(diǎn)與難點(diǎn) 生產(chǎn)任務(wù)的最終落實(shí) ? MRP確定各車(chē)間的零部件投入出產(chǎn)計(jì)劃，將全廠性的產(chǎn)品出產(chǎn)計(jì)劃變成了各車(chē)間的生產(chǎn)任務(wù)。 ? 將任務(wù)安排到工作地，牽涉到作業(yè)計(jì)劃。 ? 編制作業(yè)計(jì)劃要解決先加工哪個(gè)工件、后加工哪個(gè)工件的加工順序問(wèn)題 ? 確定機(jī)器加工每個(gè)工件的開(kāi)始時(shí)間和完成時(shí)間 ? 例如 。 第一節(jié) 排序問(wèn)題的基本概念 ? 一、名詞術(shù)語(yǔ) ? 排序：確定工件在機(jī)器上的加工順序。通常情況下都是按最早可能開(kāi)（完）工時(shí)間來(lái)編制作業(yè)計(jì)劃。 ? 趕工：實(shí)際進(jìn)度已落后于計(jì)劃進(jìn)度時(shí)采取的行動(dòng)。零件可以是單個(gè)零件，也可以是一批相同的零件 ? “加工順序”則表示每臺(tái)機(jī)器加工 n個(gè)零件的先后順序，是排序和編制作業(yè)計(jì)劃要解決的問(wèn)題 二、假設(shè)條件和符號(hào)說(shuō)明 ? 假設(shè)條件： ? 。 ? 。 ? 。 ? 有關(guān)符號(hào) ? Ji：工件 i， i=1， 2， … ， n ? Mj：機(jī)器 j， j=1， 2， … ， n ? pij為 Ji在 Mj上的加工時(shí)間 ? ri為 Ji的到達(dá)時(shí)間，指 Ji從外部進(jìn)入車(chē)間，可以加工的最早時(shí)間 ? di為 Ji的完工期限 ? Ci為 Ji的完工時(shí)間 ? Cmax為最長(zhǎng)完工時(shí)間 ? Fi為 Ji的流程時(shí)間，即工件在車(chē)間的實(shí)際停留時(shí)間 ? Fmax為最長(zhǎng)流程時(shí)間 ? Li為工件的延遲時(shí)間 ? Lmax為最長(zhǎng)延遲時(shí)間 三、排序問(wèn)題的分類(lèi) ? 根據(jù)機(jī)器數(shù)的多少 – 單臺(tái)機(jī)器的排序問(wèn)題 – 多臺(tái)機(jī)器的排序問(wèn)題 ? 對(duì)于多臺(tái)機(jī)器排序問(wèn)題，根據(jù)加工路線的特征，分成 – 單件作業(yè)排序 (Job Shop)問(wèn)題 – 流水作業(yè)排序 (Flow Shop)問(wèn)題 ? 工件的加工路線不同，是單件作業(yè)排序問(wèn)題的基本特征； ? 所有工件的加工路線完全相同，是流水作業(yè)排序問(wèn)題的基本特征。 ? 根據(jù)工件到達(dá)系統(tǒng)的情況 – 靜態(tài)排序 – 動(dòng)態(tài)排序 ? 根據(jù)參數(shù)的性質(zhì) – 確定型排序 – 隨機(jī)型排序 4參數(shù)法 ? n/m/A/B ? 其中， n為工件數(shù) ? m為機(jī)器數(shù) ? A車(chē)間類(lèi)型。當(dāng)m=1，則 A處為空白。 ? 2. 加工周期 ? 完成一組工作所需的全部時(shí)間。 ? （ WIP） ? 在制品是對(duì)介于原材料和成品之間的生產(chǎn)過(guò)程中的產(chǎn)品的稱(chēng)謂。 ? ? 用一臺(tái)機(jī)器或一個(gè)工人的有效生產(chǎn)時(shí)間占總工作時(shí)間的百分比來(lái)表示。 ? 一個(gè)工作地可選擇的下一個(gè)工件會(huì)有很多種，因此，按什么樣的準(zhǔn)則來(lái)選擇，對(duì)排序方案的優(yōu)劣有很大影響。 ? EDD規(guī)則 優(yōu)先選擇完工期限最緊的工作。 ? SCR規(guī)則 優(yōu)先選擇臨界比最小的工件。 ? MWKR規(guī)則 優(yōu)先選擇余下加工時(shí)間最長(zhǎng)的工件。 ? MOPNR規(guī)則 優(yōu)先選擇余下工序數(shù)最多的工件。 一般作業(yè)排序的目標(biāo) ?滿(mǎn)足顧客或下一道工序的交貨期要求 ?流程時(shí)間最短 ?準(zhǔn)備時(shí)間最短或成本最小化 ?在制品庫(kù)存最低 ?機(jī)器設(shè)備或勞動(dòng)力利用最大化 ? [例 ] 一個(gè)加工車(chē)間負(fù)責(zé)加工發(fā)動(dòng)機(jī)機(jī)殼，現(xiàn)在共有 5個(gè)機(jī)殼等待加工。現(xiàn)在已經(jīng)估算出各個(gè)機(jī)殼的標(biāo)準(zhǔn)加工時(shí)間，顧客也已經(jīng)明確提出了他們所希望的完工時(shí)間。 發(fā)動(dòng)機(jī)機(jī)殼 所需標(biāo)準(zhǔn)加工時(shí)間 （包括機(jī)器調(diào)整） 預(yù)計(jì)顧客取貨時(shí)間 （從現(xiàn)在開(kāi)始算起的所需工作時(shí)間） 機(jī)殼 1 8 10 機(jī)殼 2 6 12 機(jī)殼 3 15 20 機(jī)殼 4 3 18 機(jī)殼 5 12 22 機(jī)殼加工次序 開(kāi)始 工作 加工 時(shí)間 結(jié)束 工作 流程 時(shí)間 預(yù)計(jì)顧客 取貨時(shí)間 顧客實(shí)際取貨時(shí)間 提前 小時(shí)數(shù) 拖延 小時(shí)數(shù) 機(jī)殼 4 0 3 3 3 18 18 15 機(jī)殼 2 3 6 9 9 12 12 3 機(jī)殼 1 9 8 17 17 10 17 7 機(jī)殼 5 17 12 29 29 22 29 7 機(jī)殼 3 29 15 44 44 20 44 24 總數(shù) 102 120 18 38 平均數(shù) 平均在制品庫(kù)存 =102/44= 平均總庫(kù)存 =120/44= SPT規(guī)則排序結(jié)果 顧客實(shí)際取貨時(shí)間基于以下假設(shè)：顧客不會(huì)在預(yù)定取貨時(shí)間之前來(lái)取貨；如果有拖延發(fā)生，他們將在加工結(jié)束時(shí)馬上取走。加工周期 平均總庫(kù)存 =各工件實(shí)際取貨時(shí)間之和247。 比較 SPT規(guī)則和 EDD規(guī)則的排序結(jié)果，用 SPT規(guī)則排序，其平均流程時(shí)間更短，在制品庫(kù)存更少。 優(yōu)先調(diào)度法則 ? 按 SPT法則可使工件的平均流程時(shí)間最短，從而減少在制品量。 ? EDD法則可使工件延誤時(shí)間最小。 LWKR法則，使工作量小的工件盡快完成。 ? 加工路線一致，是指工件的流向一致，并不要求每個(gè)工件必須經(jīng)過(guò)加工路線上每臺(tái)機(jī)器加工。 ? 排列排序問(wèn)題：所有工件在各臺(tái)機(jī)器上的加工順序都相同的情況。 ? 最長(zhǎng)流程時(shí)間 又稱(chēng)加工周期，它是從第一個(gè)零件在第一臺(tái)機(jī)器開(kāi)始加工時(shí)算起，到最后一個(gè)零件在最后一臺(tái)機(jī)器上完成加工時(shí)為止所經(jīng)過(guò)的時(shí)間。當(dāng)按順序 S=（ 6， 1， 5， 2， 4， 3）加工時(shí)，求 Fmax。約翰遜算法包括以下幾個(gè)步驟： ? （ 1）列出每個(gè)作業(yè)在兩臺(tái)機(jī)器上的加工時(shí)間。 ? （ 3）如果最短的加工時(shí)間來(lái)自第一臺(tái)機(jī)器，那么先完成這個(gè)作業(yè)；如果來(lái)自第二臺(tái)機(jī)器，那么這個(gè)作業(yè)就放在最后完成。 ? （ 4）對(duì)于剩余的作業(yè)重復(fù)第二步和第三步，直到整個(gè)排序完成。 i 1 2 3 4 5 6 ai 5 1 8 5 3 4 bi 7 2 2 4 7 將零件 2排第 1位 2 將零件 3排第 6位 2 3 將零件 5排第 2位 2 5 3 將零件 6排第 3位 2 5 6 3 將零件 4排第 5位 2 5 6 4 3 將零件 1排第 4位 2 5 6 1 4 3 【例 題】 ? 有 5件任務(wù)都需要兩步操作（先 1后 2）來(lái)完成，下表給出了相應(yīng)的時(shí)間： ? （ 1）根據(jù) Johnson算法安排工作順序； ? （ 2）計(jì)算加工周期。 任務(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值不減的順序排成一個(gè)序列 A； ? 2. 將 ai＞ bi的工件按 bi值不增的順序排成一個(gè)序列 B； ? 3. 將 A放到 B之前，就構(gòu)成了一個(gè)最優(yōu)加工順序。其中，有 3種產(chǎn)品需要先在機(jī)器 1上加工。 ? （ 1）安排生產(chǎn)順序，使得在最短時(shí)間內(nèi)完成生產(chǎn)。 ? 啟發(fā)式方法因其易于實(shí)現(xiàn)、計(jì)算復(fù)雜度低等原因，目前應(yīng)用得最為廣泛。 ? 工件的斜度指標(biāo)可按下式計(jì)算： ? k=l， 2， … ， m ? 式中， m為機(jī)器數(shù)； pik為工件 i在 Mk上的加工時(shí)間。 ? ? ikmki pmk ???? ?? 12/)1(? m,2,1k]2/)1([1????? ??，mkiki pmk?31i3m ii pp ???? ?時(shí)，當(dāng) 4321 iiiii pppp ?????? ?時(shí)，當(dāng) 54321 21025 iiiiii ppppp ??????? ?時(shí)，當(dāng) 例 有一個(gè) 4/3/F/Fmax問(wèn)題，其加工時(shí)間如下表所示，試用帕爾默法求最優(yōu)順序。如不是這樣，則從中挑選較優(yōu)者。 ? ? 321k2/)13(1，＝ ??????ikmki pk? （二）關(guān)鍵零件法 ? 步驟如下： ? （ 1）計(jì)算每個(gè)零件的總加工時(shí)間，找出加工時(shí)間最長(zhǎng)的零件 C，將其作為關(guān)鍵零件。 ? （ 3）順序（ Sa， C， Sb）即為所求順序。 解：總加工時(shí)間最長(zhǎng)的為 3號(hào)零件， pi1≤p i3的零件為 1和 2，按 pi1不減的順序排成 Sa=（ 1， 2）； pi1≥p i3的零件為 4號(hào)零件， Sb=（ 4） ,這樣得到的加工順序?yàn)椋?1， 2， 3， 4）。 ? 解：總加工時(shí)間最長(zhǎng)的為 2號(hào)零件， pi1≤p i4的零件為1和 3，按 pi1不減的順序排成 sa=（ 1， 4）； pi1＞ pi4的零件為 4號(hào)零件， sb=（ 3），這樣得到的順序?yàn)椋?1， 4，2， 3）。 ? 具體做法是，對(duì)加工時(shí)間 ? 用 Johnson算法求（ m1）次加工順序，取其中最好的結(jié)果。和 1m21pml1mkik1????????lplkik 。 對(duì)于（ 2， 3， 1， 4），相應(yīng)的 Fmax=29。 用 Palmer法、關(guān)鍵工件法和 CDS法求以下 4/4/P/Fmax問(wèn)題的最優(yōu)解，并比較三種方法的結(jié)果。但零件在加工過(guò)程中采取的移動(dòng)方式不同，會(huì)導(dǎo)致一批零件的加工周期不同。 分鐘101 ?t 分鐘104t 設(shè)零件批量為 n（件），工序數(shù)目為 m，一批零件不計(jì)算工序間運(yùn)輸時(shí)間，只考慮加工時(shí)間，設(shè)其加工的周期為 T（分鐘），零件在 i道工序的單件工時(shí)為 ti （分鐘 /件）， i=…n 。 分鐘104 ?t 零件平行移動(dòng)的加工周期 為： T平 。 時(shí)間 工序 1