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