排序與統(tǒng)籌方法

《排序與統(tǒng)籌方法》由會(huì)員分享，可在線閱讀，更多相關(guān)《排序與統(tǒng)籌方法（74頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1 第 九 章 排 序 與 統(tǒng)籌 方 法 馬 飛 雄 / GDUFS 2 第 九 章 排 序 與 統(tǒng) 籌 方 法第 一 節(jié) 車 間 作 業(yè) 計(jì) 劃 模 型第 二 節(jié) 統(tǒng) 籌 方 法 在 本 章 中 ， 我 們 將 介 紹 車 間 作 業(yè) 計(jì) 劃 模 型 和 統(tǒng) 籌 方 法 。這 兩 個(gè) 問(wèn) 題 盡 管 處 理 的 方 法 有 所 不 同 ， 但 當(dāng) 我 們 面 臨 必 須 完成 若 干 項(xiàng) 不 能 同 時(shí) 進(jìn) 行 的 工 作 時(shí) ， 它 們 都 將 幫 助 我 們 應(yīng) 該 按照 怎 樣 的 次 序 、 怎 樣 的 時(shí) 間 表 來(lái) 做 這 些 工 作 ， 使 得 效 果 最 佳（ 例 如 完 成

2、 全 部 工 作 所 用 時(shí) 間 最 短 或 費(fèi) 用 最 少 等 等 ） 。 馬 飛 雄 / GDUFS 3 1 車 間 作 業(yè) 計(jì) 劃 模 型 車 間 作 業(yè) 計(jì) 劃 是 指 一 個(gè) 工 廠 生 產(chǎn) 工 序的 計(jì) 劃 和 安 排 。一 、 一 臺(tái) 機(jī) 器 、 n個(gè) 零 件 的 排 序 問(wèn) 題二 、 兩 臺(tái) 機(jī) 器 、 n個(gè) 零 件 的 排 序 問(wèn) 題 馬 飛 雄 / GDUFS 4 一 、 一 臺(tái) 機(jī) 器 、 n個(gè) 零 件 的 排 序 問(wèn) 題 例 1.某 車 間 只 有 一 臺(tái) 高 精 度 的 磨 床 ， 常 常 出 現(xiàn) 很多 零 件 同 時(shí) 要 求 這 臺(tái) 磨 床 加 工 的 情 況 ，

3、現(xiàn) 有 六 個(gè) 零 件同 時(shí) 要 求 加 工 ， 這 六 個(gè) 零 件 加 工 所 需 時(shí) 間 如 下 表 所 示 。 應(yīng) 該 按 照 什 么 樣 的 加 工 順 序 來(lái) 加 工 這 六 個(gè) 零 件 ，才 能 使 得 這 六 個(gè) 零 件 在 車 間 里 停 留 的 平 均 時(shí) 間 為 最 少 ？零 件 加 工 時(shí) 間 （ 小 時(shí) ） 零 件 加 工 時(shí) 間 （ 小 時(shí) ）123 1.82.00.5 456 0.91.31.5 1 車 間 作 業(yè) 計(jì) 劃 模 型 馬 飛 雄 / GDUFS 5 例 1解 ： 如 果 我 們 用 Pi表 示 安 排 在 第 i位 加 工 的 零件 所 需 的 時(shí) 間

4、 ， 用 Tj表 示 安 排 在 第 j位 加 工 的 零 件 在 車間 里 總 的 停 留 時(shí) 間 ， 則 有 Tj = P1 + P2 + Pj-1 + Pj = 不 同 的 加 工 順 序 得 到 不 同 的 各 零 件 的 平 均 停 留 時(shí)間 ， 如 何 得 到 一 個(gè) 使 得 各 零 件 的 平 均 停 留 時(shí) 間 最 少 的排 序 呢 ？ 這 就 是 我 們 最 后 要 解 決 的 優(yōu) 化 問(wèn) 題 ， 而 且 我們 要 設(shè) 法 找 到 一 種 簡(jiǎn) 便 的 算 法 。 對(duì) 于 某 種 加 工 順 序 ， 我 們 知 道 安 排 在 第 j位 加 工 的零 件 在 車 間 里 總 的

5、 停 留 時(shí) 間 為 T j ， Tj = ji iP1ji iP1 1 車 間 作 業(yè) 計(jì) 劃 模 型 馬 飛 雄 / GDUFS 6 可 知 這 六 個(gè) 零 件 的 停 留 時(shí) 間 為 ： T1 + T2 + T3 + T4 + T5 + T6 P1 + ( P1 + P2 ) + (P1 + P2 + P3 ) + (P1 + P2 + P3 + P4 ) +(P1 + P2 + P3 + P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那 么 各 個(gè) 零 件 平 均 停 留 時(shí)

6、間 為6 23456 654321 pppppp 從 上 式 可 知 ， 對(duì) 于 一 臺(tái) 機(jī) 器 n個(gè) 零 件 的 排 序 問(wèn) 題 ， 只 要 系 數(shù)越 大 ， 配 上 加 工 時(shí) 間 越 少 的 ， 即 按 照 加 工 時(shí) 間 排 出 加 工 順 序 ，加 工 時(shí) 間 越 少 的 零 件 排 在 越 前 面 ， 加 工 時(shí) 間 越 多 的 零 件 排 在 越后 面 ， 可 使 各 零 件 的 平 均 停 留 時(shí) 間 最 少 。 1 車 間 作 業(yè) 計(jì) 劃 模 型 馬 飛 雄 / GDUFS 7 二 、 兩 臺(tái) 機(jī) 器 、 n個(gè) 零 件 例 2. 某 工 廠 根 據(jù) 合 同 定 做 一 些 零

7、 件 ， 這 些 零 件 要求 先 在 車 床 上 車 削 ， 然 后 再 在 磨 床 上 加 工 ， 每 臺(tái) 機(jī)器 上 各 零 件 加 工 時(shí) 間 如 下 表 所 示 。 應(yīng) 該 如 何 安 排 這 五 個(gè) 零 件 的 先 后 順 序 才 能 使 完成 這 五 個(gè) 零 件 的 總 的 加 工 時(shí) 間 為 最 少 ？零 件 車 床 磨 床 零 件 車 床 磨 床123 1.52.01.0 0.50.251.75 45 1.250.75 2.51.25 1 車 間 作 業(yè) 計(jì) 劃 模 型 馬 飛 雄 / GDUFS 8 解 ： 由 于 每 個(gè) 零 件 必 須 先 進(jìn) 行 車 床 加 工 ， 再

8、進(jìn) 行 磨 床 加 工 ，所 以 在 車 床 上 加 工 零 件 的 順 序 與 在 磨 床 上 加 工 零 件 的 順 序 是一 樣 的 。 如 果 這 些 零 件 在 車 床 上 和 磨 床 上 加 工 順 序 都 為 1， 2，3， 4， 5。 我 們 用 圖 12-1中 的 線 條 圖 來(lái) 表 示 各 零 件 加 工 的 開(kāi) 始時(shí) 間 與 完 成 時(shí) 間 ， 這 種 圖 是 由 一 根 時(shí) 間 軸 和 車 床 、 磨 床 在 每個(gè) 時(shí) 間 段 的 狀 況 的 圖 形 所 構(gòu) 成 。 零 件 車 床 磨 床 零 件 車 床 磨 床123 1.52.01.0 0.50.251.75 45

9、1.250.75 2.51.25 1 車 間 作 業(yè) 計(jì) 劃 模 型 圖 12-1 從 上 圖 中 我 們 可 以 看 出 ， 加 工 時(shí) 間 的 延 長(zhǎng) 主 要 是由 于 磨 床 的 停 工 待 料 造 成 的 ， 只 要 減 少 磨 床 的 停 工 待 料的 時(shí) 間 就 能 減 少 整 個(gè) 加 工 任 務(wù) 的 總 時(shí) 間 。 為 了 減 少 磨 床 的 停 工 待 料 ， 我 們 應(yīng) 該 一 方 面 把 在 車床 上 加 工 時(shí) 間 越 短 的 零 件 越 早 加 工 ， 減 少 磨 床 等 待 的 時(shí)間 ； 另 一 方 面 把 在 磨 床 上 加 工 時(shí) 間 越 短 的 零 件 越 晚

10、加 工 ，以 便 充 分 利 用 前 面 的 時(shí) 間 ， 這 樣 我 們 就 得 到 了 使 完 成 全部 零 件 加 工 任 務(wù) 所 需 總 時(shí) 間 最 少 的 零 件 排 序 方 法 。1 2 3 4 51車床磨床 2 3 4 50 101.5 2.0 1.0 1.25 0.750.5 0.25 1.75 2.5 1.25 馬 飛 雄 / GDUFS 10 尋 找 例 2的 最 優(yōu) 解 ： 我 們 在 上 表 中 找 到 所 列 出 的 最短 加 工 時(shí) 間 是 0.25,它 是 第 二 道 工 序 磨 床 加 工 零 件 2的 所需 時(shí) 間 ， 由 于 這 個(gè) 時(shí) 間 與 磨 床 有 關(guān)

11、 ， 故 我 們 把 零 件 2放在 加 工 順 序 的 末 尾 ， 即 第 五 位 ， 并 在 表 中 劃 去 零 件 2 所在 行 。 如 表 中 紅 色 線 條 所 示 。 零件 車 床(第 一 工 序 ) 磨 床(第 二 工 序 ) 零件 車 床(第 一 工 序 ) 磨 床(第 二 工 序 )123 1.52.01.0 0.50.251.75 45 1.250.75 2.51.25 1 車 間 作 業(yè) 計(jì) 劃 模 型 馬 飛 雄 / GDUFS 11接 著 ， 我 們 又 找 到 最 短 加 工 時(shí) 間 為 0.5， 這 一 時(shí) 間 與 磨床 （ 第 二 工 序 ） 有 關(guān) ， 我 們

12、 把 磨 床 加 工 時(shí) 間 為 0.5的 零件 1放 到 除 第 五 外 的 加 工 順 序 的 末 尾 ， 即 第 四 位 加 工 ，同 時(shí) 把 表 中 的 零 件 1所 在 的 行 劃 去 。 如 表 中 黃 色 線 條所 示 。 零件 車 床(第 一 工 序 ) 磨 床(第 二 工 序 ) 零件 車 床(第 一 工 序 ) 磨 床(第 二 工 序 )123 1.52.01.0 0.50.251.75 45 1.250.75 2.51.25 1 車 間 作 業(yè) 計(jì) 劃 模 型 馬 飛 雄 / GDUFS 12 下 一 個(gè) 最 短 加 工 時(shí) 間 為 0.75， 這 個(gè) 加 工 時(shí)間 是

13、車 床 （ 第 一 工 序 ） 加 工 零 件 5的 所 需 時(shí) 間 ，故 把 零 件 5排 在 加 工 順 序 的 第 一 位 上 ， 同 時(shí) 把表 中 的 零 件 5所 在 的 行 劃 去 。 如 表 中 藍(lán) 色 線 條所 示 。 零件 車 床(第 一 工 序 ) 磨 床(第 二 工 序 ) 零件 車 床(第 一 工 序 ) 磨 床(第 二 工 序 )123 1.52.01.0 0.50.251.75 45 1.250.75 2.51.25 1 車 間 作 業(yè) 計(jì) 劃 模 型 馬 飛 雄 / GDUFS 13同 樣 ， 下 一 個(gè) 最 短 加 工 時(shí) 間 為 1， 這 是 車 床 加工 零

14、 件 3的 所 需 時(shí) 間 ， 故 把 零 件 3排 在 第 二 位 上 ，同 時(shí) 把 零 件 3所 在 的 行 劃 去 。 如 表 中 黑 色 線 條所 示 。 零件 車 床(第 一 工 序 ) 磨 床(第 二 工 序 ) 零件 車 床(第 一 工 序 ) 磨 床(第 二 工 序 )123 1.52.01.0 0.50.251.75 45 1.250.75 2.51.25 1 車 間 作 業(yè) 計(jì) 劃 模 型 馬 飛 雄 / GDUFS 14 這 樣 就 得 到 了 最 優(yōu) 加 工 順 序 ： 5， 3， 4， 1， 2。0.751.0 1.25 1.5 2.01.25 1.75 2.5 0.

15、5 0.255磨 床車 床 3 4 1 25 3 4 1 27這 樣 一 共 只 需 7個(gè) 小 時(shí) 就 能 完 成 全 部 加 工 。 1 車 間 作 業(yè) 計(jì) 劃 模 型 馬 飛 雄 / GDUFS 15 從 例 2中 我 們 可 以 歸 納 出 關(guān) 于 兩 臺(tái) 機(jī) 器 n個(gè)零 件 的 排 序 問(wèn) 題 ， 使 得 全 部 任 務(wù) 總 的 時(shí) 間 最 短的 排 序 算 法 。 步 驟 1: 在 加 工 所 需 時(shí) 間 表 上 選 出 最 短 加 工 時(shí)間 tij， 這 是 第 i工 序 加 工 j零 件 所 需 時(shí) 間 ， 步 驟 2: 當(dāng) i=1時(shí) ， 將 零 件 j的 順 序 盡 量 靠 前

16、 ，若 i=2時(shí) ， 將 零 件 j的 順 序 盡 量 靠 后 。 步 驟 3: 在 表 上 劃 去 零 件 j的 所 在 行 ， 回 到 步驟 1。 1 車 間 作 業(yè) 計(jì) 劃 模 型 馬 飛 雄 / GDUFS 16 思 考 題 ： m臺(tái) 機(jī) 器 n個(gè)零 件 的 排 序 問(wèn) 題如 何 解 決 ？ 1 車 間 作 業(yè) 計(jì) 劃 模 型 馬 飛 雄 / GDUFS 17 2 統(tǒng) 籌 方 法 統(tǒng) 籌 法 又 稱 網(wǎng) 絡(luò) 計(jì) 劃 法 。 它 是 以 網(wǎng) 絡(luò) 圖 反 映 、表 達(dá) 計(jì) 劃 安 排 ， 據(jù) 以 選 擇 最 優(yōu) 工 作 方 案 ， 組 織 協(xié) 調(diào)和 控 制 生 產(chǎn) （ 項(xiàng) 目 ） 的 進(jìn)

17、度 （ 時(shí) 間 ） 和 費(fèi) 用 （ 成本 ） ， 使 其 達(dá) 到 預(yù) 定 目 標(biāo) ， 獲 得 更 佳 經(jīng) 濟(jì) 效 益 的 一種 優(yōu) 化 決 策 方 法 。 1957年 ， 美 國(guó) 化 學(xué) 公 司 Du Pont的 M.R.Walker與Rand通 用 電 子 計(jì) 算 機(jī) 公 司 的 J.E.Kelly為 了 協(xié) 調(diào) 公 司內(nèi) 部 不 同 業(yè) 務(wù) 部 門 的 工 作 , 共 同 研 究 出 關(guān) 鍵 路 線 方 法（ 簡(jiǎn) 記 作 CPM） .首 次 把 這 一 方 法 用 于 一 家 化 工 廠 的籌 建 ， 結(jié) 果 籌 建 工 程 提 前 兩 個(gè) 月 完 成 .隨 后 又 把 這 一方 法 用

18、于 工 廠 的 維 修 ， 結(jié) 果 使 停 工 時(shí) 間 縮 短 了 47個(gè)小 時(shí) ， 當(dāng) 年 就 取 得 節(jié) 約 資 金 達(dá) 百 萬(wàn) 元 的 要 觀 效 益 。 1958年 ， 美 國(guó) 海 軍 武 器 規(guī) 劃 局 特 別 規(guī) 劃 室 研 制 含 約 3000項(xiàng)工 作 任 務(wù) 的 北 極 星 導(dǎo) 彈 潛 艇 計(jì) 劃 ， 參 與 的 廠 商 達(dá) 11000多 家 。 為了 有 條 不 紊 地 實(shí) 施 如 此 復(fù) 雜 的 工 作 ， 特 別 規(guī) 劃 室 領(lǐng) 導(dǎo) 人W.Fazar積 極 支 持 與 推 廣 由 專 門 小 組 創(chuàng) 建 的 計(jì) 劃 評(píng) 審 技 術(shù) （ 簡(jiǎn)記 作 PERT） 。 結(jié) 果 研

19、 制 計(jì) 劃 提 前 兩 個(gè) 完 成 ， 取 得 了 極 大 的 成 功 。 CPM在 民 用 企 業(yè) 與 PERT在 軍 事 工 業(yè) 中 的 顯 著 成 效 ,自 然 引起 了 普 遍 的 重 視 。 很 快 CPM與 PERT就 被 應(yīng) 用 于 工 業(yè) 、 農(nóng) 業(yè) 、國(guó) 防 與 科 研 等 等 復(fù) 雜 的 計(jì) 劃 管 理 工 作 中 ,隨 后 又 推 廣 到 世 界 各 國(guó) 。在 應(yīng) 用 推 廣 CPM與 PERT的 過(guò) 程 中 ,又 派 生 出 多 種 各 具 特 點(diǎn) ， 各有 側(cè) 重 的 類 似 方 法 。 但 是 萬(wàn) 變 不 離 其 宗 ， 各 種 有 所 不 同 的 方 法 ，其

20、基 本 原 理 都 源 于 CPM與 PERT。 馬 飛 雄 / GDUFS 19 CPM與 PERT兩 種 方 法 實(shí) 質(zhì) 上 大 同 小 異 ，因 此 ， 人 們 把 CPM與 PERT及 其 他 類 似 方 法統(tǒng) 稱 為 網(wǎng) 絡(luò) 計(jì) 劃 技 術(shù) ， 簡(jiǎn) 稱 為 網(wǎng) 絡(luò) 技 術(shù) 或 網(wǎng)絡(luò) 方 法 ， 簡(jiǎn) 記 為 統(tǒng) 籌 法 。 統(tǒng) 籌 方 法 包 括 繪 制 計(jì) 劃 網(wǎng) 絡(luò) 圖 、 進(jìn) 度 安排 、 網(wǎng) 絡(luò) 優(yōu) 化 等 環(huán) 節(jié) ， 下 面 進(jìn) 行 分 別 討 論 ：一 、 計(jì) 劃 網(wǎng) 絡(luò) 圖 統(tǒng) 籌 方 法 的 第 一 步 工 作 就 是 繪 制 計(jì) 劃 網(wǎng)絡(luò) 圖 ， 也 就 是 將 工

21、序 （ 或 稱 為 活 動(dòng) ） 進(jìn) 度 表轉(zhuǎn) 換 為 統(tǒng) 籌 方 法 的 網(wǎng) 絡(luò) 圖 。 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 20 網(wǎng) 絡(luò) 圖 畫(huà) 法(一 )、 結(jié) 構(gòu) 網(wǎng) 絡(luò) 圖 中 的 點(diǎn) 表 示 一 個(gè) 事 件 ,是 一 個(gè) 或 若 干 個(gè) 工序 的 開(kāi) 始 或 結(jié) 束 ,是 相 鄰 工 序 在 時(shí) 間 上 的 分 界 點(diǎn) ,點(diǎn) 用圓 圈 表 示 ,圓 圈 里 的 數(shù) 字 表 示 點(diǎn) 的 編 號(hào) 。 弧 表 示 一 個(gè) 工 序 （ 或 活 動(dòng) ） ， 弧 的 方 向 是 從 工序 開(kāi) 始 指 向 工 序 的 結(jié) 束 ， 弧 上 是 各 工 序 的 代 號(hào) ， 下面 標(biāo) 以 完

22、 成 此 工 序 所 需 的 時(shí) 間 （ 或 資 源 ） 等 數(shù) 據(jù) ，即 為 對(duì) 此 弧 所 賦 的 權(quán) 數(shù) 。 例 如 ： 5a1 2 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 21 (二 )、 畫(huà) 法 注 意 事 項(xiàng) ：(1)、 從 左 右1 23 45 6 7824 33 1 2 1 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 22 (2)、 兩 事 項(xiàng) 間 只 有 一 個(gè) 工 序bi j 75a3 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 23 (3)、 不 允 許 回 路1 23 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 24 (4)、 虛 工 序 的 運(yùn) 用

23、 1 20 正 確 表 達(dá) 工 序 的 前 行 、 后 續(xù) 關(guān) 系 (連 結(jié) 、隔 離 ) 解 決 畫(huà) 法 中 問(wèn) 題 ： 網(wǎng) 絡(luò) 圖 中 只 有 一 個(gè) 始點(diǎn) 和 一 個(gè) 終 點(diǎn) ， 中 間 點(diǎn) 前 后 均 要 有 弧 相 連 接 ，不 允 許 中 斷 。 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 251 2 3 4 65 7824 0 3 13 0 2 01 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 26 i jk 75 0a3b 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 27 例 1、 假 設(shè) 某 工 作 有 a, b, c, d四 個(gè) 工 序 , c在 a, b完 工

24、 后 開(kāi) 始 ， d在 b完 工 后 開(kāi) 始 。cab dab cd 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 28 例 3、 某 公 司 研 制 新 產(chǎn) 品 的 部 分 工 序 與 所 需 時(shí) 間 以 及它 們 之 間 的 相 互 關(guān) 系 都 顯 示 在 其 工 序 進(jìn) 度 表 如 表 12-8所 示 ， 請(qǐng) 畫(huà) 出 其 統(tǒng) 籌 方 法 網(wǎng) 絡(luò) 圖 。 工 序代 號(hào) 工 序內(nèi) 容 所 需 時(shí) 間（ 天 ) 緊 前 工 序abcde 產(chǎn) 品 設(shè) 計(jì) 與 工 藝 設(shè) 計(jì)外 購(gòu) 配 套 零 件外 購(gòu) 生 產(chǎn) 原 料自 制 主 件主 配 可 靠 性 試 驗(yàn) 601513388 -aacb,d

25、2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 29解 ： 用 網(wǎng) 絡(luò) 圖 表 示 上 述 的 工 序 進(jìn) 度 表 。 a bc d e60 13 83815 工 序代 號(hào) 工 序內(nèi) 容 所 需 時(shí) 間（ 天 ) 緊 前 工 序abcde 產(chǎn) 品 設(shè) 計(jì) 與 工 藝 設(shè) 計(jì)外 購(gòu) 配 套 零 件外 購(gòu) 生 產(chǎn) 原 料自 制 主 件主 配 可 靠 性 試 驗(yàn) 601513388 -aacb,d 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 30 例 、 把 例 的 工 序 進(jìn) 度 表 做 一 些 擴(kuò) 充 ， 如下 表 ， 請(qǐng) 畫(huà) 出 其 統(tǒng) 籌 方 法 的 網(wǎng) 絡(luò) 圖 。 工 序代 號(hào) 所 需

26、 時(shí) 間（ 天 ） 緊 前工 序 工 序代 號(hào) 所 需 時(shí)間 (天 ) 緊 前 工序abcd 60151338 aac efgh 810165 b， dde, , 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 31 工 序代 號(hào) 所 需 時(shí) 間（ 天 ） 緊 前工 序 工 序代 號(hào) 所 需 時(shí)間 (天 ) 緊 前 工序abcd 60151338 aac efgh 810165 b， dde, ,1 52 643a60 b15 8e1013 dc 38 f 7g16 8由 于 是 的緊 前 工 序 ， 故 的 結(jié) 束 應(yīng) 該是 的 開(kāi) 始 ，所 以 代 表 的弧 的 起 點(diǎn) 應(yīng) 該是 ， 由

27、于 工序 的 結(jié) 束 也是 ， 所 以 工序 也 成 了 工序 的 緊 前 工序 ， 與 題 意 不符 。為 此 我 們 設(shè)立 虛 工 序 。虛 工 序 是 實(shí)際 上 并 不 存在 而 虛 設(shè) 的工 序 ， 用 來(lái)表 示 相 鄰 工序 的 銜 接 關(guān)系 ， 不 需 要人 力 、 物 力等 資 源 與 時(shí)間 。 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 32 工 序代 號(hào) 所 需 時(shí) 間（ 天 ） 緊 前工 序 工 序代 號(hào) 所 需 時(shí)間 (天 ) 緊 前 工序abcd 60151338 aac efgh 810165 b， dde, ,1 52 643a60 b15 8e1013 dc

28、38 f g16 在 統(tǒng) 籌 方 法的 網(wǎng) 絡(luò) 圖 中不 允 許 兩 個(gè)點(diǎn) 之 間 多 于一 條 弧 ， 因此 需 增 加 一個(gè) 點(diǎn) 和 虛 工序 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 33 工 序代 號(hào) 所 需 時(shí) 間（ 天 ） 緊 前工 序 工 序代 號(hào) 所 需 時(shí)間 (天 ) 緊 前 工序abcd 60151338 aac efgh 810165 b， dde, ,1 52 643a60 b15 8e1013 dc 38 f 716g 8h5在 繪 制 統(tǒng) 籌 方 法 的 網(wǎng)絡(luò) 圖 時(shí) ， 要 注 意 圖 中不 能 有 缺 口 和 回 路 。 2 統(tǒng) 籌 方 法 練 習(xí)工 序

29、內(nèi) 容 工 時(shí) (天 ) 緊 前 工 序 A 初 步 研 究 1 / B 研 究 選 點(diǎn) 2 A C 準(zhǔn) 備 調(diào) 研 方 案 4 A D 聯(lián) 系 調(diào) 研 點(diǎn) 2 B E 培 訓(xùn) 工 作 人 員 3 B,C F 準(zhǔn) 備 表 格 1 C G 實(shí) 地 調(diào) 研 5 D,E,F H 寫 調(diào) 研 報(bào) 告 2 G I 開(kāi) 會(huì) 匯 總 3 H 馬 飛 雄 / GDUFS 351 2 325F E200C4 1 3DBA G H I1 2 34 5 6 7 8 9 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 36 二 、 網(wǎng) 絡(luò) 時(shí) 間 與 關(guān) 鍵 路 線 路 線 ： 在 網(wǎng) 絡(luò) 圖 上 從 始 點(diǎn) （ 發(fā)

30、 點(diǎn) ） 開(kāi) 始 ， 沿 弧的 方 向 （ 即 按 各 工 序 的 順 序 ） 連 續(xù) 不 斷 地 到 終 點(diǎn)（ 收 點(diǎn) ） 的 一 條 路 線 。 例 如 ：1 2 325F E200C4 1 3DBA G H I1 2 34 5 6 7 8 9 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 37 關(guān) 鍵 路 線 ： 網(wǎng) 絡(luò) 中 最 長(zhǎng) 的 路 線 ， 通 常 可 用 雙 線 標(biāo)出 。 關(guān) 鍵 路 線 的 長(zhǎng) 等 于 該 路 線 上 各 工 序 的 時(shí) 間 之 和 ，又 稱 為 工 程 時(shí) 間 或 工 期 ， 其 它 路 線 稱 為 非 關(guān) 鍵 路 線 。 關(guān) 鍵 （ 非 關(guān) 鍵 ） 工

31、序 ： 關(guān) 鍵 路 線 上 的 各 工 序 ， 其它 工 序 稱 為 非 關(guān) 鍵 工 序 。1 2 325F E200C4 1 3DBA G H I1 2 34 5 6 7 8 9工 期 T 18 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 38 顯 然 ， 縮 短 工 期 就 是 要 縮 短 關(guān) 鍵 路 線 的 長(zhǎng) 度 ，也 就 是 說(shuō) 要 加 快 關(guān) 鍵 工 序 的 進(jìn) 度 。 而 縮 短 非 關(guān) 鍵 路線 的 長(zhǎng) 度 或 縮 短 非 關(guān) 鍵 工 序 的 時(shí) 間 均 不 能 縮 短 工 期 。1 2 325F E200C4 1 3DBA G H I1 2 34 5 6 7 8 9工 期

32、 T 18 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 39 在 繪 制 出 網(wǎng) 絡(luò) 圖 之 后 ， 我 們 可 以 由 網(wǎng) 絡(luò) 圖 求 出 ：1、 完 成 此 工 程 項(xiàng) 目 所 需 的 最 少 時(shí) 間 。2、 每 個(gè) 工 序 的 開(kāi) 始 時(shí) 間 與 結(jié) 束 時(shí) 間 。3、 關(guān) 鍵 路 線 及 其 應(yīng) 用 的 關(guān) 鍵 工 序 。4、 非 關(guān) 鍵 工 序 在 不 影 響 工 程 的 完 成 時(shí) 間 的 前 提 下 ， 其 開(kāi) 始時(shí) 間 與 結(jié) 束 時(shí) 間 可 以 推 遲 多 久 。 例 5、 某 公 司 裝 配 一 條 新 的 生 產(chǎn) 線 ， 具 體 過(guò) 程 如 下 表 ,求 ：完 成 此

33、 工 程 的 最 少 時(shí) 間 ， 關(guān) 鍵 路 線 及 相 應(yīng) 的 關(guān) 鍵 工 序 ， 各 工序 的 最 早 開(kāi) 始 時(shí) 間 和 非 關(guān) 鍵 工 序 在 不 影 響 工 程 完 成 時(shí) 間 的 前提 下 ， 其 開(kāi) 始 時(shí) 間 與 結(jié) 束 時(shí) 間 可 以 推 遲 多 久 。 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 40 工 序 代 號(hào) 工 序 內(nèi) 容 所 需 時(shí) 間 (天 ) 緊 前 工 序abcdefghij 生 產(chǎn) 線 設(shè) 計(jì)外 購(gòu) 零 配 件下 料 、 鍛 件工 裝 制 造 1木 模 、 鑄 件機(jī) 械 加 工 1工 裝 制 造 2機(jī) 械 加 工 2機(jī) 械 加 工 3裝 配 調(diào) 試

34、60451020401830152535 /aaaacdd,egb,i,f,h 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 41 解 ： 據(jù) 表 繪 制 網(wǎng) 絡(luò) 圖 如 圖 。1 2 3 4 6 7 85a60 b45ec h j35ig10 30d2040 25f1815如 圖 , - - - - 就 是 一 條 關(guān) 鍵 路 線 ， 我 們 要 干 完所 有 的 工 序 就 必 須 走 完 所 有 這 樣 的 路 線 ， 由 于 很 多工 序 可 以 同 時(shí) 進(jìn) 行 ， 所 以 網(wǎng) 絡(luò) 中 最 長(zhǎng) 的 路 線 就 決 定了 完 成 整 個(gè) 工 程 所 需 的 最 少 時(shí) 間 ， 這 條

35、路 線 就 是 關(guān)鍵 路 線 。 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 42 下 面 我 們 給 出 找 關(guān) 鍵 路 線 的 辦 法 首 先 ， 從 網(wǎng) 絡(luò) 的 發(fā) 點(diǎn) 開(kāi) 始 ， 按 順 序 計(jì) 算 出 每 個(gè) 工 序 的 最早 開(kāi) 始 時(shí) 間 （ ES )和 最 早 結(jié) 束 時(shí) 間 （ EF) ， 設(shè) 一 個(gè) 工 序 所 需 的時(shí) 間 為 t， 這 對(duì) 于 同 一 個(gè) 工 序 來(lái) 說(shuō) ， 有 : EF=ES+t。工 序 a的 最 早開(kāi) 始 時(shí) 間 工 序 a的 最 早完 成 時(shí) 間1 1a0， 6060 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 43 g80,11030d6

36、0.8020e60.100 h100,11515 j135,170a0,6060其 次 ,從 網(wǎng) 絡(luò) 的 收 點(diǎn) 開(kāi) 始 計(jì) 算 出 在 不 影 響 整 個(gè) 工 程 最早 結(jié) 束 時(shí) 間 的 情 況 下 各 個(gè) 工 序 的 最 晚 開(kāi) 始 時(shí) 間 (縮 寫為 LS)和 最 晚 結(jié) 束 時(shí) 間 （ 縮 寫 為 LF),顯 然 對(duì) 同 一 工 序有 : LS=LF-t 85b60,10545 35i110,13540 25f70, 88184101 72 63c60,70 2 統(tǒng) 籌 方 法 f70,8810107,1174080,120e60.1003080,110g80,110d60.8020

37、60,80 i110.13515120,135 j135,17035135,170a0,60600,60 運(yùn) 用 此 法 則 ， 可 以 從 首 點(diǎn) 開(kāi) 始 計(jì) 算 出 每 個(gè) 工 序 的LF與 LS， 如 下 圖 所 示 。1 85b60,1054590,135c60,70 h100,11525110,13518117,1354接 著 ， 可 以 計(jì) 算 出 每 一 個(gè) 工 序 的 時(shí) 差 ， 把 在 不 影 響工 程 最 早 結(jié) 束 時(shí) 間 的 條 件 下 ， 工 序 最 早 開(kāi) 始 （ 或 結(jié)束 ） 的 時(shí) 間 可 以 推 遲 的 時(shí) 間 ， 成 為 該 工 序 的 時(shí) 差 ，對(duì) 每 個(gè)

38、 工 序 來(lái) 說(shuō) 其 時(shí) 差 記 為 Ts有 T s=LS-ES=LF-EF 72 3 6 馬 飛 雄 / GDUFS 45 最 后 將 各 工 序 的 時(shí) 差 ， 以 及 其 他 信 息 構(gòu) 成 工 序 時(shí) 間表 如 下 表 所 示 。 一 般 來(lái) 說(shuō) ， 關(guān) 鍵 工 序 的 時(shí) 差 為 零 。這 樣 就 找 到 了 一 條 由 關(guān) 鍵 工 序 a,d,g,i和 j依 次 連 接 成 的從 發(fā) 點(diǎn) 到 收 點(diǎn) 的 關(guān) 鍵 路 線 。 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 46 練 習(xí) ： 設(shè) 某 工 程 的 資 料 如 以 下 網(wǎng) 絡(luò) 圖 所 示 ，用 時(shí) 差 的 方 法 求 關(guān)

39、鍵 線 路 。1 2 534 1 1252 24 8 967 4 23a b c de 4 f gh ij k 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 47 三 、 完 成 工 序 所 需 時(shí) 間 與 關(guān) 鍵 路 線 當(dāng) 完 成 工 序 所 需 時(shí) 間 不 確 定 的 情 況 下 如 何 求 網(wǎng) 絡(luò) 時(shí) 間和 關(guān) 鍵 路 線 ？ 例 6. 長(zhǎng) 征 研 究 院 培 訓(xùn) 中 心 負(fù) 責(zé) 明 年 春 天 的 各 干 部 的 工商 管 理 培 訓(xùn) ,培 訓(xùn) 中 心 列 出 有 關(guān) 培 訓(xùn) 組 織 的 各 項(xiàng) 活 動(dòng) 的 信 息如 表 12-12所 示 ,要 求 繪 制 出 統(tǒng) 籌 方 法 的

40、網(wǎng) 絡(luò) 圖 ， 設(shè) 法 求 出網(wǎng) 絡(luò) 時(shí) 間 和 關(guān) 鍵 路 線 ， 并 確 定 開(kāi) 始 這 個(gè) 組 織 工 作 的 時(shí) 間 以保 證 培 訓(xùn) 工 作 如 期 舉 行 。 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 48 活 動(dòng)(工 序 ) 活 動(dòng) （ 工 序 ） 內(nèi) 容 緊 前 活 動(dòng)(工 序 )a bc d e f ghi 制 定 培 訓(xùn) 計(jì) 劃選 聘 培 訓(xùn) 教 師列 出 一 些 可 供 選 擇 的 培 訓(xùn) 地 點(diǎn)確 定 培 訓(xùn) 地 點(diǎn)確 定 培 訓(xùn) 的 日 程 安 排落 實(shí) 教 學(xué) 設(shè) 備 ,器 材 ,資 料發(fā) 培 訓(xùn) 通 知 并 確 定 學(xué) 員 名 單訂 旅 館 房 間處 理 最

41、 后 的 一 些 事 務(wù) - a - c b,d e b,d g f,g 2 統(tǒng) 籌 方 法 1 23 564 87a b ec d fg h i活 動(dòng) 活 動(dòng) （ 工 序 ） 內(nèi) 容 緊 前 活 動(dòng)a bc d e f ghi 制 定 培 訓(xùn) 計(jì) 劃選 聘 培 訓(xùn) 教 師列 出 一 些 可 供 選 擇 的 培 訓(xùn) 地 點(diǎn)確 定 培 訓(xùn) 地 點(diǎn)確 定 培 訓(xùn) 的 日 程 安 排落 實(shí) 教 學(xué) 設(shè) 備 ,器 材 ,資 料發(fā) 培 訓(xùn) 通 知 并 確 定 學(xué) 員 名 單訂 旅 館 房 間處 理 最 后 的 一 些 事 務(wù) - a - c b,d e b,d g f,g 由 于 是 第 一 次 搞 培

42、 訓(xùn) ， 缺 乏 統(tǒng) 計(jì) 來(lái) 確 定 完 成 每個(gè) 活 動(dòng) 所 需 時(shí) 間 ， 但 對(duì) 所 需 時(shí) 間 做 了 三 種 估 計(jì) ：1.樂(lè) 觀 時(shí) 間 。 指 所 需 最 少 時(shí) 間 ， 用 a表 示 。2.最 可 能 時(shí) 間 。 指 正 常 時(shí) 間 ， 用 m表 示 。3.悲 觀 時(shí) 間 。 指 不 順 利 情 況 下 ， 最 多 時(shí) 間 ， 用 b表 示 。如 下 表 （ 單 位 ： 周 ） 所 示 ：活 動(dòng) 樂(lè) 觀 時(shí) 間 最 可 能 時(shí) 間 悲 觀 時(shí) 間abcdefgh i 1.52.01.01.50.51.03.03.01.5 2.02.52.02.01.02.03.54.02.0

43、2.56.03.02.51.53.07.05.02.5 馬 飛 雄 / GDUFS 51 顯 然 這 三 種 完 成 活 動(dòng) 所 需 時(shí) 間 都 具 有 一 定 概 率 ，由 經(jīng) 驗(yàn) ， 我 們 可 以 可 以 假 定 這 些 時(shí) 間 的 概 率 分 布 近似 服 從 分 布 。 我 們 可 以 用 如 下 公 式 計(jì) 算 出 完 成 活動(dòng) 所 需 的 平 均 時(shí) 間 ： 以 及 方 差 64 bmaT 22 )6( ab 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 52 例 如 ： 完 成 工 作 g所 需 平 均 時(shí) 間 ：同 時(shí) 求 出 方 差 為 46 0.75.340.364 b

44、maTg 94 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 53 同 樣 可 以 求 出 每 個(gè) 活 動(dòng) 的 完 成 所 需 平 均 時(shí) 間 及 方 差 ，如 下 表 ： 活 動(dòng) T（ 平 均 時(shí) 間 ） 方 差 活 動(dòng) T 方 差a 2 0.028 f 2 0.111b 3 0.445 g 4 0.445c 2 0.111 h 4 0.111d 2 0.028 i 2 0.028e 1 0.028 2 統(tǒng) 籌 方 法 i13,152i13,15 下 面 就 用 平 均 時(shí) 間 代 替 完 成 活 動(dòng) 所 需 時(shí) 間 ， 并 在網(wǎng) 絡(luò) 圖 上 標(biāo) 上 每 個(gè) 活 動(dòng) 最 早 開(kāi) 始 時(shí) 間

45、 和 最 早 結(jié) 束 時(shí)間 ， 如 圖 12-14所 示 。23 4 5 876同 樣 也 可 以 標(biāo) 上 最 晚 開(kāi) 始 時(shí) 間 和 最 晚 完 成 時(shí) 間 等 。a0,2 g5,9b2,5 e5,6d2,4 f6,8c0,2 h9,13322 2 1 4241 23 4 5 876a0,2 g5,9b2,5 e5,6d2,4 f6,8c0,2 h9,1321,3 110,1145,949,1323,520,232,5 213,15211,13圖 12-14圖 12-151 馬 飛 雄 / GDUFS 55 從 表 12-15上 我 們 找 到 了 一 條 從 發(fā) 點(diǎn) 到 收 點(diǎn) 由 關(guān) 鍵

46、 工 序a,b,g,h,i組 成 的 關(guān) 鍵 路 線 ， 用 雙 線 標(biāo) 出 來(lái) 。 則 完 成 培 訓(xùn) 工 作所 需 的 平 均 時(shí) 間 為 各 關(guān) 鍵 路 線 的 時(shí) 間 之 和 ： =2+3+4+4+2=15（ 周 ） 同 時(shí) 完 成 時(shí) 間 近 似 服 從 一 定 的 概 率 分 布 正 態(tài) 分 布 ， 則 均值 為 關(guān) 鍵 路 線 上 各 關(guān) 鍵 活 動(dòng) 之 均 值 之 和 15， 方 差 也 為 關(guān) 鍵 路線 上 各 關(guān) 鍵 活 動(dòng) 方 差 之 和 1.05。 由 此 我 們 可 以 計(jì) 算 出 此 項(xiàng) 培 訓(xùn) 組 織 工 作 不 同 完 工 時(shí) 間 的概 率 ， 如 16周 內(nèi)

47、完 工 的 概 率 。 ihgba TTTTT 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 56 為 求 此 概 率 ， 可 以 先 求 u值 。 式 中 的 T為 預(yù) 定 完 工 時(shí) 間 16， E（ T） =15， 算 得 u=0.976。 查 正 態(tài) 分 布 函 數(shù) 表 可 知 概 率 為0.8355。 即 16周 內(nèi) 完 工 的 概 率 為 83.55%. )(TETu 025.105.1 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 57 其 正 態(tài) 分 布 圖 如 圖 12-16所 示 ：16 15)( 025.1TE圖 12-16 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDU

48、FS 58 四 、 網(wǎng) 絡(luò) 優(yōu) 化 得 到 初 始 的 計(jì) 劃 方 案 ， 但 通 常 要 對(duì) 初 始 方 案 進(jìn)行 調(diào) 整 與 完 善 。 根 據(jù) 計(jì) 劃 目 標(biāo) ， 綜 合 考 慮 資 源 和 降低 成 本 等 目 標(biāo) ， 進(jìn) 行 網(wǎng) 絡(luò) 優(yōu) 化 ， 確 定 最 優(yōu) 的 計(jì) 劃 方案 。 1.時(shí) 間 -資 源 優(yōu) 化做 法 ：1） 優(yōu) 先 安 排 關(guān) 鍵 工 序 所 需 的 資 源 。2） 利 用 非 關(guān) 鍵 工 序 的 時(shí) 差 ， 錯(cuò) 開(kāi) 各 工 序 的 開(kāi) 始 時(shí) 間 。 3） 統(tǒng) 籌 兼 顧 工 程 進(jìn) 度 的 要 求 和 現(xiàn) 有 資 源 的 限 制 ， 多次 綜 合 平 衡 。 2

49、 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 59 下 面 列 舉 一 個(gè) 拉 平 資 源 需 要 量 最 高 峰 的 實(shí) 例 。 在 例 5中 ， 若 加 工 工 人 為 65人 ， 并 假 定 這 些 工 人 可 完 成 這 5個(gè) 工 序 任 一 個(gè) ， 下 面 來(lái) 尋 求 一 個(gè) 時(shí) 間 -資 源 最 優(yōu) 方 案 。如 表 12-16所 示 ： 表 12-16工 序 需 要 人 數(shù) 最 早 開(kāi) 始 時(shí) 間 所 需 時(shí) 間 時(shí) 差d 58 60 20 0f 22 70 18 47g 42 80 3 0h 39 100 15 20i 26 110 25 0 2 統(tǒng) 籌 方 法 d(58人 ）

50、20 15h(39人 ) g(42人 ） i(26人 ） 在 圖 的 上 半部 中 ， 工 序 代 號(hào)后 的 數(shù) 字 是 人 數(shù) ，線 下 面 的 數(shù) 字 是非 關(guān) 鍵 工 序 時(shí) 差長(zhǎng) 度 。 圖 的 下 半部 表 示 從 第 60天至 135天 內(nèi) 的 75天 里 ， 所 需 機(jī) 械加 工 工 人 數(shù) ， 這樣 的 圖 稱 為 資 源負(fù) 荷 圖 。2 74 635 f(22人 ）1858人 64人80人 81人42人 26人65人60 80 100 120 13030 25圖 12-17 若 上 述 工 序 都 按 最 早 開(kāi) 始 時(shí) 間 安 排 ， 那 么 從 第 60天 至 第 135

51、天 的 75天 里 ， 所 需 的 機(jī) 械 加 工 工 人 人 數(shù) 如圖 12-17所 示 。 h(39人 ） g(42人 ） d(58人 ） i(26人 ） 同 時(shí) 我 們 應(yīng) 優(yōu)先 安 排 關(guān) 鍵 工 序 所需 的 工 人 ， 再 利 用非 關(guān) 鍵 工 序 的 時(shí) 差 ，錯(cuò) 開(kāi) 各 工 序 的 開(kāi) 始時(shí) 間 ， 從 而 拉 平 工人 需 要 量 的 高 峰 。經(jīng) 過(guò) 調(diào) 整 ， 我 們 讓非 關(guān) 鍵 工 序 f從 第 80天 開(kāi) 始 ， 工 序 h從 第110天 開(kāi) 始 。 找 到 了時(shí) 間 -資 源 優(yōu) 化 的 方案 ， 如 圖 12-18所 示 ，在 不 增 加 工 人 的 情況 下

52、保 證 了 工 程 按期 完 成 。 2 4 6 753 f(22人 ）工 人 數(shù)65人60 80 100 120 13058人 42人64人 26人65人圖 12-18 馬 飛 雄 / GDUFS 62 2.時(shí) 間 -費(fèi) 用 優(yōu) 化 需 要 考 慮 時(shí) 間 與 費(fèi) 用 的 問(wèn) 題 ： 在 既 定 的 時(shí) 間 前 工 程 完 工的 前 提 下 ， 使 得 所 需 的 費(fèi) 用 最 少 ， 或 者 在 不 超 工 程 預(yù) 算 的 條件 下 使 工 程 最 早 完 工 。 這 些 是 時(shí) 間 -費(fèi) 用 優(yōu) 化 要 研 究 和 解 決 的問(wèn) 題 。 直 接 費(fèi) 用 ： 為 了 加 快 工 程 進(jìn) 度

53、， 需 要 增 加 人 力 、 設(shè) 備 和工 作 班 次 ， 這 需 要 增 加 一 筆 費(fèi) 用 ， 成 為 直 接 費(fèi) 用 。 間 接 費(fèi) 用 ： 由 于 工 程 早 日 完 工 ， 減 少 了 管 理 人 員 的 工 資辦 公 費(fèi) 等 費(fèi) 用 稱 為 間 接 費(fèi) 用 。 一 般 說(shuō) 工 序 越 短 ， 直 接 費(fèi) 用 越多 ， 間 接 費(fèi) 用 越 少 。 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 63 工 序 的 最 快 完 成 時(shí) 間 ： 指 完 成 時(shí) 間 的 最 高 限 度 。 我 們 設(shè) 完 成 工 序 j的 正 常 所 需 時(shí) 間 為 Tj;直 接 費(fèi) 用為 cj;完 成

54、工 序 j的 最 快 完 成 時(shí) 間 為 Tj,直 接 費(fèi) 用 為 cj。這 樣 我 們 可 以 計(jì) 算 出 縮 短 工 序 j的 一 天 工 期 所 增 加 的直 接 費(fèi) 用 ， 用 kj表 示 ， 稱 為 直 接 費(fèi) 用 變 動(dòng) 率 。 有 時(shí) 間 -費(fèi) 用 優(yōu) 化 問(wèn) 題 可 建 立 兩 個(gè) 線 性 規(guī) 劃 模 型 。 模 型 一 ， 在 既 定 的 時(shí) 間 T完 工 的 前 提 下 ， 問(wèn) 各 工序 的 完 成 時(shí) 間 為 多 少 才 使 因 縮 短 工 期 而 增 加 的 直 接費(fèi) 用 最 少 。 jj jjj TT cck 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 64 設(shè)

55、工 序 （ i ,j)的 提 前 完 工 時(shí) 間 為 Yij,我 們 用 Tij,Tij分 別表 示 正 常 完 工 時(shí) 間 與 最 快 完 工 的 時(shí) 間 ， 則 有 工 序（ i ,j)的 實(shí) 際 完 工 時(shí) 間 為 ： Tij-Yij。 我 們 用 Cij,Cij表 示用 正 常 完 工 時(shí) 間 和 最 快 完 成 時(shí) 間 完 成 工 序 所 需 要 的費(fèi) 用 ， Kij為 工 序 （ i ,j)的 直 接 費(fèi) 用 變 動(dòng) 率 。 得 到 這 個(gè)問(wèn) 題 的 線 性 規(guī) 劃 模 型 如 下 ：S.t. Xj-Xi Tij-Yij,對(duì) 一 切 弧 （ i, j) Yij Tij-Tij, 對(duì)

56、 一 切 弧 （ i, j) X n-X1 T, Xi 0， Yij 0。 )(min ),( ijji ij YKf 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 65 例 7. 例 5所 提 供 的 信 息 都 作 為 本 例 的 信 息 ，另 外 還 給 出 了 在 裝 配 過(guò) 程 中 各 道 工 序 所 需 正常 完 工 時(shí) 間 與 最 快 完 工 時(shí) 間 ， 以 及 對(duì) 應(yīng) 正 常完 工 時(shí) 間 與 最 快 完 工 時(shí) 間 的 所 需 的 直 接 費(fèi) 用和 每 縮 短 一 天 工 期 所 需 增 加 的 直 接 費(fèi) 用 ， 如表 12-17所 示 。 2 統(tǒng) 籌 方 法 工序 Ti

57、j正 常完 工 Cij直 接費(fèi) 用 Tij最快 完 工 Cij直 接費(fèi) 用 直 接 費(fèi) 用變 動(dòng) 率a 60 10000 60 10000 -b 45 4500 30 6300 120c 10 2800 5 4300 300d 20 7000 10 11000 400e 40 10000 35 12500 500f 18 3600 10 5440 230g 30 9000 20 12500 350h 15 3750 10 5750 400i 25 6250 15 9150 290j 35 12000 35 12000 - 馬 飛 雄 / GDUFS 67c 該 工 程 要 求 在 150天 內(nèi)

58、 完 工 ， 問(wèn) 每 個(gè) 工 序 應(yīng) 比 正常 完 工 時(shí) 間 提 前 多 少 天 完 成 ， 才 能 使 整 個(gè) 工 程 因 縮短 工 期 而 增 加 的 直 接 費(fèi) 用 為 最 少 。 如 果 工 期 要 求 在140天 完 工 呢 ？1 2 3 45 6 7 8a bfe hg i jd 2 統(tǒng) 籌 方 法 解 ： 根 據(jù) 此 網(wǎng) 絡(luò) 圖 建 立 數(shù) 學(xué) 模 型 。 設(shè) 此 網(wǎng) 絡(luò) 圖 上 第 i點(diǎn)發(fā) 生 的 時(shí) 間 為 xi， 工 序 提 前 完 工 的 時(shí) 間 為 yij。 目 標(biāo) 函 數(shù) : minf=120y27+300y23+400y24+500y25+230y37 +350y

59、46+400y57+290y67. s.t. x2-x1 60-y12, x7- x2 45-y27 x3-x210-y23 x4-x220-y24 x5-x240-y25 x 7-x318-y37 x6-x430-y46 x5-x40虛 擬 弧 （ 4， 5） x7-x515-y57 x7-x625-y67 馬 飛 雄 / GDUFS 69 x1 =0, y120, y2715, y23 5 y24 10 y25 5 y37 8 y46 10 y57 5 y78 0 x8 150 xi 0， yij 0.（ 對(duì) 一 切 可 能 的 ij)運(yùn) 算 得 到 結(jié) 果 ： f=6400。 2 統(tǒng) 籌

60、 方 法 馬 飛 雄 / GDUFS 70 模 型 二 ， 我 們 知 道 直 接 費(fèi) 用 是 隨 著 完 成 時(shí) 間 的縮 短 而 增 加 ， 而 間 接 費(fèi) 用 卻 會(huì) 隨 著 完 成 時(shí) 間 的 縮 短 而減 少 ， 設(shè) 單 位 時(shí) 間 的 間 接 費(fèi) 用 為 d,計(jì) 劃 期 的 間 接 費(fèi) 用與 總 工 期 成 正 比 ， 即 為 d(xn-x1),那 么 求 使 包 括 間 接 費(fèi)用 與 直 接 費(fèi) 用 在 內(nèi) 的 總 費(fèi) 用 最 少 的 整 個(gè) 工 程 最 優(yōu) 完 成時(shí) 間 T和 各 個(gè) 工 序 最 優(yōu) 完 成 時(shí) 間 的 模 型 為 ： 目 標(biāo) 函 數(shù) min f=d(xn-x1

61、)+ s.t. xj-xi Tij-yij， 對(duì) 一 切 弧 （ i ,j) y ijTij-Tij ， 對(duì) 一 切 弧 （ i ,j) xi 0， yij 0。 j)(i, ijij )y(k 2 統(tǒng) 籌 方 法 例 8 如 果 在 例 7中 ， 每 天 的 間 接 費(fèi) 用 為 330元 ， 求使 包 括 間 接 費(fèi) 用 與 直 接 費(fèi) 用 在 內(nèi) 的 總 費(fèi) 用 最 少 的 整 個(gè)工 程 最 優(yōu) 完 成 時(shí) 間 T和 各 個(gè) 工 序 最 優(yōu) 完 成 時(shí) 間 。 解 ： 決 策 變 量 的 含 義 同 例 7。 此 數(shù) 學(xué) 模 型 的 目 標(biāo)函 數(shù) 為 ：minf=330(x8-x1)+12

62、0y27+300y23 +400y24+500y25+230y37 +350y46+290y67 此 模 型 的 約 束 條 件 與 例 7的 約 束 條 件 基 本 相 同 ，只 要 在 例 子 的 約 束 條 件 中 去 掉 x8 150就 得 到 了 例 8模型 的 約 束 條 件 了 。 計(jì) 算 得 到 以 下 結(jié) 果 ： f=55700. x 1=0, y12=0, y67 =10, x2=60, y27 =0, y78=0. 馬 飛 雄 / GDUFS 72 x3 =125, y23 =0, x4 =107, y24 =0, x5 =110, y25 =0, x6 =110, y3

63、7 =0, x7 =125, y46 =0, x8 =160, y57 =0, 也 就 是 說(shuō) 整 個(gè) 工 程 工 期 為 160天 時(shí) 總 費(fèi) 用最 少 為 55700元 ， 各 個(gè) 工 序 開(kāi) 始 時(shí) 間 如 解 所 示 ，工 序 i 要 提 前 10天 完 工 ， 其 余 的 工 序 按 正 常 時(shí)間 完 工 。 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 73 列 出 項(xiàng) 目 和 工 序 的 明 細(xì) 表 ； 改 平 行 、 交 叉 工 序 ； 延 用 時(shí) 差 ， 抽 調(diào) 非 關(guān) 鍵 工 作 上 的 人 力 物力 到 支 援 關(guān) 鍵 工 作 ， 以 加 快 關(guān) 鍵 工 作 的 進(jìn)度 ； 在 最 小 成 本 的 工 作 上 趕 工 。調(diào) 整 優(yōu) 化 方 法 小 結(jié) ： 2 統(tǒng) 籌 方 法 馬 飛 雄 / GDUFS 74 祝 大 家 身 體 健 康 ， 學(xué) 習(xí) 進(jìn) 步 ！第 九 章 排 序 與 統(tǒng) 籌 方 法