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

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

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: 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	198	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....