NSGA-II for solving a bicriteria general job shop scheduling problem with layers

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：172

、訪客IP：3.19.30.232

姓名

江欣諭(Hsin-Yu Chiang) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

(NSGA-II for solving a bicriteria general job shop scheduling problem with layers)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2027-7-31以後開放)

摘要(中)

本研究主旨在探討具有工件具回流特性的雙目標零工式排程問題，在此我們選擇最大化“stage-out”的數目以及最小化工件總延遲時間做為目標，以同時滿足短期排程規劃及長期排程規劃。“stage-out”是實務中半導體環境的每日績效之一，我們將其轉換為最小化延遲工作總件數來優化它，而最小化工件總延遲時間則可視為長期目標，為因應不同的時程規劃，我們將給予兩目標不同的截止日期。另外，我們建立了一個新的分離弧線圖，其中每個工件都具有多個層級，每個層級包含多個操作，而在層和層之間有額外的弧線去界定各層級的順序。
針對我們研究的問題，我們提出了不同以往的非支配排序遺傳演算法，將原本完全隨機的變異過程改由使用局部搜索中的鄰里結構取代，盡可能有依據的改善當前的解。在實驗中我們分成兩大部分，其中一個實驗我們和過去的實例做比較，另一個實驗則是針對改善後的非支配排序遺傳演算法評估效益，最終實驗結果也證明了此改善能有效的在短時間內找到還不錯的解。

摘要(英)

The main purpose of this study is to solve the bi-objective of job shop scheduling problem with recirculation. We choose to maximize the number of "stage-out" and minimize the total tardiness as objectives. Try to meet the requirements of short-term scheduling and long-term scheduling at the same time. "Stage-out" is one of the daily performances in a practical semiconductor environment, and we optimize it by converting it to minimize the total number of tardy jobs. While minimizing the total tardiness can be considered a long-term goal. For two different targets, we also give two different due dates. In addition, we proposed a new disjunctive graph, which contains multiple layers in a job and each layer contains multiple operations. There also introduce additional arcs between layers to define the processing order.
In our research, we propose a non-dominated sorting genetic algorithm (NSGA-II) that is different from the traditional one. That we do the mutation operator with the neighborhood structures of local search and aim to find a good solution in a short time. In the experimental, we do two tests. First, we compare with benchmark instances to evaluate the performance of NSGA-II. Second, we compare the NSGA-II we proposed and the NSGA-II that all of the processes are depend on randomly generate. The result proves that this improvement can effectively speed up finding a good solution.

關鍵字(中)

★ 零工式排程
★ 工件回流
★ 雙目標
★ 分離弧線圖
★ 非支配排序遺傳演算法

關鍵字(英)

★ Job shop problem
★ recirculation
★ bi-objective
★ disjunctive graph
★ NSGA-II

論文目次

摘要 i
Abstract i
Table of contents ii
List of Figures iv
List of Tables v
Chapter 1 Introduction 1
1.1 Research motivation and background 1
1.2 Research problem 2
1.3 Research objective 3
1.4 Research methodology 4
1.5 Research framework 4
Chapter 2 Literature Review 6
2.1 Job shop problem 6
2.2 Disjunctive graph 9
Chapter 3 Research Methodology 12
3.1 Disjunctive graph 12
3.2 Neighborhood operator 14
3.2.1 Neighborhood structure 15
3.2.2 Feasibility guarantee 16
3.2.3 Connectivity property 16
3.3 NSGA-II algorithm 17
3.3.1 Encoding and initialization 19
3.3.2 Non-dominated sorting 21
3.3.3 Crowding distance procedures 21
3.3.4 Crossover operator 22
3.3.5 Mutation operator 23
Chapter 4 Computational analysis 24
4.1 Test problem generation 24
4.2 Fixing NSGA-II parameters 25
4.3 Computational results 26
4.3.1 Job shop instances of Singer and Pinedo (1998) 26
4.3.2 Objective improvement 28
Chapter 5 Conclusion 36
5.1 Research contribution 36
5.2 Research limitation 37
5.3 Future research 37
Reference 38
Appendix A – Lemma 1 41
Appendix B - Fast non dominated sort 42
Appendix C - Crowding-distance-assignment (I) 43

參考文獻

[1] Adams, J., Balas, E., & Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management science, 34(3), 391-401.
[2] B. Roy & B. Sussmann. (1964). Les probl`emes d’ordonnancement avec constraintes disjonctives. SEMA, Note D.S., No. 9, Paris.
[3] Balas, E., & Vazacopoulos, A. (1998). Guided local search with shifting bottleneck for job shop scheduling. Management science, 44(2), 262-275.
[4] Balas, E. (1969). Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. Operations research, 17(6), 941-957.
[5] Braune, R., & Zäpfel, G. (2016). Shifting bottleneck scheduling for total weighted tardiness minimization—A computational evaluation of subproblem and re-optimization heuristics. Computers & Operations Research, 66, 130-140.
[6] Braune, R., Zäpfel, G., & Affenzeller, M. (2013). Enhancing local search algorithms for job shops with min-sum objectives by approximate move evaluation. Journal of Scheduling, 16(5), 495-518.
[7] Carlier, J., & Pinson, E. (1994). Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research, 78(2), 146-161.
[8] Carlier, J., & Pinson, É. (1989). An algorithm for solving the job-shop problem. Management science, 35(2), 164-176.
[9] Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. A. M. T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6(2), 182-197.
[10] Dorndorf, U. and Pesch, E., (1995) Evolution based learning in a job shop scheduling environment. Computers and Operations Research; 22:25–40.
[11] Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. In Annals of discrete mathematics. Vol. 5. Elsevier, 1979. 287-326.
[12] Kreipl, S. (2000). A large step random walk for minimizing total weighted tardiness in a job shop. Journal of Scheduling, 3(3), 125-138.
[13] Kuhpfahl, J., & Bierwirth, C. (2012). A new neighbourhood operator for the job shop scheduling problem with total weighted tardiness objective. In Proceedings of international conference on applied mathematical optimization and modelling (pp. 204-209).
[14] Kuhpfahl, J., & Bierwirth, C. (2016). A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective. Computers & Operations Research, 66, 44-57.
[15] Braune, R., Zäpfel, G., & Affenzeller, M. (2013). Enhancing local search algorithms for job shops with min-sum objectives by approximate move evaluation. Journal of Scheduling, 16(5), 495-518.
[16] Mason, S. J., Fowler, J. W., & Matthew Carlyle, W. (2002). A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops. Journal of Scheduling, 5(3), 247-262.
[17] Mati, Y., Dauzère-Pérès, S., & Lahlou, C. (2011). A general approach for optimizing regular criteria in the job-shop scheduling problem. European Journal of Operational Research, 212(1), 33-42.
[18] 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.
[19] Murovec, B. (2015). Job-shop local-search move evaluation without direct consideration of the criterion’s value. European Journal of Operational Research, 241(2), 320-329.
[20] Muth, J. F., & Thompson, G. L. (Eds.). (1963). Industrial scheduling. Prentice-Hall.
[21] Nowicki, E., & Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management science, 42(6), 797-813.
[22] Pezzella, F., & Merelli, E. (2000). A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research, 120(2), 297-310.
[23] 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.
[24] Snyman, S., & Bekker, J. F. (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.
[25] Vilcot, G., & Billaut, J. C. (2008). A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem. European Journal of Operational Research, 190(2), 398-411.
[26] Zhou, H., Cheung, W., & Leung, L. C. (2009). Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. European Journal of Operational Research, 194(3), 637-649.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2022-7-5

推文