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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：19

、訪客IP：3.141.202.187

姓名

周書平(Shu-Ping Chou) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

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

相關論文

★ 應用失效模式效應分析於產品研發時程之改善	★ 服務品質因子與客戶滿意度關係研究-以汽車保修廠服務為例
★ 家庭購車決策與行銷策略之研究	★ 計程車車隊派遣作業之研究
★ 電業服務品質與服務失誤之探討-以台電桃園區營業處為例	★ 應用資料探勘探討筆記型電腦異常零件-以A公司為例
★ 車用配件開發及車主購買意願探討(以C公司汽車配件業務為實例)	★ 應用田口式實驗法於先進高強度鋼板阻抗熔接條件最佳化研究
★ 以層級分析法探討評選第三方物流服務要素之研究-以日系在台廠商為例	★ 變動良率下的最佳化批量研究
★ 供應商庫存管理架構下運用層級分析法探討供應商評選之研究-以某電子代工廠為例	★ 台灣地區快速流通消費產品銷售預測模型分析研究–以聯華食品可樂果為例
★ 競爭優勢與顧客滿意度分析以中華汽車為例	★ 綠色採購導入對電子代工廠的影響-以A公司為例
★ 以德菲法及層級分析法探討軌道運輸業之供應商評選研究–以T公司為例	★ 應用模擬系統改善存貨管理制度與服務水準之研究-以電線電纜製造業為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本研究討論不可分割工作的平行機台的最大完工時間最小化問題，其中機器具有任意的可用區間限制；假設至少有一台機器在整個規劃期間始終可用，這種設置契合在產業應用上和學術上的需求。例如，製造業中，這樣的限制來自於機器需要進行例行性維護。而在學術上，根據本研究的探討，過去沒有提出對輸入添加結構的多項式時間近似方案演算法（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.

關鍵字(中)

★ 多項式時間近似方案
★ 機器可用區間限制
★ 平行機台

關鍵字(英)

★ Polynomial time approximation scheme
★ Availability constraints
★ Parallel Machines

論文目次

摘要 i
Abstract ii
Contents iii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Research Objective 2
1.3 Research Methodology 2
1.3.1 Approximation Scheme 2
1.4 Research Methodology 3
1.4.1 Structuring the Input 3
Chapter 2 Literature Review 6
2.1 Hardness Results 6
2.2 Related Problems and Previous Results 7
2.2.1 Cases with Machine Release Times 7
2.2.2 General Cases and Other Special Cases 7
2.3 Methodology: Polynomial Time Approximation Schemes (PTAS) 9
Chapter 3 Polynomial Time Approximation Scheme 11
3.1 Problem Definition & Preliminaries 11
3.1.1 Problem Definition 11
3.1.2 Preliminaries 12
3.2 Polynomial Time Approximation Scheme 15
3.2.1 Introduction to the Algorithm 15
3.2.2 Phase I 16
3.2.3 Phase II 16
3.2.4 Phase III 18
3.2.5 Phase IV 19
3.3 Numerical Example 20
3.3.1 The Input 20
3.3.2 Phase I with Numerical Example 22
3.3.3 Phase II with Numerical Example 22
3.3.4 Phase III with Numerical Example 23
3.3.5 Phase IV with Numerical Example 24
3.4 The Algorithm 26
Chapter 4 Computational Analysis 30
4.1 Algorithm Verification 30
4.2 Evaluation: Maximum Size of Instance for Heuristic Results 31
4.2.1 Examples Maximum Size Exanimated and Results 32
4.3 Sensitivity Analysis on Precision Parameter 33
Chapter 5 Conclusion 34
5.1 Main Results 34
5.2 Research Limitation 34
5.3 Future Research Direction 35
References 37

參考文獻

Caprara, A., Kellerer, H., & Pferschy, U. (2000). A PTAS for the Multiple Subset Sum Problem with Different Knacpsack Capacities. Inf. Proces. Lett., 73(3-4), 111-118.
Chang, S. Y., & Hwang, H.-C. (1999). The Worst-case Analysis of the MULTIFIT Algorithm for Scheduling Nonsimultaneous Parallel Machines. Discrete Applied Mathematics, 92(2-3), 135-147.
Chukuri, C., & Khanna, S. (2005). A Polynomial Time Approximation Scheme for the Multiple Knapsack Porblem. SIAM J. COMPUT., 35(3), 713-728.
Diedrich, F., Jansen, K., & Pascual, F. (2010). Approximation Algorithms for Scheduling with Reservations. Algorithmica, 58, 391-404.
Eyraud-Dubois, L., Mounie, G., & Trystram, D. (2007). Analysis of Scheduling Algorithms with Reservations. Paper presented at the IPDPS 2007, Long Beach, California, United States.
Fu, B., Huo, Y., & Zhao, H. (2011). Approximation Schemes for Parallel Machine Scheduling with Availability Constraints. Discrete Applied Mathematics, 159, 1555-1565.
Garey, M., & Johnson, D. S. (1978). ′Strong′ NP-completeness Results: Motivation, Examples, and Implications. Journal of the ACM, 25, 499-508.
Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, United States: Freeman.
Graham, R. L. (1966). Bounds for Certain Multiprocessing Anomalies. Discrete Applied Mathematics, 3, 313-318.
Graham, R. L. (1969). Bounds on Multiprocessing Timing Anonalies. SIAM J. APPL. MATH., 17(2), 416-429.
Hochbaum, D. S., & Shmoys, D. B. (1987). Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results. Journal of the ACM, 34, 144-162.
Hochbaum, D. S., & Shmoys, D. B. (1988). A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach. SIAM J. COMPUT., 17(3), 539-551.
Horowitz, E., & Sahni, S. (1974). Computing Partitions with Applications to the Knapsack Problem. Journal of the ACM (JACM), 21(2), 277-292.
Hwang, H.-C., Lee, K., & Chang, S. Y. (2005). The Effect of Machine Availability on the Worst-case Performance of LPT. Discrete Applied Mathematics, 148, 49-61.
Iverson, K. E. (1962). A Programming Language: John Wiley & Sons Inc.
Johnson, D. S. (1974). Approximation Algorithms for Combinatorial Problems. Journal of Computer and Systems Sciences, 9, 256-278.
Kaabi, J., & Harrath, Y. (2014). A Survey of Parallel Machine Scheudling uder Availability Constraints. International Journal of Computer and Information Technology, 3(2), 238-245.
Kellerer, H. (1998). Algorithms for Multiprocessor Scheduling with Machine Release Times. IIE Transactions, 30, 991.
Kellerer, H., Mansini, R., Sferschy, U., & Speranza, M. G. (2003). An Efficient Fully Polynomial Approximatiom Scheme for the Subset-sum Problem. J. Comput. Syst. Sci., 66(2), 349-370.
Lee, C.-Y. (1991). Parallel Machines Scheduling with Nonsimultaneous Machine Available Time. Discrete Applied Mathematics, 30, 53-61.
Lee, C.-Y. (1996). Machine Scheduling with An Availabiluty Constraint. Journal of Global Optimization, 9, 395-416.
Liao, L.-W., & Sheen, G.-J. (2008). Parallel Machine Scheduling with Machine Availability and Eligibility Constraints. European Journal of Operational Research, 184, 458-467.
Lin, G., Yujun, Y., & Lu, H. (1997). Exact Bounds of the Modified LPT Algorithms Applying to Parallel Machines Scheduling with Nonsimultaneous Machine Available Times. Applied Mathematics-A Journal of Chinese Universities, 12(1), 109-116.
Ma, Y., Chu, C., & Zuo, C. (2010). A Survey of Scheduling with Deterministic Machine Availability Constraints. Computers & Industrial Engineering, 58, 199-211.
Pinedo, M. L. (2016). Scheduling: Theory, Algorithms, and Systems (5th ed.): Springer.
Sahni, S. (1975). Approximate Algorithms for the 0/1 Knapsack Problem. Journal of the ACM (JACM), 22(1), 115-124.
Schuurman, P., & Woeginger, G. J. (2011). Approximation Schemes - A Tutorial. In R. H. Moring, C. N. Potts, A. S. Schulz, G. J. Woeginger, & L. A. Wolsey (Eds.), Lectures on Scheduling (pp. 1-68).
Suresh, V., & Ghaudhuri, D. (1996). Schduling of Unrelated Parallel Machines when Machine Availability Is Specified. Production Planning & Control: The Management of Operations, 7(4), 393-400.

指導教授

葉英傑(Yin-Chieh Yeh)

審核日期

2018-7-20

推文