A branch and bound algorithm for scheduling job family on flexible job shop with material assignment when minimizing makespan and total weighted material-wasted

NCU Institutional Repository > 管理學院 > 工業管理研究所 > 博碩士論文 > Item 987654321/97331

請使用永久網址來引用或連結此文件: https://ir.lib.ncu.edu.tw/handle/987654321/97331

題名:	A branch and bound algorithm for scheduling job family on flexible job shop with material assignment when minimizing makespan and total weighted material-wasted
作者:	陳微筑;Chen, Wei-Chu
貢獻者:	工業管理研究所
關鍵詞:	分支定界演算法;彈性零工式排程;雙目標優化;分離圖;材料分配;Branch and bound algorithm;Flexible Job shop scheduling;bi-objective;disjunctive graph;material assignment
日期:	2025-07-24
上傳時間:	2025-10-17 11:08:58 (UTC+8)
出版者:	國立中央大學
摘要:	本研究針對具材料分配限制的彈性零工式排程問題（Flexible Job Shop Scheduling Problem, FJSP），提出一套基於分支定界演算法（Branch and bound algorithm）的求解框架，並同時對工序指派（Operation assignment）與材料配置（Material assignment）進行展枝操作。為提升完工時間下限估計之精度，本方法結合二階段排程特性，應用 Johnson’s Rule 進行下界計算，以達成最小完工時間（Makespan）與最小材料浪費（Material wasted）之雙目標優化。考量實務生產環境中，每道工序需消耗特定材料，而機台可同時裝載多種材料但受限於容量與成本，材料配置策略對整體資源使用效率具有關鍵影響。因此，本研究以分離圖（Disjunctive graph）建模工序間先後順序與機台使用狀態，並設計符合材料分配邏輯的節點展開與剪枝機制，提升解空間探索效率。此外，演算法中導入可動態更新之可排程集合及材料剩餘量追蹤機制，以強化排程彈性與計算效能。實驗結果顯示，本方法可有效求得在資源效率與加工時間兩目標間達成最佳權衡的帕累托前緣（Pareto front）解。;This study addresses the Flexible Job Shop Scheduling Problem (FJSP) with material assignment constraints and proposes a branch and bound-based solution framework. The framework simultaneously performs branching on both operation assignment and material assignment. To improve the accuracy of the makespan lower bound estimation, the method leverages a two-stage structure and applies Johnson’s rule for effective lower bound computation, aiming at bi-objective optimization of minimizing makespan and total weighted material waste. In practical manufacturing settings, each operation consumes specific materials, and machines can load multiple types of materials simultaneously, subject to capacity and cost constraints. Thus, material allocation strategies significantly impact overall resource efficiency. To reflect this, the problem is modeled using a disjunctive graph to represent both operation precedence and machine usage. A set of branching and pruning mechanisms tailored to material assignment is designed to effectively reduce the search space. The algorithm also incorporates a dynamically updated schedulable operation set and a material consumption tracking mechanism to enhance scheduling flexibility and computational efficiency. Experimental results demonstrate that the proposed method successfully obtains Pareto front solutions, achieving optimal trade-offs between resource efficiency and processing time.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	24	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....