臺灣博碩士論文加值系統

在生產系統中，零工排程問題(Job Shop Scheduling Problem)的求解方法是很重要的，其適用於種類多數量少的生產方式。在這種生產型態下，產品每次經過的加工路線可能不同，因此也就增加求解上的困難。在眾多的求解方法中，移動瓶頸法(Shifting Bottleneck Procedure)為一種針對零工排程問題求解的啟發式演算法，本研究主要目的是以修正之移動瓶頸法(Modified Shifting Bottleneck Procedure)為基礎，將演算過程中產生的瓶頸，使用資源平準化(Resource Leveling) 來解決資源衝突問題，以求零工排程問題之最少完工時間。
移動瓶頸法的概念，是將一個複雜的排程問題分解成數個單機子問題，並透過子問題之近似最佳解，得到趨近整體問題之局部最佳解(local optimum)。本研究即是在子問題求解過程中，配合具有時間導向之指標，排定需處理工作之優先順序後，將演算階段中資源衝突的問題進行資源平準化，並藉由範例問題測試，從數值資料來驗證求解品質是否提升。研究結果顯示，在執行資源平準的動作時，若是能夠知道越多工作優先平準化順序的資訊，則對於整體問題的求解，會得到不錯的改善。

Solutions for Job Shop Scheduling problems are in most demand in production systems. Job Shop has high production variability and usually applies to special products. It is difficult to solve the scheduling problems because of a variety of products passed through different sequences of machines and operations. The Shifting Bottleneck Procedure is one of effective heuristic algorithms to resolve Job Shop Scheduling problems. The main purpose of this research is to obtain minimum makespan for Job Shop Scheduling problems using Modified Shifting Bottleneck Procedure and Resource Leveling technique, combined with several time-priority indexes. The study shows that this approach can improve scheduling results.

中文摘要 i
Abstract ii
誌謝 iii
目錄 iv
表目錄 vi
圖目錄 vii
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍與限制 2
1.4 研究架構與流程 3
第二章 文獻探討 5
2.1 零工排程問題之研究 5
2.1.1最佳化方法 5
2.1.2 啟發式方法 6
2.1.3 限制理論 8
2.2 移動瓶頸法
2.2.1 移動瓶頸法介紹 11
2.2.2 移動瓶頸法主要架構 12
2.2.3 移動瓶頸法相關研究 13
2.2.4 修正之移動瓶頸法 15
2.3 資源平準 17
2.3.1 資源平準介紹 18
2.3.2 資源平準相關文獻 19
2.3.3 資源平準假設與進行程序 21
2.4 文獻探討小結 23
第三章 研究方法 24
3.1 問題描述與流程概要 24
3.2 研究方法流程 25
3.3 解決資源衝突之移動瓶頸法 27
3.4 解決資源限制 29
3.5 設定優先順序 32
3.6 範例說明 39
3.7 研究方法小結 45
第四章 實例驗證 46
4.1 測試問題描述 46
4.2 設定瓶頸機台工作優先順序 51
4.3 不同工作數目優先順序設定 54
4.4 綜合分析 56
4.5 實例驗證結論 62
第五章 結論與建議 63
5.1 結論 63
5.2 未來研究建議 63
參考文獻 65
附錄 69

Adams, J., Balas, E. and Zawack, D., The shifting bottleneck procedure for job shop scheduling, Management Science, Vol. 34, pp. 391-401, 1998.
Antill, J.M. and Woodhead, R.W., Critical Path Methods in Construction Practice, 4th ed, Wiley Interscience, 1990.
Applegate, D. and Cook, W., A computational study of the job-shop scheduling problem, ORSA Journal on Computing, Vol. 3, pp. 149-156, 1990.
Balas, E., Machine sequencing via disjunctive graphs: an implicit enumeration algorithm, Operations Research, Vol. 17, pp. 941-957, 1969.
Balas, E., Lenstra, J. K. and Vazacopoulos, A., The one-machine problem with delayed precedence constraints and its use in job shop scheduling, Management Science, Vol. 41, pp. 94-109, 1995.
Balas, E. and Vazacopoulos, A., Guided local search with shifting bottleneck for job shop scheduling, Management Science, Vol. 44, pp. 262-275, 1998.
Byeon, E. S., Wu, S. D. and Storer, R. H., Decomposition Heuristics for Robust Job-Shop Scheduling, IEEE Transations on Robotics and Automation, Vol. 14, pp. 303-313, 1998.
Carlier, J., The one-machine sequencing problem, European Journal of Operational Research, Vol. 11, pp. 42-47, 1982.
Carlier, J., and Pinson, E., A practical use of Jackson’s preemptive scheduling for solving the job-shop problem, Annals of Operation Research, Vol. 26, pp. 269-287, 1989.
Chan, W. T., Chua, D. K. H. and Kannan, G.., Construction Resource Scheduling with Genetic Algorithms, Journal of Construction Engineering and Management, Vol. 122, pp. 125-132, 1996.
Cheng, J., Karuno, Y. and Kise, H., A shifting bottleneck approach for a parallel-machine flowshop scheduling problem, Journal of Operational Research Society of Japan, Vol. 44, pp.140-156, 2001.
Dauzere-Peres, S. and Lasserre, J. B., A modified shifting bottleneck procedure for job-shop scheduling, International Journal of Production Research, Vol. 31, pp. 923-932, 1993.
Dorndorf, U. and Pesch, E., Evolution based learning in a job shop scheduling, Computers and Operations Research, Vol. 22, pp. 25-40, 1995.
Garey, M. R. and Johnson, D. S., Computers and Intractability, A Guide to Theory of NP Completeness, San Francisco, CA: Freeman, 1979.
Goldratt, E. M., Theory of Constraints, Croton-on-Hudson, NY: North River Press, 1990.
Harris, R. B., Precedence and Arrow Networking Techniques for Construction, John Wiley & Sons, New York, NY, 1978.
Harris, R. B., Packing Method for Resource Leveling (PACK), Journal of Construction Engineering and Management, Vol. 116, pp. 331-350, 1990.
Hegazy, T., Optimization of Resource Allocation and Leveling Using Genetic Algorithms, Journal of Construction Engineering and Management, Vol. 125, pp. 167-175, 1999.
Hiyassat, M.A.S., Modification of Minimum Moment Approach Resource Leveling, Journal of Construction Engineering and Management, Vol. 126, pp. 278-284, 2000.
Huang, W. and Yin, A., An improved shifting bottleneck procedure for the job shop scheduling problem, Computers & Operations Research, Vol. 31, pp. 2093-2110, 2004.
Kelley, J. E., The Critical Path Method: Resources Planning and Scheduling Chapter 21 in Industrial Scheduling, Prentice-Hall, Englewood Cliffs, New Jersey, 1963.
Koulamas, C., A guaranteed accuracy shifting bottleneck, Computers Operations, Vol. 25, pp. 83-89,1998.
Leu, S. S. and Yang, C. H., GA-Based multicriteria optimal model for construction scheduling, Journal of Construction Engineering and Management, Vol. 125, pp. 420-427, 1999.
Muth, J. F. and Thompson, G. L., eds., Industrial Scheduling, Englewood Cliffs, N. J.: Prentice-Hall, 1963.
Neumann, K. and Zimmermann, J., Procedures for resource leveling and net present value problems in project scheduling with general temporal and resource constraints, European Journal of Operational Research, Vol. 127, pp. 425-443, 2000.
Pezzella, F., and Merelli, E., A tabu search method guided by shifting bottleneck for the job shop scheduling problem, European Journal of Operational Research, Vol. 120, pp. 297-310, 2000.
Raman, N., Input control in job shops, IIE Transactions, Vol. 27, pp. 201-209, 1995.
Ramudhin, A. and Marier, P., The Generalized Shifting Bottleneck Procedure, European Journal of Operational Research, Vol. 93, pp. 34-48, 1996.
Schragenheim, E. and Rozen, B., Drum－Buffer－Rope Shop Floor Control, Production and Inventory Management Journal, Vol. 31, pp. 18-23, 1990.
Son, J. and Mattila, K.G., Binary Resource Leveling Model: Activity Splitting Allowed, Journal of Construction Engineering and Management, Vol. 130, pp. 887-894, 2004.
Son, J. and Skibniewski, M.J., Multiheuristic Approach for Resource Leveling Problem in Construction Engineering: Hybrid Approach, Journal of Construction Engineering and Management, Vol. 125, pp. 23-31, 1999.
Sotskov, Y., Sotskova, NY. and Werner, F., Stability of an optimal schedule in a job shop, Omega , Vol. 25, pp. 397-414, 1997.
Sule, D. R., Industrial Scheduling, PWS publishing company, pp. 156-163, 1997.
Sun, D. and Batta, R., Scheduling larger job shops：A decomposition approach, International Journal of Production Research , Vol. 34, pp. 2019-2033, 1996.
Vancheeswaran, R. and Townsend, M. A., Two-Stage Heuristic Procedure for Scheduling Job Shops, Journal of Manufacturing Systems, Vol. 12, pp. 315-325, 1993
Van Laarhoven, P. J. M., Aarts, E. H. L. and Lenstra, J. K., Job shop scheduling by simulated annealing, Operations Research, Vol. 40, pp. 113-125, 1992.
Younis, M. A. and Saad, B., Optimal Resource Leveling of Multi-Resource Projects, Computers and Industrial Engineering, Vol. 31, pp. 1-4, 1996.