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

NCUIR > School of Management at National Central University > Graduate Institute of Industrial Management > Electronic Thesis & Dissertation > Item 987654321/76531

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/76531

Title:	A Polynomial Time Approximation Scheme for Parallel Machine Scheduling with Machine Availability Constraints
Authors:	周書平;Chou, Shu-Ping
Contributors:	工業管理研究所
Keywords:	多項式時間近似方案;機器可用區間限制;平行機台;Polynomial time approximation scheme;Availability constraints;Parallel Machines
Date:	2018-07-20
Issue Date:	2018-08-31 11:26:41 (UTC+8)
Publisher:	國立中央大學
Abstract:	本研究討論不可分割工作的平行機台的最大完工時間最小化問題，其中機器具有任意的可用區間限制；假設至少有一台機器在整個規劃期間始終可用，這種設置契合在產業應用上和學術上的需求。例如，製造業中，這樣的限制來自於機器需要進行例行性維護。而在學術上，根據本研究的探討，過去沒有提出對輸入添加結構的多項式時間近似方案演算法（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.
Appears in Collections:	[Graduate Institute of Industrial Management] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	198	View/Open

社群 sharing

Loading...