组合优化问题广泛出现在计算机科学以及其它学科的许多领域当中，例如图论中的图着色问题，生物信息学中的蛋白质结构预测问题，计算机科学中的布尔可满足性问题等。同时，工业生产中也存在大量组合优化问题，如云计算负载均衡，车间作业调度，无线信号频率分配等。许多组合优化问题是相应学科或工业应用中的核心难题，因此研究求解这些问题的算法既具有重要的学术价值，也可以提高工业生产效率，给人们的日常生活带来更大的便利。　　在组合优化问题当中，资源分配问题是一类常见的问题。这类问题都涉及优化匹配两个或两个以上集合中的元素。在具体问题当中，这些需要匹配的集合可以是机器与程序，信号与频率，也可以是出租车与乘客，劳动力与工作岗位等。本文主要研究了两个典型的资源分配问题―机器再分配问题(Machine Reassignment Problem,MRP)和多阶段护士排班问题(Multi-stage Nurse Rostering Problem,MSNRP)，这两个问题分别是云计算负载均衡及医疗人力资源优化中的重要难题。由于这两个问题都属于NP难度问题，且具有多约束的特点，单纯依靠精确算法难以在合理的时间内获得满意的结果，而近三十年的研究表明，启发式算法是求解NP难度的组合优化问题的有效方法之一，可以在有限的计算资源内获得优质的解方案，因此研究人员在面对这类问题时多采用启发式算法来进行求解。　　本文首先介绍了组合优化问题及启发式算法的理论背景，然后将机器再分配问题和多阶段护士排班问题中的约束归类到常见的抽象约束模型，分析了这两个问题的共同点和代表性，提出了求解的总体思路，分别设计了求解机器再分配问题和多阶段护士排班问题的启发式算法。　　针对机器再分配问题，本文提出了多邻域局部搜索算法(Multi-neighborhood Local Search,MNLS)，主要贡献包括：　　(1)提出了三种基本邻域结构，充分搜索机器再分配问题的解空间。提出了一种辅助邻域结构用来修复非法解，并设计了相应的修复策略，使得算法能够搜索非法解空间，增强了算法的搜索能力　　(2)针对机器再分配问题规模大的特点，设计了邻域划分的机制，在算法的邻域评估范围和效率之间取得平衡。　　(3)使用机器再分配问题的30个标准算例对多邻域局部搜索算法进行了测试，算法改进了1个算例的当前最好解，3个算例的解与当前最好解持平。　　针对多阶段护士排班问题，本文提出了带权禁忌搜索算法(Weighted Tabu Search,WTS)，主要贡献包括：　　(1)提出了三种简单邻域结构和一种复合邻域结构，并通过自适应调整的方式在不同的邻域之间切换。为护士设置了惩罚权重，动态调整权重来实现算法在集中性和疏散性之间的平衡。　　(2)针对多阶段护士排班问题在单阶段无法预知其它阶段信息的特点，设计了跨阶段约束的近似评估策略，使得这些约束在单个阶段中也可以得到考虑。　　(3)使用多阶段护士排班问题的60个标准算例对带权禁忌搜索算法进行了测试，算法在第二届国际护士排班竞赛决赛中取得了第四名的成绩。　　本文主要研究了机器再分配问题和多阶段护士排班问题的启发式求解算法，并在标准算例上对算法进行了测试，表明了算法的有效性。本文的研究体现了设计求解复杂多约束NP难度问题的启发式算法时邻域结构、高效的搜索策略，算法鲁棒性的重要性。同时，也可将本文所提出的算法思路应用于求解其它类似的NP难度资源分配问题。