臺灣博碩士論文加值系統

本論文探討雙機流線型機組上總加權延遲時間最小化的排程問題，此問題已知屬於NP-hard之問題。為了求取問題之最佳解，我們使用分枝界定演算法作為解題工具。本研究中提出全新的工作序列建構方式。利用工作本身權重的的特性，下界函數以加權最短時間優先規則 (WSPT) 為基礎，藉由問題轉換的方式設計之。由雙機流線型機組針對總延遲時間最小化問題的最佳化條件衍生出適合本問題之型式，並用於分枝界定法。由實驗數據顯示，本演算法在許多問題下皆效能優異。另一方面，使用新序列建構策略對於傳統方式難以解決的問題上有不錯的效果，具有互補之效。

In this thesis, we study the scheduling problem, F2||wiTi, of minimizing total weighted tardiness in a two-machine flowshop. This problem is already known to be NP-hard. To derive optimal solutions, we develop branch-and-bound algorithms. A new sequence construction scheme is presented. Using characteristics associated with the weight of the jobs, we design a lower bound through problem transformations based on WSPT rule. Dominance rules adapted from those for the F2||Ti problem are also incorporated into the algorithm. We conducted computational experiments to show that the algorithm performs well in many cases. And the results also suggest that the new sequence construction strategy can complementarily compensate the weakness of the traditional one for the cases that the traditional strategy does not perform well.

Abstract
中文摘要
List of Tables
List of Figures
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Scope of Our Study 3
Chapter 2 Problem Statement and Notation 5
Chapter 3 Literature Review 8
3.1 Single Machine 8
3.2 Two-machine Flowshop 10
Chapter 4 Branch-and-bound Algorithms 11
4.1 Branching Scheme 11
4.2 Dominance Conditions 13
4.3 Lower Bounds 18
4.4 Branch-and-bound Algorithms 21
Chapter 5 Experimental Results 22
Chapter 6 Conclusions 29
References 30

1. M.S. Akturk, M.B. Yildirim, A new lower bounding scheme for the total weighted tardiness problem, Computers and Operations Research 25 (1998), 265-278.
2. K. Baker, Introduction to Sequencing and Scheduling, Wiley, New York, 1974.
3. J. Du, J.Y.T. Leung, Minimizing total tardiness on one machine NP-hard problems, Mathematics of Operations Research 15 (1990), 483-495.
4. H. Emmons, One machine sequencing to minimize certain functions of job tardiness, Operations Research 17 (1969), 701-715.
5. M.L. Fisher, A dual algorithm for the one-machine scheduling problem, Mathematical Programming 11 (1976), 229-251.
6. Y.D. Kim, A new branch and bound algorithm for minimizing mean tardiness in two machine flowshops, Computers and Operations Research 20 (1993), 391-401.
7. Y.D. Kim, Heuristics for flowshop scheduling problems minimizing mean tardiness, Journal of the Operational Research Society 44 (1993), 19-28.
8. C. Koulamas, The total tardiness problem : Review and extensions, Operations Research 42 (1994), 1025-1041.
9. C. Koulamas, On the complexity of two-machine flowshop problems with due date related objectives, European Journal of Operational Research 106 (1998), 95-100.
10. J.K. Lenstra, A.H.G. Kan Rinnooy, P. Brucker, Complexity of machine scheduling problems, Annals of Discrete Mathematics 1 (1977), 343-362.
11. B.M.T. Lin, Scheduling in the two-machine flowshop with due date constraints, International journal of Production Economics 70 (2001), 117-123.
12. J.C.H. Pan and E.T. Fan, Two-machine flowshop scheduling to minimize total tardiness, International Journal of Systems Science 28 (1997), 405-414.
13. J.C.H. Pan, J.S. Chen and C.M. Chao, Minimizing tardiess in a two-machine flow-shop, Computers and Operations Research 29 (2002), 869-885.
14. J. Picard, M. Queyranne, The time-dependent traveling salesman problem and its application to the tardiness problem in one machine scheduling, Operations Reserach 26 (1978), 86-110.
15. M. Pinedo, Scheduling :Theory, Algorithms and Systems, Prentice-Hall, Englewood Cliffs, New Jersey, 1995.
16. C.N. Potts, L.N. Van Wassenhove, A branch-and-bound algorithm for the weighted tardiness problem, Operations Research 33 (1985), 363-377.
17. A.H.G. Rinnooy Kan, B.J. Lageweg, J.K. Lenstra, Minimizing total costs in one machine scheduling, Operations Research 23 (1975), 908-927.
18. L. Schild, K.R. Fredman, Scheduling tasks with linear loss functions, Management Science 7 (1961), 280-285.
19. T. Sen, J.M. Sulek and P. Dileepan, Static scheduling research to minimizing weighted and unweighted tardiness : A state-of-art survey, International Journal of Production Economics 83 (2003), 1-12.
20. T. Sen, P. Dileepan and J.N.D. Gupta, The two-machine flowshop scheduling problem with total tardiness, Computers and Operations Research 16 (1989), 333-340.
21. J. Shwimer, On the n-job one machine sequencing independent scheduling problem with tardiness penalities : A branch-and-bound solution, Management Science 18 (1972), 301-313.
22. W. Szwarc, S. Mukhopadhyay, Decomposition of the single machine total tardiness problem, Operations Research Letters 19 (1996), 243-250.