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