【正文】 程設(shè)計 生產(chǎn)過程對顧客有直接、及時的影響 多數(shù)過程和步驟顧客不介入 時間排程 顧客在生產(chǎn)過程中 顧客主要關(guān)心完成日期 生產(chǎn)計劃 訂貨不可存儲，平穩(wěn)生產(chǎn) 會 丟失機會 積壓、平穩(wěn)生產(chǎn)是可能的 員工技藝 現(xiàn)場員工 應(yīng)能與顧客交互 現(xiàn)場員工只需要技術(shù)技能 質(zhì)量控 制 標(biāo)準(zhǔn)由接受者確定，是變化的 標(biāo)準(zhǔn)是可測的、固定的 時間標(biāo)準(zhǔn) 依賴顧客需求，是松弛的 是緊的 工資方式 變化的產(chǎn)出要求計時工資 可固定產(chǎn)出容許計件工資 能力規(guī)劃 為避免丟失機會，能力應(yīng)滿足峰需求 平均需求水平 資本密集型 vs 人員密集型 ? 技術(shù)密集型服務(wù)（基于設(shè)備的服務(wù)） ? 如：航空，運輸，銀行、醫(yī)院、通訊 、廣播電視 等 ? 管理重點： 設(shè)備投資、 R＆ D、控制服務(wù)交貨進(jìn)度與準(zhǔn)確性 ? 人員密集型服務(wù)（基于人員的服務(wù)） ? 如：百貨商店、餐飲、學(xué)校、咨詢 、同城速遞、搬家公司 等 ? 管理重點：設(shè)施選址和布置、員工的聘用、培訓(xùn)和激勵、工作方式的改進(jìn) 組合：客戶參與度＋投入密集度 客戶參與度 高接觸 低接觸 投入密集度 資本密集 醫(yī)院、客運等 貨運、金融、郵政、通訊、廣播電視等 人員密集 咨詢、設(shè)計、理發(fā)、保健等 零售批發(fā)、快遞等 結(jié)構(gòu) 第一節(jié)：產(chǎn)品開發(fā) 1 第二節(jié)： 工藝選擇 2 第三節(jié)：制造業(yè)作業(yè)計劃 3 排序問題的基本概念 ? 名詞與術(shù)語 ? 假設(shè)條件與符號說明 ? 排序問題的分類和表示法 名詞與術(shù)語 ? 排序 (Sequencing): ? 確定工件在機器上的加工順序。 ? 編制作業(yè)計劃 (Scheduling): ? 確定工件在機器上的加工順序以及每個工件的開始加工時間和完成時間 ? 調(diào)度 (Controlling)包括派工 (Dispatching)和趕工 (Expediting)。 ? 派工指依據(jù)作業(yè)計劃將具體任務(wù)安排到具體的機床加工。 ? 趕工指實際進(jìn)度落后于計劃時采取的資源調(diào)配行動。 名詞與術(shù)語 ? 排序問題的基本術(shù)語 ? 機器：服務(wù)者，具體可以是機床、工人、碼頭 。 ? 工件：服務(wù)對象，可以是單個或多個相同的零件 。 ? 加工路線：工件加工的工藝過程決定的，它是工件加工在技術(shù)上的約束 。 ? 加工順序：表示每臺機器加工 n個工件的先后順序，是排序要解決的問題。 假設(shè)條件與符號說明 ? 假設(shè)條件 ? 一個工件不能同時在幾臺不同的機器上加工； ? 工件在加工過程中采用平行移動方式（無等待）； ? 工件開始加工后，完工前不能插入其它工件； ? 每道工序只在一臺機器上完成； ? 工件數(shù)、機器數(shù)和加工時間已知，且與加工順序無關(guān)； ? 每臺機器同時只能加工一個工件。 假設(shè)條件與符號說明 Ji: 工件 i， i=1, 2,… , n Mj: 機器 j, j=1, 2,… , m pij: Ji 在 Mj上的加工時間 , Pi = ? pij ri: Ji 的到達(dá)時間 , 即從外部進(jìn)入車間 ,可以開始加工的最早時間 di: Ji 的完工期限 Ci: Ji 的完工時間 , Ci = ri + ?(pij + wij) = ri + Wi + Pi Cmax: 最長完工時間 , Cmax = max {Ci} 假設(shè)條件與符號說明 Fi: Ji 的流程時間 ,即工件在車間的實際停留時間 Fmax: 最長流程時間 , Fmax = max{ Fi } Li: 工件的延遲時間 wij : Ji 在 Mj上加工前的等待時間 Wi: Ji 在加工過程中總的等待時間 ai: Ji 的允許停留時間 , Li = Ci – di = Fi ai Lmax: 最長延遲時間 , Lmax = max {Li} 假設(shè)條件與符號說明 n/m/A/B n: 工件數(shù) m: 機器數(shù) A: 車間類型 F表示流水作業(yè)排序問題 Flowshop問題 P表示流水作業(yè)排列排序問題，也常被稱為 “ 同順序 ” 排序問題。 G一般單件作業(yè)排序問題 Jobshop問題 B: 目標(biāo)函數(shù) 使其值最小 流水作業(yè)的排序問題 ? 一般的流水作業(yè)排序問題： ? 工件在機器上的加工順序可能不一致 。 ? 流水作業(yè)的排列排序問題 的加工順序相同 。 ? 排列排序問題的最優(yōu)解： ? 在 2~3臺機器時為流水作業(yè)排序問題的最優(yōu)解，一般為較優(yōu)解 . 最長流程時間 fmax的計算 n/m/p/fmax問題 ? 使從第一個工件在第一臺機床開始加工到最后一個工件在最后一臺機器上完成加工為止的時間最短； ? 所有工件到達(dá)時間都為零 ? fmax等于一批工件的最長完工時間； ? n個工件的加工順序為 S=(S1, S2, … , Sn)。 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???? 最長流程時間 fmax的計算 例：有一個 6/ 4/ p/ f m ax 問題，其加工時間如下表。當(dāng)加工順序為 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 最長流程時間 fmax的計算 ? 按 S的順序列出加工矩陣 ? 第一行第一列加工時間等于其右上角的完工時間 ? 第一行其他列完工時間等于其前一列完工時間加上其加工時間 ? 第二行以下 ,第一列完工時間等于其前一行完工時間加上其加工時間；其他列完工時間等于 前一列、前一行完工時間取大者 加上其加工時間 i 6 1 5 2 4 3p i1 2246410212113316p i2 57411415520727633p i3 512517522830535742p i4 113421325232338446n/2/F/fmax 問題的最優(yōu)算法 ? 1954年 Johnson提出 ? 用 ai 和 bi分別表示 Ji在 M1 和 M2的加工時間。每個工件都按 M1?M2的路線加工。 ? 若 min (ai, bj) min(aj, bi), 則 Ji 應(yīng)排在 Jj 之前。 ? Johnson算法： ? 從加工時間矩陣中找出最短的加工時間 。 ? 若它出現(xiàn)在 M1上，則其對應(yīng)的工件應(yīng)盡可能往前排；若它出現(xiàn)在 M2上，則其對應(yīng)的工件應(yīng)盡可能往后排 。 ? 劃去已排序工件并重復(fù)上述步驟直至排完。 ? 最優(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 ? Johnson算法的改進(jìn)算法 ? 將所有 ai ?bi的工件按 ai值不減的順序排成一個序列 A ? 將所有 ai bi的工件按 bi值不增的順序排成一個序列 B ? 將 A放到 B之前即構(gòu)成最優(yōu)加工順序 ? Johnson法則所得到的最優(yōu)順序中任意去掉一些工件，余下的仍構(gòu)成最優(yōu)順序 一般 n/m/P/fmax問題的啟發(fā)式算法 ?一般須通過整數(shù)規(guī)劃方式求最優(yōu)解 ?有幾個求有效解或較好解的啟發(fā)式算法 （ 1） Palmer法（ 1965年 Palmer提出） ? 定義斜度指標(biāo) ? m為機器數(shù)， pik為工件 i在 Mk上的加工時間 ? 按各工件的斜度指標(biāo)不增順序排列工件，可得滿意順序 ?????mkiki pmk1]2/)1([? k =1,2,… n （ 2）關(guān)鍵工件法（ 1983年陳榮秋提出） ? 計算步驟為 ? 計算每個工件的總加工時間 Pi ，找出最長的工件 C，將其作為關(guān)鍵工件； ? 對其它工件，將所有 pi1?pim的工件按 pi1值不減的順序排成一個序列 Sa；將所有 pi1pim 的工件按 pim值不增的順序排成一個序列 Sb； ? （ Sa ,C, Sb ）為滿意順序。 一般 n/m/P/fmax問題的啟發(fā)式算法 （ 3） CDS法（由 Compbell， Dudek和 Smith提出） ?求 m1個加工順序中的第 l個（ l=1,2,… m1）時將前 l臺機器和后 l臺機器分別看成兩個機器群體，并對其加工時間分別進(jìn)行求和，即，求 ?將 Jonhson算法求 m1個加工順序， ?比較得到其中的最優(yōu)順序作為一般 n/m/P/ fmax問題的滿意順序。 11 1 , ..., 1lmik ikk k m lp p l m? ? ? ? ???? 和 ，表 加工時間矩陣 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? ? ? ? ????