應用模糊限制為基礎之軟體代理人協商機制於生產規劃與排程─以某UPS生產製造公司之生產排程為範例

Application of Fuzzy Constraint-based Agent Negotiation to Distributed Planning/Scheduling —A Case Study for Production Planning and Scheduling at a UPS Manufacturer

華明煌(Ming-Huang Hua)

指導教授 ： 賴國華 博士

元智大學/資訊學院/資訊工程學系/碩士(2004年)

摘要

摘要
排程問題為NP Hard問題，許多研究針對生產排程，提出相當多的人工智慧演算方法及其改良，例如：基因演算、TABU或是模擬退火法。其中有許多研究是為了尋找排程問題的最佳解。也因為如此，這樣的生產排程問題要付出相當的運算效能及時間的代價來處理，即便許多演算方式已做了許多改良。
我們在此提出關於生產排程問題不同的觀點，本研究主要應用以模糊限制為基礎之代理人協商機制(FCAN)的觀念帶入生產排程中。令生產排程可以由幾個生產參數互相關聯，使其可以讓使用者針對其需求的排程結果推向其預設的方向(例如：符合交期、成本較低或品質較優)。我們會這樣處理生產排程問題的主要原因，是因為不同的生產管理者基於其專業或不同公司在不同時期對於生產排程結果的需求，有不同的看法。因此，對於有特殊生產排程規劃預設立場或一般無特殊生產排程規劃預設立場的使用者，都可以應用生產參數的設定，達到其預期的目標。
對於上述生產排程的要求，本研究使用模糊限制理論之α CUT以及最低滿意度設定，將生產排程搜尋的求解區間控制在一定的範圍之內，並且透過以模糊限制為基礎之代理人協商機制的方式提供業務協商策略之生產計劃。因此、我們可以有效的改善生產排程的速度並且令排程結果也被限定在可接受的程度之上。除此之外，因為生產排程並不保證其結果可以同時被生產廠商及客戶接受。這是因為在現實生活中，往往會有訂單過於集中而導致無法生產的情形。因此，本研究利用代理人協商機制置入生產排程規劃之中。使得當生產排程有某些訂單之交期有所改變時，可以提供業務或業務之軟體代理人作為協商的策略及建議，也為未來的自動化協商做一預先的處理。
本研究使用某UPS生產製造公司之實際生產狀況為實驗之基礎，並利用我們的方法與LPT以及TABU之排程演算法，實際運用程式計算不同數量訂單之排程結果，再將其結果互相比較並統計。
本研究之實驗結果，符合我們的預期，可獲得令人滿意之成效。例如：我們的方法與TABU以及LPT之計算效能遠優於TABU，而總體滿意值更遠優於現行之LPT之結果。另外，本研究方法之生產成本與現行使用之LPT演算法比較亦可降低約8.2%之生產成本。

關鍵字

生產排程 ； 排程 ； 生產規劃 ； 模糊限制

並列摘要

Abstract
The scheduling problem is a NP Hard problem. Many researches presented many artificial intelligent algorithmic ways and improvements. Such as: Genetic practice, Tabu or simulated annealing. Most of the researches look for the best solution of the scheduling problem. Even after tons of algorithmic formulation and improvement, still it takes enormous computing performance and time to handle such scheduling problems.
We would like to raise a different ideal for production scheduling problem. Our approach applies the fuzzy constraints base agent negotiation (FCAN) to production scheduling. With this approach, the production line is provide with several scheduling parameters that are interrelated with each other thereby allowing the user to establish a production line that suit its demands. (Such as: meeting the delivery time, lowering the cost or improving the quality.). Since different companies, production plans and production managers have varying demands thereby several production parameters are required. This is the main reason of using FCAN principle in the process of scheduling in our research. Therefore, for special production scheduling requirements as well as the general ones, users can attain their scheduling target, simply by defining their production scheduling parameters.
Based on aforementioned necessities and demands of production, our approach applies the concepts of α CUT and minimum acceptable satisfaction degree in fuzzy constraints theory into the production line. It limits the scheduling problem solution under the α CUT solution space. This approach can efficiently improve and reduce the processing time for production scheduling problems as well as limiting the results within acceptable parameters. Other than this, during production there is no certainty that the result will be acceptable to the producing company itself or the client this is so because in reality there are several instances wherein orders get piled up and the production line wouldn’t be able to meet the demands. Therefore, on instances like these, our approach also applies the FCAN on sales negotiation strategy into the production planning that can support the scheduling suggestions to avoid no solution scheduling.
Our approach is utilized into an actual production scheduling of a UPS (Uninterruptible Power Supply) manufacturer who implements their production scheduling by LPT and TABU. We employ the approach base on actual order quantities and different scheduling results then compare these results and compute the statistics.
The result of our study is the same as our expectations. We got satisfactory results. Our approach has faster running speed than TABU and we also got higher satisfaction value than LPT. Moreover, our approach had resulted in a much lower production cost as compare to the present production scheduling of this manufacturer and LPT. It can reduce the production cost up to approximately 8.2%.

並列關鍵字

Production Scheduling ； Scheduling ； Production Planning ； Fuzzy Constraints

參考文獻

[Bagas 2004] Bagas Wardono and Yahya Fathi *, 2004. ”A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities,” European Journal of Operational Research, Vol. 155, pp. 380-401.

[Bond 1988] Bond, A. H., and L. Gasser. 1988. Reading in Distributed Artificial Intelligence, San Mateo, CA: Morgan Kaufmann.

[Dubios 1999] Dubios, Didier and Philippe Fortemps, 1999. “Theory and Methodology Computing improved optimal solutions to max-min flexible constrain satisfaction,” European Journal of Operational Research, Vol. 118, pp. 95-126.

[Dubios 2003] Dubios, Didier, Helene Fargier and Philippe Fortemps, 2003. “Invited Review Fuzzy scheduling: Modeling flexible constraints vs. coping with incomplete knowledge,” European Journal of Operational Research, Vol. 147, pp. 231-252.

[Dhodhi 1997] Dhodhi, M.K. and Ahmad, I., 1997. “Task tree scheduling onto linear arrays using tabu search,” IEE Proceedings on Computers and Digital Techniques, Vol. 144 (5), pp. 317-323.