簡易檢索 / 詳目顯示

回結果列表
研究生： 黃國祐
Guo-You Huang
論文名稱： 考量相依整備時間之完工時間最小化的非等效平行機問題
Makespan minimization for unrelated parallel machine problem with sequence dependent setup times
指導教授： 廖慶榮
Ching-Jong Liao
口試委員: 王孔政
Kung-Jeng Wang
鄭元杰
Yuan-Jye Tseng
學位類別： 碩士
Master
系所名稱： 管理學院 - 工業管理系
Department of Industrial Management
論文出版年： 2009
畢業學年度： 97
語文別： 英文
論文頁數： 38
中文關鍵詞： 排程 、非等效平行機 、相依的整備時間 、懲罰值 、變動鄰域搜尋法
外文關鍵詞： Scheduling, Unrelated parallel machines, Sequence dependent setup times, Penalty, Variable neighborhood search
相關次數： 點閱：225  下載：3 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本論文旨在探討非等效平行機考量相依整備時間之完工時間最小化問題。由於這類問題的複雜度較高，因此在大問題上求取最佳解是比較困難的。本篇論文將發展一個以懲罰值為概念的演算法去獲得初始解。在本論文中我們同時提出變動鄰域搜尋法，包含了三個鄰域搜尋的方法，以期望能夠改善初始解並得到一個較佳可行解。最後，我們將所提出的演算法對標竿問題作測試，實驗結果顯示，我們在本篇論文中所提出的方法對於求解這類型的問題上是比原有的方法更有效率的。

    This thesis focuses on an unrelated parallel machine scheduling problem with sequence dependent setup times. The objective of the problem is to minimize the makespan. Due to the complexity of the problem, finding optimal solutions for large problems is very difficult, and hence we develop a heuristic based on penalty to obtain a good solution. To further improve the solution, we propose a metaheuristic that uses variable neighborhood search (VNS) with three different local searches. By examining the benchmark problem instances, the method we proposed in this thesis significantly outperforms an existing method in solving the problem.

    CHINESE ABSTRACT i ENGLISH ABSTRACT ii ACKNOWLEDGEMENTS iii CONTENTS iv LIST OF FIGURE v LIST OF TABLES vi Chapter 1 INTRODUCTION 1 Chapter 2 LITERATURE REVIEW 2 2.1 Unrelated parallel machine 2 2.2 Variable neighborhood search 3 Chapter 3 PROPOSED ALGORITHMS 5 3.1. The Penalty-based heuristic procedure 8 3.2. The parameter setting 18 3.3. Variable neighborhood search 18 Chapter 4 COMPUTATIONAL EXPRIMENTS 23 4.1. Experiments for comparing the initial solution 23 4.2. Experiments for comparing the metaheuristics 29 Chapter 5 CONCLUSIONS AND FUTURE RESEARCH 36 REFERENCES 37

    Al-Salem, A. (2004). Scheduling to minimize makespan on unrelated parallel machines with sequence dependent setup times. Engineering Journal of the University of Qatar, 17, 177-187.
    Allahverdi, A., Ng, C.T., Cheng, T.C.E., & Kovalyov, M.Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 187, 985-1032.
    Allahverdi, A., & Mittenthal, J. (1994). Scheduling on M parallel machines subject to random breakdowns to minimize expected mean flow time. Naval Research Logistics, 41, 677-682.
    Biskup, D., Herrmann, J., & Gupta, J.N.D. (2008). Scheduling identical parallel machines to minimizes total tardiness. Int.J.production Economics, 115, 134-142.
    DePuy, G.. W., Moraga, R. J., & Whitehouse, G. E. (2005). Meta-Raps: a simple and effective approach for solving the traveling salesman problem, Transportation Research part E: Logistics & Transportation Review, 41, 115-130.
    Felipe, Á., Ortuño, M. T., & Tirado, G. (2009). The double traveling salesman problem with multiple stacks: A variable neighborhood search approach. Computers & Operations Research, 36, 2983-2993.
    Garey, M. R., & Johnson, D. S. (1979). A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York, Computers & Intractability.
    Hansen, P., & Mlasenović, N. (2001). Variable neighborhood search: Principles and applications. European Journal of Operational Research, 130, 449-467.
    Imran, A., Salhi, S., & Wassan, N. A. (2009). A variable neighborhood-based heuristic for the heterogeneous fleet vechicle routing problem. European Journal of Operational Research, 197, 509-519.
    Koulamas, C., & Kyparisis G.. J. (2009). A modified LPT for the two uniform parallel machine makespan minimization problem. European Journal of Operational Research, 196, 61-68.
    Kashan, A. H., & Karimi, B. (2009). A discrete particle swarm optimization algorithm for scheduling parallel machines. Computers & Industrial Engineering, 56, 216-223.
    Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1989). Sequencing and Scheduling: Algorithms and Complexity. In: Report BS-R8909, Department of Operations Research, Statistic, and System Theory, Centre for Mathematics and Computer Science, Amsterdam.
    Logendran, R., McDonell, B., & Smucker, B. (2007) Scheduling unrelated parallel machines with sequence-dependent setups. Computers & Operations Research, 34, 3420-3438.
    Moraga, R. J., Dupuy, G. W., & Whitehouse, G. E. (2005). Meta-Raps approach for the 0-1 multidimensional knapsack problem. Computers & Industrial Engineering, 48, 83-96.
    Mlasenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & operations Research, 24, 1097-1100.
    Pinedo, M. (2002). Scheduling: Theory, Algorithms, & Systems, 2nd edition, Printce Hall, New Jersey.
    Rabadi, G., Moraga, R. J., & Al-Salem, A. (2006).Heuristics for the unrelated parallel machine scheduling problem with setup times. Journal of Intelligent manufacturing, 17, 85-97.
    Rocha, M., Mateus, G.. R., & Pardalos, P. M. (2007). Solving parallel machines scheduling problems with sequence-dependent setup times using variable neighborhood search. IMA Journal of Management Mathematics, 18, 101–115.
    Scheduling Research (2005). http://www.SchedulingResearch.com, a web site that includes benchmark problem data sets and solutions for scheduling problems.
    Tseng, F. T., Gupta, J. N. D., & Stafford Jr., E.F. (2006). A penalty-based heuristic algorithm for the permutation flowshop scheduling problem with sequence-dependent set-up times. Journal of the Operational Research Society, 57, 541-551.

    QR CODE