Abstract: In order to realize automatic optimal scheduling of the cigarette production plan, the hierarchical automatic optimal scheduling flow is designed. The task allocation mathematical model for cigarette production in multi-location and the detail scheduling mathematical model in one production factory with constraints are established. The improved genetic algorithms for these models are designed. Genetic-pattern searching algorithm for cigarette production in multi-location is proposed, which improves the partial search ability of the single GA. The completion time of the detail scheduling model is optimized by the corresponding algorithm tactics. The priority rules of cigarette brands and production constraint conditions are embedded into the genetic algorithm, which meets the actual requirement. The example of the actual cigarette production proves these methods’validity. The optimal exact cigarette production plan is obtained. The production cost of cigarette and inventory are decreased and the makespan is decreased significantly.

Key words: cigarette production scheduling in multi-location, hierarchical model, parallel machine scheduling problem, genetic algorithm, pattern searching algorithm

摘要： 为了对卷烟生产进行自动优化排产，构建出卷烟排产分层递阶优化流程，对流程的关键环节设计了自动优化模型；分别建立了带约束限制的卷烟多点生产任务分配和生产点详细排产数学模型。对两个模型分别设计了改进的遗传优化算法。对多点生产模型，提出了一种基于遗传算法-模式搜索法的任务分配优化算法，改善了单独使用遗传算法局部搜索能力差的缺陷；对详细排产最大完工时间数学模型，设计了相应的算法操作策略，将牌号优先规则、生产约束嵌入到遗传算法中，满足了实际生产限制。通过卷烟生产排产实例，验证了算法的有效性，给出了优化的卷烟精确排产计划，降低了卷烟生产总成本和库存，缩短了总生产流程时间，提高了设备效率。

关键词: 卷烟多点生产排产, 分层模型, 并行机调度, 遗传算法, 模式搜索法