An integrated approach for solving Bi-Objective flexible job shop problem with preventive maintenance and parallel batching when minimizing makespan and total number of tardy stage-outs

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：28

、訪客IP：18.223.125.219

姓名

陳冠融(Guan-Rong Chen) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

(An integrated approach for solving Bi-Objective flexible job shop problem with preventive maintenance and parallel batching when minimizing makespan and total number of tardy stage-outs)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2029-1-31以後開放)

摘要(中)

本研究討論在彈性車間環境中考慮平行批次處理(parallel batching)及預防性維護(preventive maintenance)的問題。在半導體製造環境中，材料的更換依據其服務的工件批次數量或使用壽命，而在產能滿載的情況下材料經常依據服務的工件批次數量達到上限進行更換。並以極小化“stage-out”的數目及總完成時間(Makespan)為目標，以同時滿足短期及長期排程規劃。極大化“stage-outs”為半導體製造的每日績效之一，我們將其轉換為極小化延遲工作總件數來進行優化。而極小化工作總完成時間則視為長期目
標。
依據此問題特性，我們透過在分離圖(conjunctive graph)上呈現工作中各層級結束時連接終止節點(sink node)以計算其完成時間，並在各層間以分離弧(conjunctive arc)連接以表示各層級間的順序中。這種方法使我們能夠基於多個終止節點(sink node)的關鍵路徑(critical path)來定義鄰域結構(neighborhood structure)，並引入重疊值(overlapping
value)來優化搜索過程。我們定義一種以兩個目標為基礎的節省法(saving method)，用於評估移動(move)操作對於兩個目標優化效果。通過結合於多條關鍵路徑與兩個目標中切換的搜索策略(search strategy)中，期望優化局部搜索過程。

摘要(英)

This study discusses the consideration of incorporating parallel batching andpreventative maintenance in a flexible job shop scheduling problem. In the semiconductor manufacturing environment, materials are replaced according to the number of batches they serve or their service life, and at full capacity, materials are often replaced when the number of batches served reaches the upper limit. The goal is to minimize the number of stage-outs and the makespan to satisfy both short and long-term schedules. One of the daily performance metrics in semiconductor manufacturing is to maximize stage-outs, which we optimize by transforming it into minimizing the total number of tardy stage-outs. While minimizing makespan can be regarded as a long-term
goal.
Based on the characteristics of this problem, we propose a method for calculating completion times by representing the sink nodes at the end of each level in a conjunctive graph and connecting them with conjunctive arcs to indicate the order between layers. This approach allows us to define a neighborhood structure based on multiple critical paths to sink nodes and introduces overlapping values to optimize the
search process. We define a saving method based on two objectives to evaluate the optimization ability of move. By combining this method with a search strategy that switches between multiple critical paths and two objectives, we aim to optimize the local search process.

關鍵字(中)

★ 彈性零工式排程
★ 雙目標
★ 分離弧線圖
★ 節省法

關鍵字(英)

★ Flexible Job shop scheduling problem
★ bi-objective
★ disjunctive graph
★ saving method

論文目次

摘要 ..........................................................................................................................i
Abstract....................................................................................................................ii
Acknowledgement ..................................................................................................iii
Table of contents.....................................................................................................iv
List of Figures.........................................................................................................vi
List of Tables .........................................................................................................vii
Chapter 1 Introduction.............................................................................................1
1.1 Research motivation and background .........................................................1
1.2 Research problem........................................................................................3
1.3 Research objective ......................................................................................5
1.4 Research methodology................................................................................6
Chapter 2 Literature Review....................................................................................8
2.1 Flexible Job shop problem ..........................................................................8
2.2 Preventive Maintenance............................................................................10
2.3 Disjunctive graph ......................................................................................12
2.4 Search Strategy..........................................................................................14
Chapter 3 Research Methodology .........................................................................17
3.1 Disjunctive graph model ...........................................................................17
3.2 Neighborhood Structure............................................................................20
3.2.1 Feasibility guarantee ......................................................................21
3.2.2 Estimate of moves..........................................................................25
3.2.3 Lower bounds.................................................................................29
3.2.4 Saving method................................................................................35
3.2.5 Classification of moves by lower bounds on both objectives........38v
3.3 Search Strategy..........................................................................................40
Chapter 4 Computational analysis.........................................................................43
4-1 Experiment design ....................................................................................43
4-2 Advantage of Preference-Based Critical Path Selection...........................45
4-3 Analysis of Intensification Strategies with Saving Method......................52
Chapter 5 Conclusion ............................................................................................59
Reference ...............................................................................................................60
Appendix ...............................................................................................................64

參考文獻

1. Adams, J., Balas, E., Zawack, D., 1988. Shifting Bottleneck Procedure for Job Shop
Scheduling. Manage. Sci. 34, 391–401.
2. Balas, E., 1969. Machine sequencing via disjunctive graphs: An implicit enumeration
algorithm. Oper. Res. 17, 941–957.
3. Bierwirth, C., Kuhpfahl, J., 2017. Extended GRASP for the job shop scheduling
problem with total weighted tardiness objective. Eur. J. Oper. Res. 261(3), 835-848.
4. Braune, R., Zäpfel, G., Affenzeller, M., 2013. Enhancing local search algorithms for job
shops with min-sum objectives by approximate move evaluation. J. Sched. 16, 495–518.
5. Brucker, P., Jurisch, B., Sievers, B., 1994. A branch and bound algorithm for the jobshop scheduling problem. Discret. Appl. Math. 49, 107–127.
6. Carlier, J., Pinson, É., 1989. An algorithm for solving the job-shop problem. Manage.
Sci. 35, 164–176.
7. Carlier, J., Pinson, É., 1994. Adjustment of heads and tails for the job-shop problem.
Eur. J. Oper. Res. 78, 146-161.
8. Chaudhry, I.A., Khan, A.A., 2016. A research survey: Review of flexible job shop
scheduling techniques. Int. Trans. Oper. Res. 23, 551–591.
9. Dauzère-Pérès, S., Paulli, J., 1997. An integrated approach for modeling and solving the
general multiprocessor job-shop scheduling problem using tabu search. Ann Oper. Res.
70, 281-306.
10. Dorndorf, U., Pesch, E, 1995. Evolution based learning in a job shop scheduling
environment. Comput. Oper. Res. 22, 25-40.
11. Essafi, I., Mati, Y., Dauzère-Pérès, S., 2008. A genetic local search algorithm for
minimizing total weighted tardiness in the job-shop scheduling problem. Comput. Oper.
Res. 35, 2599–2616.
12. García-León, A.A., Dauzère-Pérès, S., Mati, Y., 2019. An efficient Pareto approach for
solving the multi-objective flexible job-shop scheduling problem with regular criteria.
Comput. Oper. Res. 108, 187–200.
13. Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R., 1979. Optimization and
approximation in deterministic sequencing and scheduling: A survey. Ann. Discret.
Math. 5, 287-326.
14. Jiang, X.Y., 2022. NSGA-II for solving a bicriteria general job shop scheduling problem
with layers. Institute of Industrial Management, National Central University.
15. Kreipl, S, 2000. A large step random walk for minimizing total weighted tardiness in a
job shop. J. Sched. 3,125-138.
16. Kuo, Y.H., 2023. An extended batch-oblivious approach for flexible Job shop with
batching and material consumption when minimizing the total weighted material
consumed and makespan. Institute of Industrial Management, National Central
University.
17. Manne, A.S., 1960. On the job-shop scheduling problem. Oper. Res. 8, 219–223.
18. Mason, S.J., Fowler, J.W. and Matthew Carlyle, W., 2002. A modified shifting
bottleneck heuristic for minimizing total weighted tardiness in complex job shops. J.
Sched. 5, 247-262.
19. Mati, Y., Dauzere-Pérès, S., Lahlou, C., 2011. A general approach for optimizing regular
criteria in the job-shop scheduling problem. Eur. J. Oper. Res. 212, 33–42.
20. Mokhtari, H., Hasani, A., 2017. An energy-efficient multi-objective optimization for
flexible job-shop scheduling problem. Comput. Chem. Eng. 104, 339–352.
21. Murovec, B., 2015. Job-shop local-search move evaluation without direct consideration
of the criterion’s value. Eur. J. Oper. Res. 241, 320-329.
22. Muth, J.F., Thompson, G.L., 1963. Industrial Scheduling. Prentice-Hall, Englewood
Cliffs, N.J.
23. Nowicki, E., Smutnicki, C., 1996. A fast taboo search algorithm for the job shop
problem. Manage. Sci. 42, 797–813. https://doi.org/10.1287/mnsc.42.6.797
24. Nguyen, H.G.A., 2022. Scheduling Parallel Batch Processing Machines with
Incompatible Families, Time Window Constraints and Machine Eligibility
Determination. Institute of Industrial Management, National Central University.
25. Pezzella, F., Merelli, E., 2000. Tabu search method guided by shifting bottleneck for the
job shop scheduling problem. Eur. J. Oper. Res. 120, 297–310.
26. Pinedo, M., Singer, M., 1999. A shifting bottleneck heuristic for minimizing the total
weighted tardiness in a job shop. Nav. Res. Logist. 46, 1–17.
27. Potts, C. N., & Kovalyov, M. Y., 2000. Scheduling with batching: A review. Eur. J. Oper.
Res. 120(2), 228-249.
28. Roy, B., Sussmann, B., 1964. Les Problems d’Ordon Ordonnancement Avec Constraints
Disjunctives. SEMA. Note D.S., No. 9, Paris.
29. Ruiz, R., Carlos García-Díaz, J., Maroto, C., 2007. Considering scheduling and
preventive maintenance in the flowshop sequencing problem. Comput. Oper. Res,
34(11), 3314–3330.
30. Singer, M., Pinedo, M., 1998. A computational study of branch and bound techniques
for minimizing the total weighted tardiness in job shops. IIE transactions, 30(2), 109-
118.
31. Singh, M.R., Singh, M., Mahapatra, S.S., Jagadev, N., 2016. Particle swarm
optimization algorithm embedded with maximum deviation theory for solving multiobjective flexible job shop scheduling problem. Int. J. Adv. Manuf. Technol. 85, 2353–
2366.
32. Snyman, S., Bekker, J., 2019. Comparing the performance of different metaheuristics
when solving a stochastic bi-objective job shop scheduling problem. In Proceedings of
the 2019 ORSSA Annual Conference.
33. Tamssaouet, K., Dauzère-Pérès, S., Knopp, S., Bitar, A., Yugma, C., 2021.
“Multiobjective Optimization for Complex Flexible Job-Shop Scheduling Problems.
Eur. J. Oper. Res. 296, 1-30.
34. Vilcot G., Billaut J.C., 2008. A tabu search and a genetic algorithm for solving a
bicriteria general job shop scheduling problem. Eur. J. Oper. Res. 190(2), 398-411.
35. Zhou, H., Cheung, W., Leung, L.C., 2009. Minimizing weighted tardiness of job-shop
scheduling using a hybrid genetic algorithm. Eur. J. Oper. Res. 194,637-649.

指導教授

沈國基

審核日期

2024-1-30

推文