節省法為基礎之分支定界法以決定機器合適度區間之零工式批量排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：10

、訪客IP：3.145.164.47

姓名

李穎琪(Ying-Chi Lee) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

節省法為基礎之分支定界法以決定機器合適度區間之零工式批量排程問題
(A Saving Method-based Branch-and-Bound Algorithm for Machine Eligibility Period Determination Problem on Job Shop Batch Processing)

相關論文

★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立	★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究	★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用	★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究	★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討－以平面式觸控面板產業為例	★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例	★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例	★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例	★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本文主要探討節省法為基礎之分支定界法以決定機器合適度區間之零工式批量排程問題。此論文將環境以三種相關的單位作探討，由單位小到大分別為Operation、Batch、Period。Operation為每個工件在指定機台的操作。將Operation依工件大小總和、工件族等特性依特定規則組合並同時送進機台加工稱為Batch。Period為機台此次添加物料至下一次添加物料的時間段，Period會根據物料消耗的多寡決定服務多少Batch。
我們提出一個分支定界演算法去尋找這個問題的佳解。將利用Proposition以job size及release time計算各種Operation組合的節省面積。每個節點都會計算input operation及output operation的節省面積後得到多個batch，並在input batches及output batches中各選出一個指派到加工順序中成為一個節點，將所有指派可能舉出後便完成分支。
本論文依照環境設計出分離圖，分離圖上的分離弧線會依照節點的排程狀況更動，當找到起源點至終節點的最長路徑可得此節點的lower bound。得到可行解之節點的最長路徑並同Upper bound比較，可得目前已知最佳解。
最後，我們驗證節省法對物料消耗及尋找批量組合有不錯的表現。並發現節省法可降低批量的列舉數，分離圖計算出最長路徑後也明顯的提高砍支的數目。因此證明此演算法可快速及有效地找到此環境中表現優異的可行解。

摘要(英)

This thesis is mainly designed with a saving method-based branch-and-bound algorithm for machine eligibility period determination problem on job shop batch processing. We discuss the environment in terms of Operation, Batch and Period. Operation is the processing of each job on the designated machine. Combining Operations according to the characteristics of sum of job size, family, etc., combined with specific rules and processed by the machine at the same time is called Batch. Period is the time interval from when the machine starts adding materials to the next time when materials are added. The amount of materials consumed determines how many batches are served by one period.
We propose a branch and bound algorithm to find an excellent solution. Proposition will be used to calculate the area savings of multiple operation combinations with job size and release time. Each node will calculate the saving area of input operations and output operations to get batch. Select one of the input batches and output batches and assign them to the processing sequence to become a node. After all possible assignments are listed, the branch is completed.
This thesis designs a disjunctive graph according to the problem, and the disjunctive arc on the disjunctive graph will change according to the scheduling status of the node. The longest path from the start point to the end point can get the lower bound of this node. Comparing the longest path of the feasible solution with the upper bound, we can see that the final solution has been obtained.
Finally, we verify that the saving method has a good performance on material consumption and finding batch combinations. It is found that the saving method can reduce the enumeration number of the batch. The longest path of the disjunctive graph also significantly increases the number of cut branches. Therefore, it is proved that this algorithm can quickly and effectively find feasible solutions with excellent performance in this environment.

關鍵字(中)

★ 零工式生產
★ 存活時間限制
★ 批量
★ 分支定界
★ 排程
★ 最晚完工時間

關鍵字(英)

★ Job Shop
★ Remaining life time
★ Batch
★ Branch and Bound
★ Scheduling
★ Material

論文目次

Contents iii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Description 2
1.2.1 Batch 2
1.2.2 Material Restrictions 3
1.3 Research Objectives 4
1.4 Research Methodology 4
1.5 Research Framework 5
Chapter 2 Literature Review 6
2.1 Job-Shop Scheduling 6
2.2 Disjunctive Graph 7
2.3 Batch 8
2.4 Time Lags 10
Chapter 3 Branch-and-Bound 12
3.1 Notations 13
3.2 Disjunctive Graph 15
3.3 Proposition 18
3.3.1 Lower Bound 19
3.3.2 Batch 20
3.3.3 The Characteristic of Machine 23
3.3.4 Computing E and S 25
3.3.5 Input and Output Determination 27
3.3.6 Material Consumption 29
3.4 Branch Scheme 29
3.5 Branch and Bound Algorithm 33
3.5.1 Branch and Bound 33
3.5.2 Find the Set of Batches 35
3.5.3 Fixing an Input Batch to Yield a Lower Bound 36
3.5.4 Fixing an Output Batch to Yield a Lower Bound 37
3.5.5 Establishing for Makespan 38
3.5.6 Create a Child Node β 39
Chapter 4 Computational Analysis 41
4.1 Test Problem Generation 41
4.2 Validation of the Branch and Bound Algorithm 42
4.3 Test Problem Efficient 44
Chapter 5 Conclusion 47
5.1 Research Contribution 47
5.2 Research Limitation 47
5.3 Future Research 48
Reference 49

參考文獻

[1] Azizoglu, M., Webster, S. (2001). Scheduling a batch processing machine with incompatible job families. Computers & Industrial Engineering, 39(3-4), 325–335.

[2] Brucker, P., Jurisch, B., Sievers, B. (1994). A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49(1-3), 107–127.
[3] Carlier, J., Pinson, E. (1989). An Algorithm for Solving the Job-Shop Problem. Management Science, 35(2), 164–176.
[4] Carlier, J., Pinson, E. (1994). Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research, 78(2), 146–161.

[5] Carlier, J., Rebaï, I. (1996). Two branch and bound algorithms for the permutation flow shop problem. European Journal of Operational Research, 90(2), 238–251.
[6] Centeno, G., Armacost, R. L. (1997). Parallel machine scheduling with release time and machine eligibility restrictions. Computers & Industrial Engineering, 33(1-2), 273–276.
[7] Chandru, V., Lee C.Y., Uzsoy, R. (1993) Minimizing total completion time on batch processing machines, International Journal of Production Research, 31(9), 2097-2121
[8] Chen, H., B. Du., George Q,. Huang. 2011. “Scheduling a Batch Processing Machine with Non-Identical Job Sizes: A Clustering Perspective.” International Journal of Production Research 49 (19): 5755–5778.
[9] Dupont, L., Dhaenens-Flipo, C. (2002). Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure. Computers & Operations Research, 29(7), 807–819.
[10] El Adl, M.K., Rodriguez, A.A., Tsakalis, K.S. (1996). Hierarchical modeling and control of re-entrant semiconductor manufacturing facilities. Proceedings of the 35th Conference on Decision and Control, Kobe, Japan.
[11] Fowler, J.W., Hogg, G.L., Phillips, D.T. (1992) Control of multiproduct bulk service diffusion/oxidation processes. liE Transactions,24, 8~96.
[12] Garey, M.R., Johnson, D.S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman
[13] Jamrus, T., Chien, C.F., Gen, M., Sethanan K. (2018). Hybrid Particle Swarm Optimization Combined with Genetic Operators for Flexible Job-Shop Scheduling Under Uncertain Processing Time for Semiconductor Manufacturing. IEEE Transactions on Semiconductor Manufacturing, 31(1), 32–41.
[14] Karimi, N., Davoudpour, H. (2015). A branch and bound method for solving multi-factory supply chain scheduling with batch delivery. Expert Systems with Applications, 42(1), 238–245.
[15] Li, X., Li, Y., Wang, Y. (2016). Minimizing makespan on a batch processing machine using heuristics improved by an enumeration scheme. International Journal of Production Research, 55(1), 176–186.
[16] Li, X.L., Li, Y.P., Wang, Y. (2017). Minimising makespan on a batch processing machine using heuristics improved by an enumeration scheme, International Journal of Production Research, 55:1, 176-186.
[17] Mason, S.J., Fowler, J.W., Carlyle, W.M., Montgomery, D.C. (2005). Heuristics for minimizing total weighted tardiness in complex job shops, International Journal of Production Research, 43:10, 1943-1963.
[18] Mazdeh, M. M., Sarhadi, M., Hindi, K. S. (2007). A branch-and-bound algorithm for single-machine scheduling with batch delivery minimizing flow times and delivery costs. European Journal of Operational Research, 183(1), 7486.
[19] Mönch, L., Fowler, J. W., Dauzère-Pérès S., Mason, S. J., Rose, O. (2011). A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations. Journal of Scheduling, 14(6), 583–599.
[20] Rossi, A., Dini, G. (2007). Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimization method. Robotics and Computer-Integrated Manufacturing, 23(5), 503–516.
[21] Sangsawang, C., Sethanan, K., Fujimoto, T., Gen, M. (2015). Metaheuristics optimization approaches for two-stage reentrant flexible flow shop with blocking constraint. Expert Systems with Applications, 42(5), 2395–2410.
[22] Scholl, W., Domaschke, J. (2000). Implementation of modeling and simulation in semiconductor wafer fabrication with time constraints between wet etch and furnace operations. IEEE Transactions on Semiconductor Manufacturing, 13(3), 273–277.
[23] Sforza, A., Sterle, C. (Eds.). (2017). Optimization and Decision Science: Methodologies and Applications. Springer Proceedings in Mathematics & Statistics.
[24] Sheen, G.J., Liao, L.W. (2007). A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags. European Journal of Operational Research, 181(1), 102–116.
[25] Tangudu, S. K., Kurz, M. E. (2006). A branch and bound algorithm to minimize total weighted tardiness on a single batch processing machine with ready times and incompatible job families. Production Planning & Control, 17(7), 728–741.
[26] Thitipong J., Chen F. C., Mitsuo G., Kanchana S. (2018). Hybrid Particle Swarm Optimization Combined with Genetic Operators for Flexible Job-Shop Scheduling Under Uncertain Processing Time for Semiconductor Manufacturing. IEEE transactions on semiconductor manufacturing, vol. 31, no. 1, 32-41.
[27] Uzsoy, R. (1995). Scheduling batch processing machines with incompatible job families. International Journal of Production Research, 33(10), 2685–2708.
[28] Uzsoy, R., Lee, CY. and Martin-Vega, L.A. (1992) A review of production planning and scheduling models in the semiconductor industry, part I: system characteristics, performance evaluation and production planning. liE Transactions, 24, 47-60.
[29] Wang, H.K., Chien, C.F., Gen, M. (2015). An Algorithm of Multi-Subpopulation Parameters with Hybrid Estimation of Distribution for Semiconductor Scheduling With Constrained Waiting Time. IEEE Transactions on Semiconductor Manufacturing, 28(3), 353–366.
[30] Xiao H. (2000). Introduction to semiconductor manufacturing technology. New Jersey: Prentice Hall.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2020-8-18

推文