臺灣博碩士論文加值系統

現實的生產環境大多屬於混合型流線式生產排程 (Hybrid Flow Shop；HFS) ，因此本研究以多目標混合型流程式排程作為研究主題，其結合平行機台 (Parallel machine) 及流線型排程 (Flow shop) 兩者之特點，生產環境包括一個以上之加工階段 (Stages) ，每一階段都有一個或數個功能相同的機器執行加工，而工件 (job) 只需在每個階段中的任一台機器進行加工即可，其常為一個具高複雜度的組合問題。
在現實生活中混合型流線式生產排程問題常結合其他生產環境的限制與特性，例如：等候時間限制，其廣泛存在半導體晶圓廠、光電業、食品加工業和鋼鐵製造業的製造程序中，其指在限制的時間內在製品必須完成特殊製程的加工，若當等候時間超出時間限制時，在製品必須重新加工或報廢，嚴重影響工件品質和生產成本。此外還有可分割工件特性，由於不同的設備參數設定與製程設計，產品會有各自的可用機台的清單，根據此清單之限制，產品可拆解成數個部分同時在不同的機台上進行加工，而以上限制不僅增加此排程問題的複雜度，並提高求解的困難度。
本研究主要探討半導體及電子製造產業中常見的具可分割工件、成批加工與等候時間限制的混合型流線式生產排程問題，並將此問題建構為一混合整數規劃模型，目標為在最小化違反等候時間限制之數量下減少總完工時間 (total completion) 以期各個工件皆能在不違反等候時間限制的前提下以最少的時間完成製程。本研究以IBM ILOG CPLEX Optimization Studio V12.5.1驗證並求解數學模型，但由於數學規劃模型無法在有效的時限下求解較大規模的問題，因此進一步提出一套啟發式演算法，在短時間內求得合理的排程解。
本研究透過情境分析，將演算法與先進先出派工法進行各種情境的求解表現之比較，結果顯示所提出的演算法皆可有效求解不同情境的問題，可在不違反等候時間限制下減少所有工件的完工時間。

In this study, we consider a job-splitting and batching hybrid multi-stage flowshop with queue time constraint. A hybrid flowshop is composed of a series of production stages with several identical parallel machines at each stage. Jobs are processed through all stages in the same production flow. In many real world applications, there are often queue time limitations among process stages. Any violation of the process queue time constraint affects yield quality and also incurs significant scrap costs. Furthermore, Lot streaming combined job splitting with operations overlapping is one of the effective techniques used to implement the time-based strategy in today’s era of global competition. Besides, Batching in a manufacturing system is very common policy in most industries. The main reasons for batching are avoidance of set ups and/or facilitation of material handling. As a consequence, we purpose a hybrid flowshop scheduling problem which combines with job splitting, batching and queue time constraint in order to solve a complex combinatorial problem encountered in many real world applications. The objective is to minimize the total completion time of all of jobs under minimizing the number of jobs violating the queue time constraint. We formulate this problem as a mixed integer linear programming model (MILP) . Computational tests have shown that the total elapsed time resulting from the purposed formulation which solves the large-scale problem is costly. Therefore, we present a solution approach, a kind of heuristic, based on the characteristic of the problem. Numerical results show that this solution approach generates higher quality solutions in moderate computational time.

誌謝 i
中文摘要 ii
ABSTRACT iii
目錄 iv
圖目錄 vii
表目錄 ix
第1章. 緒論 1
1.1 研究背景 1
1.2 研究目的 2
1.3 研究方法與架構 3
第2章. 文獻探討 5
2.1 混合型流線式排程問題 5
2.2 批量製造排程問題 8
2.3 工件可分割問題 10
2.4 具等候時間限制排程問題 11
第3章. 數學模型建構 14
3.1 問題描述 14
3.2 問題假設與限制 19
3.3 混合整數規劃數學模型之建構 19
3.3.1 模型概念說明 19
3.3.2 參數與決策變數說明 21
3.3.3 混合整數規劃模型建構 23
3.3.4 目標式與限制式說明 25
3.4 數學模型驗證與範例說明 29
第4章. 啟發式演算法 32
4.1 啟發式演算法概論 32
4.2 啟發式演算法主要流程說明 32
4.2.1 兩階段演算法 33
4.2.2 非批量式加工階段演算法 34
4.2.3 批量式加工階段演算法 55
第5章. 數值分析 65
5.1 情境設定與說明 65
5.2 先進先出派工法則 67
5.3 最小處理時間派工法則 68
5.4 求解範例與分析 69
5.4.1 標準範例 69
5.4.2 批次容量因子 70
5.4.3 機台數量因子 74
5.4.4 非批量式加工機台之加工速率因子 77
第6章. 結論與建議 82
6.1 結論 82
6.2 未來研究建議 83
參考文獻 84

Ahmadi, J. H., Ahmadi, R. H., Dasu, S., &; Tang, C. S. (1992). Batching and scheduling jobs on batch and discrete processors. Operations research, 40(4), 750-763.
Albers, S., &; Brucker, P. (1993). The complexity of one-machine batching problems. Discrete Applied Mathematics, 47(2), 87-107.
Attar, S., Mohammadi, M., &; Tavakkoli-Moghaddam, R. (2013). Hybrid flexible flowshop scheduling problem with unrelated parallel machines and limited waiting times. The International Journal of Advanced Manufacturing Technology, 68(5-8), 1583-1599.
Baker, K. R., &; Jia, D. (1993). A comparative study of lot streaming procedures. Omega, 21(5), 561-566.
Brucker, P., Gladky, A., Hoogeveen, H., Kovalyov, M. Y., Potts, C., Tautenhahn, T., &; Van De Velde, S. (1997). Scheduling A Batching Machine 1.
Chang, P.-Y., Damodaran*, P., &; Melouk, S. (2004). Minimizing makespan on parallel batch processing machines. International Journal of Production Research, 42(19), 4211-4220.
Fanti, M., Maione, B., Piscitelli, G., &; Turchiano, B. (1996). Heuristic scheduling of jobs on a multi-product batch processing machine. International Journal of Production Research, 34(8), 2163-2186.
Grabowski, J., &; Pempera, J. (2000). Sequencing of jobs in some production system. European Journal of Operational Research, 125(3), 535-550.
Guinet, A. (1991). Textile production systems: a succession of non-identical parallel processor shops. Journal of the Operational Research Society, 655-671.
Gupta, J. N. (1988). Two-stage, hybrid flowshop scheduling problem. Journal of the Operational Research Society, 359-364.
Jacobs, F. R., &; Bragg, D. J. (1988). Repetitive Lots: Flow-time Reductions through Sequencing and Dynamic Batch Sizing. Decision Sciences, 19(2), 281-294.
Jin, Z., Ohno, K., Ito, T., &; Elmaghraby, S. (2002). Scheduling Hybrid Flowshops in Printed Circuit Board Assembly Lines. Production and Operations Management, 11(2), 216-230.
Johnson, S. M. (1954). Optimal two&;#8208;and three&;#8208;stage production schedules with setup times included. Naval research logistics quarterly, 1(1), 61-68.
Kropp, D. H., &; Smunt, T. L. (1990). Optimal and heuristic models for lot splitting in a flow shop. Decision Sciences, 21(4), 691-709.
Linn, R., &; Zhang, W. (1999). Hybrid flow shop scheduling: a survey. Computers &; industrial engineering, 37(1), 57-61.
Liu, C.-Y., &; Chang, S.-C. (2000). Scheduling flexible flow shops with sequence-dependent setup effects. Robotics and Automation, IEEE Transactions on, 16(4), 408-419.
Liu, S., Cui, J., &; Li, Y. (2008). Heuristic-tabu algorithm for hybrid flowshop scheduling with limited waiting time. Paper presented at the Computational Intelligence and Design, 2008. ISCID''08. International Symposium on.
Mathirajan, M., Sivakumar, A., &; Chandru, V. (2004). Scheduling algorithms for heterogeneous batch processors with incompatible job-families. Journal of Intelligent Manufacturing, 15(6), 787-803.
Potts, C. N., &; Kovalyov, M. Y. (2000). Scheduling with batching: a review. European Journal of Operational Research, 120(2), 228-249.
Potts, C. N., &; Van Wassenhove, L. N. (1992). Integrating scheduling with batching and lot-sizing: a review of algorithms and complexity. Journal of the Operational Research Society, 395-406.
Ram, B., &; Patel, G. (1998). Modeling furnace operations using simulation and heuristics. Paper presented at the Proceedings of the 30th conference on Winter simulation.
Ramasesh, R. V., Fu, H., Fong, D. K., &; Hayya, J. C. (2000). Lot streaming in multistage production systems. International Journal of Production Economics, 66(3), 199-211.
Robinson, J. K., &; Giglio, R. (1999). Capacity planning for semiconductor wafer fabrication with time constraints between operations. Paper presented at the Simulation Conference Proceedings, 1999 Winter.
Ruiz, R., &; Vazquez-Rodriguez, J. A. (2010). The hybrid flow shop scheduling problem. European Journal of Operational Research, 205(1), 1-18.
Scholl, W., &; Domaschke, J. (2000). Implementation of modeling and simulation in semiconductor wafer fabrication with time constraints between wet etch and furnace operations. Semiconductor Manufacturing, IEEE Transactions on, 13(3), 273-277.
Sherali, H. D., Sarin, S. C., &; Kodialam, M. S. (1990). Models and algorithms for a two-stage production process. Production Planning &; Control, 1(1), 27-39.
Su, L.-H. (2003). A hybrid two-stage flowshop with limited waiting time constraints. Computers &; industrial engineering, 44(3), 409-424.
Trietsch, D., &; Baker, K. R. (1993). Basic techniques for lot streaming. Operations research, 41(6), 1065-1076.
Van De Rzee, D., Van Harten, A., &; Schuur, P. (1997). Dynamic job assignment heuristics for multi-server batch operations-a cost based approach. International Journal of Production Research, 35(11), 3063-3094.
Webster, S., &; Baker, K. R. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43(4), 692-703.
Weng, W. W., &; Leachman, R. C. (1993). An improved methodology for real-time production decisions at batch-process work stations. Semiconductor Manufacturing, IEEE Transactions on, 6(3), 219-225.
Wittrock, R. J. (1985). Scheduling algorithms for flexible flow lines. IBM Journal of Research and Development, 29(4), 401-412.
Wittrock, R. J. (1988). An adaptable scheduling algorithm for flexible flow lines. Operations research, 36(3), 445-453.
Wu, C.-H., Lin, J. T., &; Chien, W.-C. (2012). Dynamic production control in parallel processing systems under process queue time constraints. Computers &; industrial engineering, 63(1), 192-203.
Yang, D.-L., &; Chern, M.-S. (1995). A two-machine flowshop sequencing problem with limited waiting time constraints. Computers &; industrial engineering, 28(1), 63-70.
Yuan, J., Liu, Z., Ng, C., &; Cheng, T. E. (2004). The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. Theoretical Computer Science, 320(2), 199-212.
Zhang, W., Yin, C., Liu, J., &; Linn, R. J. (2005). Multi-job lot streaming to minimize the mean completion time in< i> m-1 hybrid flowshops. International Journal of Production Economics, 96(2), 189-200.
林則孟, 蔡建基, 陳盈彥, &; 陳子立. (2009). 考量等候時間限制之半導體爐管機台派工法則. Journal of Advanced Engineering, 4(3), 273-278.
張玉鈍和曾毓文. (2000). 運用系統模擬與遺傳演算法從事非相關平行機器排程之研究. Paper presented at the 科技與管理學術研討會.
陳幸滿. (2003). 雙機流程型生產環境下具批量流與等候時間限制的多產品排程問題. 中央大學.