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