|
學年
|
110 |
|
學期
|
2 |
|
出版（發表）日期
|
2022-03-28 |
|
作品名稱
|
An approximation algorithm for the two identical parallel machine problem under machine availability constraints. |
|
作品名稱（其他語言）
|
|
|
著者
|
Anh H. G. Nguyen, Gwo-Ji Sheen, Yingchieh Yeh |
|
單位
|
|
|
出版者
|
|
|
著錄名稱、卷期、頁數
|
Journal of Industrial and Production Engineering, Volume 40, Issue 1 |
|
摘要
|
This study addresses the scheduling problem of two identical parallel machines with the objective of minimizing the total completion time under the machine availability constraints. To the best of our knowledge, this study is the first to develop a fully polynomial-time approximation scheme (FPTAS), a solution method which has been neglected in past studies, to solve the studied problem. The FPTAS, which is based on a dynamic programming algorithm is developed by applying a trimming-the-state-space approach. Theoretical proofs of the error bound and the time complexity for the proposed FPTAS are also provided. The computational results indicate that the proposed FPTAS performs more efficiently than a dynamic programming algorithm in terms of both run time and problem size. The error bound of the FPTAS is demonstrated to be within the pre-specified error bound. |
|
關鍵字
|
Parallel machine scheduling; Machine availability constraints; Dynamic programming algorithm; Fully polynomial-time approximation scheme; Trimming-the-state-space approach |
|
語言
|
en |
|
ISSN
|
|
|
期刊性質
|
國外 |
|
收錄於
|
|
|
產學合作
|
|
|
通訊作者
|
Gwo-Ji Sheen |
|
審稿制度
|
否 |
|
國別
|
TWN |
|
公開徵稿
|
|
|
出版型式
|
,電子版 |