A branch and bound algorithm for single machine with dependent due date and precedence constraints when minimizing makespan and total number of tardy jobs

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

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

Title:	A branch and bound algorithm for single machine with dependent due date and precedence constraints when minimizing makespan and total number of tardy jobs
Authors:	陳昱臻;Chen, Yu-Chen
Contributors:	工業管理研究所
Keywords:	單機排程問題;雙目標;分離弧線圖;分支界限演算法;single machine scheduling problem;bi-objective;disjunctive graph;branch and bound
Date:	2025-07-24
Issue Date:	2025-10-17 11:09:17 (UTC+8)
Publisher:	國立中央大學
Abstract:	本研究針對單機排程問題，考慮釋放時間相關的到期日條件，目標為同時最小化完工時間（Makespan）與遲交作業數（Total number of tardy jobs）。此問題包含不同到期日及前置限制，並透過分離弧線圖模型描述作業間的順序與依賴關係，以提供系統性的問題表達方式。為解決此問題，本研究提出雙目標分支定界演算法（Bi-objective branch-and-bound algorithm），結合向前排程（Forward Scheduling, FB）與向後排程（Backward Scheduling, BB）的動態策略，根據節點的下界值進行優先排序，並結合下界計算與剪枝規則提升搜尋效率。在下界部分，透過結合現有文獻中的方法進行改良，針對完工時間與遲交作業數分別估算精確下界；在剪枝部分，基於非支配解集動態更新的方式，排除無法貢獻改善的解，以集中計算資源於高潛力解。未來研究將著重於改進下界計算公式，使其能更準確地反映問題特性，進一步提升演算法的剪枝效率與精度；此外，優化排除準則（Elimination criteria），將進一步提升界限計算技術，增加解空間探索的效率，希望能在複雜約束下亦能維持穩定的解品質與計算效能。;This study addresses the single-machine scheduling problem with head-dependent due dates, aiming to minimize both the makespan and the total number of tardy jobs. The problem incorporates distinct due dates, and precedence constraints, represented through a disjunctive graph model that captures job sequencing and dependencies systematicall. To solve the problem, a bi-objective branch-and-bound algorithm is proposed, integrating dynamic forward scheduling (Forward Scheduling, FB) and backward scheduling (Backward Scheduling, BB) strategies. Nodes are prioritized based on lower bound values calculated for the two objectives, ensuring an efficient exploration of the solution space. The makespan and tardy job lower bounds are derived using improved methods from the literature, providing accurate estimates. Additionally, pruning rules based on dynamically updated non-dominated solution sets are employed to exclude suboptimal branches and focus on promising regions of the search space. Future research directions include refining the lower bound calculation formulas to better reflect the problem′s characteristics, thereby enhancing the algorithm′s pruning efficiency and accuracy. Furthermore, optimization of the elimination criteria will aim to advance bound calculation techniques, improving the efficiency of solution space exploration. The goal is to maintain stable solution quality and computational performance even under complex constraints.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

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

社群 sharing

Loading...