臺灣博碩士論文加值系統

顧客的需求是依照各個單位的目的而有所不同，要想在人力、資源有限且控制成本下達到雙方都能得到最佳平衡結果，若能事先規畫良好的排程是能有效解決這樣的問題。
近年來，關於在兩個相互競爭的代理商之排程問題已經有越來越流行的趨勢。在本文中，我們研究了具有釋放時間的單機排程問題，其目標的限制為第二代理商的工作件最大延遲時間不得超過某一上限數值，進而尋找一種排程使得第一代理商工作件總延遲時間達到最小化。
我們針對此主題發展分枝界限法(branch-and-bound algorithm)尋找最佳解。此外，我們提出基因演算法(genetic algorithm, GA)尋找近似解。本文總共提出三種不同的基因演算法，並從事實際電腦模擬測試，其中加入一些控制參數設定的統計測試，進而評估分枝界限法和基因演算法。

The needs of customers are different under limited labor power, resourses and cost control. It will be more effective if we plan ahead.
In recent years, the scheduling problems with two competing agents have become more popular. In this paper, we studied a single-machine scheduling problem with release time where the objective is to minimize the total tardiness of jobs from the first agent given that the maximum tardiness of jobs from the second agent does not exceed an upper bound.
A branch-and-bound algorithm is developed to search for the optimal solution. In addition, genetic algorithm are proposed to obtain the near-optimal solutions. Computational experiments are conducted to evaluate the performance of the proposed branch-and-bound algorithm and the genetic algorithms. Statistical tests are also performed to study the impact of the parameters.

第一章 緒論 1
第一節 研究背景與動機 1
第二節 研究目的與架構 2
第二章 文獻探討 4
第三章 理論性質與解題方法 8
第一節 問題描述 8
第二節 凌越性質與定理 10
第三節 下界值 24
第四節 分枝界限法 26
第四章 基因演算法 27
第一節 基因演算法之程序 27
第二節 三種基因演算法之編碼 34
第三節 參數設定與分析 37
第五章 資料模擬與分析 43
第一節 生成資料之設定 43
第二節 小工作件之情形 45
第三節 大工作件之情形 59
第六章 結論與未來研究方向 65
參考文獻 67

[1]K.R. Baker, J.C. Smith, A multiple-criterion model for machine scheduling, Journal of Scheduling 6 (2003) 7–16.
[2]M.A. Kubzin, V.A. Strusevich, Planning machine maintenance in two-machine shop scheduling, Operations Research 54 (2006) 789–800.
[3]C.R. Meiners, E. Torng, Mixed criteria packet scheduling, Proceedings of the Third Internation Conference on Algorithmic Aspects in Information and Management, Lecture Notes in Computer Science 4508 (2009) 120–133.
[4]M.J Soomer, G.J. Franx, Scheduling aircraft landings using airlines’ preferences, European Journal of Operational Research 190 (2008) 277–291.
[5]A. Agnetis, P.B. Mirchandani, D. Pacciarelli, A. Pacifici, Scheduling problems with two competing agents, Operations Research 52 (2004) 229–242.
[6]J.J. Yuan, W.P. Shang, Q. Feng, A note on the scheduling with two families of jobs, Journal of Scheduling 8 (2005) 537–542.
[7]C.T. Ng, T.C.E. Cheng, J.J. Yuan, A note on the complexity of the problem of two-agent scheduling on a single machine, Journal of Combinatorial Optimization 12 (2006) 387–394.
[8]T.C.E. Cheng, C.T. Ng, J.J. Yuan, Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs, Theoretical Computer Science 362 (2006) 273–281.
[9]A. Agnetis, D. Pacciarelli, A. Pacifici, Multi-agent single machine scheduling, Annals of Operations Research 150 (2007) 3–15.
[10]T.C.E. Cheng, C.T. Ng, J.J. Yuan, Multi-agent scheduling on a single machine with max-form criteria, European Journal of Operational Research 188 (2008) 603–609.
[11]P. Liu, L. Tang, Two-agent scheduling with linear deteriorating jobs on a single machine, Lecture Notes in Computer Science 5092 (2008) 642–650.
[12]A. Agnetis, G. Pascale, D. Pacciarelli, A Lagrangian approach to single-machine scheduling problems with two competing agents, Journal of Scheduling 12 (2009) 401–415.
[13]K.B. Lee, B.C. Choi, J.Y.T. Leung, M.L. Pinedo, Approximation algorithms for multi-agent scheduling to minimize total weighted completion time, Information Processing Letters 109 (2009) 913–917.
[14]P. Liu, L. Tang, X. Zhou, Two-agent group scheduling with deteriorating jobs on a single machine, International Journal of Advanced Manufacturing Technology 47 (2010) 657–664.
[15]W.C. Lee, W.J. Wang, Y.R. Shiau, C.C. Wu, A single-machine scheduling problem with two-agent and deteriorating jobs, Applied Mathematical Modelling 34 (2010) 3098–3107.
[16]J.Y.T. Leung, M. Pinedo, G.H. Wan, Competitive two agents scheduling and its applications, Operations Research 58 (2010) 458–469.
[17]W.C. Lee, S.K. Chen, C.C. Wu, Branch-and-bound and simulated annealing algorithms for a two-agent scheduling problem, Expert Systems with Applications 37 (2010) 6594–6601.
[18]P. Liu, X. Zhou, L. Tang, Two-agent single-machine scheduling with position- dependent processing times, International Journal of Advanced Manufacturing Technology 48 (2010) 325–331.
[19]G. Wan, S.R. Vakati, J.Y.T. Leung, M. Pinedo, Scheduling two agents with controllable processing times, European Journal of Operational Research 205 (2010) 528–539.
[20]W.C. Lee, S.K. Chen, C.W. Chen, C.C. Wu, A two-machine flowshop problem with two agents, Computers and Operations Research 38 (2011) 98–104.
[21]P. Liu, N. Yi, X. Zhou, Two-agent single-machine scheduling problems under increasing linear deterioration, Applied Mathematical Modelling 35 (2011) 2290–2296.
[22]C. Darwin, On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life, Mentor Reprint, 1958, NY (1859).
[23]I. Rechenberg, Cybernetic solution path of an experimental problem, Library Translation 1122, Royal Aircraft Establishment, Farnborough, UK (1965).
[24]H.P. Schwefel, Numerische Optimierung von Computer – Modellen mittels der Evolutionsstrategie, Birkhäuser, Basel (1977).
[25]V. Neumann, A.W. Burks, Theory of self-reproducing automata, The Uuiversity of Illinois Press, USA (1966).
[26]J.H. Holland, Adapation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbo (1975).
[27]J.R. Koza, Hierarchical Genetic Algorithms Operating on Populations of Computer Program, Proceedings of the 11th International Joint Conference on Artificial Intelligence (1989).
[28]J.R. Koza, Genetic Programming：On the Programming of Computers by Means of Natural Selection, MIT Press, Cambridge, MA (1992).
[29]J. Du, J.Y.T. Leung, Minimizing Total Tardiness on One Machine is NP-Hard, Mathematics of Operations Research 15 (1990) 483–495.
[30]K.I. Srikanth, S. Barkha, Improved genetic algorithm for the permutation flowshop scheduling problem, Computers & Operations Research 31 (2004) 593–606.
[31]D. Thierens, D. Goldberg, Convergence Models of Genetic Algorithm Selection Schemes, Parallel Problem Solving from Nature: PPSN III, Springer-Verlag, Berlin (1994) 119–129.
[32]R.C. Chen, C.H. Jian, Solving Unbounded Knapsack Problem Using an Adaptive Genetic Algorithm with Elitism strategy, International Workshop on Intelligent Systems and Smart Home, Springer''s Lecture Notes in Computer Science (2007).
[33]C. Chu, A branch and bound algorithm to minimize total flow time with unequal release dates, Naval Research Logistics 39 (1992) 859–875.