A bi-objective flexible job shop scheduling problem with batching to minimize total tardiness and total number of tardy stage-outs

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：66

、訪客IP：3.142.12.158

姓名

林家禾(Chia-Ho Lin) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

(A bi-objective flexible job shop scheduling problem with batching to minimize total tardiness 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-7-31以後開放)

摘要(中)

本研究考慮了彈性零工式排程問題(Flexible job shop scheduling problem)，旨在最小化總延遲時間(Total tardiness)和Total number of tardy stage-outs，其中限制條件包括批次處理(Batching)和順序相依整備時間(Sequence-dependent setup time)。兩個目標的解可以用分離圖(Conjunctive graph)來表示。再者，Total number of tardy stage-outs的目標可以用layer的方式呈現在分離圖中。NSGA-II將被採用作為基於帕累托(Pareto-based)的方法尋找解答來解決雙目標問題。鄰域結構(Neighborhood structure)將被使用於突變運算子(Mutation operator)中且包含兩種類型的移動(Move)。移動的可行性保證(Feasibility guarantees)確保移動後不會產生循環(Cycle)。對於兩個目標的下界(Lower bounds)期待能確保在兩個目標的移動之後不會有增加目標值。兩種移動的偏好值(Preference value)有助於選擇哪個作業(Operation)或子區塊(Sub-block)將進行移動。此外，基於下界的階層式移動分類(Hierarchy of moves)將被應用以試圖增強多樣性。

摘要(英)

The study considers a flexible job-shop scheduling problem to minimize the total tardiness and the total number of tardy stage-outs with batching and sequence-dependent setup time. The solution representation for the two objectives can be described in a conjunctive graph. Besides, the objective of the total number of tardy stage-outs can be depicted in a disjunctive graph with layers. NSGA-II, a Pareto-based approach, is applied to find solutions for the bi-objective problem. The neighborhood structure is involved in the mutation operator, incorporating the two types of moves. Feasibility guarantees for the moves ensure that a cycle will not be generated after their execution. The lower bounds for the two objectives are found. The preference value for two types of moves helps select an operation or sub-block to move. Moreover, the hierarchy of moves based on the lower bounds is applied in an effort to enhance diversification.

關鍵字(中)

★ 彈性零工式排程問題
★ 分離弧線圖
★ 批次生產
★ 非支配排序遺傳演算法

關鍵字(英)

★ Flexible job-shop scheduling problem
★ conjunctive graph
★ batch processing
★ NSGA-II

論文目次

摘要 i
Abstract ii
Table of Contents iii
List of Figures v
List of Tables ix
Chapter 1. Introduction 1
1.1. Research background and motivation 1
1.2. Problem definition 6
1.3. Research objectives 6
1.4. Research methodology 7
Chapter 2. Literature review 11
2.1. Flexible job shop scheduling problem 11
2.2. Disjunctive graph 13
2.3. Lower bounds 16
Chapter 3. NSGA-II and Neighborhood operator 17
3.1. Batch-oblivious conjunctive graph 17
3.2. Neighborhood structures 20
3.2.1. Feasibility guarantees 22
3.2.2. Lower bounds 28
3.2.2.1. Lower bound on the total tardiness 29
3.2.2.2. Lower bound on the total number of tardy stage-outs 30
3.2.3. Hierarchy of moves 31
3.2.4. Three-level Diversification 33
3.3. NSGA-II 34
3.3.1. Initial solution 35
3.3.2. Fast non-dominated sorting method 36
3.3.3. Crowding distance method 36
3.3.4. Crossover operator 36
3.3.5. Generate an active schedule 46
3.3.6. Mutation operator 49
Chapter 4. Computational Experiments 53
4.1. Experiment design 53
4.2. Performance of non-dominated solutions 54
4.3. Computational results 56
Chapter 5. Conclusion 58
References 59
Appendix A. Proof of the theorem 3 62
Appendix B. Proof of the theorem 4 120
Appendix C. Fast non-dominated sorting method 131
Appendix D. Crowding distance method 132
Appendix E. Pareto fronts of each instance 133

參考文獻

Adams, J., Balas, E., Zawack, D., 1988. The Shifting Bottleneck Procedure for Job Shop Scheduling. Management Science. 34(3), 391-401.
Balas, E., 1969. Machine Sequencing via Disjunctive Graphs: An Implicit Enumeration Algorithm. Operations Research. 17(6), 941-957.
Bierwirth, C., Kuhpfahl, J., 2017. Extended GRASP for the Job Shop Scheduling Problem with Total Weighted Tardiness Objective. European Journal of Operational Research. 261(3), 835-848.
Brucker, P., 2007. Scheduling Algorithms. Fifth edition. Springer.
Brucker, P., Schlie, R., 1990. Job-shop scheduling with multi-purpose machines. Computing. 45(4), 369-375.
Carlier, J., Pinson, E., 1989. An Algorithm for Solving the Job-Shop Problem. Management Science. 35, 164-176.
Chaudry, I.A., Khan, A.A., 2016. A research survey: review of flexible job shop scheduling techniques. International transactions in operational research. 23(3), 591-991.
Chiang, H.Y., 2022. NSGA-II for solving a bicriteria general job shop scheduling problem with layers (Unpublished master’s thesis). National Central University, Taoyuan City.
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. Annals of Operations Research. 70, 281-306.
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T., 2002. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation. 6(2), 182-197.
Drießel, R., Mönch, L., 2012. An integrated scheduling and material-handling approach for complex job shops: a computational study. International Journal of Production Research. 50(20), 5966-5985.
Fowler, J.W., Mönch, L., 2022. A survey of scheduling with parallel batch (p-batch) processing. European Journal of Operational Research. 298(1), 1-24.
Gao, J., Sun, L., Gen, M., 2008. A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers & Operations Research. 35(9), 2892-2907.
García-León, 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. Computers & Operations Research. 108, 187-200.
Ham, A., 2017. Flexible job shop scheduling problem for parallel batch processing machine with compatible job families. 45, 551-562.
Knopp, S., Dauzère-Pérès, S., Yugma, C., 2017. A Batch-Oblivious Approach for Complex Job-Shop Scheduling Problems. European Journal of Operational Research. 263(1), 50-61.
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.
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 (Unpublished master’s thesis). National Central University, Taoyuan City.
Lei, D., 2010. A genetic algorithm for flexible job shop scheduling with fuzzy processing time. International Journal of Production Research. 48(10), 2995-3013.
Mati, Y., Dauzère-Pérès, S., Lahlou, C., 2007. A general approach for optimizing regular criteria in the job-shop scheduling problem. Research report 07/4/AUTO. Ecole des mines de Nantes, France.
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.
Mönch, L., Roob, S., 2018. A matheuristic framework for batch machine scheduling problems with incompatible job families and regular sum objective. Applied Soft Computing. 68, 835-846.
Ovacik, IM., Uzsoy, R., 1997. Decomposition Methods for Complex Factory Scheduling Problems. Kluwer Academic Publishers Boston.
Paulli, J., 1995. A hierarchical approach for the FMS scheduling problem. European Journal of Operational Research. 86(1), 32-42.
Pinedo, M., 2012. Scheduling: theory, algorithms, and systems. Fourth edition. Springer.
Poppenborg, J., Knust, S., Hertzberg, J., 2012. Online scheduling of flexible job-shops with blocking and transportation. European Journal of Industrial Engineering. 6(4), 497-518.
Rabiee, M., Zandieh, M., Ramezani, P., 2012. Bi-objective partial flexible job shop scheduling problem: NSGA-II, NRGA, MOGA and PAES approaches. International Journal of Production Research. 50(24), 7327-7342.
Roy, B., Sussmann, B., 1964. Les problemes d’ordon ordonnancement avec constraints disjunctives. SEMA, Note D.S., No. 9, Paris.
Shen, L., Buscher, U., 2012. Solving the serial batching problem in job shop manufacturing systems. European Journal of Operational Research. 221(1), 14-26.
Shen, L., Dauzère-Pérès, S., Neufeld, J.S., 2018. Solving the flexible job shop scheduling problem with sequence-dependent setup times. European Journal of Operational Research. 265(2), 503-516.
Taillard, E., 1994. Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing. 6, 108-117.
Tamssaouet, K., Dauzère-Pérès, S., Knopp, S., Bitar, A., Yugma, C., 2022. Multiobjective optimization for complex flexible job-shop scheduling problems. European Journal of Operational Research. 296, 87-100.
Tamssaouet, K., Dauzère-Pérès, S., 2023. A general efficient neighborhood structure framework for the job-shop and flexible job-shop scheduling problems. European Journal of Operational Research. 311(2), 455-471.
Thörnblad, K., Strömberg, A. B., Patriksson, M., Almgren, T., 2015. Scheduling optimisation of a real flexible job shop including fixture availability and preventive maintenance. European Journal of Industrial Engineering. 9(1), 126-145.
Türkyılmaz, A., Senvar, O., b, Ünal, İ, Bulkan, S., 2022. A hybrid genetic algorithm based on a two-level hypervolume contribution measure selection strategy for bi-objective flexible job shop problem shop including fixture availability and preventive maintenance. Computers & Operations Research. 141.
Verma, S., Pant, M., Snasel, V., 2021. A comprehensive review on NSGA-II for multi-objective combinatorial optimization problems. IEEE Access. 9, 57757-57791.
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.
Vilcot, G., Billaut, J. C., 2011. A tabu search for solving a multicriteria flexible job shop scheduling problem. International Journal of Production Research. 49(23), 6963-6980.
Xie, J., Gao, L., Peng, K., Li, X., Li, H., 2019. Review on flexible job shop scheduling. IET Collaborative Intelligent Manufacturing. 1(3), 67-77.
Yugma, C., Dauzère-Pérès, S., Artigues, C., Derreumaux, A., Sibille, O, 2012. A batching and scheduling algorithm for the diffusion area in semiconductor manufacturing. International Journal of Production Research. 50(8), 2118-2132.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2024-7-29

推文