作业车间调度问题(JSSP)是一个典型的NP-难问题,也是迄今为止所有组合优化问题中最难问题之一,同时在工程应用中有着十分重要的意义,因此得到了广泛的关注。本文在对JSSP进行透彻分析的基础上,结合已有研究成果,借鉴自然计算的方法,对JSSP求解进行研究。主要工作概括如下：(1)以多种群遗传算法(MGA)为基础,本文提出了基于记忆库和拉马克进化机制求解JSSP。该算法针对多种群遗传算法容易陷入局部最优解和局部搜索能力差的缺点,通过引入记忆库策略,不但使子种群间的个体可以进行信息交换,而且有利于保持整个种群的多样性；通过构造基于拉马克进化机制的局部搜索算子来提高多种群遗传算法中子种群的局部搜索能力。并且由于本文算法采用了全局寻优能力较强的模拟退火(SA)算法对记忆库中的个体进行优化,从而缓解了多种群遗传算法易陷入局部最优解的问题,并提高了本文算法求解作业车间调度问题的性能。(2)应用克隆选择(CS)算法求解JSSP时,如果初始种群的分布不够理想,其收敛速度比较慢,通过G&T算法可以产生较好的初始解,加快收敛速度；CS算法的主要算子是变异算子,因此如何选择合适的变异算子会对算法的性能有较大的影响。本文利用三种变异算子(交换,倒置,插入)对种群进行优化,同时记录各个变异算子的贡献,在克隆变异的过程中,通过轮盘赌方法动态的选择合适的变异算子。此外,克隆个体的变异强度应该与个体的适应度成反比,即适应度大的个体,应有较小的变异强度；适应度小的个体,应有较大的变异强度,基于这个原因,本文设计了自适应的变异强度算子。(3)差分进化(DE)算法采用浮点编码,成功的应用在求解连续空间上的全局优化问题。针对离散空间上的作业车间调度问题,本文设计了离散差分进化(DDE)算法。该算法采用DE算法的框架,继承了DE算法的优点。通过与克隆选择和遗传算法在benchmark标准测试问题上进行仿真对比实验,结果表明了离散差分进化算法快速收敛的特性。(4)克隆选择算法将局部搜索和全局搜索有机的结合起来,使算法具有较好的种群多样性,但对于作业车间调度问题,CS的收敛速度比较慢；离散差分进化算法采用差分进化算法的框架,具有快速收敛的优点,但相比克隆选择算法,差分进化算法的种群多样性较差,容易快速收敛到局部最优。本文充分利用CS和DDE算法的优点,将两种算法结合在一起,有效的弥补了各自的不足。通过在benchmark标准测试数据上的验证,证实了算法的有效性。本文得到了国家教育部博士点基金(No.20060701007)和国家自然科学基金(No.60703107)的资助。