臺灣博碩士論文加值系統

面對日益複雜的生產系統，如何在多資源衝突的環境下做出最佳的生產排程，並即時反應生產環境的變化已成重要課題。本文提出一多資源限制下之基因演算排程法，提供一解決此類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.

摘 要I
ABSTRACTII
誌 謝III
目 錄IV
表 目 錄VIII
圖 目 錄IX

第一章 緒論1
1.1 研究背景1
1.2 問題描述2
1.2.1 半導體測試作業流程2
1.2.2 半導體測試作業之多資源衝突4
1.3 研究目的5
1.4 研究與論文架構6

第二章 文獻探討8
2.1 協商決策相關文獻8
2.1.1 多方協商函式（Multilateral Negotiation Functions）8
2.1.2 協商戰術（Negotiation Tactics）10
2.1.2.1 時間相依戰術10
2.1.2.2 資源相依戰術13
2.1.2.3 行為相依戰術15
2.1.3協商戰略（Negotiation Strategies）17
2.1.4 協商權衡（Negotiation Trade-Offs）19
2.2 代理人自主性協商相關文獻21
2.3 多資源限制下之排程相關文獻25
2.4 半導體測試廠排程之相關文獻26
2.5 平行機台排程問題相關文獻27
2.6 結語28

第三章 多資源限制下之生產排程30
3.1 染色體編碼（REPRESENTATION）32
3.1.1 生產組構（Operating Modes）33
3.1.2 開始加工時間（Start Time）33
3.2 基因操作（GENETIC OPERATORS）34
3.2.1 起始解（Initial Population）34
3.2.2 再生（Reproduction）35
3.2.3 交配（Crossover）35
3.2.3.1 Uniform Crossover36
3.2.3.2 Blend Crossover37
3.2.4 突變（Mutation）38
3.3 適當值（FITNESS VALUE）39
3.3.1 提早或延遲交貨時間（Earliness or Tardiness）39
3.3.2 總設定時間（Total Setup Time）40
3.3.3 最晚完成時間（Makespan）40
3.3.4 價格（Profit）40
3.4 演算法程序（OVERALL ALGORITHM）40
3.5 參數選擇44
3.6 績效評估52
3.7 多資源限制下之基因演算法排程範例56
3.8 結語58

第四章 協商決策函式與權衡機制於多資源生產排程之應用59
4.1 以NDF為基礎之多資源限制協商模型59
4.1.1 客戶端（Client）架構60
4.1.2 伺服器端（Server）架構61
4.1.3 加入協商權衡機制之協商模型61
4.1.4 協商議題與評分函式66
4.2 模擬協商系統之假設與評估指標68
4.2.1 模擬協商結果產出69
4.2.2 模擬協商系統參數69
4.2.3 模擬協商系統績效評估指標70
4.3 柏拉圖最佳化（PARETO-OPTIMAL）72
4.4 結合自主式排程系統之協商機制績效評估74
4.4.1 無權衡機制下之協商戰術表現74
4.4.2 加入權衡機制的協商表現77
4.4.3 協商權衡機制於不同議題權重之表現78
4.4.4 協商權衡機制於不同協商戰術之表現80
4.4.5 預測協商對手偏好之準確度對協商結果的影響84
4.4.6協商權衡機制於不同協商底限之表現86
4.4.7 加入協商權衡機制後之排程結果差異88
4.5 結語90

第五章 結論與未來研究方向91
5.1 結論91
5.2 未來研究方向93
5.2.1 多資源限制下之生產排程方面93
5.2.2 協商機制方面94

參考文獻95
附錄 I100
附錄 II108

王俊程(2000a)，企業對企業電子商務之合作式談判代理人之研究，國科會專題研究計畫。王俊程(2000b)，電子商務自動談判系統 (II)--代理人自主性之研究，國科會專題研究計畫，2000。吳仲昇(1996)，遺傳演算法在晶圓針測排程問題上之應用，國立清華大學工業工程研究所碩士論文。李威亭(2000)，邏輯IC最終測試廠之測試機台排程研究，國立清華大學工業工程研究所碩士論文。周崇皓(2000)，全方位製造系統之協商機制設計，中原大學工業工程研究所碩士論文。林福仁(2000)，應用於電子商務的線上機動議價代理人之研究，國科會專題研究計畫。陳元璞(2001)，以代理程式為基礎的電子市集協商機制，淡江大學資訊工程學系碩士論文。湯景富(1995)，半導體廠測試區生產規劃模式之建構，國立交通大學工業工程研究所碩士論文。黃聖智(1999)，半導體針測區之互動式排程研究，國立清華大學工業工程與工程管理研究所博士論文。楊文怡(1998)，半導體測試廠之限制驅導式排程管理模式研究，中華大學工業工程與管理研究所碩士論文。楊佳璁(2001)，智慧型代理人運用於線上談判之研究─以C2C為例，東海大學工業工程學系碩士論文。劉瑞瓏(2001)，運用於有限資源下企業環境資訊持續偵搜之適性化代理人，國科會專題研究計畫。鄧豐毅(1998)，半導體針測區現場作業排程分析，國立清華大學工業工程研究所碩士論文。賴勇良(1998)，以人工生命進行移動式代理人電子商務協商之安全性研究，國立雲林科技大學資訊管理研究所碩士論文。羅盛豪(1996)，運用基因法則建構半導體測試區現場排程模式，國立交通大學工業工程研究所碩士論文。蘇豐文(2000)，不確定戲局中透過可靠第三者的多代理人間的協調與溝通，國科會專題研究計畫。Alidaee, B. (1993), “Two Parallel Machine Sequencing Problems Involving Controllable Job Processing Time”, European Journal of Operational Research, Vol. 70, pp. 335-341.Azizoblu, M. and Kircal, O. (1998), “Tardiness Minimization on Parallel Machines”, International Journal of Production Economics, Vol. 55, No. 2, pp. 163-168.Baker, K. R. (1974), Introduction to Sequencing and Scheduling, John Wiley & Sons, New York.Baruah, S.K.; Gehrke, J.E. and Plaxton, C.G. (1995), “Fast scheduling of periodic tasks on multiple resources”, Parallel Processing Symposium, 1995. Proceedings., 9th International, pp. 280 —288.Bikramjit Banerjee, Sandip Debnath and Sandip Sen (1999), “Using Bayesian Network to aid Negotiations among Agents”, in the Working Notes of the AAAI-99 Workshop on Negotiation: Settling Conflicts and Identifying Opportunities (also available as AAAI Technical Report WS-99-12), pp. 44-49.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.De, S. and Lee, A. (1998), “Parallel Machine Scheduling Using Memetic Algorithm”, Mathematical Computing Modeling, Vol. 33, No, 3-4, pp. 761-764.Eshelman, L. J. and J. D. Schaffer. (1992). “Real-Coded Genetic Algorithm and Interval-Schemata”. In L Darrel Whitley (ed), Foundations of Genetic Algorithm 2. San Mateo, CA, Morgan Kaufmann Publishers.Faratin, P., Sierra, C., and Jennings, R.N. (1998), “Negotiation Decision Functions for Autonomous Agents”, Robotics and Autonomous Systems, Vol. 24, Issues 3, pp. 159-182.Faratin, P., Sierra, C., and Jennings, R.N. (2000), “Using similarity criteria to make negotiation trade-offs”, MultiAgent Systems, 2000. Proceedings. Fourth International Conference on, pp. 119-126.Faratin, P., Sierra, C., Jennings, N., and Buckle, P. (1999), “Designing Flexible Automated Negotiators: Concessions, Trade-Offs and Issue Changes”, Institut d''Investigacio en Intel.ligencia Artificial Technical Report, RR-99-03.Halland, H. H. (1975), Adaptation in natural and artificial systems, Detroit MI: University of Michigan Press.Hu, T.C., Kuo, Y.S., and Ruskey, F. (1987), “Some Optimal Algorithms for Scheduling Problems with Changeover Costs”, Operations Research, Vol. 35, No. 1, pp. 94-99.Hung H., Bui, D., Kieronska, and Venkatesh, S. (1996), “Learning other agents'' preferences in multiagent negotiation”, In Proceedings of the National Conference on Artificial Intelligence (AAAI-96), pp. 114-119.Jennings, N., Faratin, P., Lomuscio, A., Parsons, S., Sierra, C., and Wooldridge, M. (2001), “Automated Negotiation: Prospects, Methods and Challenges”, Int. Journal of Group Decision and Negotiation, Vol. 10, No. 2, pp. 199-215.Joan Morris, Jim Youll, and Pattie Maes (1999-2001), Impulse, Software Agents Group, Media Laboratory Massachusetts Institute of Technology. （http://agents.media.mit.edu/projects/impulse/）Katia Sycara (1987), PERSUADER, The Robotics Institute, School of Computer Science Carnegie-Mellon University. （http://www-2.cs.cmu.edu/~sycara/persuader.html）Lin, and Wen Yuan (1993), “A model of the integrated multiple resources project and personnel scheduling problems”, ARIZONA STATE UNIVERSITY PHD Thesis.Mailler, Roger, Vincent, Regis, Lesser, Victor, Middlekoop, Tim, and Shen, Jiaying. (2001), “Soft-Real Time, Cooperative Negotiation for Distributed Resource Allocation”, In AAAI for Symposium on Negotiation, Falmouth, MA.Morse, Lucy Crymble (1987), “An evaluation of combining heuristics for scheduling projects with limited multiple resources”, UNIVERSITY OF CENTRAL FLORIDA PHD Thesis.Piersam, N. and Dijk, W.V. (1996), “A Local Search Heuristic for Unrelated Parallel Machine Scheduling with Efficient NeighborhoodnSearch”, Mathematical Computing Modeling, Vol. 24, No. 9, pp. 11-19.Rose Gamble and Sandip Sen (1994), “Using Formal Specification to Resolve Conflicts between Contracting Agents”, in Proc. AAAI-94 Workshop on Conflict Management in Cooperative Problem Solving, Seattle, Washington, pp. 33-38.Sandholm, T. and Lesser, V. (1995), “Issues in Automated Negotiation and Electronic Commerce: Extending the Contract Net Framework”, First International Conference on Multiagent Systems (ICMAS-95), San Fransisco, pp. 328-335Shen, W. and Norrie, D. H. (1999a), “A Hybrid Agent-Oriented Infrastructure for Modeling Manufactruing Enterprises”. （http://imsg.enme.ucalgary.ca/）Shen, W. and Norrie, D. H. (1999b), “Agent-Based Systems for Intelligent Manufacturing: A State-of-the-art Survey”, International Journal Knowledge and Information Systems, Vol 1, No. 2, pp.129-156.Sierra C., Faratin P. and Jennings N. (1997), “A Service-Oriented Negotiation Model between Autonomous Agents”, Proc. 8th European Workshop on Modeling Autonomous Agents in a Multi-Agent World (MAAMAW-97), Ronneby, Sweden, pp. 17-35.Sierra C., Faratin P. and Jennings N. (1999), “Deliberative Automated Negotiators Using Fuzzy Similarities”, Proc EUSFLAT-ESTYLF Joint Conference on Fuzzy Logic, Palma de Mallorca, Spain, pp. 155-158.Simons, J.V.Jr, Stephens, M.D., and Simpson, W.P. (1999), “Simultaneous versus sequential scheduling of multiple resources which constrain system throughput”, International Journal of Production Research, Vol. 37, No. 1, pp. 21-33.Sivrikaya, M. and Patnaik, M.L. (1999), “Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms”, IEEE Transctions on System, Man and Cybernetics, Vol. 24, No. 4, pp. 656-667.So, K.C. (1990), “Some Heuristics for Scheduling Jobs on Parallel Machines with Setups”, Management Science, Vol. 36, No. 4, pp. 467-476.Syswerda, G. (1989), “Uniform crossover in genetic algorithms”, in Schaffer, J., editor, Proceedings of the 3rd International Conference on Genetic Algorithms, Morgan Kaufmann publishers, San Francisco, pp. 2-9.Uzsoy, R., Church, L. K., Ovacik, I. M. and Hinchman, J. (1993), “Performance evaluation of dispatching rules for semiconductor testing operations”, Journal of Electronics Manufacturing, Vol. 3, pp. 95-105.Uzsoy, R., Lee, C.Y., and Martin-Vega L.A. (1992), “Scheduling Semiconductor Test Operations：Minimizing Maximum Lateness and Number of Tardy Jobs on a Single Machine”, Naval Research Logistics, Vol. 39, pp. 369-388.Vepsalainen, A.P.J. and Morton T.E. (1987), “Priority rules for job shops with weighted tardiness costs”, Management Science, Vol. 33, pp. 1035-1047.Yang J. and Chang, T. S. (1998), “Multiobjective scheduling for IC sort and test with a simulation tested”, IEEE transactions on semiconductor manufacturing, Vol. 11, No. 2, pp. 304-315.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.