1.1目的及意义

随着智能制造的兴起和信息技术的发展，现代制造业正经历着由传统制造业向智能制造的转变。广泛运用人工智能技术和信息化手段的智能制造无疑将是制造业的未来发展方向。而作为制造业效益源泉的作业车间正是实现这一目标的重点控制对象。实现作业车间的合理调度是促进企业制造效率提高，实现企业利益持续增长的重要保证。

准时制生产方式（Just In Time，简称JIT），又称无库存生产方式、零库存生产方式等。JIT以准时生产为出发点，力求消除生产过程中的浪费及不必要的库存，在适当的时间将适当的物品送至适当的地方。虽然JIT中所追求的零库存模式是一种理想模式，很难在实际应用中实现。但准时化生产是制造企业追求的主要目标之一，同时也是企业低成本运营和精益化管控的重要手段。^[2]

面向准时交货的作业车间调度问题正是将JIT思想运用于车间调度问题。将准时化交货作为衡量作业车间调度计划效率的主要指标，以达到促进各项作业准时完成，避免提前/拖期现象出现的目标。

目前针对车间作业调度问题展开的研究并不少，主要采取的解决方法有拉格朗日松弛法、遗传算法、神经网络算法、启发式方法等。作业车间调度问题已经被证实是一个典型的NP-hard问题^[3]。理论上而言，此类问题在充分的时间和条件下，可以求得最优解。然而，若采用枚举法或LINGO求解等方法，当作业复杂、工序众多时，求解难度及计算复杂程度将会呈数量级增长，难以在合理的时间内取得最优解。而在实际运用中，我们只需在合理的时间内取得良好的解即可。

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质使其常常被用于求解NP-hard问题。近年来，在作业车间调度问题中，也有大量研究是基于遗传算法来进行求解的，现今也取得了十分丰硕的成果。从最初的传统车间调度（JSP）问题到柔性作业车间调度问题（FJSP），遗传算法都有优异的表现，在很多算例中都得到了最优或近优解。

局部搜索是解决最优化问题的一种启发式算法，常用于解决某些计算难度非常大的最优化问题，如各种NP完全问题等。这种近似算法（Approximate algorithms）运用以时间换精度的思想，可以无穷接近最优解。

针对遗传算法在寻优过程中容易陷入局部最优解的情况，本文将采用遗传算法与局部搜索相结合的方法，从而在较为合适的时间内取得理想的近似最优解。

该方法既可以避免在计算数据增大时，计算量出现指数型增长，也可以结合遗传算法与局部搜索的优点，从而得出适宜在实际生活中运用的、较为理想的算法。

1.2国内外研究现状