高成炎臺灣大學：資訊工程學研究所王麒瑋Wang, Chi-WayChi-WayWang2007-11-262018-07-052007-11-262018-07-052007http://ntur.lib.ntu.edu.tw//handle/246246/54128本文主要描述一個在醫院重要的排班－住院醫師排班問題。論文中首先指出住院醫師排班問題主要著重如何在滿足三個關鍵且重要的需求－公平的分配工作、醫師選擇値班或不值班的計劃達成以及連續工作次數的避免(包含上月工作情況)，排出一個合理且令所有人滿意的班表。為了達成上述目的，本文採用基因演算法，求解，得此班表。不僅如此，針對上述住院醫師排班問題所需要達成的需求，改良傳統基因演算法的步驟－突變，命名為動態突變。本文相關實驗指出此一改良，可使演算法本身在搜尋最佳解的過程效能更好。This thesis formally presents the resident physician scheduling problem, which is one of the most important scheduling problems in hospital. The resident physician scheduling problem is characterized as satisfying the fair schedule constraint, the physician specification constraint and the safe schedule constraint simultaneously. To minimize the penalties from violating the constraints, this study adopts the evolutionary approach to propose a genetic algorithm for solving the problems. In addition the well-known genetic operators, this study proposed a new mutation operator called dynamic mutation for solving the resident physician scheduling problem. The experimental results show that the proposed algorithm performs well in searching optimal schedules.謝辭 i 摘要 ii Abstract iii List of Figures vi List of Tables vii List of Algorithms vii Chapter 1 Introduction 1 1.1 Background 1 1.2 Motivations 2 1.3 Contribution 3 1.4 Thesis Structure 4 Chapter 2 Related Work 5 2.1 Hospital Scheduling 5 2.2 Methods for hospital Scheduling 7 2.2.1. Manual Schedule Method 7 2.2.2. Goal programming Methods 7 2.2.2.1. Mathematical programming 7 2.2.2.2. Column generation 8 2.2.3. Meta-heuristics Methods 9 2.2.3.1. Tabu Search 9 2.2.3.2. Genetic Algorithm 10 Chapter 3 Problem Definition 12 3.1 The Problem Descriptions 12 3.2 The Notations 16 3.3 Solution Format and Constraints 17 3.4 Resident Physician Scheduling Problem 19 Chapter 4 Proposed Mechanism and Algorithm 22 4.1 The Chromosome and Initial Population 24 4.2 The Fitness Function 25 4.3 The Reproduction Methods 26 4.4 The Crossover Operators 28 4.5 The Mutation Operators 31 Chapter 5 Experimental Results and Comparisons 33 5.1. The Benchmark Problems 33 5.2. The Experimental Results and Comparisons 36 5.3. Algorithm Modified 42 5.4. The Improved Results 43 Chapter 6 Conclusions and Future Works 47 6.1 Conclusions 47 6.2 Future Works 48 Reference 49 Appendix 1: A roster of intern physicians in northern Taiwan 54 Appendix 2: A roster of emergency physicians in southern Taiwan 55 Appendix 3: A hospital roster rules of resident physicians in central Taiwan 563950376 bytesapplication/pdfen-US住院醫師排班問題基因演算法啟發式演算法Genetic AlgorithmResident Physician Scheduling ProblemMeta-heuristicthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54128/1/ntu-96-R94922092-1.pdf