【正文】 i 的完工時間 , Ci = ri + ?(pij + wij) = ri + Wi + Pi Cmax: 最長完工時間 , Cmax = max {Ci} 【 88】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 假設條件與符號說明 Fi: Ji 的流程時間 ,即工件在車間的實際停留時間 Fmax: 最長流程時間 , Fmax = max{ Fi } Li: 工件的延遲時間 wij : Ji 在 Mj上加工前的等待時間 Wi: Ji 在加工過程中總的等待時間 ai: Ji 的允許停留時間 , Li = Ci – di = Fi ai Lmax: 最長延遲時間 , Lmax = max {Li} 【 89】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 假設條件與符號說明 n/m/A/B n: 工件數(shù) m: 機器數(shù) A: 車間類型 F表示流水作業(yè)排序問題 Flowshop問題 P表示流水作業(yè)排列排序問題，也常被稱為“同順序”排序問題。 G一般單件作業(yè)排序問題 Jobshop問題 B: 目標函數(shù) 使其值最小 【 90】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 流水作業(yè)的排序問題 ? 一般的流水作業(yè)排序問題： ? 工件在機器上的加工順序可能不一致 。 ? 流水作業(yè)的排列排序問題 的加工順序相同 。 ? 排列排序問題的最優(yōu)解： ? 在 2~3臺機器時為流水作業(yè)排序問題的最優(yōu)解，一般為較優(yōu)解 . 【 91】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 最長流程時間 fmax的計算 n/m/p/fmax問題 ? 使從第一個工件在第一臺機床開始加工到最后一個工件在最后一臺機器上完成加工為止的時間最短； ? 所有工件到達時間都為零 ? fmax等于一批工件的最長完工時間； ? n個工件的加工順序為 S=(S1, S2, …, Sn)。 【 92】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 iSkC 和iSkp 分別表示工件 Si 在機器 M k 上的完工時間和加工時間。 iSkC 的遞推計算公式為： 11 1 1S S Si i iC C p??? 11m a x { , }S S S Si i i ik k k kC C C p???? 【 93】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 最長流程時間 fmax的計算 例：有一個 6/ 4/ p/ f m ax 問題，其加工時間如下表。當加工順序為 S= （ 6 ， 1 ， 5 ， 2 ， 4 ， 3 ）時，求 f m ax 。 i 1 2 3 4 5 6 p i1 4 2 3 1 4 2 p i2 4 5 6 7 4 5 p i3 5 8 7 5 5 5 p i4 4 2 4 3 3 1 【 94】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 最長流程時間 fmax的計算 ? 按 S的順序列出加工矩陣 ? 第一行第一列加工時間等于其右上角的完工時間 ? 第一行其他列完工時間等于其前一列完工時間加上其加工時間 ? 第二行以下 ,第一列完工時間等于其前一行完工時間加上其加工時間；其他列完工時間等于 前一列、前一行完工時間取大者 加上其加工時間 i 6 1 5 2 4 3p i1 2246410212113316p i2 57411415520727633p i3 512517522830535742p i4 113421325232338446【 95】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 n/2/F/fmax 問題的最優(yōu)算法 ? 1954年 Johnson提出 ? 用 ai 和 bi分別表示 Ji在 M1 和 M2的加工時間。每個工件都按 M1?M2的路線加工。 ? 若 min (ai, bj) min(aj, bi), 則 Ji 應排在 Jj 之前。 ? Johnson算法： ? 從加工時間矩陣中找出最短的加工時間 。 ? 若它出現(xiàn)在 M1上，則其對應的工件應盡可能往前排；若它出現(xiàn)在 M2上，則其對應的工件應盡可能往后排 。 ? 劃去已排序工件并重復上述步驟直至排完。 【 96】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 ? 最優(yōu)加工順序為 S=（ 2， 5， 6， 1， 4， 3） ? 最優(yōu)加工順序下 fmax =28 例：求 6/ 2/ F / F m ax 問題的最優(yōu)解 i 1 2 3 4 5 6 a i 5 1 8 5 3 4 b i 7 2 2 4 7 4 【 97】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 ? Johnson算法的改進算法 ? 將所有 ai ?bi的工件按 ai值不減的順序排成一個序列 A ? 將所有 ai bi的工件按 bi值不增的順序排成一個序列 B ? 將 A放到 B之前即構(gòu)成最優(yōu)加工順序 ? Johnson法則所得到的最優(yōu)順序中任意去掉一些工件，余下的仍構(gòu)成最優(yōu)順序 【 98】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 一般 n/m/P/fmax問題的啟發(fā)式算法 ?一般須通過整數(shù)規(guī)劃方式求最優(yōu)解 ?有幾個求有效解或較好解的啟發(fā)式算法 （ 1） Palmer法（ 1965年 Palmer提出） ? 定義斜度指標 ? m為機器數(shù)， pik為工件 i在 Mk上的加工時間 ? 按各工件的斜度指標不增順序排列工件，可得滿意順序 ?????mkiki pmk1]2/)1([? k=1,2,… n 【 99】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 （ 2）關鍵工件法（ 1983年陳榮秋提出） ? 計算步驟為 ? 計算每個工件的總加工時間 Pi ，找出最長的工件 C，將其作為關鍵工件； ? 對其它工件，將所有 pi1?pim的工件按 pi1值不減的順序排成一個序列 Sa；將所有 pi1pim 的工件按 pim值不增的順序排成一個序列 Sb； ? （ Sa ,C, Sb ）為滿意順序。 一般 n/m/P/fmax問題的啟發(fā)式算法 【 100】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 （ 3） CDS法（由 Compbell， Dudek和 Smith提出） ? 求 m1個加工順序中的第 l個（ l=1,2,… m1）時將前 l臺機器和后 l臺機器分別看成兩個機器群體，并對其加工時間分別進行求和，即，求 ? 將 Jonhson算法求 m1個加工順序， ? 比較得到其中的最優(yōu)順序作為一般 n/m/P/ fmax問題的滿意順序。 11 1,..., 1lmik ikk k m lp p l m? ??? ???? 和 ，【 101】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 表 加工時間矩陣 i 1 2 3 4 Pi1 1 2 6 3 Pi2 8 4 2 9 Pi3 4 5 8 2 表 用 CDS法求解 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 11 1,..., 1和 ，lmik ikk k m lp p l m? ??? ???? 【 102】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 Many thanks for your attention! 【 103】 生產(chǎn)運作管理 POM 主講：中國科技大學 楊鋒 靜夜四無鄰，荒居舊業(yè)貧。 2023/2/272023/2/27Monday, February 27, 2023 雨中黃葉樹，燈下白頭人。 2023/2/272023/2/272023/2/272/27/2023 10:53:54 PM 1以我獨沈久，愧君相見頻。 2023/2/272023/2/272023/2/27Feb2327Feb23 1故人江海別，幾度隔山川。 2023/2/272023/2/272023/2/27Monday, February 27, 2023 1乍見翻疑夢，相悲各問年。 2023/2/272023/2/272023/2/272023/2/272/27/2023 1他鄉(xiāng)生白發(fā)，舊國見青山。 2023年 2月 27日星期一 2023/2/272023/2/272023/2/27 1比不了得就不比，得不到的就不要。 2023年 2月 2023/2/272023/2/272023/2/272/27/2023 1行動出成果，工作出財富。 2023/2/272023/2/27February 27, 2023 1做前，能夠環(huán)視四周；做時，你只能或者最好沿著以腳為起點的射線向前。 2023/2/272023/2/272023/2/272023/2/27 沒有失敗，只有暫時停止成功！。 2023/2/272023/2/27Monday, February 27, 2023 很多事情努力了未必有結(jié)果，但是不努力卻什么改變也沒有。 2023/2/272023/2/272023/2/272/27/2023 10:53:54 PM 1成功就是日復一日那一點點小小努力的積累。 2023/2/272023/2/272023/2/27Feb2327Feb23 1世間成事，不求其絕對圓滿，留一份不足，可得無限完美。 2023/2/272023/2/272023/2/27Monday, February 27, 2023 1不知香積寺，數(shù)里入云峰。 2023/2/272023/2/272023/2/272023/2/272/27/2023 1意志堅強的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 2月 27日星期一 2023/2/272023/2/272023/2/27 1楚塞三湘接，荊門九派通。 2023年 2月 2023/2/272023/2/272023/2/272/27/2023 1少年十五二十時，步行奪得胡馬騎。 2023/2/272023/2/27February 27, 2023 1空山新雨后，天氣晚來秋。 2023/2/272023/2/272023/2/272023/2/27 楊柳散和風，青山澹吾慮。 2023/2/272023/2/27Monday, February 27, 2023 閱讀一切好書如同和過去最杰出的人談話。 2023/2/272023/2/272023/2/272/27/2023 10:53:54 PM 1越是沒有本領的就越加自命不凡。 2023/2/272023/2/272023/2/27Feb2327Feb23 1越是無能的人，越喜歡挑剔別人的錯兒。 2023/2/272023/2/272023/2/27Monday, February 27, 2023 1知人者智，自知者明。勝人者有力，自勝者強。 2023/2/272023/2/272023/2/272023/2/272/27/2023 1意志堅強的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 2月 27日星期一 2023/2/272023/2/272023/2/27 1最具挑戰(zhàn)性的挑戰(zhàn)莫過于提升自我。 2023年 2月 2023/2/272023/2/272023/2/272/27/2023 1業(yè)余生活要有意義，不要越軌。 2023/2/272023/2/27February 27, 2023 1一個人即使已登上頂峰，也仍要自強不息。 2023/2/272023/2/272023/2/272023/2/27 MOMODA POWERPOINT Lorem ipsum dolor sit, eleifend nulla ac, fringilla purus. Nulla iaculis tempor felis amet, consectetur adipiscing elit. Fusce id urna blanditut cursus. 感 謝 您 的 下 載 觀 看 專家告訴