運用基因演算法於降低延遲時間及運輸成本之研究｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	李展榮 Zhan-Rong Li
論文名稱：	運用基因演算法於降低延遲時間及運輸成本之研究 Genetic Algorithm with Dominance Properties for Production and Transportation Logistics Scheduling
指導教授：	潘昭賢 Chao-Hsien Pan
口試委員:	蕭裕正 Yu-Zheng Xiao 許總欣 Zong-Xin Xu
學位類別：	碩士 Master
系所名稱：	管理學院 - 工業管理系 Department of Industrial Management
論文出版年：	2008
畢業學年度：	96
語文別：	英文
論文頁數：	42
中文關鍵詞：	排程問題、總延遲時間、凌越特性、基因演算法
外文關鍵詞：	scheduling, total weighted tardiness, dominance properties, genetic algorithm
相關次數：	點閱：214 下載：2
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

本論文在實務上發現工廠運輸產品於顧客的過程中，分為快捷及普通產品的運送模式。送貨員根據顧客需求進行運輸模式的選擇。我們推導兩種運輸模式的選擇以及證明凌越特性來進行運送產品的排序，目的是可以快速的找到較佳的排列順序，而我們的目標值是使總運輸成本以及總延遲成本最小化。接著，我們將運輸模式選擇的數學模式以及凌越特性兩種結合基因演算法，試圖降低目標值的成本。我們利用各種工作數量的大小以及運輸成本的高低變化來進行測試，實驗結果顯示，結合凌越特性的基因演算法明顯的降低了目標成本，並且可以快速的達到收斂值，對於提升效率有顯著的效果。

This paper considers total weighted tardiness problem arising in logistics systems in which two different transportation modes are available at the stage of product delivery. The mode with the shorter transportation time charges a higher cost. Each job ordered by the customer is first processed in the manufacturing facility and then transported to the customer.
We know that kind of problem are NP-hard. The aim of this study is to minimizing the total weighted tardiness cost and the sum of the total transportation cost by using genetic algorithm (GA). Meanwhile, we provide dominance properties of the optimal schedule are developed based on the switching of two adjacent jobs i and j. Therefore, these dominance properties are further combined with the genetic algorithm and we call it genetic algorithm with dominance properties (GADP). The initial populations of schedules in the genetic algorithm are generated using these dominance properties. GA can further improve the performance of these initial solutions after the evolving procedures. The performances of GADP have been compared with pure-GA with some instances. Computational results show that our GADP algorithm is more efficiency and effectiveness than GA.

CHINESE ABSTRACTSI
ABSTRACTSII
CONTENTSIII
TABLE INDEXIV
CHAPTER 1 INTRODUCTION1
CHAPTER 2 LITERATURE REVIEW4
CHAPTER 3 NOTATION AND ASSUMPTION9
3.1 NOTATION9
3.2 PROBLEM ASSUMPTIONS10
CHAPTER 4 MINIMIZING THE TOTAL WEIGHTED TARDINESS AND TRANSPORTATION COST11
4-1. TRANSPORTATION MODE SELECTION 11
4-2.DOMINANCE PROPERTIES11
CHAPTER 5 IMPLEMENTATION OF GENETIC ALGORITHM21
5.1 BASIC GENETIC ALGORITHM STRUCTURE21
5.2 GENETIC ALGORITHM WITH DOMINANCE PROPERTIES22
5.2.1 Parameter Settings24
5.2.2 Encoding25
5.2.3 Initial population25
5.2.4 Fitness function27
5.2.5 Crossover27
5.2.6 Mutation30
5.2.7 Termination condition31
CHAPTER 6 EXPERIMENTAL RESULTS32
6.1 COMPUTATIONAL EXPERIMENTS32
6.2 CONCLUSIONS AND FUTURE STUDY SUGGESTIONS38
REFERENCES...........................................................................................................30



TABLE INDEX
Table 4 1. Properties of different schedule conditions23
Table 5 1. The parameter testing of crossover and mutation27
Table 5 2. A list of dispatching rules.29
Table 6-1. The initial heuristic testing36
Table 6-2. DP, PGA and GADP compared with each other for 25 jobs37
Table 6-3. Objective values in PGA and GADP for 30, 40, 50 and 100 jobs38
Table 6-4. The experiment results for the PGA and GADP with k and n39
Table 6-5. Comparision with PGA and GADP on mean value39
FIGURE INDEX
Figure 4-1. Transportation mode selection (1)14
Figure 4-2. Transportation mode selection (2)15
Figure 4-3. The adjacent interchange method16
Figure 4-4. Tardy jobs diagram in property 117
Figure 4-5. Tardy jobs diagram in property 218
Figure 4-6. Tardy jobs diagram in property 319
Figure 4-7. Tardy jobs diagram in property 420
Figure 4-8. Tardy jobs diagram in property 522
Figure 5 1. The flow chart of the genetic algorithm structure26
Figure 5 2. Two chromosomes for Parent 1 and Parent 231
Figure 5 3. Two-point crossover of offspring 132
Figure 5 4. Two-point crossover of offspring 232
Figure 5 5. Two-point crossover of offspring 332
Figure 5 6. Two-point crossover of offspring 433
Figure 5 7. Simple Exchange Mutation (Swap mutation)33
Figure 6-1. Performance comparison of PGA and GADP40

                                

1.Wang, H., Lee, C.-Y., Production and Transport Logistics Scheduling with Two Transport Mode Choices, Naval Research Logistics 52 (2005)pp.796-809
2.Lawler, E. L., A pseudo-polynomial algorithm for sequencing jobs to minimize total tardiness, Ann. Discrete Mathematics 1(1977) pp.331-342
3.Szwarc, W., Croce, F.D., Grosso, A., Solution Of the single machine total tardiness problem, Journal of Scheduling 2 (1999), pp.55-71
4.Potts, C., Van Wassenhove, L., A branch and bound algorithm for the total weighted tardiness problem, Operations Research 33(1985), pp.363-377.
5.Emmons, H., One-machine sequencing to minimize certain functions of job tardiness, Operations Research 17 (1969), pp. 702-715.
6.Lee, C.-Y., Chen, Z.-L., Machine scheduling with transportation considerations, Journal of Scheduling 4 (2001), pp. 3-24.
7.Zhong, W., Dosa, G., Tan, Z., On the machine scheduling problem with job delivery coordination, European Journal of Operational Research 182 (2007), pp. 1057-1072.
8.Tain, Z.-J., Ng, C.-T., Cheng, T.C.-E., On the single machine total tardiness problem, European Journal of Operational Research 165 (2005), pp. 843-846.
9.Cheng, T.C.E, Ng, C.T., Yuan, J.J., Liu, Z.H., Single machine scheduling to minimize total weighted tardiness, European Journal of Operational Research 165 (2005), pp.423-443.
10.Chang, Y.-C. and Lee, C.-Y., Machine scheduling with job delivery coordination, European Journal of Operational Research 158 (2004), pp.470-487.
11.Potts, C.-N and Wassenhove, L.N.-V, A Branch and Bound Algorithm for the Total Weighted Tardiness Problem, Operations Research 33 (1985), pp.3302-0363.
12.Fisher, M.L., The Lagrangian Relaxation Method for Solving Integer Programming Problems, Management Science 50 (2004), pp.1861-1871.
13.Hariri, A.M.A. and Potts, C.N., An algorithm for single machine sequencing with release dates to minimize total weighted completion time, Discrete Applied Mathematics 5 (1983), pp.99-109.
14.Rinnooy Kan, A.H.G., Lageweg, B.J., and Lenstra, J.L, Minimizing total costs in one machine scheduling, Operations Research 23(1975), pp. 908-927.
15.Tanaka, S., Sasaki, T., Araki, M., A branch-and-bound algorithm for the single-machine weighted earliness-tardiness scheduling problem with job independent weights , IEEE International Conference on Systems, Man and Cybernetics 2 (2003), pp. 1571-1577.
16.Liaw, C.F., A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem, Computers & Operations Research 26 (1999), pp.679-693.
17.Chang, P.C., A branch and bound approach for single machine scheduling with earliness and tardiness penalties, Computers and Mathematics with Applications 37 (1999), pp.133-144.
18.Du, J., Leung, J.Y.-T., Minimizing total tardiness on one machine is NP-HARD*, Mathematics of Operations Research 15 (1990), pp. 2277-2292.
19.Szwarc, W., Mukhopadhyay, S.K., Decomposition of the single machine total tardiness problem, Operations Research 19 (1996), pp.243-250.
20.Lee, C.Y., Chen, Z.L., Machine scheduling with transportation considerations, Journal of Scheduling 4 (2001), pp.3-24.
21.Mazdeh, M.M., Sarhadi, M., Hindi, K.S., A branch-and-bound algorithm for single-machine scheduling with batch delivery minimizing flow times and delivery costs, European Journal of Operational Research 183 (2007), pp.74-86.
22.Koulamas, C., Single-machine scheduling with time windows and earliness/tardiness penalties, European Journal of Operational Research 91 (1996), pp.190-202.
23.Potts, C.N., Van Wassenhove, I.N., A decomposition algorithms for the single machine total tardiness problem, Operations Research Letters 1(1982), pp.177-181.
24.Szwarc, W., Della Croce, F., Grosso, A., Solution of the single machine total tardiness problem, Journal of Scheduling 2 (1999), pp.55-71.
25.Koulamas, C., Total tardiness problem: review and extentions, Operations Research 42 (1994), pp.1025-1041.
26.Yang, Q.W., Jiang, J.P., Chen, G., How to select optimal control parameters for genetic algorithms, IEEE International Symposium on Industrial Electronics 1 (2000), pp. 37-41
27.Cochran, J.K., Horng, S.M., Fowler, J.W., A multi-population genetic algorithm to solve multi-objective scheduling problem for parallel machines, Computers and Operations Research 30 (7), pp.1087-1102.
28.Murata, T., Ishibuchi, H., Tanaka, H., Multi-objective genetic algorithm and its applications to flowshop scheduling, Computers and Industrial Engineering 30 (4), pp. 957-968.
29.Madureira, Ana Maria, Meta-heuristics for the single-machine scheduling total weighted tardiness problem, IEEE International Symposium on Assembly and Task Planning (1999), pp. 405-410.
30.Yang, Y., Kreipl, S., Pinedo, M., Heuristics for minimizing total weighted tardiness in flexible flow shops, Journal of Scheduling 3 (2000), pp. 89-108.
31.Lin, S.-W., Ying, K.-C., Solving single-machine total weighted tardiness problems with sequence-dependent setup times by meta-heuristics, International Journal of Advanced Manufacturing Technology 34 (2007), pp. 1183-1190.
32.Maheswaran, R., Ponnambalam, S.G., Aravindan, C., A meta-heuristic approach to single machine scheduling problems, International Journal of Advanced Manufacturing Technology 25 (2005), pp. 772-776.
33.Chen, S.-S., Chang, P.-C., Hsiung, S.-M., Fan, C.-Y., A genetic algorithm with dominance properties for single machine scheduling problems, IEEE Symposium on Computational Intelligence in Scheduling, CI-Sched (2007), art. no. 4218603, pp. 98-104.
34.Chang, P.C., Chen, S.H., Mani, V., A hybrid genetic algorithm with dominance properties for single machine scheduling with dependent penalties, Applied Mathematical Modelling in press, (2008).
35.Valente, J.M.S., Improving the performance of the ATC dispatch rule by using workload data to determine the lookahead parameter value, International Journal of Production Economics 106 (2007), pp. 563-573.
36.Jayamohan, M.S., Rajendran, C., New dispatching rules for shop scheduling: A step forward, International Journal of Production Research 38 (2000), pp. 563-586.
37.Sun, X., Noble, J.S., Klein, C.M., Single-machine scheduling with sequence dependent setup to minimize total weighted squared tardiness, IIE Transactions (Institute of Industrial Engineers) 31 (1999), pp. 113-124.
38.Balasubramanian, H., Monch, L., Fowler, J., Pfund, M., Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness, International Journal of Production Research 42 (2004), pp. 1621-1638.
39.Zhou, H., Cheung, W., Leung, L.C., Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm, European Journal of Operational Research in Press (2008).
40.Franca, P.M., Mendes, A., Moscato, P., A memetic algorithm for the total tardiness single machine scheduling problem, European Journal of Operational Research 132 (2001), pp. 224-242.
41.White, D.J,. Multiple objective optimization with vector evaluated genetic algorithms, European Journal of Operational Research 19 (1985), pp. 82-90
42.Holland, J.H., Adaptation in Natural and Artificial Systems. Ann Arbor, MJ: Univ. Michigan Press, 1975.
43.Lee, Y.H., A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Transactions (Institute of Industrial Engineers) 29 (1997), pp. 45-52.

全文公開日期 2013/06/05 (校內網路)
全文公開日期本全文未授權公開 (校外網路)
全文公開日期本全文未授權公開 (國家圖書館：臺灣博碩士論文系統)

簡易檢索 / 詳目顯示

相關論文