臺灣博碩士論文加值系統

生產排程一直以來都是企業非常重視的問題，因為一個良好的排程方法不僅可以提高生產效率、降低存貨水準與生產成本，而且還能提升市場反應能力與競爭優勢。就理論而言排程問題屬於NP-hard的問題，在求解此類型的問題時，常運用啟發式演算法來求解。然而目前在探討排程問題上，卻只著重在生產過程中資源的分配，忽略生產完成後產品倉儲與運送的限制，可是在實務上有些體積較大的產品就會有倉儲與運送的限制，而使生產排程因倉儲限制影響而導致生產計畫變動。本研究以單機排程為對象，建立有倉儲限制之最佳化排程模式，模式中的目標函數包含倉儲成本、緊急送貨成本以及延遲成本三項，此外並建立產能、交期、倉儲空間以及連續生產限制條件。本研究應用蟻族最佳化(ant colony optimization, ACO) 演算法來求解，並進一步對蟻族最佳化演算法的參數進行分析設定，經所得結果顯示蟻族最佳化求得的排程解有收斂的趨勢。最後，本研究將所得的排程解進行成本分析，結果顯示懲罰成本是決定總成本大小的主要因素。

Scheduling has been one of the major tasks in operational management. It has direct impact on the efficiency and effectiveness of production operations. In order to obtain a better production schedule to improve the performance of daily production operations and to increase the competition of the business organization, numerous academic researchers and industrial participants have devoted tremendous amount of effort in developing scheduling algorithms. Most of the articles assume that there are always enough storage space for raw materials and warehouse space for finished products. But, in food processing industry, the freezer space is always limited. When there is insufficient space in the freezer to store the finished products or raw materials, the company can either lease extra freezers or postpone the production operations, causing higher costs or late delivery. This thesis proposes a single facility optimal scheduling methodology with storage and warehouse constraints. The sum of three type of costs, namely storage, rush delivery and late delivery penalty costs, is minimized by ant colony optimization technique. The constraints encompassed in the model include due-date, warehouse space, continuous production, and so on. The results show the by ant colony optimization search procedure can converge in limited among of trails. It is also showed that the penalty cost dominates the quality of the solution. Additionally, sensitivity analysis of parameters encountered in ant colony optimization is conducted to search a set of good parameter settings.

目錄
摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 VII
表目錄 VIII
1. 緒論 1
1.1 研究動機 1
1.2 研究目的 4
1.3 研究假設 4
1.4 研究流程與架構 6
2. 文獻探討 9
2.1 排程理論 9
2.1.1 排程特性分類 10
2.2 排程問題的解法 12
2.2.1 最佳解法 13
2.2.2 近似解法 15
2.2.3 限制理論 18
2.3 排程機台的型態 21
2.3.1 單製程排程 21
2.3.2 零工式生產 24
2.3.3 流程式生產 25
2.4 蟻族最佳化演算法的簡介 26
2.4.1 原理與演進 27
2.4.2 演算法說明 29
2.5 蟻族最佳化的應用 38
2.5.1 排程問題 38
2.5.2 其他方面的應用 43
3. 研究方法 47
3.1符號定義 47
3.2 模式建構 48
3.2.1 成本項說明 48
3.2.2 限制式說明 51
3.2.3 本研究模式 52
3.3 蟻族最佳化( ACO） 53
3.3.1 演算法以及演算流程圖 53
3.3.2 貪婪法則的應用 57
4. 實證分析 60
4.1 參數設定 60
4.2 範例描述 63
4.3 結果 64
4.3.1 蟻族最佳化分析 64
4.3.2 成本分析 65
4.3.3 倉儲空間分析 68
4.3.4 討論 73
5. 結論與建議 76
5.1 結論 76
5.2 建議 77
參考文獻 79
附錄一 90
附錄二 91
圖目錄
圖1-1 研究流程圖 8
圖2-2 螞蟻覓食行為圖 28
圖2-3 蟻族系統演算法 34
圖2-4 開發與探索 35
圖3-1 演算流程圖 56
圖3-2 生產順序 59
圖4-1 排程結果 65
圖4-2 歷史最佳解的自有倉儲空間與額外倉儲空間比較 72
圖4-3 最終解的自有倉儲空間與額外倉儲空間比較 72
表目錄
表2-1 排程特性之分類 10
表2-2 常見排程之評估標準 11
表2-3 最佳解相關文獻 15
表2-4 常見的優先派工法則 16
表2-5 近似解相關文獻 18
表2-6 單機排程研究彙整表 22
表2-7 平行機排程研究彙整表 24
表2-8 零工式生產排程研究彙整表 25
表2-9 流程式生產排程研究彙整表 26
表2-10 螞蟻系統的演進 29
表2-11 國內蟻族最佳化的研究 42
表2-12 蟻族最佳化的應用 43
表4-1 參數測試值範圍 61
表4-2 的設定 61
表4-3 的設定 62
表4-4 的設定 62
表4-5 的設定 62
表4-6 U的設定 63
表4-7 參數設定 63
表4-8 歷史最佳解與最終解 66
表4-9 倉儲成本分析 67
表4-10 緊急送貨成本分析 67
表4-11 延遲成本分析 68
表4-12 懲罰成本分析 68
表4-13 歷史最佳解的自有倉儲使用狀況 70
表4-14 歷史最佳解的額外倉儲使用狀況 70
表4-15 最終解的自有倉儲使用狀況 71
表4-16 最終解的額外倉儲使用狀況 71
表4-17 原始排程結果 74
表4-18 產品倉儲成本佔原料總價百分比0.02 74
表4-19 產品延遲成本佔原料總價百分比0.02 74
表4-20 緊急送貨成本佔原料總價百分比0.02 75
表4-21 倉儲空間1200 75
表4-22 懲罰係數4倍 75

1. 方志成，「應用蟻群系統於自動化排程之研究」，佛光人文社會學院資訊學系研究所碩士論文（2003）。
2. 江朋南，「蟻族系統在零工型排程問題之應用」，國立台灣科技大學工業管理系研究所碩士論文（2003）。
3. 吳鴻輝和李榮貴，「限制驅導式現場排程與管理技術」，全華科技圖書股份有限公司，2002年3月，二版三刷。
4. 陳夏祥，「蟻族系統求解相依整備時間之單機總延遲問題」，國立台灣科技大學工業管理系研究所碩士論文（2002）。
5. 陳建勛，「蟻拓尋優法為基的擴充式零工生產排程器」，國立臺灣大學工業工程學系研究所碩士論文（2003）。
6. 陳致遠，「非相關平行機台排程及派工之研究」，屏東科技大學工業管理研究所碩士論文（2003）。
7. 許宏賓，「群蟻演算法於開放型排程問題求解模式建構」，大葉大學工業工程學系研究所碩士論文（2003）。
8. 熊鴻鈞，「螞蟻族群演算法於生產排程之應用」，暨南國際大學資訊管理學系研究所碩士論文（2003）。
9. 應國卿，「蟻群系統於排程問題之應用」，國立台灣科技大學工業管
理系研究所博士論文（2003）。
10. Agliari, A., M. Diligenti, and L. Zavanella, “Variable priority dispatching rules: An analytical approach,” International Journal of Production Economics, 41, October, 51-58 (1995).
11. Alidaee, B., and D. Rosa, “Scheduling parallel machines to minimize total weighted and unweighted tardiness,” Computers & Operations Research, 24, August, 775-788 (1997).
12. Amaral, A. V., and C. S. Rigão, “Tabu search for minimizing total tardiness in a job shop,” International Journal of Production Economics, 63, January 15, 131-140 (2000).
13. Asano, M., and H. Ohta, “A heuristic for job shop scheduling to minimize total weighted tardiness,” Computers and Industrial Engineering, 42, April 11, 137-147 (2002).
14. Baptiste, P., L. Peridy, and E. Pinson, “A branch and bound to minimize the number of late jobs on a single machine with release time constraints,” European Journal of Operational Research, 144, January 1, 1-11 (2003).
15. Bauer, A., B. Bullnheimer, R. F. Hartl, and C. Strauss, “An ant colony optimization approach for the single machine total tardiness problem,” In Proceedings of the 1999 Congress on Evolutionary Computation, 1445—1450 (1999).
16. Benyoucef, L., Y. Frein, and B. Penz, “Optimal solution for a two-product dynamic scheduling problem in a just-in-time environment,” International Journal of Production Economics, 74, December, 85-91 (2001).
17. Besten, M., T. Stutzle, and M. Dorigo, “Ant colony optimization for the total weighted tardiness problem,” In Proceedings of the Parallel Problem Solving from Nature Conferenc, (2000).
18. Bilge, Ü., F. Kraç, M. Kurtulan, and P. Pekgün, “A tabu search algorithm for parallel machine total tardiness problem,” Computers and Operations Research, 31, March, 397-414 (2004).
19. Bonabeau, E., G. Theraulaz, J. L. Deneubourg, S. Aron, and S. Camazine, “Self-organization in social insects,” Trends in Ecol. Evol., 12, 188-193 (1997).
20. Botee, H. M., and E. Bonabeau, “Evolving ant colony optimization,” Adv. Complex System, 149-159 (1998).
21. Bouleimen, K., and H. Lecocq, “A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version,” European Journal of Operational Research, 149, September 1, 268-281 (2003).
22. Brucker, P., and S. Knust, “A linear programming and constraint propagation-based lower bound for the RCPSP,” European Journal of Operational Research, 127, December 1, 355-362 (2000).
23. Bullnheimer, B., R. F. Hartl, and C. Strauss, “Applying the ant system to the vehicle routing problem,” Presented at the 2nd Metaheuristic International Conference, (1997).
24. Carlier, J., and E. Néron, “On linear lower bounds for the resource constrained project scheduling problem,” European Journal of Operational Research, 149, September 1, 314-324 (2003).
25. Caro, G. D., and M. Dorigo, “AntNet: A mobile agents approach to adaptive routing,” Technical Report IRIDIA/97-12, Université Libre de Bruxelles, (1997).
26. Chan, W. T., and H. Hu, “An application of genetic algorithms to precast production scheduling,” Computers and Structures, 79, July, 1605-1616 (2001).
27. Chen, Z. L., L. Qing, and T. Guochun, “Single machine scheduling with discretely controllable processing times,” Operations Research Letters, 21, September, 69-76 (1997).
28. Costa, D., and A. Hertz, “Ants Can Colour Graphs,” Journal of the Operational Research Society, 48, 295-305 (1997).
29. Daniel, V., and R. Guide, Jr., “Scheduling with priority dispatching rules and drum-buffer-rope in a recoverable manufacturing system,” International Journal of Production Economics, 53, November 6, 101-116 (1997).
30. Dorigo, M., V. Maniezzo, and A. Colorni, “Positive feedback as a search strategy, ” Technical Report, 91-016 (1991).
31. Dorigo, M., and L. M. Gambardella, “Ant colonies for the travelling salesman problem,” Biosystems, 43, July, 73-81 (1997A).
32. Dorigo, M., and L. M. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, 53-66 (1997B).
33. Dorigo, M., and G. Caro, “The ant colony optimization meta-heuristic,” in New Ideas in Optimization, 11-32 (1999).
34. Gambardella, L. M., and M. Dorigo, “Ant-Q: A reinforcement learning approach to the travelling salesman problem,” In Proc. ML-95. 12th Int. Conf. Machine Learning., 252-260 (1995).
35. Gamila, M. A., and S. Motavalli, “A modeling technique for loading and scheduling problems in FMS,” Robotics and Computer-Integrated Manufacturing, 19, February - April, 45-54 (2003).
36. Goldratt, E. M., and J. Cox, “The Goal — A process of ongoing improvement, ”The North River Press Publishing Corporation, (1992).
37. Gupta, J. N. D., K. Hennig, and F. Werner, “Local search heuristics for two-stage flow shop problems with secondary criterion,” Computers and Operations Research, 29, February, 123-149 (2002).
38. Gutjahr, W. J., “ACO algorithms with guaranteed convergence to the optimal solution,” Information Processing Letters, 82, May 16, 145-153 (2002).
39. Holthaus, O., and C. Rajendran, “Efficient dispatching rules for scheduling in a job shop,” International Journal of Production Economics, 48, January 10, 87-105 (1997).
40. Iyer, S. K., and B. Saxena, “Improved genetic algorithm for the permutation flowshop scheduling problem,” Computers and Operations Research, 31, April, 593-606 (2004).
41. Kher, H. V., “Examination of worker assignment and dispatching rules for managing vital customer priorities in dual resource constrained job shop environments,” Computers & Operations Research, 27, May, 525-537 (2000).
42. Kim, Y. K., K. Park, and J. Ko, “A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling,” Computers and Operations Research, 30, July, 1151-1171 (2003).
43. Krishnaiyer, K., and S. H. Cheraghi, “Ant algorithms: review and future applications,” (2002).
http://fie.engrng.pitt.edu/iie2002/proceedings/ierc/papers/
44. Lee, C. Y., and V. J. Leon, “Machine scheduling with a rate-modifying activity,” European Journal of Operational Research, 128, January 1, 119-128 (2001).
45. Liaw, C. F., “A new branch-and-bound approach for the n/2/flowshop/αF+βCmax flowshop scheduling problem,” Computers & Operations Research, 26, November, 1293-1310 (1999).
46. Liaw, C. F., “An efficient tabu search approach for the two-machine preemptive open shop scheduling problem,” Computers and Operations Research, 30, December, 2081-2095 (2003).
47. Mamalis, A. G., and I. Malagardis, “Determination of due dates in job shop scheduling by simulated annealing,” Computer Integrated Manufacturing Systems, 9, May, 65-72 (1996).
48. Maniezzo, V., A. Colorni, and M. Dorigo, “The ant system applied to the quadratic assignment problem,” Tecnical Report IRIDIA/94-28, (1994).
49. Merkle, D., and M. Middendorf, “Ant colony optimization with the relative pheromone evaluation method,” (2002).
http://citeseer.nj.nec.com/correct/505576
50. Moursli, O., and Y. Pochet, “A branch-and-bound algorithm for the hybrid flowshop,” International Journal of Production Economics, 64, March 1, 113-125 (2000).
51. Pan, Y., “An improved branch and bound algorithm for single machine scheduling with deadlines to minimize total weighted completion time,” Operations Research Letters, 31, November, 492-496 (2003).
52. Park, Y., S. Kim, and Y. H. Lee, “Scheduling jobs on parallel machines applying neural network and heuristic rules,” Computers and Industrial Engineering, 38, January 1, 189-202 (2000).
53. Pei, C. C., “A branch and bound approach for single machine scheduling with earliness and tardiness penalties,” Computers & Mathematics with Applications, 37, May, 133-144 (1999).
54. Rajendran, C., and H. Ziegler, “Scheduling to minimize the sum of weighted flowtime and weighted tardiness of jobs in a flowshop with sequence-dependent setup times,” European Journal of Operational Research, 149, September 16, 513-522 (2003).
55. Sakawa, M., and R. Kubota, “Fuzzy programming for multiobjective job shop scheduling with fuzzy processing time and fuzzy duedate through genetic algorithms,” European Journal of Operational Research, 120, January 16, 393-407 (2000).
56. Schoonderwoerd, R., O. Holland, J. Bruten, and L. Rothkrantz, “Ant-based load balancing in telecommunications networks,” Adaptive Behavior, 169-207 (1997).
57. Sevaux, M., and S. Dauzère-Pérès, “Genetic algorithms to minimize the weighted number of late jobs on a single machine,” European Journal of Operational Research , 151, December 1, 296-306 (2003).
58. Sidney, J. B., C. N. Potts, and C. Sriskandarajah, “A heuristic for scheduling two-machine no-wait flow shops with anticipatory setups,” Operations Research Letters, 26, May, 165-173 (2000).
59. Stützle, T., and H. Hoos, “MAX-MIN ant system,” Future Generation Computer Systems, Journal 16(8), 889-914 (2000).
60. Wan, G., and B. P. C. Yen, “Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties,” European Journal of Operational Research, 142, October 16, 271-281 (2002).
61. Webster, S., and M. Azizoglu, “Dynamic programming algorithms for scheduling parallel machines with family setup times,” Computers and Operations Research, 28, February, 127-137(2001).
62. Yalaoui, F., and C. Chu, “Parallel machine scheduling to minimize total tardiness,” International Journal of Production Economics, 76, April 11, 265-279 (2002).
63. Yang, H., Y. Ye, and J. Zhang, “An approximation algorithm for scheduling two parallel machines with capacity constraints,” Discrete Applied Mathematics, 130, August 23, 449-467 (2003).
64. Ying, K. C., and C. J. Liao, “An ant colony system approach for scheduling problem,” Production planning & control, 14(1), 68-75 (2003).
65. Ying, K. C., and C. J. Liao, “An ant colony system for permutation flow-shop sequencing,” Computers and Operations Research, 31, April, 791-801 (2004).
66. Zamani, M. R., “A high-performance exact method for the resource-constrained project scheduling problem,” Computers and Operations Research, 28, December, 1387-1401 (2001).