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

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

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

題名:	A branch and bound algorithm for single machine with dependent due date and precedence constraints when minimizing makespan and total number of tardy jobs
作者:	陳昱臻;Chen, Yu-Chen
貢獻者:	工業管理研究所
關鍵詞:	單機排程問題;雙目標;分離弧線圖;分支界限演算法;single machine scheduling problem;bi-objective;disjunctive graph;branch and bound
日期:	2025-07-24
上傳時間:	2025-10-17 11:09:17 (UTC+8)
出版者:	國立中央大學
摘要:	本研究針對單機排程問題，考慮釋放時間相關的到期日條件，目標為同時最小化完工時間（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.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

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

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

社群 sharing

資料載入中.....