臺灣博碩士論文加值系統

摘 要
生產排程與資源配置問題為生產與作業管理領域長期所關注之研究主題，然而回顧過去相關研究中，多數將其區隔為兩類問題分別進行探討；於實際作業環境中，工件於機台上之作業時間常隨所配置資源量多寡而變動，而非固定已知參數；因此，本研究針對非等效平行機台排程與非再生性資源之配置問題做一深入研究與探討；其中，各工件因處理特性不同只能至特定幾部候選機台上進行加工處理，且每一工件於可加工機台上之作業時間與資源配置量呈線性遞減關係。
在本文中將以1.費洛蒙陣列架構定義(pheromone representation)與編碼(encoding)；2.螞蟻建構解之方法(solution construction)；3.費洛蒙更新方式(pheromone update)三個部份討論如何設計不同求解模式之蟻群最佳化演算法(Ant Colony Optimization Algorithm；ACO Algorithm)求解此問題；並在不同問題規模下進行測試分析，針對不同求解模式之求解時間與求解品質做一探討，以評估演算法於非等效平行機台排程與資源配置問題之績效。

ABSTRACT
In this paper, a scheduling and resource allocation problem of which processing time of each job with its machine eligibility restrictions may be reduced linearly by the using of discrete divisible nonrenewable resource on unrelated parallel machines with the objective of minimizing makespan is tackled. The problem is solved with Ant Colony Optimization Algorithm (ACO Algorithm).
Three different designs of ACO algorithm are proposed and can be discussed with three aspects: pheromone representation and encoding solution construction and pheromone update. Numerical result shows that ACO Ⅰ favorably produce better schedules than others.

目錄
中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
一、緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究問題描述 2
1.4 研究範圍與限制 3
1.5 研究方法與架構 4
二、文獻探討 5
2.1 排程問題之概述 5
2.2 平行機台排程問題之探討 6
2.2.1 平行機台分類 6
2.2.2 非等效平行機台排程問題之相關文獻 7
2.3 資源配置暨生產排程問題 8
2.4 蟻群最佳化演算法(Ant Colony Optimization；ACO) 8
2.4.1 螞蟻系統(Ant System；AS) 10
2.4.2 螞蟻族群系統(Ant Colony System；ACS) 11
2.4.3 超立方體架構(The Hyper-Cube Framework ;HCF) 13
2.4.4 相關文獻 16
三、研究方法 17
3.1 數學模式之建構 17
3.2 ACO求解模式探討 22
3.2.1 ACO-Ⅰ 22
3.2.1.1 費洛蒙陣列架構定義(Pheromone Representation) 22
3.2.1.2 螞蟻建構解之方法(Solution Construction) 23
3.2.1.3 費洛蒙更新方式(Pheromone Update) 27
3.2.2 ACO-Ⅱ 30
3.2.2.1 費洛蒙陣列架構定義(Pheromone Representation) 30
3.2.2.2 螞蟻建構解之方法(Solution Construction) 31
3.2.2.3 費洛蒙更新方式(Pheromone Update) 34
3.2.3 ACO-Ⅲ 36
四、參數設計 38
4.1 測試規模說明 38
4.2 參數分析 38
4.2.1 田口實驗設計 39
4.2.2 特性要因分析 39
4.2.3 ACO-Ⅰ和ACO-Ⅱ之實驗設計與分析 39
4.2.3.1 控制因子與水準之設定 39
五、驗證結果與分析 47
5.1 演算法之比較 47
5.1.1 演算法驗證 47
5.1.3 規模二 51
5.1.4 規模三 53
5.1.5 規模四 55
5.1.6 規模五 57
5.2 演算法於不同問題規模之績效評估 59
六、結論與建議 62
6.1 研究結論 62
6.2 未來研究建議 62
參考文獻 64

參考文獻
[1]江朋南，2003，蟻族系統在零工型排程問題之應用，國立台灣科技大學，碩士論文。
[2]林熙凱，2005，蟻群演算法於非等效平行機台之多階段流程型排程問題研究，大葉大學，碩士論文。
[3]徐誠佑，2002，螞蟻演算法求解零壹多限制式背包問題，國立清華大學，碩士論文。
[4]陳明俊，2004，蟻群演算法於具非等效平行機台考量之排程問題研究，大葉大學，碩士論文。
[5]張秀玲，2008，應用蟻群最佳化建構有限產能零工式排程決策支援系統之研究，世新大學，碩士論文。
[6]黃國凌，2004，螞蟻塔布混合演算法求解零工型排程問題，國立台灣科技大學，碩士論文。
[7]練俊源，2003，平行機製程在資源限制下之排程問題，中原大學，碩士論文。
[8]鍾承志，2004，多目標零工式平行機台排程之研究-應用蟻群最佳化演算法， 東海大學，碩士論文。
[9]Andrea Rossi, Gino Dini, 2007, “Flexible job-shop scheduling with flexibility and separable setup times using ant colony optimization method”, ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING, vol. 23, pp.503-516.
[10]A., Allahverdi and J., Mittenthal, Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time, Naval Research Logistics, Vol. 41, No. 5, pp. 677-682, 1994.
[11]V., Bharadwaj, D., Ghose, V., Mani, T.G., Robertazzi, 1996, Scheduling divisible loads in parallel and distributed systems, IEEE Computer Society, New Jersey
[12]B.M.T. Lin, C.Y. Lu, S.J. Shyu, C.Y. Tasi 2008, “Development of new features of ant colony optimization for flowshop scheduling”, INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS, vol. 112, pp.742-755.
[13]J.F.Chen, Unrelated parallel machine scheduling with setups, Proceeding of the 5th annual international conference on industrial engineering theory, application and practice, 1-7 (2000).
[14]T.C.E.Cheng, Z.L., Chen, C.L., Li, 1996, Single-machine scheduling with trade-off between number of tardy jobs and resource allocation, Operations Research Letters, 19,237–242.
[15]Z.L.Chen, 2004, Simultaneous job scheduling and resource allocation on parallel Machines, Annals of Operations Research, 129, 135–153.
[16]Christian Blum, 2005, “Review: Ant colony optimization: Introduction and recent trends”, PHYSICS OF LIFE REVIEW, vol. 2, pp.353-373.
[17]Christian Blum, Student Member, IEEE, and Marco Dorigo, Senior Member, IEEE 2004, “The Hyper-Cube Framework for Ant Colony Optimization”, IEEE TRANSACTIONS ON SYSTEMS ,MAN, AND CYBERNETICS, vol. 34, No. 2.
[18]Daniels, R.L., Hoopes, B.J., Mazzola, J.B., 1996, Scheduling parallel cells with resource flexibility, Management Science, 42, 1260–1276.
[19]Daniels, R.L., 1990, A multi-objective approach to resource allocation in single machine scheduling, European Journal of Operational Research, 48, 226–241.
[20]Glass, C. A., Potts, C. N. and Shade, P., Unrelated parallel machine scheduling using local search, Mathematical and computer modeling, Vol. 20, No 2, pp.41-52, 1994.
[21]Hariri, A. M. A. and Potts, C. N., Heuristics for scheduling unrelated parallel machines, Computers and Operations Research, Vol. 18, No. 3, pp. 323-31, 1991.
[22]Janiak, A.,1998, Minimization of the makespan in a two-machine problem under given resource constraints, European Journal of Operational Research, 107, 325–337.
[23]Maheswaran, R., Ponnambalam, S.G., 2003, An investigation on single machine total weighted tardiness scheduling problems, International Journal of Advanced Manufacturing Technology, 22, 243–248.
[24]Oguz, C., Zinder, Y., Do, V.H., Janiak, A., 2004, Hybrid flow-shop scheduling problems with multiprocessor task systems, European Journal of Operational Research,152, 115–131.
[25]Suresh, V. and Chaudhuri, D., Minimizing maximum tardiness for unrelated parallel machines, International Journal of Production Economics, Vol. 34, No.2,pp. 223-239, 1994.
[26]Suresh, V. and Chaudhuri, D., Bicriteria scheduling problem for unrelated parallel machines, Computer and Industrial Engineering, Vol. 30, No. 1, pp. 77-82, 1996.
[27]Shabtay, D., 2004, Single and two-resource allocation algorithms for minimizing the maximal lateness in a single machine, Computers & Operations Research, 31, 1303–1315.
[28]Shabtay, D., Kaspi, M., 2006, Parallel machine scheduling with a convex resource consumption function, European Journal of Operational Research, 173, 92–107.