Trimming-the-state-space mechanism embedded branch-and-bound algorithm for two-parallel machines scheduling with availability constraints
學年 112
學期 2
出版（發表）日期 2024-03-03
作品名稱 Trimming-the-state-space mechanism embedded branch-and-bound algorithm for two-parallel machines scheduling with availability constraints
作品名稱（其他語言）
著者 Anh H. G. Nguyen; Gwo-Ji Sheen
單位
出版者
著錄名稱、卷期、頁數 Computers & Industrial Engineering 190
摘要 In this research, a trimming-the-state-space mechanism is embedded into the branch-and-bound algorithm to improve the performance of the pure branch-and-bound algorithm in finding a near-optimal solution with a pre-specified error bound. We propose general guidelines for trimming out nodes in the branching process while elimination criteria and bounding schemes are still utilized to eliminate nodes. As to the performance evaluation, we apply the proposed algorithm to a two-parallel machines scheduling problem with machine availability constraints. Computational results indicate that the proposed approximation algorithm performs very efficiently compared to the pure branch-and-bound algorithm in terms of run time and problem sizes. The error bound of the proposed algorithm is also demonstrated to be within the specified -value. Besides, it shows that our algorithm outperforms an existing heuristic from the literature in terms of solution quality.
關鍵字 Brand-and-Bound algorithm; Trimming-the-state-space approach; Parallel-machine scheduling problem; Machine availability constraints; Approximation algorithm
語言 en
ISSN 1879-0550
期刊性質 國外
收錄於 SCI
產學合作
通訊作者 Gwo-Ji Sheen
審稿制度 否
國別 GBR
公開徵稿
出版型式 ,電子版
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/128710 )

SDGS 尊嚴就業與經濟發展,產業創新與基礎設施,負責任的消費與生產