A Polynomial Time Approximation Scheme for Parallel Machine Scheduling with Machine Availability Constraints

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

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

題名:	A Polynomial Time Approximation Scheme for Parallel Machine Scheduling with Machine Availability Constraints
作者:	周書平;Chou, Shu-Ping
貢獻者:	工業管理研究所
關鍵詞:	多項式時間近似方案;機器可用區間限制;平行機台;Polynomial time approximation scheme;Availability constraints;Parallel Machines
日期:	2018-07-20
上傳時間:	2018-08-31 11:26:41 (UTC+8)
出版者:	國立中央大學
摘要:	本研究討論不可分割工作的平行機台的最大完工時間最小化問題，其中機器具有任意的可用區間限制；假設至少有一台機器在整個規劃期間始終可用，這種設置契合在產業應用上和學術上的需求。例如，製造業中，這樣的限制來自於機器需要進行例行性維護。而在學術上，根據本研究的探討，過去沒有提出對輸入添加結構的多項式時間近似方案演算法（PTAS）。透過向輸入資料添加結構，本研究提供第一個多項式時間近似方案演算法（PTAS）。;This study analyzes the makespan minimization problem of non-preemptively scheduling identical parallel machines where machines may be unavailable during arbitrary time intervals. Assuming at least one machine is always available throughout the planning horizon, this setting is relevant practically and academically. For example, the unavailability occurs when machines are under preventive maintenance. So far as this study is concerned, no polynomial-time approximation scheme (PTAS) via structuring the input data has been proposed. This study aims to provide the first polynomial-time approximation scheme (PTAS) by adding structure to the input.
顯示於類別:	[工業管理研究所 ] 博碩士論文

文件中的檔案:

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

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

社群 sharing

資料載入中.....