生產(chǎn)運(yùn)作管理制造業(yè)作業(yè)計(jì)劃與控制-文庫吧
2025-01-29 22:56 本頁面
【正文】 臺機(jī)器加工，目標(biāo)是使這批零件的最長流程時間最短。 ? 最長流程時間 又稱加工周期，它是從第一個零件在第一臺機(jī)器開始加工時算起，到最后一個零件在最后一臺機(jī)器上完成加工時為止所經(jīng)過的時間。 ? 例 有一個 6/4/P/Fmax問題，其加工時間如下表所示。當(dāng)按順序 S=（ 6， 1， 5， 2， 4， 3）加工時，求 Fmax。 i 1 2 3 4 5 6 4 2 3 1 4 2 4 5 6 7 4 5 5 8 7 5 5 5 4 2 4 3 3 1 1iP2i3iPi 二、兩臺機(jī)器排序問題 ? 兩個或更多的作業(yè)必須在兩臺機(jī)器上以相同的工序進(jìn)行加工，要使加工周期最短，約翰遜于 1954年提出了一個有效算法，那就是著名的 Johnson算法 。約翰遜算法包括以下幾個步驟： ? （ 1）列出每個作業(yè)在兩臺機(jī)器上的加工時間。 ? （ 2）選擇最短的加工時間，如果有兩個相同的值，則任選一個。 ? （ 3）如果最短的加工時間來自第一臺機(jī)器，那么先完成這個作業(yè)；如果來自第二臺機(jī)器，那么這個作業(yè)就放在最后完成。然后從加工時間矩陣中劃去已排序工件的加工時間。 ? （ 4）對于剩余的作業(yè)重復(fù)第二步和第三步，直到整個排序完成。 【例】求如表所示的 6/2/F/Fmax問題的最優(yōu)解。 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）來完成，下表給出了相應(yīng)的時間： ? （ 1）根據(jù) Johnson算法安排工作順序； ? （ 2）計(jì)算加工周期。 任務(wù) 操作 1所需時間（小時） 操作 2所需時間（小時） A B C D E 任務(wù) 操作 1所需時間（小時） 操作 2所需時間（小時） A B C D E A, E, D,3 B,2 C,1 0 操作 1 A, E, D, B, C, 11 操作 2 A, E, D,3 B,2 C,1 0 操作 1 A, E, D, B, C, 11 操作 2 i C B D E A 操作 1 操作 2 1 . 【例 題】 根據(jù) Johnson算法求以下 8/2/F/Fmax問題的最優(yōu)解。 任務(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)加工順序。 改進(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)品，需要兩臺機(jī)器 1和 2。其中，有 3種產(chǎn)品需要先在機(jī)器 1上加工。下表給出了兩臺機(jī)器上加工各產(chǎn)品所需的時間。 ? （ 1）安排生產(chǎn)順序，使得在最短時間內(nèi)完成生產(chǎn)。 ? （ 2）機(jī)器 1共需工作多長時間？ ? （ 3）機(jī)器 2應(yīng)該在機(jī)器 1開始工作后多長時間開始運(yùn)轉(zhuǎn)？ 任務(wù) 在機(jī)器 1上加工所需時間（小時） 在機(jī)器 2上加工所需時間（小時） A B C D 0 任務(wù) 在機(jī)器 1上加工所需時間（小時） 在機(jī)器 2上加工所需時間（小時） A B C D 0 B, A, C, D, B, A, C, 機(jī)器 1 機(jī)器 2 三、一般 n/m/P/Fmax問題的啟發(fā)式算法 ? 啟發(fā)式算法是一個基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi) (時間、占用空間等 )下給出待解決組合優(yōu)化問題的可行解 。 ? 啟發(fā)式方法因其易于實(shí)現(xiàn)、計(jì)算復(fù)雜度低等原因，目前應(yīng)用得最為廣泛。 （一） Palmer法 ? 1965年， D． S． Palmer提出按 斜度指標(biāo) 排列工件的啟發(fā)式算法，稱之為 Palmer法。 ? 工件的斜度指標(biāo)可按下式計(jì)算： ? k=l， 2， … ， m ? 式中， m為機(jī)器數(shù)； pik為工件 i在 Mk上的加工時間。 ? 按照各工件 λ i不增 的順序排列工件，可得出令人滿意的順序。 ? ? ikmki pmk ???? ?? 12/)1(? m,2,1k]2/)1([1????? ??，mkiki pmk?31i3m ii pp ???? ?時，當(dāng) 4321 iiiii pppp ?????? ?時，當(dāng) 54321 21025 iiiiii ppppp ??????? ?時，當(dāng) 例 有一個 4/3/F/Fmax問題，其加工時間如下表所示，試用帕爾默法求最優(yōu)順序。 i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 解：對于本例， λ i =－ Pi1＋ Pi3 于是， λ 1 = － P11＋ P13=－ 1＋ 4=3 λ 2 = － P21＋ P23=－ 2＋ 5=3 λ 3 = － P31＋ P33=－ 6＋ 8=2 λ 4 = － P41＋ P43=－ 3＋ 2=－ 1 按 λi 不增的順序排列工件，得到加工順序 (1， 2， 3， 4)和 (2， 1， 3， 4)，恰好這兩個順序都是最優(yōu)順序。如不是這樣，則從中挑選較優(yōu)者。在最優(yōu)順序下， F max =28。 ? ? 321k2/)13(1，，＝ ??????ikmki pk? （二）關(guān)鍵零件法 ? 步驟如下： ? （ 1）計(jì)算每個零件的總加工時間，找出加工時間最長的零件 C，將其作為關(guān)鍵零件。 ? （ 2）對于余下的零件，若 pi1≤p im，則按 pi1不減 的順序排成一個序列 Sa；若 pi1≥p im，則按 pim不增 的順序排成一個序列 Sb。 ? （ 3）順序（ Sa， C， Sb）即為所求順序。 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)順序。 解：總加工時間最長的為 3號零件， pi1≤p i3的零件為 1和 2，按 pi1不減的順序排成 Sa=（ 1， 2）； pi1≥p i3的零件為 4號零件， Sb=（ 4） ,這樣得到的加工順序?yàn)椋?1， 2， 3， 4）。 例 題 ? 用關(guān)鍵工件法求解下表的最優(yōu)排序。 ? 解：總加工時間最長的為 2號零件， pi1≤p i4的零件為1和 3，按 pi1不減的順序排成 sa=（ 1， 4）； pi1＞ pi4的零件為 4號零件， sb=（ 3），這樣得到的順序?yàn)椋?1， 4，2， 3）。 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法。 ? 具體做法是，對加工時間 ? 用 Johnson算法求（ m1）次加工順序，取其中最好的結(jié)果。 。，，和 1m21pml1mkik1????????lplkik 。，，和 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，加工時間分別
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1