考虑机器调整次数和产品质量的卷烟批量计划和柔性流水车间调度集成问题

柴剑彬, 刘 赫, 贝晓强

(1.北京大学 光华管理学院，北京 100871; 2.中国科学院 数学与系统科学研究院,北京 100190; 3.中国科学院大学，北京 100049; 4.清华大学 经济管理学院，北京 100084)

0 引言

在我国，烟草行业的年税收在国家总税收中占有很大比重，是国家利税主要贡献者之一。烟草行业受政策性影响很大，因而国家对其实施统一领导、垂直管理的运行体制。但是由于市场经济的发展所趋以及国内市场国际化的迫切需要，行业之间的竞争也日益激烈。对于卷烟生产企业来说，优化其生产流程对提高企业的生产效率和产能利用率，提高卷烟质量，降低生产成本，提高企业经济效益具有十分重要的意义。但目前国内很多大中型卷烟企业在编制有关生产计划时依然在依靠经验进行排产，难以保证决策的及时性和准确性；即使是已有的排产软件，也多是利用一些简单的排产算法，很难有效解决排产问题普遍存在的复杂性问题，因此有必要对卷烟企业的生产计划问题进行深入研究。本文的研究正是来源于国内某卷烟企业所遇到的生产计划和调度集成问题。

卷烟从包装环节到封箱环节的生产过程中普遍遇到的一类排产问题是生产计划与调度集成问题。由于包装至封箱环节的生产过程将直接决定库存成品是否能够满足市场需求，因此这一段生产过程是卷烟企业整个排产计划的核心。针对生产计划与调度集成问题的排产过程是一个复杂的决策过程，其复杂性主要表现为对象复杂性、任务复杂性、目标多样性和关联复杂性[1]。生产批量计划问题主要研究生产企业同一时间不同任务之间及同一任务不同时间的组合计划，按照生产能力划分, 包括有能力约束和无能力约束批量问题[2,3]。目前，批量计划问题中研究最为广泛的问题是能力约束批量计划问题(CLSP，the capacitated lot sizing problem)，即研究在满足生产能力约束和生产单元容量限制的情况下使许多相似或相同的加工任务件组合在同一加工单元中，从而降低调整费用，降低成本，提高总体经济效益。Karimi等[2]对批量计划问题研究进展及算法应用进行了综述，Bitran等[4]证明了一类批量计划问题的NP-hard性。作业排序问题(Scheduling Problem)也称为作业调度问题，按照工件在机器上的流动形式，一般分为：单机车间(Single machine)、同型并行机车间(Identical Machine in Parallel)、作业车间(Job Shop)、流水车间(Flow Shop)、开放车间(Open Shop)等几种形式[5]。作业排序问题作为生产作业计划的主要研究问题，目前已经得到广泛研究[6～12]。柔性流水车间作业排序问题(Flexible Flow Shop Scheduling Problem，FFSP)是生产作业计划中广泛存在的问题，是流水车间问题的一种拓展，广泛存在于化工制造、钢铁铸造、食品加工、塑料塑造等领域，逐渐成为研究的热点[13～19]。而对于生产批量计划和作业排序的集成问题，建立单个模型来描述整个集成化的计划问题并考虑所有层次的约束是求解该类问题的有效方法，但主要困难在于模型求解的复杂度很高[20]。基于此，现有对于生产批量计划和作业排序的集成问题的研究，作业排序层面针对复杂的Job Shop和Flow Shop问题如柔性流水车间作业排序问题的研究很少[21]。Meyr[22]研究了能力约束生产批量计划问题和双机台并行作业排序集成问题，考虑无缺货情况下不同种类的需求如何满足，建立了整数规划模型并结合局部搜索元策略阈值接受法和模拟退火算法求解；安玉伟等[23]研究了单机器同步混批装配线组成的两阶段生产系统的作业排序问题和能力约束生产批量计划问题的集成问题，采用一种基于混合优化方法的分支定界法进行求解；Ramezanian等[24]研究了多产品多阶段能力约束生产批量计划问题和流水车间集成问题，采用了两种基于混合整数规划的滚动时域启发式算法求解模型；Wolosewicz等[25]研究了一类用连接图表示的复杂作业调度问题和能力约束生产批量计划问题，并采用拉格朗日松弛法求解。针对批量计划与柔性流水车间作业排序问题，目前尚无较为成熟的模型和算法。

就本文研究的问题来说，目前国内外有关卷烟生产批量计划和调度集成问题的研究几乎没有。已有的研究卷烟生产排程问题的文献中，Nicholls[26]以最小化生产过程中运行的机器台数为目标，考虑了在制品、产品转运需求以及和生产序列相关的机台生产约束降低的影响，建立了规划模型并给出一种简单的启发算法帮助排产决策；Pattloch等[27]以卷烟生产中品牌转换次数最小作为优化目标，建立了整数规划模型，证明了该问题的NP-hard性，并针对单机台和多机台问题分别给出给出一种启发式算法；王爱民等[28]针对烟草卷包排产方案优化制定、周订单滚动追加，以及面向订单执行时间和数量变化的计划与实际同步调整等问题，提出了烟草卷包作业动态调度技术，并通过实例验证了该算法的有效性；徐屹秦等[29]提出了符合卷烟生产特点的生产计划与调度系统, 并阐述了生产计划与调度系统的体系结构、功能模块、系统工作流程，设计了基于规则的调度算法；金剑等[30]构建了卷烟排产分层递阶优化流程，分别建立了带约束限制的卷烟多点生产任务分配和生产点详细排产数学模型，并对两个模型分别设计了改进的遗传优化算法，通过卷烟生产排产实例，验证了算法的有效性。这些研究都只针对卷烟的生产计划问题或作业调度问题，而未将两者集成考虑，或缺乏对实际生产中的能力约束条件的考虑，或基于整体流程优化，而较少针对具体某个生产单元研究批量计划和作业排序问题，但这恰恰是生产计划得以贯彻执行的基础。对于卷烟排产优化的目标，除了优化生产时间和品牌转换次数，还要求生产卷烟的品质尽可能高，这在以往的研究中几乎未被提及。因此研究卷烟企业的生产批量计划和调度集成问题具有重要的工程意义。

基于上述研究现状，本文根据卷烟生产特点，研究了卷烟生产过程中从卷包环节至封箱环节的能力约束生产批量计划和柔性流水车间调度集成问题。在第1节中描述了烟草的生产工艺流程；第2节中建立了卷烟生产整数规划模型；在第3节采用遗传算法对上述整数规划模型进行求解；第4节选取了某卷烟企业的真实数据，通过实例说明该模型的应用及求解过程，验证了算法的有效性和稳定性；在第5节中对本文的研究工作进行了总结和展望。

1 问题描述

卷烟生产与一般工业生产的过程既有联系，又有其自身特殊工艺的特点，在对卷烟排程进行优化建模之前，应对卷烟生产过程有基本的了解。由于卷烟企业的实际生产过程较为复杂，为研究方便，这里将卷烟生产线抽象为图1所示。本文主要研究卷烟从包装环节到封箱环节的生产过程中遇到的生产计划与调度集成问题。

图1 卷烟生产流程图

在生产批量计划层面上，将计划周期均分为T个时段，每个时段内对K种品牌的卷烟均有不同但确定的需求量，这些需求是由国务院计划部门下达，并根据上级烟草部门分配制定的，因此在本文中我们假设所有卷烟的总需求是确定的。单位时间内包装机和封箱机的生产能力是有限的，因此需要合理安排每种卷烟在各个时段的生产量以满足市场需求。每个时段的生产时间是固定的，生产不允许加班。由于市场需求量大，因此在工作期间机器都需要满负荷生产，且对于需求量大的产品应提前生产，但超过需求部分需要入库并支付库存费用。由于包装机和封箱机的准备成本(setup cost)很大，因此在生产过程中不允许中途停机，应保证连续生产直到满足周期内的所有需求。

在作业层面上，卷烟从包装机到封箱机的加工过程中，不同品牌的卷烟连续在两道工序(卷包和封箱)上以相同的顺序加工，所有卷烟的工艺路线相同；两道工序中均存在多台并行机器，卷烟开始加工后在两道工序之间无等待直至加工完成。上述问题是一个典型的柔性流水车间调度问题(Flexible Flow Shop Scheduling Problem，FFSP)，它是传统流水车间调度问题的推广，即允许在工件加工的过程中有并行机器。已经证明，两个阶段中只有一个阶段存在并行机器的FFSP问题属于NP-hard问题[31]。但是，卷烟生产的调度问题又具有自己的特点，其中最重要的特点是：1)每种品牌的卷烟在任一工序可由多台机器加工，而具体加工的机台数目是未知的，这就意味着虽然要加工的卷烟品牌数目是已知的，但每种品牌在每台包装机和封箱机上加工的时间是不确定的；2)封箱机的生产能力远超过包装机，因此包装机的加工时间均严格大于封箱机加工时间，包装机加工时间是绝对瓶颈。另外，卷烟加工过程中受某些因素限制，某些封箱机只能和指定的包装机连接，某些卷烟品牌只能由指定的包装机生产，且不同包装机生产的卷烟质量不同。这些都比传统的柔性流水车间生产调度问题更加复杂。

综上所述，根据卷烟企业生产特点，本文研究的问题具有如下特征：

(1)卷烟企业面临的需求在计划期内是确定的；

(2)所有机台在生产的每个时段都以恒定速率满负荷生产，不考虑机器故障，不允许中途停机；

(3)每台包装机每个时段只能生产一种品牌的卷烟，但一种卷烟品牌可同时被多台包装机生产；

(4)各种品牌的卷烟生产优先级相同；

(5)两种卷烟品牌转换的生产线调整时间(setup time)相对较短，可忽略不计；

(6)每台包装机只能生产指定的卷烟品牌，且不同包装机生产的卷烟质量不同；

(7)每台包装机只能与指定的封箱机连接；

(8)同一时间内，一台包装机只能连接一台封箱机，而一台封箱机可连接多台包装机；

(9)封箱机的生产能力远超过包装机，卷烟开始加工后在两道工序之间无等待；

(10)某些卷烟品牌刚进入市场不久，对其需求预测不准，月初即投入生产。

卷烟生产企业面临的问题是：应如何制定卷烟在包装机和封装机上的生产计划，才能使得企业在上述生产规则和能力约束下，满足市场需求，并优化生产流程。

2 数学建模

设卷烟企业有M台包装机、N台封箱机负责生产K种品牌的卷烟，生产的周期为T。第i台包装机单位时间内可生产第k种品牌卷烟的产能是qik，第k种品牌在第t个时间的需求量为Dkt，库存成本为ck。对于包装机和封箱机的连接，第i台包装机可连接的封箱机的集合为Ωi，第j台封箱机可连接的包装机的集合为Φj，可连接包装机的最大上限为dj。每台包装机的生产时间为Ci，生产的最大完工时间为Cmax。不同包装机生产的卷烟质量不同，第k种品牌卷烟在第i台包装机上生产的质量系数为ρik，ρik为0则表示品牌k不能在包装机i上生产。有些卷烟品牌由于新进入市场，需求难以预测，这些品牌集合为Θ。

定义以下决策变量：第k种品牌在第t个时段的库存数量Ikt；二元变量Xikt，Zijt，Yjkt，Sit。Xikt=1表示第i台包装机在第t个时段排产第k种品牌的卷烟，否则为0；Yjkt=1表示第j台封箱机在第t个时段封装第k种品牌的卷烟，否则为0；Zijt=1表示在第t个时段第j台封箱机与第i台包装机相连，否则为0；Sit=1表示在第t个时段包装机i要更换生产的卷烟品牌，否则为0。

对于卷烟企业的生产计划制定，生产优化要达到的目标有四个：首先是最小化生产时间，因为机台运转的维护成本极大；其次是最小化同一生产线上更换生产卷烟品牌的次数，因为在机台上转换生产不同品牌的卷烟的转换成本也很大，但要小于机台运转成本；第三，应合理安排包装机生产的卷烟品牌以提高卷烟的品质；最后，需要尽可能减小卷烟成品的库存成本，对于具有高架仓储的卷烟企业来说，这项成本一般小于前三项的重要性。

排产问题中研究多个目标的问题称为多目标排产问题，多目标排产问题也是一类多目标决策问题，它的关键问题在于由于多个目标之间常常是互相冲突的，一般不存在使多个目标同时达到最优的“绝对”最优解。多目标排产问题的求解方法可以分为三类[32]：第一类是寻找约束解或多重解，其中约束解是根据问题的实际情况，将目标函数按照重要程度排成次序，之后将次要的目标函数作为约束条件；多重解是在求得前一个目标函数最优解的基础上求后一个目标函数的最优解，并把最后一个目标函数的最优解作为多目标规划问题的最优解，这样得到的解称为多重解；第二类是寻找pareto最优解或称非支配解，即对于这样的解，不可能使得在任何目标函数上的改进不损害至少一个其他目标函数；第三类是通过构造权函数的方法把多目标排序转化为单目标排序，这种方法得到的多目标排序的解称为权函数解。

对于上述问题，卷烟企业一般很难获取具体的运营成本，仅能简单凭借投入的人力物力判断其相对大小。因此设上述四个目标分别为z1，z2，z3，z4，其权重分别为P1，P2，P3，P4，令P1≫P2≫P3≫P4。采用线性加权法，将多目标排序问题转换为单目标问题[33]，利用如下的权重确定方法，使得优先满足第一目标，当第一目标值相同时再比较第二目标，以此类推。权重的设置可采用如下方法:

在每个目标的判据空间中定义两个极限点: 最大极限点z+和最小极限点z-：

(1)

(2)

其中M为包装机数量，K为生产品牌总数量，T为最大生产时长，ρik×qik代表第i个包装机单位时间生产的产品质量，ck×Ikt代表第k个品牌在t时间的累计库存。最后，我们对于权重进行归一化处理，使得各目标权重和为1:

(3)

这样可以满足前述的目标偏好要求。

综上所述，建立整数规划模型如下:

minz=ω1z1+ω2z2+ω3z3+ω4z4

(4)

s.t.z1=Cmax

(5)

(6)

(7)

(8)

(9)

Cmax≥Ci,∀i

(10)

(11)

Sit≥Xik,t+1-Xikt,∀i,j,t

(12)

(13)

(14)

Xikt-Yjkt≤1-Zijt,∀i,j,k,t

(15)

Xikt-Yjkt≥Zijt-1,∀i,j,k,t

(16)

YN+1,kt=0,∀k,t

(17)

(18)

(19)

(20)

Xikt≤ρik,∀i,k,t

(21)

Xikt,Yjkt,Zijt,Sit∈{0,1},∀i,j,k,t

(22)

Ikt≥0,Cmax≥0,Ci≥0;Ikt,Cmax,Ci为整数,∀i,k,t

(23)

其中(4)为模型目标函数，(5)～(8)分别为最小化卷烟日生产时间、最小化品牌转换次数、最大化卷烟生产质量、最小化库存成本的子目标；约束(9)表示一台包装机在单位时间内最多生产一种品牌的卷烟；(10)(11)表示系统的生产时间由工作时间最长的包装机决定；约束(12)表示换牌次数由当前时间和下一时间机台是否生产品牌的差异决定；约束(13)表示每台包装机只能且必须连接一台封箱机；约束(14)表示一台封箱机可连接的包装机不能超过其上限；约束(15)(16)表示生产的连续性，即每台包装机和与其相连的封装机生产状态必须相同；约束(17)是为了保证生产的连续性，当某些包装机不生产时，与其连接的封箱机可能还在生产，这可能违反生产连续性约束(18)(19)，即出现了不生产的包装机但没有不生产的封箱机与之相连，由于每台包装机都必须和一台封箱机相连，因此设置一个虚拟的不生产封箱机，让它连接不生产的包装机；约束(18)表示一台封箱机在单位时间内最多生产一种品牌的卷烟；约束(19)表示库存平衡，为了确保模型在需求预期不准确的情形下仍然存在可行解，我们设置了一个虚拟的包装机，此包装机不需要与封箱机相连接。在具体问题中，可以设置虚拟包装机的产能qM+1,k正比于需求的不确定性，当需求不确定越高时，虚拟包装机的产能越大，这样保证模型始终存在可行解，对于缺货成本，则可以通过ρM+1,k来刻画，即认为品牌的缺货成本越高，虚拟包装机所生产的商品质量越低。通过设置较高的虚拟包装机产能，模型可以用于应对需求的不确定性，并将缺货成本考虑在最终的目标函数之中；约束(20)表示某些品牌的卷烟由于市场需求无法准确估计因此期初应安排生产；约束(21)表示某些包装机只能生产指定品牌的卷烟；约束(22)表示所有的决策变量均为二元变量；约束(23)是变量的取值约束。

3 遗传算法

由于前述的一般性模型具有NP-hard性，随着排产的卷烟品牌和每道工序上机器数量的增加，该模型的规模便非常庞大，求解将变得十分困难。遗传算法(GA)由于具有同时在多点进行搜索，有可能获得全局最优解等等优良特点[34]，对于结构复杂的组合优化问题有很好的效果，被广泛应用到工程领域解决生产计划与详细排产问题，产生唯一可行或多个可选可行方案。因此利用遗传算法解决上述排产优化问题，是求解卷烟企业优化排产问题的一个较优选择。

遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法[34]，它从一组随机产生的初始种群开始搜索过程，种群由染色体组成。染色体不断经过交叉和变异过程进化，在每一代中用适应值来评价染色体的优劣，在新一代形成过程中，根据适应值的大小选择部分后代，适应值较高的染色体被选中的概率较高。经过若干代之后，算法满足一定条件时收敛于最好的染色体，这样就可能得到原问题的最优解或次优解。

本文的优化问题约束比较复杂，采用遗传算法求解此类具有多个不连通可行域，且解空间离散的复杂组合优化问题时，对于不可行解的处理通常有以下三种：惩罚策略、修复策略以及改进遗传算子策略[20]。本文采用改进遗传算子和修复策略相结合的方法：生成初始种群时，根据约束特点，改进遗传算子，使初始个体满足约束；在进化过程中，合理设计遗传操作并对遗传操作后的后代进行修复，使遗传操作后子代个体仍满足约束。

3.1 编码方式

遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体，这一转换操作称为编码。由于模型中存在诸多约束，显然简单的二进制编码无法奏效，且本文的主要决策变量为三维变量，这时采用一维编码很难表示，且交叉操作很不直观，因此本文采用二维编码方式。在本文的模型中，若给定Xikt，则严格遵守模型中式(5)～(23)约束条件的Zijt，Yjkt，Sit可按一定方法求得。

因此在满足约束条件的前提下，为尽量减少算法复杂度，本文采取对Xikt编码，之后按照约束条件计算其余决策变量的方法来处理该模型求解。具体编码方式为将算法中种群的第h个染色体Gh表示为一个M×T的矩阵，矩阵中的每个元素为第i台包装机在第t个时间单位生产的卷烟牌号Kit，即

(24)

给定Xikt，生成Zijt的方法为：设染色体中Gh每列数字k出现的次数(即生产k品牌卷烟的包装机总数)为Bk，可生产k品牌卷烟的包装机集合为Ψk。对于任意包装机i∈Ψk，其能连接的封箱机集合为Ωi；对于任意封箱机j∈Ωi，其所能连接的最大包装机数目为dj。将Bk和dj排序，按照顺序依次分配封箱机给包装机。如果Bk>dj,则计算Bk-dj, 将差值结果排序后继续分配，直到Bk≤dj。如Bk或dj中有两项相同，则随机安排两者的顺序。对于无品牌生产的包装机，分配虚拟封箱机与其连接。

例如：有8台包装机M1～M8，可连接3台封箱机N1～N3，每台封箱机最多连接4台包装机。染色体的某一列(即某一单位时间的排产计划)为[1 1 1 1 1 2 2 2]T，表示包装机M1～M5生产卷烟品牌1，包装机M6～M8生产卷烟品牌2，此时B1=5，B2=3，对应地d1=d2=d3=4，但B1>d1，计算得B1-d1=1

给定Xikt，Zijt后，Yjkt可由约束(15)(16)确定。

3.2 初始种群

种群初始化的方法可采用在编码矩阵中随机产生卷烟品牌的方法，但本文中所述模型约束很多，为了保证初始解可行性，采用如下的初始化策略：

之后根据封箱机的约束检查Xikt是否可行，具体方法为：检查每列中不同的数字k的个数，即包装机所生产的卷烟品牌的数目，记为TB；这些包装机可连接的封箱机总数记为TN，若TB≤TN，则Xikt可行；否则初始解不可行，需要重新生成。

3.3 适应度函数

在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。适应度函数非常关键，它是评价个体优劣的唯一指标，直接影响到遗传算法的收敛速度，因此建立合适的适应度函数是非常重要的。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。对于模型的目标函数，可取适应度函数为C/(z1ω1+z2ω2+z3ω3+z4ω4)，其中C为一调节系数，使得适应度不会过小。这样目标值最小时适应度函数最大，保证了适应度函数为正，且便于排序和选择概率的计算。

3.4 选择方式

本文采用的选择策略结合轮盘赌策略与精英保留策略，首先按照轮盘赌方式执行遗传算法的选择功能，之后将当前解群体中适应度最高的个体替换掉当前群体中的最差个体。这样有效保证遗传算法终止时得到的结果一定是历代出现过的适应度最高的个体,同时避免了算法陷入局部最优解。

3.5 自适应交叉运算

设计交叉算子是遗传算法中最关键的步骤，它决定了遗传算法的全局搜索能力,也是逐步产生最优解最重要的遗传算子，常用的交叉算法有双亲双子法、变化交配法、多交配法等方法等[7]。在生产调度问题中应用遗传算法最重要的就是让子代能够继承父代的优良特性，根据本文的问题，为尽量保证交叉后子代仍满足需求约束，采用随机互换父代染色体矩阵中某一列的方法，如图2所示。

图2 自适应交叉过程

本文的交叉概率采用Srinvivas等[36]提出的自适应遗传算法确定交叉概率，交叉概率能够随着适应度大小而改变。适应度值高于群体平均适应度值的个体的交叉概率较低，得以进入下一代；而低于平均适应度值的个体则具有较高的交叉概率，使该个体被淘汰掉。交叉概率为

(25)

其中f′为要交叉的两个个体中较大的适应度值，其中fmax为群体中最大的适应度值，favg为群体的平均适应度值；f为要变异个体的适应度值。

最后参照种群初始化的方法，根据封箱机的约束检查交叉之后的Xikt是否可行，若不可行则从种群中排除该个体，再随机生成一个新的可行染色体。

3.6 自适应变异运算

变异算子能够从很大程度上提高群体的多样性，跳出局部最优解，也是遗传算法重要的算子之一。为了在保证种群多样性的同时保留父代优良的基因，保证遗传算法的收敛性，与自适应交叉概率类似，本文的变异概率采用Srinvivas等[36]提出的自适应遗传算法确定变异概率，变异概率为

(26)

具体变异方法为：在现有种群中以变异概率Pm随机选择一个染色体，随机选择染色体的两列互换位置，通过调整不同品牌卷烟的生产计划，促进最优解的产生。

变异后参照初始化和交叉操作的方法，采用顺时段库存平衡法进行修复并检查封箱机约束,若修复失败，或修复后的染色体不能满足封箱机约束，则从种群中排除该个体，再随机生成一个新的可行染色体。

3.7 算法终止条件

采用张铁男等[37]提出的终止判断条件：为保证计算结果精度，给定极小常数ε，当种群中某代与上一代适应度函数的均值差与上一代适应度函数均值比值的绝对值小于ε，或算法迭代次数到达指定值时认为算法达到收敛条件，终止算法。

4 算例分析

本文的算例在在Intel Core i7、CPU主频3.40GHz、8GB内存的Windows 10操作系统下使用MatlabR2015a测试，以某卷烟企业月平均生产数据作为实例分析。卷烟企业的计划生产周期为一个月，企业需要决定每日的排产方案，在满足市场需求的前提下优化生产流程。根据上级部门下达的总生产计划，结合市场部门以往卷烟的销售经验，该企业总结出了不同品牌卷烟的时段需求比例以及每月月初的库存比例以作为生产的依据，日需求量根据周需求量进行平均。卷烟企业生产设备包括14台不同种类的包装机，5台封箱机，共需生产7种品牌的卷烟。表1列出了上述卷烟生产信息。其中牌号7为新投入市场的品牌，其市场需求不确定，因此需要优先生产。该品牌的月需求总量是根据相似品牌的历史需求与市场调研结果给出的保守估计，以保证满足市场需求。

表1 各个品牌卷烟周需求和月度总需求及初始库存量

由于同一卷烟品牌在不同机台上生产的品质是不一样的，因此不同卷烟品牌在不同机台上生产会有不同的质量系数。表2为该卷烟企业根据自己的生产经验总结出了不同卷烟在不同包装机生产的质量系数，质量系数越低表示包装机生产的卷烟质量越好，质量系数为0表示包装机不能生产该品牌的卷烟。该企业的生产机台安排为：包装机A1～A6对应两台GDX2型封箱机，B1～B6对应两台FK型封装机，A7和C8对应一台GDX2型封箱机，每台封箱机最多可连接4台包装机。

表2 不同卷烟在不同包装机生产的质量系数

关于排产方式：该卷烟企业一般在每月月底根据上级公司发布的下月生产指标(品牌，数量)和市场需求情况，制定下月的生产计划、进行排产；在次月的中旬组织生产调度会，总结、调整本月的生产计划，并发布下月的生产预测(预计划)，以准备生产原料。

关于约束条件：除上述模型提到的条件之外，该卷烟企业还有自己特有的约束条件。第一，该卷烟企业要求所有机器同时停止，方便工企业进行管理。第二，该企业为保证满足市场需求，每月月初的在制品量(库存)一般保持稳定，因此月末的库存量应与月初的库存量水平相差不大。

关于目标函数：由于该卷烟企业库存成本很小，而且不同包装机生产的卷烟质量基本相差不大，因此卷烟企业的主要优化目标是最小化生产时间和换牌次数。

针对上述生产特点，建立整数规划模型后，采用遗传算法，对包装机排产模型进行求解。经过对本研究算法各参数的预实验，本文选取参数设置如表3所示，其中#pop表示种群数量，实验进行20次，最大进化代数为1000。预实验还发现，初始种群的选取对算法的收敛时间影响很大。对于本算例而言，在初始种群中除随机产生和启发式方法产生的初始解外，还加入了卷烟企业凭经验排产的方案，以加速算法收敛。

表3 遗传算法参数设置

20次优化的最小生产时间均为29天，与卷烟企业凭经验排产的结果相一致，而最优换牌次数则有所不同。表4展示了最优换牌次数的优化结果，标准差在1次之内，证明了本研究算法的有效性和稳定性。

图3 遗传算法收敛过程曲线

优化后得到的生产排程结果，生产天数为29天，换牌次数为8次，最优生产天数与卷烟企业经验排产的结果相一致，而换牌次数则得到了显著降低，图3展示了最优换牌次数的遗传进化曲线，优化后的包装机生产安排如图4所示。

图4 遗传算法优化排产结果

在满足市场需求的条件下，本文的算法优化了换牌次数，证明了算法的可行性，并得到了卷烟企业排产人员的认可。目前，该算法已作为某卷烟企业排产人员的排产参考，应用于生产决策中。该算法可以快速高效地制定卷烟生产排程计划，为卷烟企业计划人员制定生产计划提供决策支持，有效降低因卷烟品牌转换造成的大量转换成本，优化生产流程。

为了进一步测试本文的求解算法(称为Improved Genetic Algorithm，IGA算法)的优化性能，本文分别采用了标准遗传算法(Standard Genetic algorithm, SGA)、模拟退火算法(Simulated annealing, SA)和优化求解软件ILOGCPLEX 12.6进行对比实验。每种算法都独立运行20次。具体算法设置为：SGA算法随机产生初始种群并去掉不满足约束解，交叉和变异方式除概率固定外其余与IGA算法相同，采用轮盘赌和精英保留策略选择新一代个体。GA的算法参数设置为:种群规模为100,交叉概率0.95,变异概率0.05。GA的算法停止规则与IGA相同。SA算法随机产生初始个体,采用与本文IGA算法中变异相似的交换方式(Swap)产生邻域个体,按照Metropolis抽样过程产生新个体。SA算法中的参数值为:初始温度为100,终止温度为0.001,退火速率为0.9995。

测试结果如表5所示。Cmax表示最优的最大化生产时间，本算例中不同算法独立运行20次均得到相同的最大化生产时间29天。TS表示最优换牌次数，BVE(TS)表示20次仿真获得的最优换牌次数，AVE(TS)表示20次仿真获得的平均换牌次数，STD(TS)表示20次仿真结果的标准差。

表5 算法性能比较

可以看出，对于本文中的案例，IGA算法相对于SGA和SA算法得到的结果具有更小的平均值和标准差(ILOG CPLEX采用确定性算法，因此结果标准差为0)，这说明IGA算法不仅有较高的精度, 而且具有较高的鲁棒性,结果受随机因素的影响较小。从时间性能方面来说，IGA算法相对于其他算法消耗的时间更长，但这一方面受算法终止条件的影响，同时也避免了算法过早陷入局部最优解。

5 结论

卷烟包装至封箱环节的生产过程将直接决定库存成品是否能够满足市场需求，是卷烟企业排产计划的核心；该过程中的批量计划和作业排序问题，是卷烟企业生产计划得以贯彻执行的基础。因此对卷烟企业生产批量计划和调度集成问题的研究具有重要的工程意义。本文对卷烟生产过程中的生产计划和柔性流水车间调度集成问题进行了优化，以减少生产时间，降低换牌次数及库存成本、提高卷烟生产质量作为排程优化的目标。建立了基于卷烟企业生产约束条件的整数规划模型，并利用遗传算法对模型进行求解，通过合理设计遗传算子避免了不可行解的出现。利用某卷烟企业的生产数据给出了具体排程结果，并与该企业之前经验排产方案进行对比，发现优化排程模型和算法在减少换牌次数，提高生产的连续性方面具有明显优势，证明了模型的有效性和稳定性。