臺灣博碩士論文加值系統

有關多個代理商的排程問題，近年來已逐漸受到釵h學者的注意與探討。然而，大多數有關代理商排程問題的研究皆著重在研究問題的複雜度上，或是考慮單一準則的問題。在很多真實狀況，製造廠商必須根據多個準則以決定生產線上的排程。本文考慮一個單機排程的問題，亦即是在第二代理商的工作件不允陬o生延遲的情況下，尋找一排程使得第一代理商工作件之總完工時間與最大延遲時間之線性組合達到最小化。為了達到此目的，本論文利用分枝界限法與啟發式演算法，分別找尋出最佳解與近似解。在電腦模擬實驗中，我們發現利用分枝界限演算法能在極短的時間範圍內，找到具有24個工作件的最佳排程。再者，啟發式演算法的近似解的平均誤差均控制在0.5%以內。

The multiple-agent scheduling problems have received increasing attention recently. However, most of the research focuses on studying the computational complexity of the intractable cases or examining problems with a single criterion. Often a decision maker has to decide the schedule based on multiple criteria. In this paper, we consider a single machine problem where the objective is to minimize a linear combination of the total completion time and the maximum tardiness of jobs from the first agent given that no tardy jobs are allowed for the second agent. We develop a branch-and-bound algorithm and several simulated annealing algorithms to search for the optimal solution and near-optimal solutions for the problem, respectively. Computational experiments show that the proposed branch-and-bound algorithm could solve problems of up to 24 jobs in a reasonable amount of time and the performance of the combined simulated annealing algorithm is very good with an average error percentage of less than 0.5% for all the tested cases.

第一章 緒論 ……………………………………………………… 1
第一節 研究動機與背景 ………………………………1
第二節 研究目的 ………………………………………2
第三節 研究架構 ………………………………………2
第四節 文獻探討 ………………………………………5

第二章 理論性質與解題方法 …………………………………… 9
第一節 問題描述 ………………………………………9
第二節 符號定義 ………………………………………9
第三節 凌越性質與定理 ………………………………10
第四節 建立下界值 ……………………………………26

第三章 建立分枝界限法與啟發式演算法 ………………………29
第一節 分枝界限法與其程序 …………………………29
第二節 模擬退火法與其程序 …………………………30

第四章 模擬計算與分析結果 ……………………………………33
第一節 模擬資料的生成 ………………………………33
第二節 電腦模擬實驗 …………………………………33

第五章 未來與展望 ………………………………………………49
參考文獻 …………………………………………………………51

[1] Agnetis A, Mirchandani PB, Pacciarelli D, Pacifici A. Scheduling problems with two competing agents. Operations Research 2004; 52: 229-242.
[2] Agnetis A, Pacciarelli D, Pacifici A. Multi-agent single machine scheduling. Annals of Operations Research 2007; 150: 3-15.
[3] Agnetis A, Pascale G, Pacciarelli D. A Lagrangian approach to single-machine scheduling problems with two competing agents. Journal of Scheduling 2009; 12: 401-415.
[4] Agnetis A. Combinatorial models for multi-agent scheduling problems. Proceedings of the 12th international conference devoted to project management and scheduling, Tours, France, April 26-28, 2010, 37-40.
[5] Baker KR, Smith JC. A multiple-criterion model for machine scheduling. Journal of Scheduling 2003; 6: 7-16.
[6] Balasubramanian H, Fowler JW, Keha AB, Pfund ME. Scheduling interfering job sets on parallel machines. European Journal of Operational Research 2009; 199: 55-67.
[7] Ben-Arieh D, Maimon O. Annealing method for PCB assembly scheduling on two sequential machines. International Journal of Computer Integrated Manufacturing 1992; 5: 361-367.
[8] Bukchin Y, Hanany E. Decentralized Cost in Scheduling: A Game-Theorethic Approach. Manufacturing Service Operations Management 2007; 9: 263-275.
[9] Cheng TCE, Ng CT, Yuan JJ. Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science 2006; 362: 273–281.
[10] Cheng TCE, Ng CT, Yuan JJ. Multi-agent scheduling on a single machine with max-form criteria. European Journal of Operational Research 2008; 188: 603–609.
[11] Gawiejnowicz S, Lee WC, Lin CL, Wu CC. A branch-and-bound algorithm for two-agent single-machine scheduling of deteriorating jobs. Journal of the Operational Research Society. 2010 (doi:10.1057/jors.2010.17).
[12] Kirkpatrick S, Gelatt C, Vecchi M. Optimization by simulated annealing. Sci 1983; 220/4598: 671-80.
[13] Kim K, Paulson BC, Petrie CJ, Lesser VR. Compensatory negotiation for agent-based schedule coordination. CIFE working paper #55, Stanford University, Stanford, CA, 1999.
[14] Kubzin MA, Strusevich VA. Planning machine maintenance in two-machine shop scheduling. Operations Research 2006; 54: 789-800.
[15] Lee KB, Choi BC, Leung JYT, Pinedo ML. Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Information Processing Letters 2009; 109: 913-917.
[16] Lee WC, Chen SK, Chen CW, Wu CC. A two-machine flowshop problem with two agents. Computers and Operations Research 2011; 38: 98-104.
[17] Lee WC, Wang WJ, Shiau YR, Wu CC. A single-machine scheduling problem with two-agent and deteriorating jobs. Applied Mathematical Modelling 2010a; 34: 3098-3107.
[18] Lee WC, Chen SK, Wu CC. Branch-and-bound and simulated annealing algorithms for a two-agent scheduling problem. Expert Systems with Applications 2010b; 37: 6594-6601.
[19] Leung JYT, Pinedo M, Wan GH. Competitive two agents scheduling and its applications. Operations Research 2010; 58: 458-469.
[20] Liu P, Tang L. Two-agent scheduling with linear deteriorating jobs on a single machine. Lecture Notes in Computer Science 2008; 5092: 642–650.
[21] Liu P, Tang L, Zhou X. Two-agent group scheduling with deteriorating jobs on a single machine. International Journal of Advanced Manufacturing Technology 2010a; 47:657–664.
[22] Liu P, Zhou X, Tang L. Two-agent single-machine scheduling with position- dependent processing times, International Journal of Advanced Manufacturing Technology 2010b; 48, 325–331.
[23] Meiners CR, Torng E. Mixed criteria packet scheduling. Proceedings of the Third Internation Conference on Algorithmic Aspects in Information and Management. Lecture Notes in Computer Science 2009; 4508: 120-133.
[24] Ng CT, Cheng TCE, Yuan JJ. A note on the complexity of the problem of two-agent scheduling on a single machine. Journal of Combinatorial Optimization 2006; 12: 387–394.
[25] Peha JM. Heterogeneous-criteria scheduling: Minimizing weighted number of tardy jobs and weighted completion time. Computers & Operations Research 1995; 22: 1089-1100.
[26] Schultz D, OH SH, Grecas CF, Albani M, Sanchez J, Arbib C. A QoS concept for packet oriented SUMTS services. In: Proceedings of the 1st Mobile Summit, Thessaloniki, Greece, 2002.
[27] Wan G, Vakati SR, Leung JYT, Pinedo M. Scheduling two agents with controllable processing times. European Journal of Operational Research 2010; 205: 528–539.
[28] Yuan JJ, Shang WP and Feng Q. A note on the scheduling with two families of jobs. Journal of Scheduling 2005; 8: 537–542.