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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李展榮
研究生(外文):Zhan-Rong Li
論文名稱:運用基因演算法於降低延遲時間及運輸成本之研究
論文名稱(外文):Genetic Algorithm with Dominance Properties for Production and Transportation Logistics Scheduling
指導教授:潘昭賢潘昭賢引用關係
指導教授(外文):Zhao-Xian Pan
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:工業管理系
學門:商業及管理學門
學類:其他商業及管理學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:42
中文關鍵詞:排程問題總延遲時間凌越特性基因演算法
外文關鍵詞:schedulingtotal weighted tardinessdominance propertiesgenetic algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:131
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文在實務上發現工廠運輸產品於顧客的過程中,分為快捷及普通產品的運送模式。送貨員根據顧客需求進行運輸模式的選擇。我們推導兩種運輸模式的選擇以及證明凌越特性來進行運送產品的排序,目的是可以快速的找到較佳的排列順序,而我們的目標值是使總運輸成本以及總延遲成本最小化。接著,我們將運輸模式選擇的數學模式以及凌越特性兩種結合基因演算法,試圖降低目標值的成本。我們利用各種工作數量的大小以及運輸成本的高低變化來進行測試,實驗結果顯示,結合凌越特性的基因演算法明顯的降低了目標成本,並且可以快速的達到收斂值,對於提升效率有顯著的效果。
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 ABSTRACTS I
ABSTRACTS II
CONTENTS III
TABLE INDEX IV
CHAPTER 1 INTRODUCTION 1
CHAPTER 2 LITERATURE REVIEW 4
CHAPTER 3 NOTATION AND ASSUMPTION 9
3.1 NOTATION 9
3.2 PROBLEM ASSUMPTIONS 10
CHAPTER 4 MINIMIZING THE TOTAL WEIGHTED TARDINESS AND TRANSPORTATION COST 11
4-1. TRANSPORTATION MODE SELECTION 11
4-2.DOMINANCE PROPERTIES 11
CHAPTER 5 IMPLEMENTATION OF GENETIC ALGORITHM 21
5.1 BASIC GENETIC ALGORITHM STRUCTURE 21
5.2 GENETIC ALGORITHM WITH DOMINANCE PROPERTIES 22
5.2.1 Parameter Settings 24
5.2.2 Encoding 25
5.2.3 Initial population 25
5.2.4 Fitness function 27
5.2.5 Crossover 27
5.2.6 Mutation 30
5.2.7 Termination condition 31
CHAPTER 6 EXPERIMENTAL RESULTS 32
6.1 COMPUTATIONAL EXPERIMENTS 32
6.2 CONCLUSIONS AND FUTURE STUDY SUGGESTIONS 38
REFERENCES...........................................................................................................30



TABLE INDEX
Table 4 1. Properties of different schedule conditions 23
Table 5 1. The parameter testing of crossover and mutation 27
Table 5 2. A list of dispatching rules. 29
Table 6-1. The initial heuristic testing 36
Table 6-2. DP, PGA and GADP compared with each other for 25 jobs 37
Table 6-3. Objective values in PGA and GADP for 30, 40, 50 and 100 jobs 38
Table 6-4. The experiment results for the PGA and GADP with k and n 39
Table 6-5. Comparision with PGA and GADP on mean value 39
FIGURE INDEX
Figure 4-1. Transportation mode selection (1) 14
Figure 4-2. Transportation mode selection (2) 15
Figure 4-3. The adjacent interchange method 16
Figure 4-4. Tardy jobs diagram in property 1 17
Figure 4-5. Tardy jobs diagram in property 2 18
Figure 4-6. Tardy jobs diagram in property 3 19
Figure 4-7. Tardy jobs diagram in property 4 20
Figure 4-8. Tardy jobs diagram in property 5 22
Figure 5 1. The flow chart of the genetic algorithm structure 26
Figure 5 2. Two chromosomes for Parent 1 and Parent 2 31
Figure 5 3. Two-point crossover of offspring 1 32
Figure 5 4. Two-point crossover of offspring 2 32
Figure 5 5. Two-point crossover of offspring 3 32
Figure 5 6. Two-point crossover of offspring 4 33
Figure 5 7. Simple Exchange Mutation (Swap mutation) 33
Figure 6-1. Performance comparison of PGA and GADP 40
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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔