以基因演算法規劃啤酒釀造排程

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：15

、訪客IP：18.217.110.0

姓名

裴春全(Bui Xuan Toan) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

以基因演算法規劃啤酒釀造排程
(Applying Genetic Algorithm to Schedule Brewery Production)

相關論文

★ 半導體化學材料銷售策略分析-以跨國B化工公司為例	★ TFT-LCD CELL製程P檢點燈不良解析流程改善之關聯法則應用
★ 金融風暴時期因應長鞭效應的策略 –以X公司為例	★ 勞動生產力目標訂定之研究-DEA 資料包絡法應用
★ 應用田口方法導入低溫超薄ITO透明導電膜於電容式觸控面板之研究	★ 多階不等效平行機台排程與訂單決策
★ 多準則決策之應用-以雷射半導體產業為例	★ 專案管理模式進行品管圈活動-以半導體機台保養測機流程改善為例
★ 應用e8D降低不合格品之效益分析-以快速消費品製造為例	★ 供應商評選模式之建構-以塑膠射出成型機製造為例
★ 應用協同規劃預測補貨於伺服器備品存貨改善之研究－以Q代工公司為例	★ 船用五金拋光作業之生產規劃
★ 以SCOR模型探討汽車安全輔助系統供應鏈-以A公司採購作業改善為例	★ 研發補助計畫執行成效評估之研究以「工業基礎技術專案計畫」為例
★ 運用生態效益發展永續之耳機產業	★ 失效模式設計審查(DRBFM)之應用-以筆記型電腦為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

中文摘要
排程規劃在製造業有舉足輕重的地位，本研究就是站在這角度上進行研究的延伸。
由於排程規劃是指數型成長的複雜性問題，在限制求解時間的條件下，此劃問題可以被
歸類為Np-hard 的問題。因為上述原因，目前在規劃排程的應用上，不是站在求得最佳
解的角度去尋找方向，而是使用啟發式的演算法來解決排程上的研究議題。
目前有許多學者研究如何使用不同地啟發式演算法來解決排程議題，如區域搜
尋、禁忌搜尋和基因演算法等方法。根據近幾年的學術研究趨勢，基因演算法被認定為
一個有效率的解決排程議題的演算法，也由於基因演算法逐漸地被重視下，其所討論的
研究領域與應用類型更為全面。
在啤酒製造工業，作物的發酵過程是整個釀造過程中的關鍵。此過程決定了啤酒的
品質、配方、風味以及生產線上的流程規劃。原料發酵的過程佔據了整個生產流程約41
天的時間，而每一種不同類型的啤酒也有其發酵需求時間和限制，有效地規劃發酵流程
對於啤酒釀造是非常重要的。本研究提出如何使用基因演算法，進行排程規劃求解最適
宜的生產排程方式，期望藉由有效地生產計劃與分析工具，利用機台的排程規劃搭配，
減少生產排程中，可能發生的瓶頸時間以及準備時間。
關鍵字：排程規劃、批量、啤酒工業、兩階段生產法、基因演算法。

摘要(英)

Abstract
Scheduling is one of the most important problems in any manufacturing industry.
Therefore, the problem has been studied extendedly. Since, the scheduling problem is classified
as NP-hard problem, which means the time required for finding the optimal solution of the
problem is grown exponentially with the size of the problem. Therefore, it is unrealistic to find
optimal solution for the scheduling problem in the scene of the real world industrial case, even
with today advanced computer system.
There are many heuristic algorithms have been proposal to solve the scheduling problem.
They are beam search, local search technique, tabular search and Genetic Algorithm (GA), to
name a few. In recent years, GA has become a noticeable candidate for solving the scheduling
problem effectively. The idea of mimicking the evolutionary process is very interesting to
researchers. And the recent advanced in heuristic GA has sparked more attention toward new
research and application in the field of GA.
In Brewery industry, the fermentation process is the most crucial components of the whole
manufacturing process. It will decide the quality, taste of the products as well as the
productivity of the production line. Since, the fermentation time can take up to 41 days, and the
requirement time is varying a lot between different types of beers, therefore finding a good
scheduling solution to dealing with this complexity is crucial for beer manufacturers. This
research will propose a GA to solve the scheduling problem in beer production. The proposed
methodology will serve as a planning and analysis tool to utilize assets (tanks, filling lines)
effectively, reduce congestion and synchronize the production process between the two
production stages (liquid preparation and bottling).
Keywords: scheduling, lot sizing, brewery industry, two-stage production, GA.

關鍵字(中)

★ 排程規劃
★ 批量
★ 啤酒工業
★ 兩階段生產法
★ 基因演算法

關鍵字(英)

★ scheduling
★ lot sizing
★ brewery industry
★ two-stage production
★ GA

論文目次

Table of Contents
Acknowlegement ................................................................................................................. i
Abstract .............................................................................................................................. iii
Table of Contents ............................................................................................................... iv
Table of Figures ................................................................................................................. vi
List of Tables ................................................................................................................... viii
CHAPTER 1. Introduction .............................................................................................. 1
1.1 Motivations ..................................................................................................... 1
1.2 Objectives ....................................................................................................... 2
1.3 Research Framework ...................................................................................... 3
CHAPTER 2. Literature Review ..................................................................................... 4
2.1 Scheduling Problems in Industrial Management ............................................ 4
2.1.1 The Job-Shop Scheduling Problem ...................................................................... 5
2.1.2 The Flexible Job-Shop Scheduling Problem. ....................................................... 7
2.1.3 The Integrated Operation Sequence and Resource Selection Problem: ............... 8
2.1.4 The Scheduling Problem in Soft Drink and Brewery Industry. ......................... 10
2.2 GA Approach ................................................................................................ 13
2.2.1 GA in General .................................................................................................... 14
2.2.2 GA and Network Modeling ................................................................................ 16
CHAPTER 3. Proposed Methodology........................................................................... 22
3.1 Beer Production Process ............................................................................... 22
3.2 Problem Description and Modeling .............................................................. 23
3.3 Data Collection and Input Design ................................................................ 27
CHAPTER 4. Solution Approach and Sabeco Case Study ........................................... 31
4.1 Tank Types Assignment Result and Introduction to Synchronization between
Tank Types Assignment and Filling Stages ...................................................................... 31
v
4.2 Data Preparation for Synchronization between the Two Stages. .................. 34
4.3 Synchronization with GA ............................................................................. 35
4.3.1 Genetic Presentation ........................................................................................... 36
4.3.2 Decode the genes to actual plan ......................................................................... 36
4.3.3 Compute fitness of individual genes .................................................................. 38
4.3.4 Genetic operations .............................................................................................. 38
4.3.5 Populated Genetic Algorithm ............................................................................. 40
CHAPTER 5. Experiment and Discussion .................................................................... 42
5.1 Standard Test for the Proposed GA .............................................................. 42
5.1.1 Testing on the Benchmark Problem ................................................................... 43
5.1.2 Test on Simple Brewery Production Problem. ................................................... 45
5.2 The proposed Approach with Industrial Production Scale. .......................... 47
5.2.1 Synchronization between the Two Production Stages ....................................... 47
5.3 Plan Presentation and Validation .................................................................. 49
5.4 Relation between population size, number of generations and fitness ......... 52
5.5 The Relation between Mutate, Crossover and Evolution Process within the
Proposed GA .................................................................................................................... 53
CHAPTER 6. Conclusion .............................................................................................. 54
6.1 New Contributions ........................................................................................ 55
6.2 Limitations and Further Research................................................................. 55
References ........................................................................................................................ 57
Appendices ....................................................................................................................... 60

參考文獻

References
[1] Adams J, Balas E, Zawack D. (1988). The Shifting Bottleneck Procedure for Job Shop
Scheduling. Management Science. Vol 34(3), pp. 391-401.
[2] Amin-Naseri MR, Afshari AJ. (2012). A hybrid genetic algorithm for integrated process
planning and scheduling problem with precedence constraints. The International Journal
of Advanced Manufacturing Technology. Vol 59(1), pp. 273-287.
[3] Baldo TA, Santos MO, Almada-Lobo B, Morabito R. (2014). An optimization approach
for the lot sizing and scheduling problem in the brewery industry. Computers &
Industrial Engineering. Vol 72, pp. 58-71.
[4] Chang Wook A, Ramakrishna RS. (2002). A genetic algorithm for shortest path routing
problem and the sizing of populations. IEEE Transactions on Evolutionary Computation.
Vol 6(6), pp. 566-579.
[5] Cheng R, Gen M, Sasaki M. (1995). Film-copy deliverer problem using genetic
algorithms. Computers & Industrial Engineering. Vol 29(1), pp. 549-553.
[6] Cheng R, Gen M, Tsujimura Y. (1996). A tutorial survey of job-shop scheduling
problems using genetic algorithms—I. representation. Computers & Industrial
Engineering. Vol 30(4), pp. 983-997.
[7] Ferreira D, Clark AR, Almada-Lobo B, Morabito R. (2012). Single-stage formulations
for synchronised two-stage lot sizing and scheduling in soft drink production.
International Journal of Production Economics. Vol 136(2), pp. 255-265.
[8] Ferreira D, Morabito R, Rangel S. (2009). Solution approaches for the soft drink
integrated production lot sizing and scheduling problem. European Journal of
Operational Research. Vol 196(2), pp. 697-706.
[9] Fleischmann B, Meyr H. (1997). The general lotsizing and scheduling problem.
Operations-Research-Spektrum. Vol 19(1), pp. 11-21.
58
[10] Gao J, Gen M, Sun L, Zhao X. (2007). A hybrid of genetic algorithm and bottleneck
shifting for multiobjective flexible job shop scheduling problems. Computers &
Industrial Engineering. Vol 53(1), pp. 149-162.
[11] Gen M, Gao J, Lin L. Multistage-Based Genetic Algorithm for Flexible Job-Shop
Scheduling Problem. In: Gen M, Green D, Katai O, McKay B, Namatame A, Sarker RA,
et al., (Eds.) Intelligent and Evolutionary Systems. Berlin, Heidelberg: Springer Berlin
Heidelberg; (2009), pp. 183-196.
[12] Haupt R. (1989). A survey of priority rule-based scheduling.
Operations-Research-Spektrum. Vol 11(1), pp. 3-16.
[13] Inagaki J, Haseyama M, Kitajima H. (1999). A genetic algorithm for determining
multiple routes and its applications. Circuits and Systems, 1999 ISCAS ′99 Proceedings
of the 1999 IEEE International Symposium on. Vol 6, pp. 137-140.
[14] Kacem I, Hammadi S, Borne P. (2002). Approach by localization and multiobjective
evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions
on Systems, Man, and Cybernetics, Part C (Applications and Reviews). Vol 32(1), pp.
1-13.
[15] Kundakci N, Kulak O. (2016). Hybrid genetic algorithms for minimizing makespan in
dynamic job shop scheduling problem. Computers & Industrial Engineering. Vol 96, pp.
31-51.
[16] Leu G, Namatame A. Evolving Failure Resilience in Scale-free Networks. Intelligent
and Evolutionary Systems (2008), pp. 49-59.
[17] Lin L, Gen M. (2009). Auto-tuning strategy for evolutionary algorithms: balancing
between exploration and exploitation. Soft Computing. Vol 13(2), pp. 157-168.
[18] Mitsuo G, Runwei C, Lin L. Network Models and Optimization: Multiobjective Genetic
Algorithm Approach. 1st ed. London: Springer-Verlag London; (2008).
[19] Orito Y, Jun T, Takeda M, Yamamoto H. Index Fund Optimization Using Genetic
59
Algorithm and Scatter Diagram Based on Coefficients of Determination. Intelligent
and Evolutionary Systems (2009), pp. 1-11.
[20] Pezzella F, Morganti G, Ciaschetti G. (2008). A genetic algorithm for the Flexible
Job-shop Scheduling Problem. Computers & Operations Research. Vol 35(10), pp.
3202-3212.
[21] Toledo CFM, de Oliveira L, Pereira RD, Franca PM, Morabito R. (2014). A genetic
algorithm/mathematical programming approach to solve a two-level soft drink
production problem. Computers & Operations Research. Vol 48, pp. 40-52.
[22] Xia H, Li X, Gao L. (2016). A hybrid genetic algorithm with variable neighborhood
search for dynamic integrated process planning and scheduling. Computers & Industrial
Engineering. Vol 102, pp. 99-112.
[23] Xia W, Wu Z. (2005). An effective hybrid optimization approach for multi-objective
flexible job-shop scheduling problems. Computers & Industrial Engineering. Vol 48(2),
pp. 409-425.
[24] Zhang H, Gen M, Seo Y. (2006). An effective coding approach for multiobjective
integrated resource selection and operation sequences problem. Journal of Intelligent
Manufacturing. Vol 17(4), pp. 385-397.

指導教授

王啟泰(Chi-Tai Wang)

審核日期

2017-7-17

推文