Skip navigation

DSpace

機構典藏 DSpace 系統致力於保存各式數位資料(如:文字、圖片、PDF)並使其易於取用。

點此認識 DSpace
DSpace logo
English
中文
  • 瀏覽論文
    • 校院系所
    • 出版年
    • 作者
    • 標題
    • 關鍵字
  • 搜尋 TDR
  • 授權 Q&A
    • 我的頁面
    • 接受 E-mail 通知
    • 編輯個人資料
  1. NTU Theses and Dissertations Repository
  2. 工學院
  3. 工業工程學研究所
請用此 Handle URI 來引用此文件: http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/55859
完整後設資料紀錄
DC 欄位值語言
dc.contributor.advisor黃奎隆(Kwei-Long Huang)
dc.contributor.authorHao-Huai Chenen
dc.contributor.author陳顥懷zh_TW
dc.date.accessioned2021-06-16T05:09:39Z-
dc.date.available2019-08-25
dc.date.copyright2014-08-25
dc.date.issued2014
dc.date.submitted2014-08-18
dc.identifier.citationAhmadi, 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‐and three‐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</i>-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). 雙機流程型生產環境下具批量流與等候時間限制的多產品排程問題. 中央大學.
dc.identifier.urihttp://tdr.lib.ntu.edu.tw/jspui/handle/123456789/55859-
dc.description.abstract現實的生產環境大多屬於混合型流線式生產排程 (Hybrid Flow Shop;HFS) ,因此本研究以多目標混合型流程式排程作為研究主題,其結合平行機台 (Parallel machine) 及流線型排程 (Flow shop) 兩者之特點,生產環境包括一個以上之加工階段 (Stages) ,每一階段都有一個或數個功能相同的機器執行加工,而工件 (job) 只需在每個階段中的任一台機器進行加工即可,其常為一個具高複雜度的組合問題。
在現實生活中混合型流線式生產排程問題常結合其他生產環境的限制與特性,例如:等候時間限制,其廣泛存在半導體晶圓廠、光電業、食品加工業和鋼鐵製造業的製造程序中,其指在限制的時間內在製品必須完成特殊製程的加工,若當等候時間超出時間限制時,在製品必須重新加工或報廢,嚴重影響工件品質和生產成本。此外還有可分割工件特性,由於不同的設備參數設定與製程設計,產品會有各自的可用機台的清單,根據此清單之限制,產品可拆解成數個部分同時在不同的機台上進行加工,而以上限制不僅增加此排程問題的複雜度,並提高求解的困難度。
本研究主要探討半導體及電子製造產業中常見的具可分割工件、成批加工與等候時間限制的混合型流線式生產排程問題,並將此問題建構為一混合整數規劃模型,目標為在最小化違反等候時間限制之數量下減少總完工時間 (total completion) 以期各個工件皆能在不違反等候時間限制的前提下以最少的時間完成製程。本研究以IBM ILOG CPLEX Optimization Studio V12.5.1驗證並求解數學模型,但由於數學規劃模型無法在有效的時限下求解較大規模的問題,因此進一步提出一套啟發式演算法,在短時間內求得合理的排程解。
本研究透過情境分析,將演算法與先進先出派工法進行各種情境的求解表現之比較,結果顯示所提出的演算法皆可有效求解不同情境的問題,可在不違反等候時間限制下減少所有工件的完工時間。
zh_TW
dc.description.abstractIn 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.en
dc.description.provenanceMade available in DSpace on 2021-06-16T05:09:39Z (GMT). No. of bitstreams: 1
ntu-103-R01546025-1.pdf: 1864040 bytes, checksum: 314667f75b76ad482e0def7a77ab8ce1 (MD5)
Previous issue date: 2014
en
dc.description.tableofcontents誌謝 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
dc.language.isozh-TW
dc.title具可分割工件與成批加工之混合型流線式生產暨等候時間限制之排程規劃zh_TW
dc.titleJob-splitting and Batching Hybrid Flow Shop Scheduling Problem with Queue Time Constraintsen
dc.typeThesis
dc.date.schoolyear102-2
dc.description.degree碩士
dc.contributor.oralexamcommittee吳吉政(Jei-Zheng Wu),郭佳瑋(Chia-Wei Kuo),楊朝龍(Chao-Lung Yang)
dc.subject.keyword混合型流線式生產排程,等候時間限制,可分割工件,成批加工,zh_TW
dc.subject.keywordHybrid flow shop scheduling,Queue time constraint,Job splitting,Batching,en
dc.relation.page86
dc.rights.note有償授權
dc.date.accepted2014-08-19
dc.contributor.author-college工學院zh_TW
dc.contributor.author-dept工業工程學研究所zh_TW
顯示於系所單位:工業工程學研究所

文件中的檔案:
檔案 大小格式 
ntu-103-1.pdf
  目前未授權公開取用
1.82 MBAdobe PDF
顯示文件簡單紀錄


系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。

社群連結
聯絡資訊
10617臺北市大安區羅斯福路四段1號
No.1 Sec.4, Roosevelt Rd., Taipei, Taiwan, R.O.C. 106
Tel: (02)33662353
Email: ntuetds@ntu.edu.tw
意見箱
相關連結
館藏目錄
國內圖書館整合查詢 MetaCat
臺大學術典藏 NTU Scholars
臺大圖書館數位典藏館
本站聲明
© NTU Library All Rights Reserved