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

NCUIR > School of Management at National Central University > Graduate Institute of Industrial Management > Electronic Thesis & Dissertation > Item 987654321/97331

Please use this identifier to cite or link to this item: https://ir.lib.ncu.edu.tw/handle/987654321/97331

Title:	A branch and bound algorithm for scheduling job family on flexible job shop with material assignment when minimizing makespan and total weighted material-wasted
Authors:	陳微筑;Chen, Wei-Chu
Contributors:	工業管理研究所
Keywords:	分支定界演算法;彈性零工式排程;雙目標優化;分離圖;材料分配;Branch and bound algorithm;Flexible Job shop scheduling;bi-objective;disjunctive graph;material assignment
Date:	2025-07-24
Issue Date:	2025-10-17 11:08:58 (UTC+8)
Publisher:	國立中央大學
Abstract:	本研究針對具材料分配限制的彈性零工式排程問題（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.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	24	View/Open

社群 sharing

Loading...