政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/90914
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  Items with full text/Total items : 109951/140892 (78%)
Visitors : 46196940      Online Users : 758
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
    •  Adv. Search
    Home ‧ Login ‧ Upload ‧ Help ‧ About ‧ Administer Goto mobile version


    Please use this identifier to cite or link to this item: https://nccur.lib.nccu.edu.tw/handle/140.119/90914


    Title: 二元結構動態規劃方法在多機排程問題上的應用
    Authors: 董永寬
    Contributors: 余千智
    董永寬
    Date: 1987
    Issue Date: 2016-05-04 17:12:51 (UTC+8)
    Abstract: 提要
    本論文所擬探討之對象為具有優先順序關係的隨機排程問題，包括單機、多流程機、二平行機、二平行多流程機等類型，此等問題之目的在決定工作站中一組工作執行上的先後順序，以使得其最終回應成本的期望值為最佳。
    本文使用動態規劃演算法，並以二元結構的狀態及順序表示法來求得模型的最佳序列解，並對增減優先順序限制、增減機器、增減工作、規則選用等不同的決策支擾模型作有效率的求解，同時以電腦模擬方法對決策支援環境下的解題速度與重新開始原求解模型的解題速度作一CPU時間的數值此較。
    本研究同時亦允許工作的處理時間和工作的到期日為一服從多變量常態分配函數的隨機向量，以模擬方法產生資料的樣本值來求得隨機模型的最佳期望解。
    Reference: 參考書目
    1. Adolphson, D.L., " Single machine job sequencing with precedence constraints " , SIAM J. Computing , 6(1) , 40 - 54 . (1977)
    2. Akers, S.B., " A graphical approach to production scheduling problems. " Operations Research , 4(2) , 244 - 245 , (1956)
    3. Ashour, S., Moore, T.E. and Chin, N.K., " An implicit enumeration algorithm for the nonpreemptive shop scheduling problem " . AIIE Transactions , 6(1) , 62 - 72 , (1974)
    4. Bagga, P.C.. " N-job, 2-machine sequencing problem with stochastic service times" , Opsearch , 7 , 184 - 197 , (1970)
    5. Baker, K.R., Introduction to sequencing and scheduling . John Wiely & Sons , N.Y. , (1974)
    6. 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)
    7. Bakshi, M.S. and Arora, S.R.. " The sequencing problem " , Management Science , 16(4) . B247 - B263 . (1969)
    8. Bellman, R., Dynamic programming , Princeton university press , Princeton N.J. (1957)
    9. Bowman, E.H., " The schedule-sequencing problem Operations Research , 7(4) . 621 – 624 . (1959)
    10. Box, G.E.P. and Muller, M.E., " A note on the generation of random normal deviates " , Ann. Math. Stat. , 29(2) .. 610 - 611 . (1958)
    11. Brooks G.H. and White, C.R.. " An algorithm for finding optimal or near optimal solutions to the production scheduling problem " . Journal of Industrial Engineering . 16(1) : 34 - 40 . (1965)
    12. Bruno, J. and Downey, P., " Sequencing tasks with exponential service times on two machines " , Technical report, Department of electrical engineering and computer science , University of California , at Santa Barbara , (1977)
    13. Burns , R.N. and Steiner. G.. " Single machine scheduling with series - parallel precedence contraints " Research report Corr 81-5. Department of combinatories and optimization , The university of Waterloo , Waterloo , Canada . (1981)
    14. Coffman, E.G., Computer and job - shop scheduling theory . John Wiley & Sons , N.Y. (1976)
    15. Coffman, E.G. and Graham, R.L., " Optimal scheduling for two-processor system" . Acta Information , 1(3) , 200 - 213 , (1972)
    16. Conway, R.W., Maxwell. W.L. and Miller. L.W., Theory of scheduling . Addison-Wesley , Reading , Mass . (1967)
    17. Cunningham, A.A. and Dutta, S.K.. " Scheduling jobs with exponentially distributed processing times on two machines of a flow shop " . Naval Research Logistics Quarterly , 16(1) , 69 - 31 . (1973)
    18. Dempster, M.A.H. Lenstra, J.K. and Rinooy Kan, A.H.G., Deterministic and stochastic scheduling . D.Reidel Publishing Company , Holland . (1982)
    19. Denardo, E.W. Dynamic Programming : models and application . Pentice - Hall . Englewood Cliffs , N.J. (1982)
    20. Derman, C., Lieberman, G. and Ross, S., " A renewal decision problem " Management Science , 24(5) , 554 - 561 , (1978)
    21. Fisher, M.L., " A dual algorithm for the one-machine scheduling problem " Mathematical Programming , 11(2) , 458 - 481 .. (1976)
    22. French. S., Sequencing and scheduling : An introduction to the mathematics of the job-shop . John Wiely & Sons , N.Y. , (1982)
    23. Garey, M.R. " Optimal binary identification procedures " , SIAM Journal on Applied Mathematic , 23(2) , 173 - 186 . (1972)
    24. Garey, M.R. and Joshon, D.S., " Two-processor scheduling with start-times and deadlines " . Bell Laboratories , Murray Hill , N.J. (1975)
    25. Gelders, L. and Kleindorfer, P.R., " Coordinating aggregate and detailed scheduling in a one-machine job shop , part I, theory " . Operations Research, 22(1) , 46 - 60 . (1974)
    26. Geoffrion , A.M., " Duality in nonlinear programming . a simplified applications oriented development " , SIAM Review , 13(1) , 1 - 37 . (1971)
    27. Gilmore, P.C. and Gomory, R.E., " Sequencing a one-state variable machine : a solvable case of the traveling salesman problem " , Operations Research , 12(4) , 555 - 679 . (1964)
    28. Glazebrook, K.D., " On single machine sequencing with order constraints " Naval Research Logistics Quarterly , 27 . 123 -130. (1980)
    29. Gonzalez, T. and Sahni, S., " Flowshop and jobshop schedules : complexity and approximation " Operations Research , 26(1) , 36 - 52 . (1978)
    30. Graybill, F.A.. Theory and application of the linear model , Duxbury Press . North Scituate , Massachusetts . (1976)
    31. Hariri, A.M.A. and Potts.C.M., " Algorithm for two machine flow shop sequencing with precedence constraints " Europ.J.of.0ps.Res., 17(2) , 238 - 248 . (1984)
    32. Held. M., Karp, R.M., " A dynamic programming approach to sequencing problems " , J. SIAM , 10(2) , 196 -210 . (1962)
    33. Held, M., Karp, R.M. and Shareshian, R., " Assembly - line balancing : dynamic programming with precedence constraints " , Operations Research , 11(3) , 442 - 459 . (1963)
    34. Heller, J., " Some numerical experiments for an M x J flow-shop and its decision theoretical aspects " . Operations Research, 8(1) , 178 - 184 . (1960)
    35. Horn, W.A., " single-machine job sequencing with treelike precedence ordering and linear delay penalties " , SIAM J. Appl. Math , 23(2) , 189 - 202 . (1972)
    36. Hu, T.C., " Parallel sequencing and assembly line problem " , Operations Research , 9(6) , 841 -848 . (1961)
    37. Ignall. E. and Schrage, L., " Application of the branch-and-bound technique to some flow-shop scheduling problems " , Operations Research , 13(3) , 400 - 412 . (1965)
    38. Jackson, J.R., " An extension of Johnson`s results on job lot scheduling " Naval Research Logistics Quarterly , 3 201 - 203 . (1956)
    39. Johnson, R.A. and Wichern, D.W., Applied multivariate statistical analysis. Prentice - Hall , Englewood Cliffs , N.J. (1982)
    40. Johnson, S.M., " Optimal two or three-stage production schedules with setup times included " . Naval Research Logistics Quarterly, 1(1) , 61 - 68 . (1954)
    41. Lageweg, B.J., Lenstra, J.K. and Rinnooy Kan, A.H.G., " Minimizing maximum lateness on one machine : computation experience and some application" , Statistca Neerlandica , 30 , 25 - 41 , (1976)
    42. Law. A.M. and Kelton, W.D., Simulation modeling and analysis. McGraw - Hill , (1982)
    43. Lawler, E.L., " On scheduling with deferral costs " , Management science , 11(3) , 280 - 288 . (1964)
    44. Lawler, E.L., " Optimal sequencing of a single machine subject to precedence constraints " , Management science , 19(5) , 544 - 546 . (1973)
    45. Lenstra, J.K.. Sequencing by enumerative methods. Mathematisch Centrum , Amsterdam , (1977)
    46. Marsaglia, G. and Bray, T.A., " A convenient method for generating normal variables " SIAM Review , 6(2) , 260 - 264 . (1964)
    47. Mcmahon, G.B., " Optimal production schedules for flow shops " . Operations Research , 15(3) , 473 - 481 , (1967)
    48. Mcmahon, G.B. and Florian, M., " On scheduling with ready time and due dates to minimizing maximum lateness " . Operations Research. 23(3) , 475 - 482 . (1975)
    49. McNaughton, R. " Scheduling with deadlines and loss functions " . Management Science , 6(1) , 1 - 12 . (1959)
    50. Michael, H.R.. " Scheduling independent tasks on parallel processor " Management Science , 12(5) , 437 -447 . (1966)
    51. Mitten, L.G., "Precedence order dynamic programming" Management Science , 21(1) , 43 - 46 . (1974)
    52. Monma, C.L., " Sequencing with general precedence constraints. " Discrete Appl. Math , 3 , 137 -150 . (1981)
    53. Moore, J.M., " An n job, one machine sequencing algorithm for minimizing the number of late jobs " , Management Science , 15(1) , 102 - 109 . (1968)
    54. Morton, T.E. and Dharan, B.G.. " Algoristics for single machine sequencing with precedence constraints. " Management Science, 24(10) , 1011 - 1020 . (1978)
    55. Panwalkar, S.S. and Khan, A.W... " An order flow shop sequencing with mean completion time criterion " Int. J. Prod. Res. , 14 , 631 - 635 , (1981)
    56. Panwalkar. S.S. and Woollam, C.R.. " Ordered flow shop problems with no in-process waiting : further result " , J.Opl.Res.Soc. 31 , 1039 - 1043 . (1980)
    57. Pinedo, M.L. and Weiss, G., " Scheduling of stochastic tasks on two parallel processors " , Naval Research Logistics Quarterly , 26 . 527 -535. (1979)
    58. Pinedo, M.L., " Minimizing makespan with bimodal processing time distribution " Management Science , 27 (5) . 582 - 586 . (1981)
    59. Pinedo, M.L.. " A note on the two machine job shop with exponential processing times " Naval Research Logistics Quarterly , 28 . 693 - 696. (1981)
    60. Pinedo. M.L., " Minimizing the expected makespan in stochastic flow shops " Operations Research , 30(1) , 148 - 162 . (1982)
    61. Pinedo, M.L. and Ross, S.M.. " Minimizing the expected makespan in stochastic open shop " Adv. in Appl. Probab., 14 , 898-911 , (1982)
    62. Pinedo, M.L., " Stochastic scheduling with release dates and due dates " Operations Research , 31(3) , 559 - 572 . (1983)
    63. Pinedo, M.L., " A note on stochastic shop models in which jobs have the same processing requirements on each machine " Management Science , 31(7) , 840 - 846 , (1985)
    64. Potts, C.N., " A lagrangean based branch and bound algorithm for single machine sequencing with precedence constraints to minimizing total weighted completion time " . Management Science , 31 (10) , 1300 - 1311 . (1985)
    65. Pritsker, A.A.B., Watters, L.J. and Wolfe , P.M., " Multiproject scheduling with limited resources: a zero-one programming approach " . Management Science , 16(1) , 93 - 108 . (1969)
    66. Reddi, S.S. and Ramamoorthy, "On the flow-shop sequencing problem with no wait in process " , Operational Research Quarterly , 23 , 323 - 331 , (1972)
    67. Rinnooy Kan, A.H.G. Machine scheduling problems , Martinus Nijhoff , The Hague , (1976)
    68. Rinnooy Kan, A.H.G., Lazeweg, B.J. and Lenstra, J.K, " Minimizing total costs in one machine scheduling " , Operations Research , 23(5) , 908 -927 . (1975)
    69. Ross, S., Introduction to stochastic dynamic programming. Academic Press , N.Y. (1983)
    70. Schild, A. and Fredman, I.J., " On scheduling tasks with associated linear loss function " , Management Science , 7(3) , 280 - 285 , (1961)
    71. Schrage, L.E. and Baker, K.R., "Dynamic programming solution of sequening problem with precedence constraints " Operations Research . 26(3) . 444 - 449. (1978b)
    72. Sidney, J.B., "A decomposition algorithm for sequencing with general precedence constraints" . Math. of Ops. Res., 6(2) , 190 -204 . (1981)
    73. Sidney, J.B. and Steiner, G., " Optimal sequencing by modular decomposition: Polynomial algorithm " , Operations Research , 34(4) . 606 - 612. (1986)
    74. Smith, W.E., "Various optimizers for single-state production" . Naval Research Logistics Quarterly, 3(1), 59 - 66 . (1956)
    75. Smith, R.D. and Dudek, R.A., " A general algorithm for the solution of the n-job, m-machine sequencing problem of the flowshop " , Operations Research , 15(1) . 71 - 82 . (1967)
    76. Steiner, G., "Single machine scheduling with precedence constraints of dimension ? " . Mathematics of Operations Research , 9(2) , 248 -259 . (1984)
    77. Szwarc. W... "Solution of the Akers-Friedman scheduling problem " Operations Research , 8 , 782 -788 . (1960)
    78. Szwarc, W., " Elimination method in the m x n sequencing problem " , Naval Research Logistics Quarterly , 18 , 295 - 305 , (1971)
    79. Szwarc, W., " A note on the flow-shop problem without interruptions in job processing " Hayal Research Logistics Quarterly , 28, 665 - 669 , (1981)
    80. Viviers, F., "A decision support system for job shop scheduling" . Europ. J. of Ops. Res . 14(1) , 95 -103 , (1983)
    81. Wagner, H.M., "An integer programming model for machine scheduling" Naval Research Logistics Quarterly , 6, 131 - 140 . (1959)
    82. Weber, R.R., " The interchangeability of tandom /M/1 queues in series " , J. Appl. Probab , 16(3) , 689 - 697 , (1979)
    83. Weiss, H., "A greedy heuristic for single machine sequencing with precedence constraints" . Management Science , 27(10) , 1209 - 1215 , (1981)
    84. Wismer, D.A., "Solution of the flowshop scheduling problem with no intermediate queues " . Operations Research. 20(3), 689 - 697. (1972)
    85. Yu, C.C.. The optimization of stochastic multiperiod systems by an implicit dynamic programming approach. Ph. D. Dissertation , J.T. Austin , (1985)
    86. Yu, C.C.. Three tree structures for data processing in dynamic programming computation. Master Dissertation , U.T. Austin , (1983)
    87. 許淑卿,多變量模擬輸出之統計分析,國立政治大學統計研究所碩士論文,(民國76年).
    88. 黃欣伸,排程的隨機動態規劃模型及其在管理上的應用,國立政治大學統計研究所碩士論文,(民國75年).
    Description: 碩士
    國立政治大學
    統計學系
    Source URI: http://thesis.lib.nccu.edu.tw/record/#B2002006242
    Data Type: thesis
    Appears in Collections:[Department of Statistics] Theses

    Files in This Item:

    File SizeFormat
    index.html0KbHTML2485View/Open


    All items in 政大典藏 are protected by copyright, with all rights reserved.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback