臺灣博碩士論文加值系統

汽車零組件製造為一多樣少量製造型態，在生產過程中常遇到許多不確定因素，像是當機等，此種不確定因素的發生將會導致原生產排程變成不可行，在實務上，現場人員多用簡單派工法則進行排程，但排程績效通常略差(例如：較長的完工時間等)且不包含不確定因素，因此本研究將著重在多目標隨機排程，其中包含三個隨機因子，當機、修復時間及整備時間。本研究將發展兩個隨機最佳化技術，其中目標為最小化最大完工時間(Makespan)及總加權提早及延遲時間(Total Weighted Earliness and Tardiness，TWET)，以其為目標下發展隨機數學規劃模型及以抽樣為基底之多目標基因演算法(Sampling-based NSGA-II，SNSGA-II)，在小規模問題上本研究將會利用隨機數學規劃模型提供最佳解以驗證SNSGA-II的求解品質。最後，本研究將利用台灣汽車零組件製造商進行實證分析，探討瓶頸站高週波熱處理(high-frequency induction hardening)工作站之生產排程，透過實證與公司現行排程方式：最早到期日派工法則(Earliest Due Date，EDD)比較，實證研究結果發現所提出的SNSGA-II演算法於makespan改善至少22%，TWET改善至少1.4%。

Auto parts manufacturing system is characterized by a high variety of products in small volume and involves several uncertain factors such as machine failure. These characteristics and unexpected events cause the difficulties in production scheduling. This study focuses on addressing the multi-objective job shop scheduling (MOJSP) with three random events regarding machine failure, repair time, and setup time, in auto parts manufacturer. In practice, we usually solve the JSP based on heuristic or simple dispatching rules, and obtain an inconsistent scheduling even with poor performance (i.e. longer production cycle time). This study develops two stochastic scheduling techniques considering four objectives mean and variance of makespan and total weighted earliness and tardiness (TWET), respectively. The stochastic programming is developed for ensuring optimal solution in the small-scale problem and the sampling-based non-dominated genetic algorithm II (SNSGA-II) is proposed to ensure an approximate optimal solution and release computational burden in the large-scale problem. An empirical study of one auto parts manufacturer in Taiwan was conducted to validate the proposed techniques. The results show that SNSGA-II benefits the scheduling with at least 22% improvement in makespan and 1.4% in TWET while comparing to the current dispatching method.

摘要 i
Abstract ii
誌謝 vii
表目錄 xi
圖目錄 xii
符號 xiii
1. 緒論 1
1.1 研究背景 1
1.2 研究動機 3
1.3 研究目的 5
1.4 研究流程 5
2. 文獻探討 6
2.1 排程問題分類 6
2.2 排程績效衡量指標 8
2.3 排程問題的研究方法 9
2.4 多目標方法論 12
2.5 隨機數學規劃模型 15
2.6 小結 17
3. 隨機規劃 21
3.1 研究假設 23
3.2 隨機規劃模型 24
3.3 隨機規劃模型效果測試 26
3.3.1 數學規劃可行性測試 26
3.3.2 隨機規劃數值分析 28
4. 抽樣為基底之非凌越排序基因演算法 32
4.1 非凌越排序基因演算法 32
4.2 以抽樣為基底之非凌越排序基因演算法 40
4.2.1 抽樣方法 40
4.3 SNSGA-II效果測試 45
4.3.1 SNSGA-II可行性測試 45
4.3.2 SNSGA-II隨機模型數值分析 45
5. 實證研究 48
5.1 案例公司背景介紹 48
5.2 產業特性及定義問題 51
5.3 公司現行做法 52
5.4 SNSGA-II實證 53
6. 結論與建議 55
6.1 結論與建議 55
6.2 未來研究 56
參考文獻 57

商業週刊2005年千大製造業排名，民94，Retrieved September 30, 2015, Available:http://bw.businessweekly.com.tw/event/2006/1000/?cid=2＆type=1
經濟部統計處，民104，Available: http://www.moea.gov.tw/MNS/dos/home/Home.aspx
Anglani, A., Grieco, A., Guerriero, E., and Musmanno, R., 2005, Robust scheduling of parallel machines with sequence-dependent set-up costs, European Journal of Operational Research, 161 (3), 704-720.
Aytug, H., Lawley, M.A., McKay, K., Mohan, S., and Uzsoy, R., 2005, Executing production schedules in the face of uncertainties: A review and some future directions, European Journal of Operational Research, 161 (1), 86-110.
Birge, J.R., 1982, The value of the stochastic solution in stochastic linear programs with fixed recourse, Mathematical Programming, 24 (1), 314-325.
Birge, J. R., and Louveaux, F., 2011. Introduction to Stochastic Programming. 2nd eds., Springer Verlag, New York.
Bonfill, A., Espuña, A., and Puigjaner, L., 2005, Addressing robustness in scheduling batch processes with uncertain operation times, Industrial ＆ Engineering Chemistry Research, 44 (5), 1524-1534.
Cheng, R., Gen, M., and Tsujimura, Y., 1996, A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation, Computers ＆ Industrial Engineering, 30 (4), 983-997.
Cheng, R., Gen, M., and Tsujimura, Y., 1999, A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies, Computers ＆ Industrial Engineering, 36 (2), 343-364.
Chien, C.-F. and Chen, C.-H., 2007, A novel timetabling algorithm for a furnace process for semiconductor fabrication with constrained waiting and frequency-based setups, OR Spectrum, 29 (3), 391-419.
CODeM, Retrieved September 30, 2015, Available: http://codem.group.shef.ac.uk/index.php/ga-toolbox
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T., 2002, A fast and elitist multiobjective genetic algorithm: NSGA-II, Evolutionary Computation, IEEE Transactions on, 6 (2), 182-197.
Ebeling, C.E., 2004, An introduction to reliability and maintainability engineering, Tata McGraw-Hill Education.
Erickson, M., Mayer, A., and Horn, J., 2001, The niched pareto genetic algorithm 2 applied to the design of groundwater remediation systems, Evolutionary Multi-Criterion Optimization, Springer, 681-695.
Fonseca, C.M. and Fleming, P.J., 1993, Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization, ICGA, Citeseer, 416-423.
Gavett, J.W., 1965, Three heuristic rules for sequencing jobs to a single production facility, Management Science, 11 (8), B-166-B-176.
Gen, M., Tsujimura, Y., and Kubota, E., 1994, Solving job-shop scheduling problems by genetic algorithm, Systems, Man, and Cybernetics, 1994. Humans, Information and Technology., 1994 IEEE International Conference on, IEEE, 1577-1582.
Golenko-Ginzburg, D. and Gonik, A., 2002, Optimal job-shop scheduling with random operations and cost objectives, International Journal of Production Economics, 76 (2), 147-157.
Gonçalves, J.F., de Magalhães Mendes, J.J., and Resende, M.c.G., 2005, A hybrid genetic algorithm for the job shop scheduling problem, European Journal of Operational Research, 167 (1), 77-95.
Graves, S.C., 1981, A review of production scheduling, Operations Research, 29 (4), 646-675.
Gu, J., Gu, X., and Gu, M., 2009, A novel parallel quantum genetic algorithm for stochastic job shop scheduling, Journal of Mathematical Analysis and Applications, 355 (1), 63-81.
Herroelen, W. and Leus, R., 2005, Project scheduling under uncertainty: Survey and research potentials, European Journal of Operational Research, 165 (2), 289-306.
Hopp, W.J. and Spearman, M.L., 2011, Factory Physics, Waveland Press.
Horn, J., Nafpliotis, N., and Goldberg, D.E., 1994, A niched Pareto genetic algorithm for multiobjective optimization, Evolutionary Computation, 1994. IEEE World Congress on Computational Intelligence., Proceedings of the First IEEE Conference on, Ieee, 82-87.
Holland, J. H., 1975/1992, Adaption in Natural and Attificial Systems. Cambridge, MA: MIT Press. Second section 1992.(First edition, Unerversity of Michigan Press, 1975)
Ishibuchi, H. and Murata, T., 1998, A multi-objective genetic local search algorithm and its application to flowshop scheduling, Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on, 28 (3), 392-403.
Jain, A.S. and Meeran, S., 1999, Deterministic job-shop scheduling: Past, present and future, European Journal of Operational Research, 113 (2), 390-434.
Kim, S. and Bobrowski, P., 1997, Scheduling jobs with uncertain setup times and sequence dependency, Omega, 25 (4), 437-447.
Lee, C.-Y. and Chien, C.-F., 2014. Stochastic programming for vendor portfolio selection and order allocation under delivery uncertainty. OR Spectrum, 36 (3), 761–797.
Li, Z. and Ierapetritou, M., 2008, Process scheduling under uncertainty: Review and challenges, Computers ＆ Chemical Engineering, 32 (4), 715-727.
Luh, P.B., Chen, D., and Thakur, L.S., 1999, An effective approach for job-shop scheduling with uncertain processing requirements, Robotics and Automation, IEEE Transactions on, 15 (2), 328-339.
Mulvey, J.M., Vanderbei, R.J., and Zenios, S.A., 1995, Robust optimization of large-scale systems, Operations Research, 43 (2), 264-281.
Muth, J.F., and Thompson, G.L., 1963, Industrial Scheduling, Englewood Cliffs, New Jersey, Prentice Hall.
Pinedo, M.L., 2012, Scheduling: theory, algorithms, and systems, Springer Science ＆ Business Media.
Rahmani, D. and Heydari, M., 2014, Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times, Journal of Manufacturing Systems, 33 (1), 84-92.
Schaffer, J.D., 1985, Multiple objective optimization with vector evaluated genetic algorithms, Proceedings of the 1st International Conference on Genetic Algorithms, Pittsburgh, PA, USA, July 1985, 93-100.
Srinivas, N. and Deb, K., 1994, Muiltiobjective optimization using nondominated sorting in genetic algorithms, Evolutionary Computation, 2 (3), 221-248.
Taboada, H.A. and Coit, D.W., 2008, Multi-objective scheduling problems: determination of pruned Pareto sets, IIE Transactions, 40 (5), 552-564.
Vin, J.P. and Ierapetritou, M.G., 2001, Robust short-term scheduling of multiproduct batch plants under demand uncertainty, Industrial ＆ Engineering Chemistry Research, 40 (21), 4543-4554.
Wellman, M.A. and Gemmill, D.D., 1995, A genetic algorithm approach to optimization of asynchronous automatic assembly systems, International Journal of Flexible Manufacturing Systems, 7 (1), 27-46.
Zhou, H., Cheung, W., and Leung, L.C., 2009, Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm, European Journal of Operational Research, 194 (3), 637-649.
Zitzler, E. and Thiele, L., 1999, Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, Evolutionary Computation, IEEE Transactions on, 3 (4), 257-271.