生产车间的作业调度问题一直是生产企业研究的一个热点问题。很多资料已经证明大部分车间生产作业调度问题是NP完全问题,这类问题求解过程的计算量随问题复杂程度呈指数增长,求得最优解非常困难。启发式算法不仅具有实现相对容易的优点,而且在实际生产过程中面对复杂的调度问题可以保持良好的算法性能,因此,在生产调度算法的设计过程中被广泛采用。本文研究的对象是烟草企业烟丝生产环节的生产调度排程优化问题。研究的具体对象是两条并行的生产流水线,这两条生产线不完全相同又有公共部分。在工艺路径、设备性能、产品配方、设备连接关系等多重约束下,生产调度变得异常复杂。通过生产历史数据描述了生产调度的现状及问题,提出了优化改进需求。制丝车间两条并行的流水线,经常因为争夺公共部分资源而发生冲突,浪费生产资源,造成生产实际时间远大于理论生产时间。因此,本文设计了一种基于生产时间的二重优先分配启发式算法,首先根据优先分配规则排列所有的生产任务,在此基础上对生产任务进行二次启发式优化,以求得烟丝生产调度排程具有一定的柔性,能够抵御一些短暂的突发问题。然而在实际生产过程中,不可能完全按照既定计划执行,设备故障、执行偏差等都会对调度排程产生影响,因此,本文在静态调度的基础上设计了一些异常情况下的动态调度算法,以保证生产调度排程始终处于较优水平。最后,以HY卷烟厂生产实际数据举例,通过模拟生产调度排程流程验证了设计算法的有效性。