具機器可用區間限制之平行機台排程之完全多項式近似方式;A Fully Polynomial Time Approximation Scheme for Parallel Machine Scheduling with Machine Availability Constraint

NCUIR > School of Management at National Central University > Graduate Institute of Industrial Management > Research Project > Item 987654321/78129

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

Title:	具機器可用區間限制之平行機台排程之完全多項式近似方式;A Fully Polynomial Time Approximation Scheme for Parallel Machine Scheduling with Machine Availability Constraint
Authors:	沈國基
Contributors:	國立中央大學工業管理研究所
Keywords:	具機器可用區間限制之平行機台排程;近似方式;類多項式動態規劃演算法;完全多項式近似方式;修剪求解空間法;Parallel machine scheduling with machine availability constraint;Approximation scheme;Pseudo-polynomial dynamic programming algorithms;Fully polynomial-time approximation scheme;Trimming-the-state-space approach
Date:	2018-12-19
Issue Date:	2018-12-20 10:57:19 (UTC+8)
Publisher:	科技部
Abstract:	本研究將探討平行機台排程問題，這排程問題以極小化總完工時間為目標，每一機台有一事先排定的維修時間。Mellouli 等於2009年提出一個類多項式動態規劃演算法(Pseudo-polynomial dynamic programming algorithms)來求解此問題。目前為止，並沒有學者對此問題提出完全多項式近似方式(Fully polynomial-time approximation scheme；FPTAS)來求解。Schuurman 與 Woeginger (2011) 以及 Woeginger (2000) 指出，為了保證能有具修剪求解空間法(trimming-the-state-space approach)為基礎的FPTAS的存在，排程問題與其動態規劃演算法須具有某些特性且能符合某些條件。根據我們初步的研究，本排程問題與Mellouli 等提出的動態規劃演算法都能符合這些特性及條件。因此，本研究嘗試依據修剪求解空間法，於動態規劃演算法各階段(phase)中減小求解之空間(Thin out the state space)，以降低求解所需要的時間，並求能掌控誤差的增長(Propagation of error)，以發展一個 ρ近似演算法(ρ-approximation algorithm)來求解此排程問題(在此 ρ=1+ε for any ε > 0；ε為誤差)，且此一個完全多項式近似方式的運算時間複雜度為問題大小（Input size）與 1/ε的多項式。 ;This research considers a parallel machine scheduling problem to minimize total completion time, each machine with a specified maintenance time. Mellouli et al. (2009) proposed a pseudo-polynomial dynamic programming algorithm to solve this problem. To the best of our knowledge, no researches have proposed fully polynomial-time approximation schemes (FPTAS) for the problem. Schuurman and Woeginger (2011) and Woeginger (2000) pointed out that to ensure the existence of FPTAS based on the trimming-the-state-space approach, the scheduling problem and its dynamic programming algorithm must have some properties and meet certain conditions. According to our preliminary study, both the scheduling problem and the dynamic programming algorithm proposed by Mellouli et al. meet these properties and conditions. Therefore, in this research, we try to apply the trimming-the-state-space approach to reduce the state space at each phase of dynamic program and to find a ρ-approximation algorithm, where ρ = 1 + ε for any ε> 0. The state space of solution in each phase of the dynamic programming algorithm is reduced, and the propagation of error is limited. The computational time complexity of the proposed FPTAS algorithm is polynomial of input size and 1/ε.
Relation:	財團法人國家實驗研究院科技政策研究與資訊中心
Appears in Collections:	[Graduate Institute of Industrial Management] Research Project

Files in This Item:

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

社群 sharing

Loading...