(3.238.186.43) 您好!臺灣時間:2021/03/01 15:15
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:陳明德
研究生(外文):Ming-Der Chen
論文名稱:平行機台分派問題之制約模式
論文名稱(外文):Constraint Modeling for the Assignment Problems of Parallel Machines Systems
指導教授:周雍強周雍強引用關係
指導教授(外文):Yon-Chun Chou
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:工業工程學研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:77
中文關鍵詞:機台分派制約模式
外文關鍵詞:machine assignmentconstraint modeling
相關次數:
  • 被引用被引用:3
  • 點閱點閱:125
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
機台分派,廣泛的意義是指:在可用資源充滿限制的情況下,如何反應決策需求與環境的變動而有效率地去安排需要處理的工作。分派的過程中需要考慮各式各樣的限制條件,像是:機台的加工能力、機台可用的產能和管理者的偏好等等。這些多樣而且可能相互衝突的限制因子會影響到機台分派的結果。
本研究的目的為發展一個處理限制的方法。根據機台分派問題的特性,引入CSP(Constraint Satisfactory Problem)的概念,藉由對限制的分析和規劃提出三種不同變數設定的CSP模型:machine-centric model、job-centric model和assignment-centric model。並探討三種模型如何去處理機台分派問題的種種限制,而提出對應的解題程序,並對這三種CSP模型做比較,以期發現較為適當的採行模式。在驗證的實作上結合一套運算組合最佳化的發展工具:ILOG OPL而確立模型的真確性與可行性。

In general, machine assignment is to assign tasks to resources efficiently where it can response the decision requirements and the changing environment under the circumstance that available resources are limited. During the assignment process, it should take a large variety of constraints into consideration such as machine capability, machine capacity, and management preference and so on. Machine assignment is influenced by such diverse and possibly conflicting factors.
The purpose of this thesis is to develop a methodology to handle constraints. By incorporating the concept of CSP (Constraint Satisfaction Problem) into the analysis and plan of constraints involved in the machine assignment problems, three CSP models are proposed: machine-centric model, job-centric model and assignment-centric model. The solving procedures to deal with the constraints for the models are also presented. And to find the most sufficient one, there are comparisons among the three models. To check the feasibility and accuracy of the models, they have been implemented with ILOG OPL that is an integrated development environment for combinatorial optimization applications.

索引及目錄
中文摘要 i
Abstract ii
索引及目錄 iii
圖目錄 v
表目錄 vi
第1章 緒論 1
1.1 問題背景 1
1.1.1 機台分派問題的案例 1
1.1.2 限制的種類與特性 4
1.1.3 機台分配問題中動態的情境決策 5
1.2 問題分析與研究動機 6
1.2.1 傳統上解決機台分派問題的方法 6
1.2.2 採用CSP的原因 8
1.2.3 CSP的特性 9
1.3 研究目的 11
1.4 研究方法 11
1.4.1 限制條件模型的建構 12
1.4.2 CSP的解題方法 12
1.4.3 CSP解的性質 13
1.4.4 發展平台與解題工具 14
1.5 數量的範例 14
第2章 文獻回顧 17
2.1 機台分派問題的回顧 17
2.1.1 The assignment problem & the generalized assignment problem 17
2.1.2 The multi-resource generalized assignment problem 19
2.1.3 整數線性規劃模式的探討 21
2.2 限制的探討 26
2.2.1 限制的意義 26
2.2.2 限制的種類 28
2.2.3 限制的討論 29
2.3 Constraint Satisfaction Problem 30
2.3.1 Binary CSP 30
2.3.2 Variable and value ordering 33
2.3.3 Dynamic CSP 34
2.3.4 模型評估的準則 36
第3章 機台分派問題的制約模式 37
3.1 Constraint types與constraint categories 37
3.1.1 Constraint types 37
3.1.2 Constraint categories 39
3.2 制約模式的建構 41
3.2.1 Machine-centric model 42
3.2.2 Job-centric model 46
3.2.3 Assignment-centric model 47
3.3 解題的程序 49
3.3.1 數量的範例 49
3.3.2 A machine-centric model 50
3.3.3 A job-centric model 52
3.3.4 An assignment-centric model 54
3.4 限制處理方式的比較 56
第4章 模型的比較與驗證 57
4.1 三種模型的比較 57
4.1.1 Capacity constraints 58
4.2 Job-centric model V.S. Assignment-centric model 61
4.2.1 模型間對應現象的討論 61
4.2.2 Disjunctive resources 62
4.2.3 模型實作的容易程度 63
4.3 以ILOG OPL實作模型 63
4.3.1 小的數量範例 64
4.3.2 數量的範例 68
第5章 結論與未來之展望 70
5.1 結論 70
5.2 未來展望 70
參考文獻 72
附錄A:範例4-2的輸入資訊與OPL程式碼 73
圖目錄
圖 1 1:衡量環境變動對解品質的影響 9
圖 2 1:Constraint graph [7] 31
圖 2 2:Constraint graph (hidden variable encoding) [7] 32
圖 2 3:Constraint graph (dual encoding) [7] 32
圖 2 4:處理Dynamic CSP的架構 [11] 35
圖 3 1:The constraint graph of machine-centric model 45
圖 3 2:Capacity constraint (job-centric model) 46
圖 3 3:Capacity constraint (assignment-centric model) 48
圖 3 4:Alternative machine (assignment-centric model) 48
圖 3 5:The constraint graph of the machine-centric model 51
圖 3 6:The constraint graph of the job-centric model 53
圖 3 7:The constraint graph of the machine-centric model 55
圖 4 1:三個模型產能限制的constraint graph 60
表目錄
表格 1 1:零組件的加工時間(單位:分鐘) [1] 2
表格 1 2:限制因子的條列與說明 4
表格 1 3:工廠每日機台分派表 7
表格 1 4:範例1-1中機台和零組件的資料 15
表格 1 5:範例1-1的解 16
表格 2 1:ILP問題的大小 24
表格 3 1:Constraint types 38
表格 3 2:Constraint categories 39
表格 3 3:範例3-1的data set 50
表格 3 4:限制處理方式的比較 56
表格 4 1:三個模型處理constraint category的方法 57
表格 4 2:三個模型大小的整理比較 60
表格 4 3:模型變數與值域的比較 62
表格 4 4:範例4-1的data set 64

參考文獻
[1]C. Dillenberger, and A. Wollensak, “Demand Allocation for Capacity Optimization: A Solution in IBM Manufacturing,” Optimization in Industry 2: Mathematical Programming and Modeling Techniques in Practice, John Wiley & Sons, pp. 89-98, 1994.
[2]周雍強, “非等效並聯機台之生產規劃與排程,”Proceedings of the 1999 Conference on Production Scheduling: Theory and Its Application, NTHU, Taiwan, 1999.
[3]S. U. Randhawa, and C. H. Kuo, “Evaluating Scheduling Heuristics for Non-Identical Parallel Processors,” International Journal of Production Research, Vol. 35, No. 4, pp. 969-981, 1997.
[4]S. C. Chang, C. Y. Liu, and M. D. Hu, “PHOMAG: A Photolithography Machine Allocation Game,” Semiconductor Manufacturing Conference Proceedings, 1997 IEEE International Symposium on, San Francisco, CA, USA, pp. 11-13, 1997.
[5]H. P. Willams, and J. M. Wilson, “Connections Between Integer Linear Programming and Constraint Logic Programming — An Overview and Introduction to the Cluster of Articles,” INFORMS Journal on Computing, Vol. 10, No. 3, pp. 261-264, 1998.
[6]S. C. Brailsford, C. N. Potts, and B. M. Smith, “Constraint Satisfaction Problems: Algorithms and Applications,” European Journal of Operation Research 119, pp. 557-581, 1999.
[7]R. Barták, Guide to Constrain Programming, http://ktilinux.ms.mff.cuni.cz/~bartak/constraints/index.html
[8]E. Tsang, Foundations of Constraint Satisfaction, Academic Press, pp 31-52, 1993.
[9]M. S. Fox, S. F. Smith, “ISIS- A Knowledge-Based System for Factory Scheduling,” Expert Systems, Vol. 1, No. 1, pp. 25-49, 1984.
[10]L. J. LeBlanc, A. Shtub,and G. Anandalingam, “Formulating and solving production planning problems,” European Journal of Operation Research 112, pp. 54-80, 1999
[11]A. K. Jonsson, J. D. Frank. “A framework for dynamic constraint reasoning using procedural constraints,” 14th European Conference on Artificial Intelligence, 2000.
[12]S. Mittal and B. Falkenhainer, “Dynamic constraint satisfaction problems,” in Proceedings of the Eighth National Conference on Artificial Intelligence, pp. 25-32, 1990.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔