請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/42497完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 傅立成 | |
| dc.contributor.author | Hsueh-Chien Cheng | en |
| dc.contributor.author | 鄭學謙 | zh_TW |
| dc.date.accessioned | 2021-06-15T01:14:53Z | - |
| dc.date.available | 2011-08-04 | |
| dc.date.copyright | 2009-08-04 | |
| dc.date.issued | 2009 | |
| dc.date.submitted | 2009-07-28 | |
| dc.identifier.citation | [1] J. H. Blackstone, D. T. Phillips, and G. L. Hogg, “A state-of-the-art survey of
dispatching rules for manufacturing job shop operations,” International Journal of Production Research, vol. 20, no. 1, pp. 27–45, 1982. [2] D. C. Carroll, “Heuristic sequencing of single and multiple component jobs,” Ph.D. dissertation, Massachusetts Institute of Technology, 1965. [3] A. P. J. Vepsalainen and T. E. Morton, “Priority rules for job shops with weighted tardiness costs,” Management Science, vol. 33, no. 8, pp. 1035–1047, 1987. [4] J. H. Chen, L. C. Fu, M. H. Lin, and A. C. Huang, “Petri-net and GA-based approach to modeling, scheduling, andperformance evaluation for wafer fabrication,” IEEE Transactions on Robotics and Automation, vol. 17, no. 5, pp. 619–636, 2001. [5] T. C. Chiang and L. C. Fu, “Multiobjective job shop scheduling using genetic algorithm with cyclic fitness assignment,” in Proceedings of the IEEE Conference on Evolutionary Computation, Vancouver, Canada, July 2006, pp. 3266–3273. [6] H. S. Min and Y. Yih, “Selection of dispatching rules on multiple dispatching decision points in real-time scheduling of a semiconductor wafer fabrication system,” International Journal of Production Research, vol. 41, no. 16, pp. 3921–3941, 2003. [7] J. D. Schaffer, “Multiple objective optimization with vector evaluated genetic algorithms,” in Proceedings of the International Conference on Genetic Algo- rithms, Pittsburgh, PA, USA, July 1985, pp. 93–100. [8] D. F. Jones, S. K. Mirrazavi, and M. Tamiz, “Multi-objective meta-heuristics: An overview of the current state-of-the-art,” European Journal of Operational Research, vol. 137, no. 1, pp. 1–9, 2002. [9] C. M. Fonseca and P. J. Fleming, “Genetic algorithms for multiobjective optimization: Formulation, discussion and generalization,” in Proceedings of the International Conference on Genetic Algorithms, Urbana-Champaign, IL, USA, June 1993, pp. 416–423. [10] J. Horn, N. Nafpliotis, and D. E. Goldberg, “A niched Pareto genetic algorithm for multiobjective optimization,” in Proceedings of the IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intel- ligence, Orlando, FL, USA, June 1994, pp. 82–87. [11] J. D. Knowles and D.W. Corne, “Approximating the nondominated front using the Pareto archived evolution strategy,” Evolutionary Computation, vol. 8, pp. 149–172, 2000. [12] D.W. Corne, N. R. Jerram, J. D. Knowles, and M. J. Oates, “PESA-II: Regionbased selection in evolutionary multiobjective optimization,” in Proceedings of the Genetic and Evolutionary Computation Conference, San Francisco, CA, USA, July 2001, pp. 283–290. [13] E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm,” Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, Tech. Rep. 103, 2001. [14] K. C. Tan, T. H. Lee, and E. F. Khor, “Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization,” IEEE Transactions on Evolutionary Computation, vol. 5, no. 6, pp. 565–588, 2001. [15] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, pp. 182–197, 2002. [16] A. Toffolo and E. Benini, “Genetic diversity as an objective in multi-objective evolutionary algorithms,” Evolutionary Computation, vol. 11, no. 2, pp. 151– 167, 2003. [17] R. Graham, E. Lawler, J. Lenstra, and A. R. Kan, “Optimization and approximation in deterministic sequencing and scheduling: a survey,” Annals of Discrete Mathematics, vol. 5, no. 2, pp. 287–326, 1979. [18] H. Ishibuchi and T. Murata, “A multi-objective genetic local search algorithm and itsapplication to flowshop scheduling,” IEEE Transactions on Systems, Man and Cybernetics, Part C, vol. 28, no. 3, pp. 392–403, 1998. [19] H. Ishibuchi, T. Yoshida, and T. Murata, “Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling,” IEEE Transactions on Evolutionary Computation, vol. 7, no. 2, pp. 204–223, 2003. [20] J. E. C. Arroyo and V. A. Armentano, “Genetic local search for multi-objective flowshop scheduling problems,” European Journal of Operational Research, vol. 167, no. 3, pp. 717–738, 2005. [21] T. Pasupathy, C. Rajendran, and R. K. Suresh, “A multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs,” The International Journal of Advanced Manufacturing Technol- ogy, vol. 27, no. 7, pp. 804–815, 2006. [22] D. Lei and Z. Wu, “Crowding-measure-based multiobjective evolutionary algorithm for job shop scheduling,” The International Journal of Advanced Manu- facturing Technology, vol. 30, no. 1, pp. 112–117, 2006. [23] B. Giffler and G. L. Thompson, “Algorithms for solving production scheduling problems,” Operations Research, vol. 8, no. 4, pp. 487–503, 1960. [24] P. C. Chang, J. C. Hsieh, and C. Y.Wang, “Adaptive multi-objective genetic algorithms for scheduling of drilling operation in printed circuit board industry,” Applied Soft Computing, vol. 7, no. 3, pp. 800–806, 2007. [25] I. Kacem, S. Hammadi, and P. Borne, “Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems,” IEEE Transactions on Systems, Man and Cybernetics, Part C, vol. 32, no. 1, pp. 1–13, 2002. [26] W. J. Xia and Z. M. Wu, “An effective hybrid optimization approach for multiobjective flexible job-shop scheduling problems,” Computers & Industrial En- gineering, vol. 48, no. 2, pp. 409–425, 2005. [27] J. Gao, L. Y. Sun, and M. Gen, “A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems,” Computers & Operations Research, vol. 35, no. 9, pp. 2892–2907, 2008. [28] J. C. Tay and N. B. Ho, “Evolving dispatching rules using genetic programming for solving multi-objective flexible job-shop problems,” Computers & Industrial Engineering, vol. 54, no. 3, pp. 453–473, 2008. [29] J. Adams, E. Balas, and D. Zawack, “The shifting bottleneck procedure for job shop scheduling,” Management Science, vol. 34, no. 3, pp. 391–401, 1988. [30] S. Dauzere-Peres and J. B. Lasserre, “A modified shifting bottleneck procedure for job-shop scheduling,” International Journal of Production Research, vol. 31, no. 4, pp. 923–932, 1993. [31] E. Balas, J. K. Lenstra, and A. Vazacopoulos, “The one-machine problem with delayed precedence constraints and its use in job-shop scheduling,” Management Science, vol. 41, no. 1, pp. 94–109, 1995. [32] U. Dorndorf and E. Pesch, “Evolution based learning in a job-shop scheduling environment,” Computers & Operations Research, vol. 22, no. 1, pp. 25–40, 1995. [33] H. Aytug, K. Kempf, and R. Uzsoy, “Measures of subproblem criticality in decomposition algorithms for shop scheduling,” International Journal of Pro- duction Research, vol. 41, no. 5, pp. 865–882, 2003. [34] V. Osisek and H. Aytug, “Discovering subproblem prioritization rules for shifting bottleneck algorithms,” Journal of Intelligent Manufacturing, vol. 15, no. 1, pp. 55–67, 2004. [35] J. Carlier, “The one-machine sequencing problem,” European Journal of Oper- ational Research, vol. 11, no. 1, pp. 42–47, 1982. [36] L. M¨onch, R. Schabacker, D. Pabst, and J. W. Fowler, “Genetic algorithmbased subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops,” European Journal of Operational Research, vol. 177, no. 3, pp. 2100–2118, 2007. [37] P. Ivens and M. Lambrecht, “Extending the shifting bottleneck procedure to real-life applications,” European Journal of Operational Research, vol. 90, no. 2, pp. 252–268, 1996. [38] E. Demirkol, S. Mehta, and R. Uzsoy, “A computational study of shifting bottleneck procedures for shop scheduling problems,” Journal of Heuristics, vol. 3, no. 2, pp. 111–137, 1997. [39] M. Pinedo and M. Singer, “A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop,” Naval Research Logistics, vol. 46, no. 1, pp. 1–17, 1999. [40] S. J. Mason, J. W. Fowler, and W. M. Carlyle, “A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops,” Journal of Scheduling, vol. 5, no. 3, pp. 247–262, 2002. [41] K. Sourirajan and R. Uzsoy, “Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication,” Journal of Scheduling, vol. 10, no. 1, pp. 41–65, 2007. [42] M. E. Pfund, H. Balasubramanian, J. W. Fowler, S. J. Mason, and O. Rose, “A multi-criteria approach for scheduling semiconductor wafer fabrication facilities,” Journal of Scheduling, vol. 11, no. 1, pp. 29–47, 2008. [43] A. Upasani and R. Uzsoy, “Integrating a decomposition procedure with problem reduction for factory scheduling with disruptions: a simulation study,” International Journal of Production Research, vol. 46, no. 21, pp. 5883–5905, 2008. [44] C. A. C. Coello, G. B. Lamont, and D. A. Van Veldhuizen, Evolutionary Algo- rithms for Solving Multi-Objective Problems. Springer-Verlag New York Inc, 2007. [45] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Longman, 1989. [46] H. Beyer and H. Schwefel, “Evolution strategies–A comprehensive introduction,” Natural Computing, vol. 1, no. 1, pp. 3–52, 2002. [47] M. Dorigo and T. St¨utzle, Ant colony optimization. The MIT press, 2004. [48] J. Kennedy and R. C. Eberhart, Swarm Intelligence. Morgan Kaufmann, 2001. [49] M. Mitchell, An Introduction to Genetic Algorithms. Bradford Books, 1996. [50] J. Holland, Adaptation in Natural and Artificial Systems. The MIT Press, 1975. [51] L. Booker, “Intelligent behavior as an adaptation to the task environment,” Ph.D. dissertation, University of Michigan Ann Arbor, 1982. [52] J. Baker, “Reducing bias and inefficiency in the selection algorithm,” in Pro- ceedings of the International Conference on Genetic Algorithms and Their Ap- plication, Cambridge, MA, USA, July 1987, pp. 14–21. [53] I. M. Ovacik and R. Uzsoy, Decomposition Methods for Complex Factory Scheduling Problems. Kluwer Academic Publishing, 1997. [54] H. Fisher and G. L. Thompson, “Probabilistic learning combinations of local job-shop scheduling rules,” Industrial Scheduling, pp. 225–251, 1963. [55] D. Applegate and W. Cook, “A computational study of the job-shop scheduling problem,” ORSA Journal on Computing, no. 3, pp. 149–156, 1991. [56] S. Lawrence, “Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement),” Graduate School of Industrial Administration, Carnegie-Mellon University, Tech. Rep., 1984. [57] J. W. Barnes and J. B. Chambers, “Flexible job shop scheduling by tabu search,” The University of Texas at Austin, Tech. Rep. ORP96-09, 1996. [58] R. H. Myers and D. C. Montgomery, Response Surface Methodology. New York: Wiley, 1995. [59] J. Knowles, L. Thiele, and E. Zitzler, “A tutorial on the performance assessment of stochastic multiobjective optimizers,” Computer Engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH), Zurich, Switzerland, Tech. Rep. 214, 2005. [60] E. Zitzler and L. Thiele, “Multiobjective optimization using evolutionary algorithms - A comparative case study,” in Proceedings of the International Con- ference on Parallel Problem Solving from Nature, Amsterdam, Netherlands, September 1998, pp. 292–304. [61] E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. Grunert da Fonseca, “Performance assessment of multiobjective optimizers: An analysis and review,” IEEE Transactions on Evolutionary Computation, vol. 7, no. 2, pp. 117–132, 2003. [62] W. J. Conover, Pratical Nonparametric Statistics. John Wiley and Sons, 1999. [63] H. C. Cheng, T. C. Chiang, and L. C. Fu, “Multiobjective job shop scheduling using memetic algorithm and shifting bottleneck procedure,” in Proceedings of IEEE Symposium on Computational Intelligence in Scheduling, Nashville, TN, USA, April 2009, pp. 15–21. [64] B. Roy and B. Sussman, “Les probl`emes d’ordonnancement avec constraintes disjonctives,” SEMA, Paris, Tech. Rep. 9, 1964. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/42497 | - |
| dc.description.abstract | 這篇論文中研究如何解決多目標排程問題，由於基於週期時間(cycle time)與交期(due date)的目標時常互相抵觸，因此如何找出維持兩者間的平衡之排程對製造系統而 言是很重要的。我們提出了一個兩層的多目標瀰集演化演算法(memetic algorithm)及移動瓶頸法(shifting bottleneck procedure)來解決多目標排程問題，第一層使用瀰集演化演算法來搜尋初始排程，接著第二層使用移動瓶頸法中的重新最佳化程序，在我們提出的第一層演算法中使用的元件可以維持探索及利用間的平衡，在第二層中，重新最佳化程序使用了基於瀰集演化演算法的子問題解決法。透過在公開的測試資料上與一個最近的文獻比較的實驗結果驗證我們提出的方法是有效的，優秀的實驗結果指出我們提出的方法有實際應用到製造系統的潛力。 | zh_TW |
| dc.description.abstract | In this thesis, a multiobjective scheduling problem is addressed. Since cycle time-based objectives and due date-based objectives frequently contradicts with each other, a well-balanced schedule is important for manufacturing systems. A two-stage algorithm, multiobjective memetic algorithm and shifting bottleneck, MOMASB, is proposed to solve multiobjective scheduling problem. The first stage is a memetic algorithm, RMA, to generate initial schedules followed by the second stage, which is a re-optimization procedure inspired by SB. The components of the proposed RMA are carefully designed to maintain a balance between exploration and exploitation. In the second stage, the re-optimization applys a memetic algorithm-based subproblem, SSPMA. Experimental results compared with a recent approach in the literature show the effectiveness of the proposed MOMASB. The promising results indicate the potential of MOMASB to be applied to practical use. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T01:14:53Z (GMT). No. of bitstreams: 1 ntu-98-R96922066-1.pdf: 742352 bytes, checksum: 5f8439e183de0371033d9e631a055878 (MD5) Previous issue date: 2009 | en |
| dc.description.tableofcontents | 1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Rule-based Dispatching . . . . . . . . . . . . . . . . . . . . . . 3 1.2.2 Multiobjective Evolutionary Algorithm . . . . . . . . . . . . . 3 1.2.3 Multiobjective Evolutionary Scheduling . . . . . . . . . . . . . 5 1.2.4 Shifting Bottleneck Procedure . . . . . . . . . . . . . . . . . . 6 1.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Preliminary 9 2.1 Multiobjective Optimization . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.1 Multiobjective Optimization Problems (MOPs) . . . . . . . . 9 2.1.2 Existing Approaches to MOPs . . . . . . . . . . . . . . . . . . 10 2.2 Evolutionary Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.2 Multiobjective Evolutionary Algorithm . . . . . . . . . . . . . 17 2.3 Multiobjective Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Shifting Bottleneck Procedure . . . . . . . . . . . . . . . . . . . . . . 21 3 Multiobjective Memetic Algorithm and Shifting Bottleneck Proce- dure (MOMASB) for Multiobjective Scheduling 23 3.1 Overview of MOMASB . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 First Stage: Initial Schedule Generation . . . . . . . . . . . . . . . . 25 3.2.1 Chromosome Encoding and Decoding . . . . . . . . . . . . . . 25 3.2.2 Genetic Algorithm Components . . . . . . . . . . . . . . . . . 28 3.2.3 Local Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2.4 Stopping Criterion . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3 Second Stage: Schedule Re-optimization . . . . . . . . . . . . . . . . 35 3.3.1 Bottleneck Selection . . . . . . . . . . . . . . . . . . . . . . . 37 3.3.2 Subproblem Formulation . . . . . . . . . . . . . . . . . . . . . 37 3.3.3 Memetic Algorithm-based Subproblem Solution Procedure . . 40 3.3.4 Best Schedule Selection . . . . . . . . . . . . . . . . . . . . . . 45 3.3.5 Stopping Criterion . . . . . . . . . . . . . . . . . . . . . . . . 46 4 Experiments and Results 47 4.1 Description of Problem Addressed . . . . . . . . . . . . . . . . . . . . 47 4.1.1 Problem description . . . . . . . . . . . . . . . . . . . . . . . 47 4.1.2 Concerned objectives . . . . . . . . . . . . . . . . . . . . . . . 48 4.2 Benchmark Instances and Algorithm . . . . . . . . . . . . . . . . . . 48 4.2.1 Benchmark Instances . . . . . . . . . . . . . . . . . . . . . . . 48 4.2.2 Benchmark Algorithm . . . . . . . . . . . . . . . . . . . . . . 49 4.3 Parameter Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.3.1 The Proposed MOMASB . . . . . . . . . . . . . . . . . . . . . 50 4.3.2 Benchmark Algorithm . . . . . . . . . . . . . . . . . . . . . . 51 4.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.4.1 Performance Assessment . . . . . . . . . . . . . . . . . . . . . 52 4.4.2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . 53 4.4.3 Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5 Conclusions and Future Work 64 Appendix A | | Notation 66 Appendix B Disjunctive Graph Representation 67 Reference 69 | |
| dc.language.iso | en | |
| dc.subject | 瓶頸飄移法 | zh_TW |
| dc.subject | 生產排程 | zh_TW |
| dc.subject | 多目標最佳化 | zh_TW |
| dc.subject | 演化式演算法 | zh_TW |
| dc.subject | Production scheduling | en |
| dc.subject | Shifting bottleneck | en |
| dc.subject | Evolutionary algorithm | en |
| dc.subject | Multiobjective optimization | en |
| dc.title | 使用多目標演化演算法及移動瓶頸法之多目標排程 | zh_TW |
| dc.title | Multiobjective Scheduling by Multiobjective Evolutionary Algorithm and Shifting Bottleneck Procedure | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 97-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳正剛,張時中,曹承礎,蔣宗哲 | |
| dc.subject.keyword | 生產排程,多目標最佳化,演化式演算法,瓶頸飄移法, | zh_TW |
| dc.subject.keyword | Production scheduling,Multiobjective optimization,Evolutionary algorithm,Shifting bottleneck, | en |
| dc.relation.page | 77 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2009-07-28 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf 未授權公開取用 | 724.95 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。