第一章模拟退火遗传混合算法研究
1.1引论
模拟退火和遗传算法都是比较有效的解决大规模组合优化问题的算法，但是在实际应用中，这两种算法都有它们本身固有的缺点和局限性。模拟退火算法在求解大规模组合优化问题时，由于所要计算的数据庞大，很多时候运行速度太慢，尽管能够计算出所需要的结果，但是实操性变得不强。遗传算法计算效率可以接受，但是经常陷入局部早熟现象，实际的最优解没有被计算出，同样不可取。所以，在上世纪90年代，LinFeng-Tse等研究小组将遗传算法和模拟退火算法结合起来，提出了模拟退火遗传混合算法(oenetie/simulated ealingAlgorithin-GsA。该算法在理论上将两种算法的优点有效结合在一起，即通过模拟退火算法增加遗传种群的多样性克服陷入局部早熟现象，同时又利用遗传算法解决模拟退火算法运算效率低的问题。目前该混合算法己成功在自然科学、工程技术和管理等诸多领域得到广泛应用。
1.2模拟退火算法概述
模拟退火算法是在1982年由Kirkpatrick等在将固体退火思想引入组合优化领域时提出的一种解大规模组合优化问题的，尤其是NP难问题，是完全组合优化问题的有效近似算法。它是源于对固体退火过程的模拟，采用了Metr接受准则，并且运用一组被称为冷却进度表参数来控制算法进程，从而使算法在多项式时间里面给出了一个近似最优解Metropolis准则是模拟退火算法的基础，因此首先讨论Metr叩。lis准则假定某一随机变量在某一时刻的状态为“1，在另一时刻状态为“2，设这种状态的转移满足以下条件p(el1eZ)=尸(e，1eZ)(1.1)令瑟表示系统从状态“，转移至状态“2所产生的能量差值。如果能量差为负，这样就表示状态能量的降低，新状态作为算法下一步的起点，同时若能量差为正，算法在这一点进行概率操作首先，选定一个在(O，1)内服从均匀分布的随机数。根据随机数来判断是否进行选择该值，这个过程称作抽样过程。
退火过程就是通常所说的降温过程，即在抽样过程中，使温度缓慢降低来模拟退火过程，如何对参数进行选择将对算法最后的结果有很大的影响。初始温度和终止温度的设置也会影响搜索时间。如果降温太快，则可能会漏掉全局最优点，若降温太慢，则搜索速度缓慢，加大搜索的时间复杂度，而难以接受。
1.2.1模拟退火算法的特点
模拟退火算法是求解复杂系统优化问题的搜索算法，和普通优化搜索算法相比的话，它是采用了许多特有方法和技术的，具体从以下几个方面阐述:
1.以一定的比率接受恶化解SA算法
在搜索策略和传统随机搜索方法有所不同，不仅要引入适当随机的因素，还引入了物理退火过程的自然原理。自然机理的引入使得模拟退火算法在迭代的过程中，不仅接受让目标函数变的较差的结果，而且接受概率随着温度下降在不断的降低。复杂问题会使得解空间中出现许多局部的最优解，传统优化方法一般是确定的，一直沿着改善解质量的方向进行搜索，这种确定性使得搜索达不到全局最优点。而SA的搜索策略有利于防止搜索过程中因为陷入局部最优解导致无法跳出，还有利于提高求出全局最优解的可靠性。
2.引进算法控制参数T
引进算法类似于退火温度的算法控制参数T，将优化的过程分成几个阶段，而且决定每个阶段里随机状态的取舍的标准，接受函数让Metr叩0115给出一个简单数学模型。SA算法的两个重要的步骤:一在每个控制参数T之下由前迭代点x(O出发产生出邻近的随机状态x(i+1)，由T来确定的接受准则决定这个新状态的取舍，并形成一定的长度的随机的Markov链;二缓慢的降低控制参数T，提高接收的准则，一直到T~0，状态链稳定于优化问题的最优的状态，从而提高SA算法获取全局最优解可靠性。
第二章作业车间调度问题研究
2.1引论
当今企业面临着激烈的国内外竞争，要想在激烈的竞争生存和发展，必须不断提高产品的质量和生产效率，充分满足客户的多方面需求。车间作业调度问题属于计算机集成制造领域中的一个关键环节，同时也是一种典型的NP难问题之一，生产制造业的实际需求是该问题研究的主要驱动来源。由于受到现有的计算条件和车间作业调度问题复杂性的制约，在研究过程中，一般会对实际问题进行简化和抽象，将复杂的问题通过有效方法转化为可以解决的问题。然后再考虑客观实际的各种约束条件，使抽象出的系统更符合实际的车间制造系统。
2.2作业车间调度问题概述
模具制造车间调度属于生产调度问题之一，是在一定时间内进行可以用共享资源分配与生产任务排序，来满足指定的性能指标。从数学规划的角度看，车间作业调度问题是在多个不等式或着等式的约束条件之下，对一个或着多个目标函数进行的优化。简单而言之生产调度问题是按照时间来分配资源，完成任务的问题。车间作业调度决策内容包括:时间决策、分配决策和路径决策。生产调度问题是针对某项可分解的工作在一定约束的条件下，怎样安排工件和操作的组成部分占用资源、加工的时间和先后顺序，从而获得产品的制造时间或者成本的最优化。典型车间作业调度问题包含一个需要完成的作业集，而且必须按一定流程进行加工，每台机床可加工工件的操作，在不同机床上能加工的操作集可不相同。调度的目的是把作业合理安排到各机床上，合理安排作业加工次序开始的时间，保证约束条件得以满足，而优化性能指标。
第三章 一种改进的自适应模拟退火遗................... 24-40
3.1 引论 ..................24
3.2 模拟退火遗传算法的改进 ..................24-37
3.2.1 遗传编码 ..................25-29
3.2.2 初始种群和适应度函数.................. 29-31
3.2.3 选择算子.................. 31-33
3.2.4 交叉算子和变异算子.................. 33-35
3.2.5 降温操作 ..................35-36
3.2.6 改进的模拟退火遗传算法..................36-37
3.3 改进算法的验证.................. 37-38
3.4 典型Job-Shop问题验证.................. 38-39
本章小结.................. 39-40
第四章 模具制造车间调度系统..................40-47
4.1 引论.................. 40
4.2 系统功能简述.................. 40-41
4.3 车间调度排产系统实现 ..................41-44
4.4 系统实现环境及数据库设计.................. 44-46
本章小结.................. 46-47
结论
近些年来，作业车间调度问题是越来越引起研究人员的重视和研究，通过研究和实际应用，遗传算法等算法解决该类问题是有效的、合理的可适用的。相对于单一组合优化算法，混合优化算法能结合不同算法之间的优点，更好地求解决作业生产调度问题。车间调度问题是给定一个作业集合和一个机器设备集合。每台机器同一时间可以加工一个作业，而每个作业包括一系列工序，每个工序在某个机器上需要连续加工若干时间。车间调度研究的问题就是在完成既定任务的情况下如何使所需要的时间最短化。
在过去的几十年中，国内外许多研究人员都对该问题进行了深入研究，并且得出了许多令人鼓舞的成果。但是随着车间调度问题需要考虑的实际问题越来越复杂，不可预期的情况越来越多，同时对车间调度实时性和有效性的要求越来越高，企业需要更适合本企业的车间调度方案的出现。笔者通过阅读大量国内外文献，并进行实际车间的调查，将模拟退火算法和遗传算法进行结合，提出了一种改进的模拟退火遗传算法。并将该算法应用在了实际的车间调度系统中，取得了较好的效果。
本文开发的模具制造车间作业调度系统可以灵活地应用于车间调度系统中，在制造企业降低生产成本、缩短制造周期中起到积极促进作用。然而由于车间调度问题本身的复杂性，算法仍然存在许多不足之处，实际中偶然因素还有很多没有考虑到，与实际环境还存在一定的差距。因此需要进一步晚上的工作还有很多。下一步，系统需要着重考虑的是实际环境中可能出现的突发情况，并对系统的可使用范围进一步扩大，使其应用的范围更广。
参考文献
[1] Jiang Guo, Yuehong Liao, Behzad Parviz. Department ofhttp://sblunwen.com/cnc/ Computer Science. California StateUniversity Los Angeles. Proceedings of the 13th Annual IEEE International Symposium andWorkshop on Engineering of Computer Based Systems (ECBS’06).2006:1~2
[2] Chen Hao,Ying Shi, Liu Jin, SE4SC: A specific search engine for software componentsProceedings - The Fourth International Conference on Computer and Information Technology,CIT 2004, p 863-868, 2004, Proceedings - The Fourth International Conference on Computerand Information Technology, CIT 2004:1
[3] Work ． flow Mallatgement Coalition ． Workflow Standard Inter-operabifity AbstracaSpecification[M]，1 999．
[4] Bartusch M., Mohring R. H.，Radermacher F. J.. Scheduling project networkswith resource constraints and time windows[J]. Annals of Operations Research,1988, 16: 201-240
[5] Blazewicz J., Lenstra J. K.’ Rinnooy Kan A. H. G.. Scheduling subject to resourceconstraints: classification and complexity[J]. Discrete Applied Mathematics, 1983，5: 11-24
[6] Chrzanowski, E.N. , Jr && Johnston，D.W. Application of linear construction.Journal of the Construction Engineering, ASCE, 1986, 112(4): 476-491
[7] Harmelink D. J., Rowings J. E.. Linear scheduling model:development ofcontrolling activity path[J]. Journal of Construction Engineering andManagement, 1998, 124(4): 263-268
[8] Harmelink D. J.. Linear scheduling model:float characteristics[J]. Journal ofConstruction Engineering and Management, 2001, 127(4): 255-260
[9] Harris, R.B. Scheduling projects with repeating activities. UMCEE Report No.96-26, Civil and Environmental Engineering Department, University of Michigan,Ann Arbor, ML 1998
[10] Kallantzis A., Lambropoulos S.. Critical path determination by incorporatingminimum and maximum time and distance constraints into linear scheduling[J].Engineering, Construction and Architectural Management, 2004, 11(3): 211-222