车间作业调度问题是制造型企业的一个研究热点。大多数车间作业的调度问题都是NP完全问题,在计算复杂度被控制在可接受范围内的条件下,求得该问题的最优解是非常困难的。启发式算法不仅实现起来相对容易,而且在面临实际生产过程中的复杂调度问题时,依然能保持良好的算法性能,因此,在生产调度的算法设计中被普遍采用。本文的研究对象是烟草工业的卷包作业调度,其工艺路径由储丝柜、振盘(风力喂丝机)、卷包机组、封箱机四种设备构成,它们之间是一种柔性连接关系,且生产不同牌号的产品时,设备之间可以动态组合进行生产,即这些设备具有根据不同的加工要求作出应变的能力。卷包车间所有生产线中的振盘数目远小于该车间能够生产的产品种类数目,但振盘又是各产品的必经加工路径,因此本文设计了一种基于首批作业计划的二重启发式算法,首先选出首批作业计划进行启发式调度,然后再根据首批作业的执行情况对剩余待调度作业进行启发式安排,以求得在没有调度人员干预情况下卷包作业的静态调度方案。由于实际的生产过程中难免出现一些难以准确预测的突发状况,如紧急插单,因此,本文在静态调度的基础上针对异常情况设计了相应的动态调度算法,使得相应的作业计划更加符合生产车间的生产习惯和实际需求。最后,以南京卷烟厂的卷包作业调度为应用背景,通过实例验证了本文所设计算法的有效性。