【正文】 ，并針對此問題的改善策略進行研究。 再次， 從統(tǒng)籌各生產(chǎn)系統(tǒng)的高度出發(fā)， 根據(jù)各生產(chǎn)系統(tǒng) 所 具體 的 生產(chǎn)能力，以及訂單的狀況，對各生產(chǎn)系統(tǒng)的產(chǎn)能進 行整體規(guī)劃； 并根據(jù)各生產(chǎn)系統(tǒng)的具體情況，以產(chǎn)能分配結(jié) 果 作 為 先進生產(chǎn)方式進行拉動的源頭，導(dǎo)入先進 生產(chǎn)方式， 讓各生產(chǎn)系統(tǒng)的生產(chǎn)源于顧客的實際需求，并且具備根據(jù)顧客多樣化、少批量的需求而及時生產(chǎn)的柔性生產(chǎn)能力。 最后，本文也為其它類型相似的制造型企業(yè)就如何合理分配產(chǎn)能以及如何提升企業(yè)根據(jù)顧客多樣化、少批量的需求而及時生產(chǎn)的柔性生產(chǎn)能力 給出建議 ，并且就先進 生產(chǎn)方式的實戰(zhàn)應(yīng)用方面 給出了一些切實可行的建議和意見。 本文研究的思路是從理論到實踐的，先從產(chǎn)能分配及 先進 生產(chǎn)方式 等的相關(guān)理論開始著手，從其 相關(guān)研究的發(fā)展歷程中尋找規(guī)律， 通過對 GSK 公司 的產(chǎn)能分配現(xiàn)狀以及 生產(chǎn) 現(xiàn)狀進 行深入了解并且分析，然后在這個基礎(chǔ)上， 采用禁忌搜索 對 GSK公司 的產(chǎn)能分配以及 通過轉(zhuǎn)變 生產(chǎn)方式 而提高生產(chǎn)效率 提出新的建議和思路。 研究的主要方法 本文采用禁忌搜索算法對 GSK 公司的多生產(chǎn)系統(tǒng)的產(chǎn)能進行分配，為了使得初第一章 緒 論 7 始解具備更高的質(zhì)量，利用匈牙利算法求得初始解，再 應(yīng)用 Matlab 求得最優(yōu)解。然后通過制程流程圖區(qū)分生產(chǎn)現(xiàn)場的價值與浪費，然后 用價值流分析圖對生產(chǎn)現(xiàn)場的的實際價值流向進行分析，并且得出要改善的重點項目予以改善。最后采用對比分析法，對本文研究的產(chǎn)能分配方式所得結(jié)果與 GSK 公司之前的產(chǎn)能分配 方式所得結(jié)果，以及本文所研究的生產(chǎn)方式與 GSK 公司之前的生產(chǎn)方式進行對比 ，體現(xiàn)本文研究內(nèi)容的價值。 燕山大學(xué)工程碩士學(xué)位論文 第 2 章 相關(guān)理論 及概念 指派問題 指派問題數(shù)學(xué)模型 在 我們的 實際 生活 當(dāng) 中， 指派問題可以說是無處不在 。例如：有幾班級需要安排幾個教室上課 ； 有幾項工作需要指派給幾個人來完成； 有 幾 項合同需要選擇 幾個投標者來承包等。諸如類似的 問題，它們 都具備一個共同的特點：滿足一 定的指派要求條件下，使得指派方案的總體效果最優(yōu) 。 標準形式 標準形式的指派問題為 ：有 n 個 工作人員 和 n 項工作 ，已知 ：第 j 項工作 由 第i 個 工作人員完成的 費用為 ijc （ i,j=1,2,…,n ），要求給出 指派方案 ：使得這 n 個工作人員和這 n 項工作一一對應(yīng) ， 并且要求 這 n 個工作人員完成 這 n 項工作 的總費用最少。 通常 情況下， 定義 矩陣 ? ?nnijcC ??為指派問題的系數(shù)矩陣。 而在實際應(yīng)用時，則 根據(jù) ijc 的 現(xiàn)實 含 義， 給予 矩陣 C 不同的定義 ，如 成本、 費用、時間等。 矩陣 C，第 j 列各元素表示第 j 項工作由不同工作 人 員完成 的費用， 第 i 行中各元素表示第 i個工作人員完成各項工作 的費用。 建立標準指派問題的數(shù)學(xué)模型 之前 ， 首先 定義如下 ： ? ?n,2,1,i01i ?????? jji jix j 項工作個工作人員完成第若不指派第 項工作個工作人員完成第若指派第 然后 ， 建立 標準指派問題 的數(shù)學(xué)模型 如下： ??? ?? ni nj ijij xcz 1 1m in （ 21） ? ?? ?? ????????????????????njxnixnjxtsijnjijnij,2,1,i01,2,11,2,11..11i???或 （ 22） 第 2 章 相關(guān)理論 及概念 9 模型中， 式 (22)依次 表示 每 項工作 必由且只有一個 工作人員去完成 ； 表示 每個工作人員完成且只完成一項工作 ；若是 1ij?x 則表示分配成功，若 0ij?x 則表示分配失敗 。 可用解矩陣 ? ?nnijxX ??中的元素 來表示 模型中的每一個可行解 。作為可行解，矩陣 中的 每列各元素中都有且只有一個 1，以滿足 每項工作必由且只有一個工作人員去完成 ；每行各元素都有且只有一個 1，以滿足 每個工作人員完成且只完成一項工作 。 可知 指派問題有 !n 個可行解。 非標準形式 在我們的現(xiàn)實生活當(dāng)中 ， 遇到的問題往往不是標準形式的，而是工作人員數(shù) 量不等于工作數(shù)量，或者某個工作人員可以做更多的工作等形式 。 那么無論遇到怎樣形式的指派問題， 都是通過以下介紹的原理將 它們轉(zhuǎn)化為標準形式，然后用 標準形式指派問題進行求解 。 （ 1） 工作人員數(shù)和工作數(shù) 不 相 等 的情況下 的指派問題 ：一種情況為 工作人員數(shù)少于工作數(shù) ， 解決辦法為在系數(shù)矩陣添加虛擬的“人員 ” 使得工作人員數(shù)與工作數(shù)相等 。 并且 規(guī)定 ：添加的 虛擬的“ 人員 ” 完成 各 項工作 的費用為 0； 另一種情況為 工作人員數(shù)大于工作數(shù) ， 解決辦法為在系數(shù)矩陣添加 虛擬的“ 工作 ” 使得工作人員數(shù)與工作數(shù)相等 。 并且 規(guī)定 ：添加的 虛擬的“ 工作 ” 被各工作人員 完成 的費用為0。 （ 2） 一個 工作人員可完成幾項工作 的指派問題 ： 在實際應(yīng)用當(dāng)中，如果有某個工作人員可以獨立完成多項工作， 則可在系數(shù)矩陣中添加該 工作人員 來接受指派。 當(dāng)然 添加的這幾個工作人員完成同一項工作的費用相同 ，從而轉(zhuǎn)化為標準形式 。 （ 3） 某 項工作一定不能由某工作人員完成 的指派問題 ： 若 根據(jù)實際情況規(guī)定某 項工作 一定不能由某 個工作人員去完成 ，則可將 該工作人員完成該項工作 的費用系數(shù)取作足夠大的數(shù) M，指派問題原理則不會指派該類組合，從而也就實現(xiàn)了某事一定不會由某人做的指派結(jié)果 [26]。 匈牙利解法 標準 形 式 的指派問題既 屬于 整數(shù)規(guī)劃 類 問題，又是 特殊的運輸問題和 01 規(guī)劃問題， 因此 ， 求解的方法較多 。 重要的是：普遍求 解 方 法 并 不能 充分利用指派問題所具有 的性質(zhì) 來進行，而只是從數(shù)學(xué)的角度去解決問題，這樣就增加了運算量 。 而 燕山大學(xué)工程碩士學(xué)位論文 1955 年，庫恩 先生 利用 獨立零元素的定理 ，提出 求解指派問題的一種算法 ， 因為這種獨立零元素定理源于匈牙利數(shù)學(xué)家康尼格的研究成果，所以 我們 習(xí)慣上稱之為匈牙利解法 ，具體如下： 利用 匈牙利解法 求解標準形式指派問題實際上是 利用了 矩陣 的一個重要的 性質(zhì)：從矩陣 中的某行或者某列的 各元素 均 減去一個常數(shù) n，得到一個新的矩陣 ， 則這兩個矩陣擁 有相同的最優(yōu)解 ，即這種變化不影響矩陣的解 。 這個性質(zhì)的原理是由于矩陣的這種變化不會影響目標函數(shù)，而只是減少了常數(shù) n，最優(yōu)解并不變化。 因為根據(jù)上文對于非標準形式的指派問題的分析可知，即使是非標準形式的指派問題也可以通過一些方法將其轉(zhuǎn)化為標準形式的指派問題來解決，所以本文只介紹 標準 形式 的指派問題， 詳 述如下： 步驟 1：變換系數(shù)矩陣。 根據(jù)指派問題最優(yōu)解的重要性質(zhì)，使得形式矩陣的各行、各列出現(xiàn)至少一個零元素，并且保證不能出現(xiàn)負元素。具體操作為：首先找各行、各列元素中的最小元素，然后分別讓各行、各列均減 去之前找出的最小元素可得滿足以上條件的新矩陣。然后繼續(xù)步驟 2； 步驟 2： 確定獨立零元素。 首先定義獨立零元素：即矩陣中不同行、不同列的零元素稱為獨立零元素。規(guī)定若矩陣中有 n 個獨立零元素則可得矩陣最優(yōu)解，若獨立零元素少于 n 個則繼續(xù)以下步驟。根據(jù)定義和規(guī)定在矩陣中尋找。 步驟 3：繼續(xù)變換系數(shù)矩陣。 方法與步驟 1 類似，就是在沒有被直線覆蓋的各行、各列中尋找一個最小元素，然后讓各行、各列減去 之前找出的最小元素，這樣就會使得這些行、列出現(xiàn)零元素。但是同時會在其他行、列出現(xiàn)負元素，所以還需要將出現(xiàn)負元素的各行、各列再加上相 應(yīng)整數(shù)，目的是消除負數(shù)。這樣就可以使得矩陣出現(xiàn) n 個獨立零元素。若獨立零元素還是小于 n 個則返回步驟 2 繼續(xù)進行操作，直到獨立零元素的個數(shù)為 n 為止。 補充 ： 指派問題系數(shù)矩陣中 獨立零元素的確定方式如下： 首先在尋找獨立零元素的前提是系數(shù)矩陣不存在負元素，因為根據(jù)實際問題，費用、時間等不會出現(xiàn)負值的情況。在選擇零元素時，如果某行、列有多個零元素，而實際選擇時也只選擇其中之一，所以 零元素的多少不是問題的關(guān)鍵，而重點是它們是否分布在不同的行、列。 在 確定獨立零元素 的過程中，為了能夠區(qū)分不同行、列的零元素 ， 可以通過一些標記 手段：只有一個零元素的行、列 中加圈 ，即將零元素圈起來 ， 不是已經(jīng)做了第 2 章 相關(guān)理論 及概念 11 指派 。 每當(dāng)圈完一個零元素，需要將 位于同列 、行 的其他零元素劃去 ，不是這項工作及這個工作人員不得再進行指派 。如此反復(fù)，直至系數(shù)矩陣中所有零元素都被圈去或者劃去為止。 查看 獨立零元素 個數(shù)，若已經(jīng) 有 n 個 獨立零元素 則表示 已經(jīng)產(chǎn)生了 最優(yōu)指派方案。此時， 令系數(shù)矩陣中的已經(jīng)確定了的獨立零元素為 1，因此同時將矩陣中其他因素設(shè)為 0， 從而 得最優(yōu)解矩陣。 若 獨立零元素少于 n 個，則表示還 不是 最優(yōu)指派方案 ，需要繼續(xù)變換矩陣 ?？砂聪旅娴姆椒▉磉M行： （ 1） 對沒有 被圈起來 的 零 元素所在的 行 作標記 √ ； （ 2） 在 已經(jīng)作標記 的行中，對 被 劃去的零元素 所在列 作標記 √ ； （ 3） 在 已經(jīng)作標記 的列中，對 被 圈起來的零元素所在行作標記 √ ； （ 4） 重復(fù) （ 2）（ 3） ，直至 沒有可以繼續(xù) 作標記的 行或者列為止； （ 5） 對沒有 作標記 的行畫橫線，對 已經(jīng) 作標記 的列畫垂線， 最終可得覆蓋所有零元素的 最少直線數(shù)目的 直線集合 。 禁忌搜索算法 簡介 禁忌搜索 （ Tabu Search，簡稱 TS）的思想最早是由 Glover 于 1986 年 提出，它是 一種優(yōu)化組合算法，也是對 局部領(lǐng)域搜索的 一種擴展，是一種全局逐步尋優(yōu)算法，是對人類 智力過程的一種模擬。 禁忌搜索 算法 思想 局部領(lǐng)域搜索 算法 是在 當(dāng)前解的領(lǐng)域中持續(xù) 不斷 地進行搜索， 雖然 算法 通俗易懂，也容易實現(xiàn) ，但 也有其缺點： 搜索 結(jié)果 的優(yōu)劣 完全依賴于領(lǐng)域結(jié)構(gòu)和初始解 的優(yōu)劣，即領(lǐng)域結(jié)構(gòu)及初始解選擇的優(yōu)劣會 很大程度 決定 了 搜索結(jié)果的優(yōu)劣 ， 特別 容易陷入局部極小而 失去全局最優(yōu) 性。 而 禁忌搜索是 一種 人工智能的體現(xiàn)，是局部領(lǐng)域搜索的一種擴展。禁忌搜索 可以很好的避免局部領(lǐng)域搜索的不足：即 它在搜索過程中會 對已經(jīng) 搜索 過 的最優(yōu)解 進行標記，并且將其對應(yīng)的對象放入禁忌表， 避免 在接下來 的搜索 過程 中 對 這些對象 的 進 行 重復(fù)搜索 ，從而保證 不局限于局部進行搜索，而能夠更好的對全局進行搜索 。禁忌搜索涉及到領(lǐng)域、禁忌表、禁忌長度、候選解、藐視準則等概念。 禁忌搜索 算法的基本思想是： 首先， 通過隨機選取或者利用某種算法給定或者 燕山大學(xué)工程碩士學(xué)位論文 求得 一個當(dāng)前解 作為初始解 ；然后設(shè)定 一種領(lǐng)域 規(guī)則 ， 并 在 已選的 當(dāng)前解的領(lǐng)域中確定若干 個 較優(yōu)解為 候選解，將候選解一一代入目標函數(shù)， 若 所得 的目標 函數(shù) 值優(yōu)于 目前最好的 狀態(tài)，則忽略其禁忌特性 將其從禁忌表中釋放出來 ，用其代替當(dāng)前解和 目前最好的 狀態(tài)， 與此同時 將相應(yīng)的對象加入禁 忌表 ， 如果 不存在上述候選解，則在候選解中選擇非禁忌 的最佳狀態(tài)為新的當(dāng)前解，而 忽略 它的優(yōu)劣 性 ，同時將相應(yīng)的對象加入禁忌表 ；如此重復(fù)上述搜索過程，直至尋找 到 滿意的最優(yōu)解則停止，或者規(guī)定最大迭代次數(shù) 。 禁忌搜索算法實現(xiàn)步驟 禁忌搜索算法步驟可描述如下： （ 1） 通過隨機選取或者利用某種算法給定或者求得 一個當(dāng)前解作為初始解 ，同時 設(shè)禁忌表為空； （ 2） 首先 判斷 初始解對應(yīng)的目標函數(shù)值是否 滿足 終止條件 ？ 若符合 ，則 直接結(jié)束算法并輸出 結(jié)果 ；否則，繼續(xù)以下步驟； （ 3） 設(shè)定某種規(guī)則產(chǎn)生領(lǐng)域函數(shù)， 并 利用當(dāng)前解 的領(lǐng)域函數(shù)產(chǎn)生其 領(lǐng)域解，然后從 中確定若干 較優(yōu)解為候選解； （ 4） 將候選解代入目標函數(shù)并且判斷其是否優(yōu)于當(dāng)前最優(yōu)解 ？若 滿足 ，則用最優(yōu)解 替代當(dāng)前解，并 將其對應(yīng)的禁忌對象替代 禁忌表 中 的禁忌對象，同時用 最優(yōu)解 替代 目前最佳 狀態(tài)。轉(zhuǎn)步驟 （ 6） ；否則，繼續(xù)以下步驟； （ 5） 判斷候選解對應(yīng)的各對象的禁忌屬性，選擇候選解集在非禁忌對象對應(yīng)的最佳狀態(tài)為新 的當(dāng)前解，同時用與之對應(yīng)的禁忌對象替換最早進入禁忌表的禁忌對象； （ 6） 轉(zhuǎn)步驟 （ 2） 反復(fù)循環(huán)直到找到最優(yōu)解或者達到迭代次數(shù) 。 與 其他局部搜索算法以及 傳統(tǒng)的優(yōu)化算法相比， TS 算法的主要特點是： 在搜索過程中可以接受劣解， 從而可以避免對局部 最優(yōu)解的反復(fù)搜索 ； 最優(yōu)解不是在當(dāng)前解的領(lǐng)域中隨機產(chǎn)生，而或是優(yōu)于 當(dāng)前最優(yōu)解 ，或者是非禁忌的最佳解，因此選取 最優(yōu) 解的概率遠大于其他 方式 。 由于 禁忌搜索 算法具有靈活的記憶功能和藐視準則，并且在搜索過程中可以接受劣解 ,所以 可以避免對局部最優(yōu)解的反復(fù)搜索 ，轉(zhuǎn)向 未被搜索到的 其他區(qū)域，從而 更好的搜索到最優(yōu)解 ，所以 禁忌搜