學術產出-Theses
Article View/Open
Publication Export
-
題名 排程的隨機動態規劃模型及其在管理上的應用 作者 黃欣伸 貢獻者 余千智
黃欣伸日期 1986 上傳時間 5-May-2016 15:55:14 (UTC+8) 摘要 提要 排程問題乃在決定一工作站中一組工作之進行順序，爲一序列性決策問題，由於模型中對工作之進行狀態可以0和1表示個別工作之操作情形，因此本研究使用二元結構表示法表示排程模型之狀態，並應用於動態規劃方法的解題過程中以求得最佳序列。假設站中每一工作Ji有已知之到期日，而其完成日爲所有早於工作Ji完成之工作的操作時間總和加上完成工作Ji所需之操作時間。若完成日晚於到期日，必需支付違約金以作爲懲罰，而計算違約金之函數可爲任意函數，因此模型之最佳解乃在使最終支付之總違約金爲最少之工作順序。同時若由於技術或工作性質等因素，使得工作之進行有一定之順序限制時，二元結構表示法仍可以較節省之電腦記憶體求得符合優先順序限制之最佳工作順序，並可於允許改變工作之優先順序限制時，利用原模型之個別狀態最佳解求得新模型之最佳解。此外尚可將模型一般化，以允許工作之操作時間爲單變量或多變量之隨機變數，而求得該隨機模型之最佳工作順序。 參考文獻 參考書目 1. Baker, K.R., and Schrage, L.E. “Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence Related Tasks”, Operations Research, 26, 1, 111-120, (1978a) 2. Baker, K.R., and Schrage, L.E. “Dynamic Programming Solution of Sequening Problems with Precedence Constraints”, Operations Research, 26, 3, 444-449 (1978b) 3. Bellman, R. Dynamic Programming, Princeton University Press, Princeton N.J. (1957) 4. Butcher, W.S., “Stochastic Dynamic Programming for Optimal Resources Operations”, Water Resources Bulletin, 7, 1, 115-123 (1971) 5. Denardo, E.V., Dynamic Programming: Models and Applications, Pentice-Hall, Englewood Cliffs, N.J. (1982) 6. Gal, Shmuel, “Optiomal Management of a Multireservoir water Supply System”, Water Resources Research, 15, 4, 737-749 (1973) 7. Garey, M.R., “Optimal Binany Identification Procedures” SIAM Journal on Applied Mathematic, 23, 2, 173-186, (1972) 8. Gourlay, A.R., and Watson, G.A., Computational Methods for Matrix Eigenproblems, John Wiley & Sons (1973) 9. Graybill, F.A., Theory and Application of the Linear Model, Duxbury Press, North Scituate, Massachusetts, (1976) 10. Held, M., Karp, R.M., and Shareshian, R., “Assembly-line Balancing: Dynamic Programming with Precedence Constraints”, Operations Research, 11, 3, 442-459 (1963) 11. Johnson, R.A., and Wichern, D.W., “Applied Multivariate Statistical Analysis, Prentice-Hall, Englewood Cliffs, N.J. (1982) 12. Kennedy, Jr. W. J., and Gentle, J.E., Statistical Computing, Marcel Dekker, New York (1980) 13. Maidment, D.R., and Chow, V.T., “Stochastic State Variable Dynamic Programming for Reservoir System Analysis”, water Resources Research, 17, 6, 1578-1584, (1981) 14. McNaughton, R., “Scheduling with Deadlines and Loss Fuactions”, Management Science, 6, 1, 1-12, (1959) 15. Mitten, L.G., “Precedence Order Dynamic Programming” Management Science, 24, 1, 43-46, (1974) 16. Nash, R., “Controlled Jump Processes Models for Stochastic Scheduling”, International Journal of Control, 29, 6, 1011-1025, (1979) 17. Ross, S., Introduction to Stochastic Dynamic Programming, Academic Present, N. Y. (1983) 18. Schild, A., and Fredman, I.J., “On Scheduling Tasks with Associated Linear Loss Functions”, Management Science, 7, 3, 280-285 (1961) 19. Schild, A., and Fredman, I.J., “Scheduling Tasks with deadlines and Non-Lineer Loss Functions”, Management Science, 9, 1, 73-81 (1962) 20. Shwirmer, Joel. “On The N-Job. One-Machine Sequenice-Independent Schednling Problem with Tardness Penalties: A Branch-Found Solution.”, Management Science, 18, 6, B301-B303 (1972). 21. Steiner, G., “Single Machine Scheduling with Precedence Constraints of Dimension 2”, Mathematics of Opuations Research, 9, 2, 248-259. (1984) 22. Takeuchi, K., and Moreau, D.H., “Optimal Control of Multiunit Inter-basin Water Resource Systems”, Water Resources Research, 10, 3, 407-414 (1974) 23. Yu, C.C. Three Tree Structures For Data Processing in Dynamic Programming Computation, Master Dissertation, U.T. Austin, (1983) 24. Yu, C.C. The Optimization of Stochastic Multiperiod Systems By an Implicit Dynamic Programming Approoch Ph. D. Dissertation U. T. Austin, (1985) 描述 碩士
國立政治大學
統計學系資料來源 http://thesis.lib.nccu.edu.tw/record/#B2002006689 資料類型 thesis dc.contributor.advisor 余千智 zh_TW dc.contributor.author (Authors) 黃欣伸 zh_TW dc.creator (作者) 黃欣伸 zh_TW dc.date (日期) 1986 en_US dc.date.accessioned 5-May-2016 15:55:14 (UTC+8) - dc.date.available 5-May-2016 15:55:14 (UTC+8) - dc.date.issued (上傳時間) 5-May-2016 15:55:14 (UTC+8) - dc.identifier (Other Identifiers) B2002006689 en_US dc.identifier.uri (URI) http://nccur.lib.nccu.edu.tw/handle/140.119/91721 - dc.description (描述) 碩士 zh_TW dc.description (描述) 國立政治大學 zh_TW dc.description (描述) 統計學系 zh_TW dc.description.abstract (摘要) 提要 排程問題乃在決定一工作站中一組工作之進行順序，爲一序列性決策問題，由於模型中對工作之進行狀態可以0和1表示個別工作之操作情形，因此本研究使用二元結構表示法表示排程模型之狀態，並應用於動態規劃方法的解題過程中以求得最佳序列。假設站中每一工作Ji有已知之到期日，而其完成日爲所有早於工作Ji完成之工作的操作時間總和加上完成工作Ji所需之操作時間。若完成日晚於到期日，必需支付違約金以作爲懲罰，而計算違約金之函數可爲任意函數，因此模型之最佳解乃在使最終支付之總違約金爲最少之工作順序。同時若由於技術或工作性質等因素，使得工作之進行有一定之順序限制時，二元結構表示法仍可以較節省之電腦記憶體求得符合優先順序限制之最佳工作順序，並可於允許改變工作之優先順序限制時，利用原模型之個別狀態最佳解求得新模型之最佳解。此外尚可將模型一般化，以允許工作之操作時間爲單變量或多變量之隨機變數，而求得該隨機模型之最佳工作順序。 zh_TW dc.description.tableofcontents 目錄 第一章 緒論………1 第一節 模型簡介………1 第二節 研究動機與目的………2 第三節 本文結構………4 第二章 理論及解法之回顧與分析………6 第一節 確定性模型………6 第二節 隨機性模型………19 第三章 二元結構之隨機動態規劃模型………26 第一節 二元結構表示法及動態規劃方法………26 第二節 多變量常態分配………30 第三節 電腦模擬法………33 第四章 二元結構表示法………42 第一節 二元結構表示法之特性………42 第二節 一般模型………44 第三節 具有優先順序限制之模型………45 第四節 工作間優先順序之改變………47 第五章 排程之隨機動態規劃方法………50 第一節 工作操作時間之隨機性………50 第二節 模型最佳解之求解程序………51 第六章 數值結果與分析………55 第一節 確定性模型之電腦模擬………55 第二節 隨機性模型之電腦模擬………65 第七章 結論與建議………74 附錄………78 參考書目………96 zh_TW dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#B2002006689 en_US dc.title (題名) 排程的隨機動態規劃模型及其在管理上的應用 zh_TW dc.type (資料類型) thesis en_US dc.relation.reference (參考文獻) 參考書目 1. Baker, K.R., and Schrage, L.E. “Finding an Optimal Sequence by Dynamic Programming: An Extension to Precedence Related Tasks”, Operations Research, 26, 1, 111-120, (1978a) 2. Baker, K.R., and Schrage, L.E. “Dynamic Programming Solution of Sequening Problems with Precedence Constraints”, Operations Research, 26, 3, 444-449 (1978b) 3. Bellman, R. Dynamic Programming, Princeton University Press, Princeton N.J. (1957) 4. Butcher, W.S., “Stochastic Dynamic Programming for Optimal Resources Operations”, Water Resources Bulletin, 7, 1, 115-123 (1971) 5. Denardo, E.V., Dynamic Programming: Models and Applications, Pentice-Hall, Englewood Cliffs, N.J. (1982) 6. Gal, Shmuel, “Optiomal Management of a Multireservoir water Supply System”, Water Resources Research, 15, 4, 737-749 (1973) 7. Garey, M.R., “Optimal Binany Identification Procedures” SIAM Journal on Applied Mathematic, 23, 2, 173-186, (1972) 8. Gourlay, A.R., and Watson, G.A., Computational Methods for Matrix Eigenproblems, John Wiley & Sons (1973) 9. Graybill, F.A., Theory and Application of the Linear Model, Duxbury Press, North Scituate, Massachusetts, (1976) 10. Held, M., Karp, R.M., and Shareshian, R., “Assembly-line Balancing: Dynamic Programming with Precedence Constraints”, Operations Research, 11, 3, 442-459 (1963) 11. Johnson, R.A., and Wichern, D.W., “Applied Multivariate Statistical Analysis, Prentice-Hall, Englewood Cliffs, N.J. (1982) 12. Kennedy, Jr. W. J., and Gentle, J.E., Statistical Computing, Marcel Dekker, New York (1980) 13. Maidment, D.R., and Chow, V.T., “Stochastic State Variable Dynamic Programming for Reservoir System Analysis”, water Resources Research, 17, 6, 1578-1584, (1981) 14. McNaughton, R., “Scheduling with Deadlines and Loss Fuactions”, Management Science, 6, 1, 1-12, (1959) 15. Mitten, L.G., “Precedence Order Dynamic Programming” Management Science, 24, 1, 43-46, (1974) 16. Nash, R., “Controlled Jump Processes Models for Stochastic Scheduling”, International Journal of Control, 29, 6, 1011-1025, (1979) 17. Ross, S., Introduction to Stochastic Dynamic Programming, Academic Present, N. Y. (1983) 18. Schild, A., and Fredman, I.J., “On Scheduling Tasks with Associated Linear Loss Functions”, Management Science, 7, 3, 280-285 (1961) 19. Schild, A., and Fredman, I.J., “Scheduling Tasks with deadlines and Non-Lineer Loss Functions”, Management Science, 9, 1, 73-81 (1962) 20. Shwirmer, Joel. “On The N-Job. One-Machine Sequenice-Independent Schednling Problem with Tardness Penalties: A Branch-Found Solution.”, Management Science, 18, 6, B301-B303 (1972). 21. Steiner, G., “Single Machine Scheduling with Precedence Constraints of Dimension 2”, Mathematics of Opuations Research, 9, 2, 248-259. (1984) 22. Takeuchi, K., and Moreau, D.H., “Optimal Control of Multiunit Inter-basin Water Resource Systems”, Water Resources Research, 10, 3, 407-414 (1974) 23. Yu, C.C. Three Tree Structures For Data Processing in Dynamic Programming Computation, Master Dissertation, U.T. Austin, (1983) 24. Yu, C.C. The Optimization of Stochastic Multiperiod Systems By an Implicit Dynamic Programming Approoch Ph. D. Dissertation U. T. Austin, (1985) zh_TW
