臺灣博碩士論文加值系統

迴流式混合流程型生產(Reentrant Hybrid Flow Shop)被廣泛應用於機台設備價格昂貴之製造業如薄膜電晶體液晶顯示器陣列製程、半導體製程、飛機引擎製程，隨著半導體製造業的發展，排程相關研究中，關於迴流式混合流程型生產排程問題，如何加速生產效率備受重視。因產品製程的迴流特性，在製品容易堆積於需要較長加工時間或是平行機台數量較少的工作站，實務上平行機台前存在提供暫時存放在製品之緩存區(Buffer)，以及工作站之間存在亦可暫時存放在製品之自動倉儲(Stocker)，當平行機台滿載時，在製品將暫時存放於機台前緩存區，而緩存區亦滿載時將會把在製品傳送至自動倉儲暫存，此時當自動倉儲若滿載，在製品將需滯留於前一階段的加工機台，造成該加工機台無法立即加工下一個工單，使總完工時間延長。過去已有部分排程研究將緩存區納入考慮，然而卻鮮少考慮自動倉儲存在的情形。此外，過去研究中已證實整合型自動物料搬運系統只需要工作站數量0.7倍的自動倉儲，相關研究卻皆仍將自動倉儲假設為每個工作站各放置一個，未曾有排程研究考慮自動倉儲的擺放位置對生產效率的影響。然而並非所有工作站的使用率皆相同，考慮到在製品較容易堆積於特定工作站，且自動倉儲購置成本佔總生產成本高，本研究設定在自動倉儲的總數量能減少至工作站數量的0.7倍，且一個工作站不限只放置一個自動倉儲，透過同時求解工單排程與自動倉儲擺放位置，來最小化總完工時間。由於迴流式混合流程型生產排程問題為NP-hard問題，過去混合猴群演算法已被證實在求解流程型排程問題有良好表現，為提升求解的品質與速度，我們提出加入蟻群優化法局部搜索機制的改良式混合猴群演算法來求解本問題，目標設定為最小化最大完工時間。

Reentrant hybrid flow shop production lines have been practiced in many manufactur-ing systems which expensive equipment are used, such as TFT-LCD array, semicon-ductor manufacturing, and air plane engine manufacturing. With the development of semiconductor industry, it has been an important issue to improve the production effi-ciency in re-entrant hybrid flow shop scheduling problem. Due to the reentrant property in the production process, work in process (WIP) gets more easily to stock at the sta-tions which need more processing time or have fewer parallel machines. In practice, in the stations each parallel machine has a buffer to provide temporary WIP storage, and between the station we have stockers to storage WIP. If all the parallel machines are fully loaded when WIP comes to a station, WIP will be put in the buffer, and if all the buffers are also fully loaded, the WIP will be temporary transfer to stockers. However, if all the stockers are also fully loaded, WIP has to retain at the station in the previous stage that makes the parallel machine can’t process the next work immediately, which extend the total completion time. In previous scheduling research, buffers have already been discussed in the problem, but there are few researches taking stockers into consid-eration. Besides, previous work has already proved that unified automated material handling system (unified AMHS) requires only 0.7 times the number of stations for stockers, however, related researches still assume that each station has one stocker. There is no scheduling study to consider the impact of the placement of stockers on production efficiency. As a matter of fact, the utilization ratio of every stations differ, and WIP is easier to stock at specific stations. Also, considering the high acquisition cost of stockers, we set our problem to optimize the reentrant hybrid flow shop scheduling problem with the consideration of the stockers layout when limiting the quantity of stockers to 0.7 times the number of stations, and each station can have more than one stocker. Since the re-entrant hybrid flow shop scheduling problem is NP-hard and has already been proven that it can successfully solved by using hybrid monkey search al-gorithm (HMSA), we propose an improved hybrid monkey search algorithm (IHMSA) which using an ACO local search approach to improve the performance of HMSA aiming to minimize makespan.

摘 要 I
ABSTRACT II
誌謝 IV
目錄 V
表目錄 VII
圖目錄 VIII
第一章 緒論 1
第二章 問題描述 5
2.1 情境描述 5
2.2 問題描述 5
2.3 相關文獻回顧 8
2.3.1 迴流式混合流程型生產排程 8
2.3.2 自動物料搬運系統 10
第三章 研究方法 12
3.1 解的表示法 13
3.2 解碼與適應度值計算 15
3.2.1 第一部分 15
3.2.2 第二部分 16
3.3 產生起始解 19
3.4 爬行 19
3.5 PSO速度更新猴子位置 20
3.6 蟻群優化局部搜索 21
3.7 突變 22
3.8 觀望後跳躍 22
3.9 翻筋斗 23
3.10 終止條件 23
第四章 實驗結果 24
4.1 參數與實驗環境 24
4.2 演算法參數設定 25
4.3 實驗結果分析之演算法比較 26
4.4 實驗結果分析之自動倉儲擺放位置 30
第五章 結論 36
參考文獻 37

Gartland, K. (1999). Automated material handling system (AMHS) framework user requirements document: Version 1.0. International SEMATECH.
Pillai, D. et al. (1999). Integration of 300 mm fab layouts and material handling auto-mation. In 1999 IEEE International Symposium on Semiconductor Manufac-turing Conference Proceedings (Cat No. 99CH36314) IEEE Press, pp. 23-26.
Ruiz, R. et al. (2010). The hybrid flow shop scheduling problem. European journal of operational research, 205(1), 1-18.
Gupta, J. N. (1988). Two-stage, hybrid flowshop scheduling problem. Journal of the Operational Research Society, 39(4), 359-364.
Gourgand, M. et al. (2000). Meta-heuristics for the deterministic hybrid flow shop problem. Journal Europeen Des Systemes Automatises, 34(9), 1107-1136.
Ying, K. C. et al. (2006). Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach. International Journal of Produc-tion Research, 44(16), 3161-3177.
Zandieh, M. et al. (2006). An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times. Applied Mathematics and Computation, 180(1), 111-127.
Marichelvam, M. K. et al. (2017). Hybrid monkey search algorithm for flow shop scheduling problem under makespan and total flow time. Applied Soft Compu-ting, 55, 82-92.
Shelokar, P. S. et al. (2007). Particle swarm and ant colony algorithms hybridized for improved continuous optimization. Applied mathematics and computa-tion, 188(1), 129-142.
Kim, J. et al. (2016). Semiconductor FAB layout design analysis with 300-mm FAB data:“Is minimum distance-based layout design best for semiconductor FAB design?”. Computers & Industrial Engineering, 99, 330-346.
Lee, S. et al. (2019). Iterative two-stage hybrid algorithm for the vehicle lifter location problem in semiconductor manufacturing. Journal of Manufacturing Systems, 51, 106-119.
Wang, C. N., Hsu, H. P., Dang, D. C., & Nguyen, Q. T. (2019). The remaining time concept for dispatching on roller belt conveyor in 450-mm wafer fabrications. The International Journal of Advanced Manufacturing Technology, 1-15.
Meller, R. D. (1997). The multi-bay manufacturing facility layout prob-lem. International Journal of Production Research, 35(5), 1229-1237.
Castillo, I. et al. (2004). Integrating design and production planning considerations in multi-bay manufacturing facility layout. European Journal of Operational Re-search, 157(3), 671-687.
Wang, H. et al. (2017). A NSGA-II based memetic algorithm for multiobjective par-allel flowshop scheduling problem. Computers & Industrial Engineering, 113, 185-194.
Shahvari, O. et al. (2018). A comparison of two stage-based hybrid algorithms for a batch scheduling problem in hybrid flow shop with learning ef-fect. International Journal of Production Economics, 195, 227-248.
Fu, Y. et al. (2019). Scheduling Dual-Objective Stochastic Hybrid Flow Shop With Deteriorating Jobs via Bi-Population Evolutionary Algorithm. IEEE Transac-tions on Systems, Man, and Cybernetics: Systems.
Zhang, W. et al. (2019). Hybrid Multiobjective Evolutionary Algorithm based on Dif-ferential Evolution for Flow Shop Scheduling Problems. Computers & Indus-trial Engineering, 130, 661-670.
Li, Z., et al. (2019). Bi-objective hybrid flow shop scheduling with common due date. Operational Research, 1-26.
Pranzo, M. (2004). Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times. European Journal of Operational Research, 153(3), 581-592.
Wang, L. et al. (2006). An effective hybrid genetic algorithm for flow shop schedul-ing with limited buffers. Computers & Operations Research, 33(10), 2960-2971.
Liu, B. et al. (2008). An effective hybrid PSO-based algorithm for flow shop sched-uling with limited buffers. Computers & Operations Research, 35(9), 2791-2806.
Li, J. Q. et al. (2015). Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm. Information Sciences, 316, 487-502.
Dugardin, F. et al. (2010). New multi-objective method to solve reentrant hybrid flow shop scheduling problem. European Journal of Operational Research, 203(1), 22-31.
Ying, K. C. et al. (2014). Bi-objective reentrant hybrid flowshop scheduling: an iter-ated Pareto greedy algorithm. International Journal of Production Re-search, 52(19), 5735-5747.
Shen, J. N. et al. (2016). A modified teaching–learning-based optimisation algorithm for bi-objective re-entrant hybrid flowshop scheduling. International Journal of Production Research, 54(12), 3622-3639.
Cho, H. M. et al. (2017). A two-level method of production planning and scheduling for bi-objective reentrant hybrid flow shops. Computers & Industrial Engi-neering, 106, 174-181.
Lee, B. et al. (2008). A due-date based production control policy using WIP balance for implementation in semiconductor fabrications. International Journal of Production Research, 46(20), 5515-5529.
Cho, H. M. et al. (2012). Preemptive goal programming based heuristic methods for reentrant flow shop planning with bi-objective. Journal of the Society of Korea Industrial and Systems Engineering, 35.
Deb, K. et al. (2000). A fast elitist non-dominated sorting genetic algorithm for mul-ti-objective optimization: NSGA-II. In International conference on parallel problem solving from nature. pp. 849-858. Springer, Berlin, Heidelberg.
Cho, H. M. et al. (2011). Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm. Computers & Industrial Engineering, 61(3), 529-541.
Mousavi, S. M. et al. (2018). An efficient bi-objective algorithm to solve re-entrant hybrid flow shop scheduling with learning effect and setup times. Operational Research, 18(1), 123-158.
Zhang, X. Y. et al. (2018). A re-entrant hybrid flow shop scheduling problem with machine eligibility constraints. International Journal of Production Re-search, 56(16), 5293-5305.
Agrawal, N. et al. (2006). Multi-objective optimization of the operation of an industri-al low-density polyethylene tubular reactor using genetic algorithm and its jumping gene adaptations. Industrial & engineering chemistry research, 45(9), 3182-3199.
Bahri, N. et al. (2001). A comparison of unified vs. segregated automated material handling systems for 300 mm fabs. In 2001 IEEE International Symposium on Semiconductor Manufacturing. ISSM 2001. Conference Proceedings (Cat. No. 01CH37203). IEEE Press, pp. 3-6.
Zhao, R. Q. et al. (2008). Monkey algorithm for global numerical optimiza-tion. Journal of Uncertain Systems, 2(3), 165-176.
Nawaz, M. et al. (1983). A heuristic algorithm for the m-machine, n-job flow-shop se-quencing problem. Omega, 11(1), 91-95.
Tseng, L. Y. et al. (2010). A hybrid genetic algorithm for no-wait flowshop scheduling problem. International journal of production economics, 128(1), 144-152.
Ding, J. Y. et al. (2015). An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem. Applied Soft Computing, 30, 604-613.
Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimiza-tion. ORSA journal on computing, 6(2), 154-160.
Tasgetiren, M. F. et al. (2007). A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem. European journal of operational research, 177(3), 1930-1947.
Rajkumar, R. et al. (2009). An improved genetic algorithm for the flowshop schedul-ing problem. International Journal of Production Research, 47(1), 233-249.