Scheduling job family on flexible job shop with parallel batching  and material assignment when minimizing makespan  and total weighted material-wasted

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：117

、訪客IP：18.226.180.122

姓名

馬宗祺(Tsung-Chi Ma) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

(Scheduling job family on flexible job shop with parallel batching and material assignment when minimizing makespan and total weighted material-wasted)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

我們在 Job family 特性的柔性作業車間調度問題(Flexible job shop scheduling problem)下，考慮材料分配(Material assignment)以及批次處理(Batching)的問題，目標為極小化最大完工時間(Makespan)以及極小化總加權物料浪費(Sum of total weighted material-wasted)。決定哪些的材料組合要裝載在機器上去做操作就是材料分配。而在柔性作業車間調度問題中特有的機台可行性(Machine eligibility)以及考慮到在我們的環境中並不是預先決定好、不變的，會隨著不同的作業的配方(Recipe)中的材料分配組合有所變化。我們使用了Batch oblivious conjunctive graph 的方式來建構分離圖(Conjunctive graph)，以同時呈現材料分配跟批次處理的結果。除了常見的弧屬性(Arc attribute)來表示時間(Time)外，並在圖中多加了第二個弧屬性(Arc attribute)來表示每一個物料個別的剩餘量(Remaining package size for each material)。
通過這樣的處理，我們除了可以得到常見的以時間為基礎的關鍵路徑(Critical path)外，還可以衍生出另一種基於浪費的加權材料總和的關鍵路徑。針對研究的問題，我們使用了非支配排序遺傳演算法(NSGA-II)，除了延伸前人Crossover operator之外，也將原本隨機的變異過程改為使用上述兩種關鍵路徑來定義鄰域結構(Neighborhood structure)取代，以及引入重疊值(Overlapping value)來幫助我們的搜索過程。我們還透過對移動(Move)的實際值評估將候選的移動(Candidate move)做分類，以此作為選擇移動的依據。

摘要(英)

This study aims to address the Flexible Job Shop Scheduling Problem (FJSP) with job family by incorporating considerations for material assignment and parallel batching
considerations, with the objective of minimizing the maximum makespan and the sum of weighted material-wasted. Material assignment involves deciding which combinations of materials to load onto machines for operations. In our scenario, machine eligibility is not predetermined but varies with different material assignment combinations, depending on the
recipes for various operations. To represent the decision on the operation sequencing, batching and the decision on the material assignment simultaneously, we employ an Extended
Batch Oblivious Conjunctive Graph (EBOCG). The EBOCG incorporates several arc attributes to capture essential information. On each arc of the conjunctive arc, we attach the second arc attribute to represent the remaining package size for each material. By employing the proposed conjunctive graph, in addition to the conventional time-based critical path commonly discussed in the literature, we can derive another type of critical path which is based on the sum of weighted material-wasted.
To address the research problem, we employ the Non-dominated Sorting Genetic Algorithm II (NSGA-II). Beyond extending the crossover operator from previous works, we
modify the original random mutation process by defining neighborhood structures using the aforementioned critical paths and introducing an overlapping value to aid the search process. Furthermore, we classify candidate moves based on the evaluation of actual move values, using this classification as the basis for move selection.

關鍵字(中)

★ 彈性零工式排程
★ 非支配排序遺傳驗算法-II
★ 柏拉圖前緣
★ 雙目標優化
★ 分離圖
★ 材料分配

關鍵字(英)

★ Flexible Job shop scheduling
★ NSGA-II
★ pareto front
★ bi-objective
★ disjunctive graph
★ material assignment

論文目次

Table of Contents
摘要 i
Abstract ii
Table of Contents iii
Table of Figures v
Table of Tables vii
Chapter 1. Introduction 1
1.1 Research motivation and background 1
1.2 Problem description 5
1.3 Research objectives 6
1.4 Research methodologies 7
Chapter 2. Literature Review 10
2.1 Flexible job shop scheduling problem 10
2.2 Disjunctive graph 12
2.3 Neighborhood structure 14
2.4 Non-dominated sorting genetic algorithm-II 15
Chapter 3. Research Methodology 16
3.1 Conjunctive graph representation for operations and material wasted 16
3.2 NSGA-II Algorithm 20
3.2.1 Initial solution 21
3.2.2 Non-dominated sorting 25
3.2.3 Crowding distance procedures 25
3.2.4 Genetic representation 26
3.3.4.1 Determine each machine-period 27
3.2.5 Crossover operator 32
3.2.6 Mutation operator 36
3.3.6.1 Feasibility check 41
3.3 Search strategy 41
Chapter 4. Computation Result 44
4.1. Comparison between selecting i by using two types of critical path and only use one type of critical 46
4.2. Comparison between selecting move by use R-classification and randomly selecting 47
Chapter 5. Conclusion 49
Acknowledgement 50
References 51
Appendix 56
Appendix A. Fast non dominated sort 56
Appendix B. Crowding-distance-assignment (?) 57
Appendix C. Illustration of crossover operator 58
Appendix D. Illustration of the results of two objective values influenced by six boolean conditions 71
Appendix E. MIP model 80

參考文獻

Akhbari, M., (2022). “Integration of multi-mode resource-constrained project scheduling under bonus-penalty policies with material ordering under quantity discount scheme for minimizing project cost.” Scientia Iranica E 29(1), 427-446.
Brucker, P., Jurisch, B., & Sievers, B., (1994). A branch and bound algorithm for the job-shop scheduling problem. Discret. Appl. Math. 49, 107–127.
Brucker, P., & Schlie, R. (1990). Job-shop scheduling with multi-purpose machines. Computing, 45, 369-375.
Bagheri, A., & Zandieh, M., (2011). “Bi-criteria flexible job-shop scheduling with sequence-dependent setup times - Variable neighborhood search approach.” Journal of Manufacturing Systems 30, 8-15.
Bierwirth C., & Kuhpfah J., (2017). “Extended GRASP for the Job Shop Scheduling Problem with Total Weighted Tardiness Objective.” European Journal of Operational Research 261, 1-23.
Baykasoglu, A., & Özbakır, L., (2010). “Analyzing the effect of dispatching rules on the scheduling performance through grammar-based flexible scheduling system.” International Journal of Production Economics 124, 369–381.
Blazewicz, J., & Finke, G., (1994). “Scheduling with resource management in manufacturing systems”. European Journal of Operational Research, 1-14.
Balas, E., (1969). Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. Operations research, 17(6), 941-957.
Braune, R. & Zäpfel, G., (2016). “Shifting bottleneck scheduling for total weighted tardiness minimization—A computational evaluation of subproblem and reoptimization heuristics”. Computers & Operations Research, 66, 130-140
Carlier, J., & Pinson, E., (1994). “Adjustment of heads and tails for the job-shop problem”. European Journal of Operational Research, 78(2), 146-161.
Carlier, J., & Pinson, É., (1989). “An algorithm for solving the job-shop problem”. Management science, 35(2), 164-176.
Coello, C. A., & Cortés, N. C., (2005). “A study on the Inverted Generational Distance (IGD) indicator.” IEEE Transactions on Evolutionary Computation, 9(1), 58-67.
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.
Dang, Q.-V., van Diessen, T., Martagan, T., & Adan, I., (2021). “A matheuristic for parallel machine scheduling with tool replacements”. European Journal of Operational Research, 291.
De Giovanni, L., & Pezzella, F., (2010). “An improved genetic algorithm for the distributed and flexible job-shop scheduling problem”. European Journal of Operational Research, 200(2), 395-408.
Garcia-Leon A. A., Dauzere-Peres S. & Mati Y., (2019). “An efficient Pareto approach for solving the multi-objective flexible job-shop scheduling problem with regular criteria”. Computers and operations research 108, 187-200.
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.
Ghiani, C. A., Ying, Z., de Vellis, J., & Gomez-Pinilla, F., (2007). “Exercise decreases myelin-associated glycoprotein expression in the spinal cord and positively modulates neuronal growth”. Glia, 966–975.
Geiger C. D., Kempf K. G., & Uzsoy R., (1997). “A tabu search approach to scheduling an automated wet etch station.” Journal of Manufacturing Systems ,16(2), 102-116.
González M. A., Vela C. R., & Varela R., (2015). “Scatter search with path relinking for the flexible job shop scheduling problem”. European Journal of Operational Research 245(1), 35-45.
Goh, C. K., & Tan, K. C., (2009). “Non-dominance ratio for preference articulation in evolutionary multiobjective optimization”. IEEE Transactions on Evolutionary Computation, 13(2), 347-365.
Ho, N. B., Tay, J. C., & Lai, E. M.-K., (2007). “An effective architecture for learning and evolving flexible job-shop schedules”. European Journal of Operational Research, 179(2), 316-333.
Ho, N. B., & Tay, J. C., (2005). Evolving dispatching rules for solving the flexible job-shop problem. In 2005 IEEE Congress on Evolutionary Computation (pp. 2848-2855).Nowicki E., Smutnicki C., (1996). “A fast taboo search algorithm for the job shop problem.”, Management Science 42, 797–813.
Jensen, M.T., (2003). “Generating robust and flexible job shop schedules using genetic algorithms”, IEEE Transactions on Evolutionary Computation 7, 275–288.
Jia, S., Hu, & Z.-H., (2014). “Path-relinking tabu search for the multi-objective flexible job shop scheduling problem”. Computers & Operations Research 47, 11–26.
Kuhpfah, J., & Bierwirth, C. (2016). “A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective”. Computers & Operations Research,Vol. 66,44-57
Kim, Y.K., Park, K., & Ko, J. (2003). “A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling”. Computers & Operations Research 30, 1151–1171.
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..
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.
Moradi, E., Fatemi Ghomi, S. M. T., & Zandieh, M., (2011). “Bi-objective optimization research on integrated fixed time interval preventive maintenance and production for scheduling flexible job-shop problem”. Expert Systems with Applications, 38, 7169-7178.
Mecler, J., Subramaninan, A., & Vidal, T., (2021). “A simple and effective hybrid genetic search for the job sequencing and tool switching problem”. Computers and Operations Research.
Mousakhani M., (2013). “Sequence-dependent setup time flexible job shop scheduling problem to minimize total tardiness.” International Journal of Production Research 51.12, 3476-3487.
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.
Pezzella, F., Morganti, G., & Ciaschetti, G., (2008). “A genetic algorithm for the flexible job-shop scheduling problem.” Computers & Operations Research 35, 3202–3212.
Privault, C., & Finke, G., (1995). “Modelling a tool switching problem on a single NC-machine”. Journal of Intelligent Manufacturing, 87–94.
Pinedo, M., & Singer, M., (1999). “A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop”. Naval Research Logistics, 46, 1-17
Pinedo, M. L., (2008). “Scheduling: Theory, Algorithms, and Systems (4th ed.)”. Springer.
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, 7327–7342.
Rahmati, S.H.A., & Zandieh, M., (2011). “A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem.” International Journal of Advanced Manufacturing Technology 58, 1115–1129.
Rahmati, S.H.A., Zandieh, M., & Yazdani, M., (2013). “Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem.” International Journal of Advanced Manufacturing Technology 64, 915–932.
Riquelme, J. C., Coello Coello, C. A., Montes Sánchez, G., & Mostaghim, S. (2015). “Interactive evolutionary multi-objective optimization based on Kriging models.” Information Sciences 298, 139-155.
Roy, B. & Sussman, B. (1964). Les problèmes d’ordonnancement avec contraintes disjonctives, Note DS No. 9 bis, SEMA, Montroug.
Sheen, G.-J. (2022). “Saving value-based Genetic Algorithm for Bi-objective Parallel Batch Machine Scheduling Problem”, NSTC project (110-2410-H-008-011-) final report.
Shen L., & Buscher U., (2012). “Solving the serial batching problem in job shop manufacturing systems”. European journal of operational research 221, 14-26.
Shen L., Dauzère-Pérès S., & Neufeld J. S., (2017). “Solving the Flexible Job Shop Scheduling Problem with Sequence-Dependent Setup Times.” European journal of operational research 265, 503-516.
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.
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(1), 87-100.
Van Laarhoven, P. J. M., (1988). Theoretical and computational aspects of simulated annealing (PhD thesis). Erasmus University Rotterdam.
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, 389-411.
Wang, S., &Yu, J., (2010). “An effective heuristic for flexible job-shop scheduling problem with maintenance activities.” Computers & Industrial Engineering, 436-447.
Wu, M. C., Lin, C. S., Lin, C. H., & Chen, C. F., (2017). “Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems”, Computers & Operations Research, 101-112.
Yuan, Y., & Xu, H. (2015)., “Multiobjective flexible job shop scheduling using memetic algorithms.” IEEE Transactions on Automation Science and Engineering, 12(1), 336-353.
Yazdani, M., Amiri, M., & Zandieh, M., (2010). “Flexible job-shop scheduling with parallel variable neighborhood search algorithm.” Expert Systems with Applications 37, 678–687.
Zoraghi, N., Najafi, A., & Niaki, S., (2015). “Resource Constrained Project Scheduling with Material Ordering: Two Hybridized Meta-Heuristic Approaches”. International Journal of Engineering - Transaction C: Aspects, 28, 896-902.
Zhang, H., & Gen, M., (2005). “Multistage-based genetic algorithm for flexible job-shop
scheduling problem.” Journal of Complexity International 11, 223–232

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2024-7-23

推文