改革开放三十余年来,制造业已成为我国国民经济的支柱产业。在制造业中,生产管理是提升企业运营效率、降低生产成本、提高收益的最重要的一环。随着生产管理信息化建设的快速发展,现代化的生产管理系统的广泛应用,促使企业的生产效率得到较大的发展。而生产调度应该属于众多生产管理系统最核心的功能,因为它可以在不增加企业生产资源的情况下,通过最大限度发挥当前资源能力的方式改善企业的生产效率,合理分配生产资源,提高机器利用率,缩减生产周期,降低在制品库存,减少损耗,从而提高企业收益。但目前的众多生产管理系统(或生产管理模块)都欠缺更加详细的生产排程系统,无法在车间作业层面提供具体的、优化的作业计划,这使得生产调度成为目前生产管理中最为重要也最亟待解决的一个瓶颈问题。自20世纪50年代开始,学术界已广泛研究了各类生产调度问题,并已取得了诸多成果,但理论研究成果与实际应用仍存在巨大的差距,如何将经典调度理论与实际的生产调度问题相结合,提高企业实际的生产效率,在有限时间内为企业的生产排程提供稳定、优化、高效的解决方案是近年来研究人员和企业界共同关注的问题。本文从企业的实际生产调度问题出发,主要研究了基于流水线的允许工序跳跃的生产调度问题,拥有多种加工约束的异速并行机调度问题和允许工序跳跃的柔性流水线调度问题,设计了一种加速计算完工时间的改进方法,提出了多种富有针对性的局部搜索策略和局部搜索算法,具体研究内容如下：(1)针对某大型钢铁制品加工车间中独特的生产模式,首先阐述了基于流水线调度问题的研究背景,指出了该问题的特殊类别与标识；然后,分别研究了流水线调度问题的最大完工时间问题和带加工准备时间的总加权完工时间问题,分别描述了两个问题的国内外研究现状,定义了其假设条件与数学表示符号,首次提出了两个问题基于调度次序的数学模型,提出了一种利用已知信息计算完工时间的改进方法,可显著提高计算速度,分析了原有算法的不合理性,并据此分别为两个问题提出了相应的局部搜索算法,并在搜索策略方面进行诸多讨论,通过多组合的实验数据证明两个算法的求解效果皆优于已知算法,其大规模问题的求解时间也可保证其在实际生产中成功应用,求解思路和独特的局部搜索策略对同类基于流水线的允许工序跳跃的调度问题具有一定启示作用。(2)针对某汽车零部件加工车间内新老设备并行运行的情况,研究了带有设备集约束和加工准备时间的异速并行机调度问题,总结了该类问题的国内外研究现状,详细说明了该类问题的问题假设、数学表示符号和基于机器安排与调度次序的数学模型,比较分析了此类问题目前在实际生产中的常用算法,设计了5种局部搜索策略,并据此提出了一种针对此类问题的新局部搜索算法,通过实验与己知算法比较分析得证新算法的求解质量全部优于已知的同类算法,大规模问题的求解时间也符合实际生产调度的需要,其算法思路和局部搜索策略对多阶段的同类问题具有一定指导意义。(3)研究了更为通用的柔性流水线调度问题,它结合了以上两类问题,是前两者更为一般的问题形式,首先明确了该类问题的定义,总结了其国内外研究现状,阐述了该问题的假设条件、数学符号表示和数学模型,并为其设计了特有的局部搜索算法,经多组合的算法性能分析得证新算法可以比同类问题的现有最佳算法提供更优的解质量,同时运行时间可控,可满足实际生产的需要。最后,对全文的研究工作进行了总结,展望了生产调度工作进一步的研究方向和应用前景。