多資源限制下智慧型代理人協商機制之設計—以半導體測試作業為例

An Agent-based Negotiation Mechanism for Multi-Resources Scheduling

古漢舜(Han-Shun Ku)

指導教授 ： 王孔政

中原大學/工學院/工業工程研究所/碩士(2002年)

https://doi.org/10.6840/cycu200200176

摘要

面對日益複雜的生產系統，如何在多資源衝突的環境下做出最佳的生產排程，並即時反應生產環境的變化已成重要課題。本文提出一多資源限制下之基因演算排程法，提供一解決此類NP hard問題之方法。首先，針對問題形式設計基因演算法之染色體編碼與基因操作方式，以解決多資源限制下之機台動態組構問題；並透過實驗測試，選擇較佳的參數組合與探討基因演算法在不同評估指標中的表現。主要的評估指標包括：提早或延遲交貨時間、總設定時間、最晚完成時間以及排入排程之產品總價。本研究以半導體測試作業為對象，完成構模與雛型實作，以實例驗證了本研究所提構模方法之可行性與效率，並提供本研究進行協商權衡機制的重要工具。此外，本研究提出以協商決策函式（Negotiation Decision Function）為基礎之協商程序，提供排程的供需雙方進行協商；並於協商過程中加入協商權衡（Negotiation Trade-Offs）機制，以獲得整體結果較佳之折衷解。本研究以C語言實作此一自主式排程系統以及協商機制，作為研究之實驗載具；並以柏拉圖最佳化解作為實驗結果之評估依據。實驗結果證實以協商決策函式為基礎之協商權衡機制對協商雙方整體利益而言，效果確實較單獨使用協商決策函式戰術優越。另分別對不同議題權重、不同協商戰術、以及不同權重推測準度下之權衡機制表現，進行評估，發現協商權衡機制不論在何種環境下皆能逼近柏拉圖最佳化，也發現推測對手偏好的準確度對協商結果與柏拉圖最佳化之距離具重要影響。

關鍵字

協商決策模型 ； 柏拉圖最佳化 ； 多資源生產排程 ； 協商權衡 ； 基因演算法

並列摘要

As the complexity of production system increases, vital has become the issue as to how to make the best production scheduling in a multi-resources conflicting environment and to respond to the changes of production environment immediately. This study puts forward a genetic algorithm which could solve NP hard problems when many resources are limited. First, we design for different problems the chromosome representation and the genetic operators of the genetic algorithm, thereby solving resources dynamic configuration problems under resources-limited circumstances; moreover, through experiments we choose a better parameter combination and discuss the performances of the genetic algorithm when evaluated by different indexes. The main evaluation indexes includes: Earliness and Tardiness, Total Setup Time, Makespan, and Profits of scheduled products. This study experiments with the semiconductor testing operations to complete modeling and make the prototype, proving the feasibility and efficiency of the mentioned modeling method by means of actual examples and supplying important instruments to carry out the Negotiation Trade-Offs mechanism. Besides, this study suggests the negotiation procedure based on Negotiation Decision Function for suppliers and demanders to negotiate, adding the Negotiation Trade-Offs mechanism to the process of negotiation so as to achieve a better compromise solution on the whole. This study uses C language to devise as experiments tool of the scheduling system and the negotiation mechanism, and uses Pareto Optimal solution as the evaluation criterion of the results of experiments. The results prove that, in terms of the general benefits of both negotiators, the effects of using the Negotiation Trade-Offs mechanism which is based on Negotiation Decision tactics are obviously better than those of using Negotiation Decision tactics alone. Furthermore, after separately evaluating the performances of Negotiation Trade-Offs under different issue weights, different negotiation tactics, and different weight speculation accuracy, we found that the Negotiation Trade-Offs mechanism can approach to the Pareto Optimal, whatever the circumstances; we also found that the accuracy of predicting opponents’ preferences could significantly influence the distance between the results of negotiations and the Pareto Optimal.

並列關鍵字

Pareto Optimal ； Multi-Resources Scheduling ； Genetic Algorithm ； Negotiation Decision Model ； Negotiation Trade-Offs

參考文獻

Yang, J., Chang, T. S., Chang, H. and Kao, J. (1996), “Optimization-based dynamic scheduling and its tested for IC sort and test”, Proceedings of the 35th IEEE Conference on Decision and Control, Vol. 3, pp. 2759-2762.

Alidaee, B. (1993), “Two Parallel Machine Sequencing Problems Involving Controllable Job Processing Time”, European Journal of Operational Research, Vol. 70, pp. 335-341.

Candido, M.A.B., Khator, S.K., and Barcia, R.M. (1998), “A genetic algorithm based procedure for more realistic job shop scheduling problems”, International Journal of Production Research, Vol. 36, No. 12, pp. 3437-3457.

Chen Tsung-Rian, Chang Tsu-Shuan, Chen Cheng-Wu and Kao Jen (1995), “Scheduling for IC Sort and Test with Preemptiveness via Lagrangian Relaxation”, IEEE Transactions on Systems, Man and Cybernetics, Vol. 25, No. 8, pp. 1249-1256.

Chen, T.R. and Hsia, T.C. (1994), “Job shop scheduling with multiple resources and an application to a semiconductor testing facility”, Decision and Control, 1994., Proceedings of the 33rd IEEE Conference on , Vol. 2, pp. 1564 –1570.