臺灣博碩士論文加值系統

競爭環境以及消費者需求的快速變動，使得企業對於所生產之產品以及提供之服務的要求也隨時在改變，企業必須建構能迅速回應需求變動之機制，改變現行之作業方法與作業順序，方能快速而有效的回應。在大部分的排程問題研究上，大都只針對單一目標去求解最佳或最適排程順序，在實務的生產流程安排上，必須考量多項因素，因此，關於多目標之整合性生產排程問題的研究有其必要性。本研究以流程式生產排程為範圍，以基因演算法（GA）做為解決之方法，迅速的取得近似最佳解。期望達成之研究目的包括：建構一套排程機制，使企業能解決不同作業目標與條件下之排程問題、運用所建構之基因演算機制，快速的找出最佳的生產排程順序與利用排程準則的組合使企業能充分反應環境的變動。
在資料驗證部分，經過300代的演算結果，在單目標排程規劃之延遲時間結果發現，由初始值的966減少至GA解的235改進效果達75.67％，可見基因演算法為一套非常有效之搜尋法則。在多目標排程規劃，在同時考慮延遲時間與工作等待時間結果發現，延遲時間由初始值的829減少至GA解的240改進效果達71.05％，在相同條件下工作等待時間由初始值的2589減少至GA解的915改進效果達64.66％。在特殊情況排程規劃，以不考慮特定設備之情況下與考慮特定設備之情況下，以GA解進行比較，單目標的總完工時間為1096以及機器閒置時間為409，特定設備的閒置時間由103降為0，在特定設備之總完工時間為1110，只小幅增加了1.26%。以上驗證資料均說明本研究所提出之排程模型能有效解決多種不同環境中的排程問題，同時有相當好的演算效果。

Owing to the rapid changing of competitive environment and consumer’s need, enterprise must improve product quality and after sale service at any time. In the meantime, enterprise must construct quick response required alternation model, and change existent operational method and order so as to quickly but effectively response this situation. Most of the researches of scheduling problem only aim directly at single objective which leads optimal solution or best scheduling order. In fact, for enterprise, the schedule of the production flow must consider many factors. So it is a must to research multiple objective integrated production scheduling problem. This research takes flow shop production scheduling as its range, making the most of genetic algorithm to quickly seek best approximate solution. The expectant aim of this research includes： to construct a scheduling model, enterprise can solve scheduling problem under different operation objectives and condition and exert construct genetic algorithm model；to quickly find out optimal production scheduling order, and to take advantage of scheduling rules combination, and with these aims enterprise can fully go with environmental alteration.
In the part of data verify, the result of 300 generations algorithm can concluded as follows： in tardiness time, as for the result of single objective scheduling planning, the improved effect of initial solution 996 decrease to GA optimal solution 235 is 75.67% that proves GA is very effective theory for search. As for the multiple objective scheduling planning, in tardiness time and job waiting time, the improved effect of initial solution 829 decrease to GA optimal solution 240 is 71.05% in the tardiness time; the improved effect of initial solution 2589 decrease to GA optimal solution 915 is 64.66% under the same condition in the job waiting time. In the special problem scheduling planning, GA optimal solution proceed comparison between considering specific equipment situation and no considering specific equipment situation, leading to makespan for 1096 and machine idle time for 409 in the single objective, in the other hand machine idle time falls from 103 to 0 in the specific equipment, makespan for 1110 of specific equipment, only little increased by 1.26%. Verify data mentioned above illustrates that the scheduling model presented by this research can in effect settle many kinds of scheduling problems in the different situation, and with excellent algorithm effect.

中文摘要 i
英文摘要 ii
誌謝 iv
目錄 v
表目錄 vii
圖目錄 viii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 3
1.3 研究流程 3
第二章 文獻探討 5
2.1 生產排程問題 5
2.1.1 排程的定義 6
2.1.2 排程之分類 7
2.1.3 排程之衡量績效 11
2.1.4 排程之特殊情況 13
2.2 排程之解決方法 13
2.2.1 派工法則 14
2.2.2 排程之最佳解法 16
2.2.3 排程之啟發式解法 17
第三章 問題分析與模型建構 20
3.1 排程問題分析 20
3.2 排程模型建構 24
3.3 基因演算法 29
第四章 模擬分析與驗證 35
4.1模擬問題描述 35
4.2 基因演算程序 37
4.3 結果分析 40
4.3.1 單目標排程規劃 44
4.3.2 多目標排程規劃 47
4.3.3 特殊情況排程規劃 48
第五章 結論與建議 53
5.1 結論 53
5.2 建議 55
參考文獻 56

1.方曉嵐，「排程方法研究」，技術與訓練，第二十一卷，第一期， 第149-155頁（1996）。
2.毛志奇，建立動態之人員派遣排程研究－以電腦資訊服務業為例，碩士論文，屏東科技大學工業管理系，屏東（2004）。
3.周書賢，開放型工廠派工法則之模擬研究，碩士論文，朝陽科技大學工業工程與管理系，台中（2001）。
4.官長輝，基因演算法於國道客運最適車數及排程之整合研究，碩士論文，輔仁大學管理研究所，台北（2003）。
5.林我聰，「現場排程專家系統—應用個體導向技術建立之研究」，財團法人資訊工業策進會—資訊與電腦出版社，（1994）。
6.林建民，混合基因演算法應用於具迴流特性流程工廠之研究，碩士論文，國立台灣科技大學工業管理系，台北（2002）。
7.林雅文，捷運列車排班計畫之模糊多目標決策分析，碩士論文，國立海洋大學河海工程學系，基隆（2003）。
8.林暘桂，不相關平行機總加權延遲最小化之排程問題，碩士論文，朝陽科技大學工業工程與管理系，台中（2001）。
9.施榮宗，考量設置順序與工具限制之平行機排程研究，碩士論文，義守大學工業管理學系，高雄（2002）。
10.柯惠雯，結合模擬退火法與禁忌搜尋法在流程式生產排程之應用，碩士論文，大葉大學工業工程研究所，彰化縣（2000）。
11.張保隆，陳文賢等6 人，生產管理，台北：華泰書局，（1997）。
12.莊世宗，FAB廠之模擬排程與控制，碩士論文，雲林科技大學工業工程與管理技術研究所，雲林（1997）。
13.陳志合，元件化現場排程系統之發展，碩士論文，東海大學工業工程研究所，台中（2000）。
14.陳英仁，以模擬為基礎的晶圓製造廠派工法則，碩士論文，國立華大學工業工程研究所，新竹（1996）。
15.陳禎祥，最大完工時間極小化的迴流工廠排程之研究，博士論文，國立台灣科技大學工業管理系，台北（2003）。
16.游宗德，彈性製造系統排程設計與線上診斷系統之研究，碩士論文，國立高雄第一科技大學機械與自動化工程系，高雄（2003）。
17.湯璟聖，動態彈性平行機群排程的探討，碩士論文，中原大學工業工程研究所，桃園（2003）。
18.黃漢強，混合式基因演算法應用於不等待零工廠問題之研究，碩士論文，國立台灣科技大學工業管理系，台北（2002）。
19.詹金淩，整合螞蟻理論與案例式推理於知識管理之應用，碩士論文，國立臺北科技大學生產系統工程與管理研究所，台北（2003）。
20.劉仲立，雙重資源限制下開放型工廠派工法則模擬研究，碩士論文，朝陽科技大學工業工程與管理系，台中（2003）。
21.劉偉遠，應用基因演算法於批次生產排程系統做為電力預估最佳化之研究，碩士論文，國立高雄第一科技大學機械與自動化工程系，高雄（2003）。
22.蕭義梅，遺傳演算法應用在零工式工廠生產排程之應用，碩士論文，私立元智大學工業工程所，桃園（1999）。
23.羅中育，田口品質工程應用於模擬退火法參數組合之研究—以旅行推銷員問題（TSP）為例，碩士論文，雲林科技大學工業工程與管理研究所，雲林（2001）。
24.Aggoune, R. "Minimizing the makespan for the flow shop scheduling problem with availability constraints," European Journal of Operational Research, 153, 3, 534-543（2003）.
25.Armentano, V.A., and Ronconi, D.P. "Tabu search for total tardiness minimization in flowshop scheduling problems," Computers and Operations Research, 26, 219-235（1999）.
26.Bellman R. E., Dreyfus E. "Dynamic programming and reliability of multi-component devices," Operations Research, 6, 200-206(1985).
27.Chen, H., Ihlow, J. and Lehmann, C. "A Genetic Algorithm for Flexible Job-Shop Scheduling," Proceeding of the 1999 IEEE International Conference on Robotics and Automation, 1120-1125(1999).
28.Chen, G., The Application of Computer Simulation and Artificial Intelligence Techniques to Woven Fabric Manufacture, Ph.D. diss, Department of Textile Industries , The University of Leeds, England, U. K.,（1995）.
29.Cheng, T. C. E. and Ding, Q. "The complexity of scheduling starting time dependent tasks with release times," Information Processing Letters, 65, 75-79（1998）.
30.Cleveland, G. A. and Smith, S.F. "Using Genetic Algorithms to schedule Flow Shop release," Proceedings of the 3rd International Conference On Genetic Algorithms Applications ,160-169（1989）.
31.Colormi A., Dorigo M., and Maniezzo V., " Distributed optimization by ant colonies, " in Proceedings of the First European Conference on Artificial Life, Varela, F. J. and Bourgine, P. (Eds), MIP Press, Cambridge, MA,134-142(1991).
32.Crauwels, H. A. J., Potts, C.N., Van, O. D. and Van, W. L. N., Branch and bound algorithms for single machine scheduling with batching to minimize the number of late jobs, Report, Faculty of Mathematical Studies, University of Southampton, UK(1999).
33.Croce, F. D., Tadei, R. and Volta, G. "A Genetic Algorithms for the Job Shop Problem," Computers Operations Research, 22, 1, 15-24（1995）.
34.Davis, L. "Applying adaptive algorithms to episatic domains," In Proceedings of International Joint cong. On Artificial Intelligence, 162-164（1985）.
35.Davis, L., Handbook of Genetic Algorithms, New York: Van Nostrand Reinhold, (1991).
36.Falkenauer, E. and Bouffoix, S. " A Genetic Algorithm for Job Shop," Proceedings of the 1991 IEEE International Conference on Robotics and Automation,（1991）.
37.Ferland, J.A., Ichoua, S., Lavoie, A. and Gagne, E. "Scheduling using tabu search methods with intensification and diversification," Computers and Operations Research, 28, 1075-1092（2001）.
38.Goldberg, D. E., Genetic algorithm in search, optimization and machine learning (1989).
39.Gupta, J. N. D. "Single facility scheduling with multiple job classes," European Journal of Operational Research, 33, 42-45(1988).
40.Hane, C. A., Barnhart, C., Johnson, E. L., Matsten, R. E., Nemhauser, G. L.,and Sigismonndi, G. "The fleet assignment problem：solving a large-scale integer program," Mathematical Programming, 70, 211-232（1995）.
41.Haupt, R. "A survey of priority rule-based scheduling, " OR Spektum, 11, 3-16（1989）.
42.Holland, J. H., Adaptation in Natural and Artificial Systems, University of Michigan Pres, Ann Arbor (1975).
43.Holthaus, O. and Rajendran, C. "Efficient dispatching rules for scheduling in a job shop," International Journal of Production Economics, 48,1, 87-105（1997）.
44.Hurink, J., and Keuchel, J. "Local search algorithms for a single-machine scheduling problem with positive and negative time-lags,"Discrete Applied Mathematics, 112, 179-197（2001）.
45.Kim, J. U. and Kim, Y. D. "Simulated annealing and genetic algorithms for scheduling products with multi-level product structure," Computers and Operations Research, 23, 9, 857-868 (1996).
46.Krishnaiyer K. and Cheragh S. H. I, Ant algorithms: Review and future applications, IERC’02, Industrial Engineering Research Conference, Orlando, Florida, USA,（2002）.
47.Kyparisis, G. J. and Koulamas, C. “Flow shop and open shop scheduling with a critical machine and two operations per job, ”European Journal of Operational Research, 127, 1,120-125（2000）.
48.Lawler, E. L., Lenstra, L. K. and Rinnooy, K. A. H. G. "Minimizing Maximum Lateness In A Two-Machine Open Shop," Mathematics of Operations Research ,6, 1,138-158(1981).
49.Moudani, W. E. and Mora, C. F. "A dynamic approach for aircraft assignment and maintenance scheduling by airlines," Journal of Air Transport Management,6, 233-237（2000）.
50.Muratac, T. and Ishibuchi, H. "Performance evaluation of genetic algorithms for flowshop scheduling problems," IEEE International Conference on Robotics and Automation, 1, 812-817（1994）.
51.Murata, T., Ishibuchi, H. and Tanaka, H. " Genetic Algorithm for Flow-Shop Scheduling Problems,"Computers and Industrial Engineering, 30, 4, 1061-1071（1996）.
52.Parpinelli R. S., Lopes, H. S. and Freitas A. A. "Data mining with an ant colony optimization algorithm," IEEE Transactions on Evolutionary Computing, 6, 4（2002）.
53.Pierreval, H. and Mebarki, N. "Dynamic selection of dispatching rules for manufacturing system scheduling," International Journal of Production Research, 35, 6, 1575-1591（1997）.
54.Sakanashi, H., Suzuki, H. and Kakazu, Y. "Filtering-GA: The evolutionary TSP landscape, " Int. Conf. Evolutionary Computer, 1, 390-395 (1995).
55.Sipper, D., Robert, L.and Bulfin, JR., Operation Scheduling, Production Planning, Control and Integration, U.S.A: McGraw Hill Press, 382-456(1997).
56.Stevenson, W. T., Production and Operation Management, 7th ed., Irwin,（2002）.
57.Tamimi, S. A. and Rajan, V. N. " Reduction of total weighted tardiness on uniform machines with sequence dependent setups," 6th Industrial Engineering Research Conference Proceedings, pp. 181-185（1997）.
58.Vitaly A. S. "Tow machine flow shop scheduling problem with no wait in process :Controllable machine speeds," Discrete Applied Mathematics, 59, 1 , 75-86（1995）.
59.Wang, C. S. and Uzsoy, R. "A genetic algorithm to minimize maximum lateness on a batch processing machine," Computers and Operations Research, 29, 1621-1640（2002）.
60.Webster, S. and Azizoglu, M. "Dynamic programming algorithms for scheduling parallel machines with family setup times," Computers and Operations Research, 28, 127-137（2001）.
61.Yang, D. L. and Chern, M. S. "A two-machine flow shop sequencing problem with limited waiting time constraints," Computers and Industrial Engineering , 28, 1,63-70（1994）.