考虑员工移动成本的车缝生产线平衡问题

摘要

针对车缝生产线多品种小批量和自动化程度低等特点，提出了考虑员工多工序作业移动成本和为瓶颈工序增设适量设备的车缝生产线平衡问题。通过引入虚拟工作站和标准在制品（SWIP）库存概念，构建最大平衡率和最小生产节拍的双目标优化模型。最后，通过设计枚举算法和基于贪婪搜索策略的多目标遗传算法获取新增设备方案、标准在制品数量以及线平衡优化方案。车缝生产线实例计算结果表明，线平衡率及生产效率得到大幅提升，验证了模型和算法的合理性与有效性。

关键词

车缝生产线平衡问题; 员工移动成本; 虚拟工作站; 标准在制品（SWIP）库存; 遗传算法

服装制造业的订单日益趋于多品种、小批量化，每次订单切换都会导致车缝生产线的原平衡方案失效，因此需要对机器配置与人员分工方案进行调整以达到良好的生产线平衡。目前，即使在服装业的龙头企业，有标准工时数据作为基础，车缝生产线平衡和员工配置方案也多由一线生产管理者依据个人经验决定，不仅耗时良久，还难以获得最优解决方案^［1］。因此，建立具有实际应用价值的车缝生产线平衡和人员分工优化模型，对于服装制造业有重要意义。

车缝生产线本质上是借助低自动化程度的机器进行人工操作的装配生产线。国内外已有许多关于装配生产线平衡问题（assembly line balancing problem， ALBP）的研究。根据目标函数的差别，ALBP被划分成ALBP‒Ⅰ、ALBP‒Ⅱ及其他类型^［2］。ALBP‒Ⅰ为在给定生产节拍下优化工作站数量，常用于装配线设计阶段；ALBP‒Ⅱ为在给定工作站数量下优化生产效率，常用于解决产品多样化带来的不平衡问题。随着研究的拓展与深入，ALBP的优化目标也呈现多样化，包括资源、成本、生产节拍、生产周期以及工作负荷平滑指数最小化、平衡率最大化或多目标组合等。Zhang等^［3］以车缝生产线设计为目的，在ALBP‒Ⅰ的基础上考虑了产品移动距离和设备占地面积，以运输距离最小化和占地面积最小化为目标建立了双目标数学模型并求解。Araújo等^［4］以装配线平衡与员工配置问题（ALWABP）为基础提出了允许设置并行工作站处理相同任务以及同一工作站内允许多名员工合作2种拓展模型，以生产节拍最小为目标建立数学模型并优化求解。Triki等^［5］对ALBP‒Ⅱ问题进行了扩展，在工作站数量固定的条件下考虑了线上已有资源每小时消耗的成本，建立了资源消耗最小化和生产节拍最小化的双目标整数规划模型，并采用多目标遗传算法求解。邱玉莲等^［6］针对ALBP‒Ⅱ，建立了考虑最小化工资成本和最小化负载均衡的双目标数学模型。Boschetti等^［7］在生产线中引入协作机器人，将线平衡问题与机器人的任务分配问题结合，以makespan最小化为目标建立了协作装配线平衡模型（C‒ALBP）。

求解线平衡问题的方法也呈现多样化，精确算法多用于单目标简单线平衡问题。Walter等^［8］基于分支定界设计了简单生产线平滑算法，Dinler等^［9］利用精确算法求解工作负载平滑线平衡问题（workload smoothing line balancing problem， WSLBP），并比较了不同混合整数规划表达形式对结果的影响。然而，精确算法难以应对该类问题作为NP‒hard问题时的大规模情形或者复杂情形，因此近年来越来越多的学者开始使用启发式算法和元启发算法来解决各类线平衡问题。Eryuruk等^［10］利用Arena仿真程序模拟了服装流水线，并应用2种启发式装配线平衡技术来设计多模型装配线。Li等^［11］提出了一种增强的迭代分支定界与记忆的精确算法和一种增强的迭代波束搜索的启发式算法来解决ALBP‒Ⅱ。Khorram等^［12］通过改进模拟退火算法、可变领域搜索算法以及遗传算法求解U型线多目标线平衡问题。遗传算法^［13-16］、群体优化算法^［17-19］等智能搜索算法因其优秀的全局搜索能力与鲁棒性得到了广泛的应用并表现出较好的适用性。此外，利用仿真分析、理论分析以及现场实验等^［20-22］对实际服装流水线进行优化也是寻求局部最优解决方案的有效途径。

现有理论模型仍存在较大的不适应性，主要体现在划分工作站时忽略员工移动成本对优化结果的影响。车缝生产线上员工通过移动处理多道工序，实际生产数据显示，员工在工序间移动时间和工序作业时间属于同一量级，因此忽略移动时间成本使得理论模型输出显著不合理的员工配置结果。此外，“单件流”等常见假设也与实际生产存在差异。综合上述分析，以车缝生产线为研究对象，在引入“单扎流”（即标准在制品库存）的同时投入少量设备资源以优化瓶颈工序。考虑员工移动成本，以生产节拍最小化与平衡率最大为目标构建更符合车缝生产线实际情况的线平衡优化模型。最后，通过改进遗传算法和实例验证模型有效性。

1 问题描述

1.1　作为ALBP-Ⅱ的车缝生产线平衡问题

为每个工作站分配一名员工，即工作站数量固定（等于员工数量），满足ALBP‒Ⅱ工作站数量固定下优化生产效率的特征，因此本研究中车缝生产线平衡问题属于ALBP‒Ⅱ。此外，车缝生产线产品多变、换型频繁的特点是服装行业市场需求的快速变化在制造环节的投影，在此背景下，如果以ALBP‒Ⅰ的思维必然导致不同产品生产时生产线人员组成的变化，一些人员就需要在不同生产线之间被调来调去。然而以人员组成（包括人数）不变为前提寻求生产效率提升，这种ALBP‒Ⅱ的思维更有助于创造员工的团队归属感。

1.2　考虑员工移动的虚拟工作站

常规生产线将多个工序合并成一个工作站，在工作站内不考虑员工移动成本，这种假设通常有2个理由：①作业的机器自动化程度较高，员工的移动发生在机器自动化作业过程中，移动时间不增加工序的作业周期，可以忽略；②虽然作业的机器自动化程度较低，但是移动时间相对于工序作业周期来说很小，也可以忽略。对于车缝生产线来说，以上2个理由均不成立：一方面，生产的自动化程度不高，设备运转的全程需要员工操作；另一方面，各工序的典型作业周期是30 s左右，与员工移动时间属于同一数量级，不可忽略。

实际上，移动导致的效率损失（成本）^［23-25］不仅包括员工的走动时间，还包括起身、离开工位、进入工位和坐下所需要的时间，甚至包括员工重新进入一个工序时的热身成本。在本研究中，移动成本被简化为移动时间，即移动距离除以速度。

在考虑员工移动成本的基础上，员工在不同地理位置上的多工序作业可被视作“虚拟工作站”，如图1所示。每名员工是一个虚拟工作站，工作站所需作业周期是各工序的作业时间与移动成本之和。

图 1  虚拟工作站示意图

Fig. 1  Schematic diagram of virtual workstation

1.3　“单扎流”与标准在制品库存

“单件流”是生产管理追求的目标，但实际车缝生产多以“扎包”形式流转，背后有多方面原因。基本原因是产品的尺码、颜色等需要区分，不同扎的在制品可能不同。也有其他原因，如：人工作业时间有较大的变异性，多周期作业可以比单周期作业显著降低作业时间的变异性；一次传递一扎比一次传递一件能减少在制品传递时间；作为原材料的面料可能需要区分色级。

将“扎包”式流转的生产现实与车缝生产线平衡问题的理论研究结合起来，引入“单扎流”概念，每“扎”的件数可以被视为标准在制品（standard work-in-process， SWIP）库存数。员工在多工序之间的作业不再以单“件”而是以单“扎”的作业周期为生产节拍，在每“扎”的生产节拍里完成相应的车缝作业和移动。

相比于“单件流”，“单扎流”生产线可以将同一工序的作业任务以“件”为单位分给不同员工负责。在本问题中员工移动成本不可忽略，每一次移动都会使产品的实际加工时间在工序标准作业时间的基础上增加，而通过增加SWIP数来分摊员工移动时间成本，对提高总生产效率有利。然而，根据精益生产理论，过多的SWIP会导致分工不平衡、生产时间波动、设备故障和质量不良等问题被隐瞒，因此必须限制SWIP数以限制其对生产线带来的负面影响。

1.4　瓶颈工序处增设机台与时间宽松系数

考虑通过投入少量设备资源即在瓶颈工序处增设机台来优化平衡率和效率。一方面，车缝生产中的资源主要由三方面构成，分别是物料、人力和机台，机台的较低价值以及广泛应用是车缝生产线的特点之一，使用最广泛的机台价值在2 000~ 5 000元之间，使用年限超过10年，能安装不同模具以服务于有不同工艺要求的各种工序，因此机台的成本远小于人力成本（月工资5 000元左右）；另一方面，车缝工艺的各工序中每件产品必须由工人在机台上加工，一个机台只能处理一道工序且一个机台仅需一人处理，因此在为瓶颈工序增添机台的同时将部分在制品分摊到新增机台上使得工人通过移动来协助其他工序作业成为可能，也为生产率和生产效率带来更大的提升空间，因此模型中固定人力资源数量并通过适量增设服务于瓶颈工序的机台来优化平衡率与生产效率是合理的。然而，由于场地面积、现有机台种类和数量限制等因素，车缝线实际允许增设的机台数量有限，必须考虑新增机台数量的约束。

以车缝生产线中常见的单边直线型串行生产线为研究对象，该生产线一共有$P$道工序，完成工序$p$（$p\in \left\{\mathrm{1,2},\cdots ,P\right\})$的标准作业时间为$t_{\mathrm{s}p}$；$m$表示第$m$个机台，$m\in \left\{\mathrm{1,2},\cdots ,M\right\}$。

为了识别瓶颈工序并决策瓶颈工序应增设的机台数量，引入时间宽松系数$\rho \in (\mathrm{0,2}]$。瓶颈工序判断的基准工时阈值

$$\mu =\rho \frac{{\displaystyle \sum _{p=\mathrm{1}}^P}{t}_{\mathrm{s}p}}{P}$$

（1）

将标准作业时间大于基准工时阈值$\mu$的工序视为瓶颈工序，记瓶颈工序为$p^{\text{'}}$。在瓶颈工序处配置额外机台，使该工序的平均作业周期不超过阈值，同时新增机台的总数不超过最大允许新增机台数$m^{\text{'}}$。${\theta }_{p\text{'}}$表示瓶颈工序$p^{\text{'}}$增设的备用机台数，计算式如下所示：

（2）

$$\sum _{U_{m^{\text{'}}}}({\theta }_{p^{\text{'}}}{)}_{\mathrm{m}\mathrm{i}\mathrm{n}}\le m^{\text{'}}$$

（3）

式中：$U_{m\text{'}}$为瓶颈工序$p^{\text{'}}$备用机台集合；$m^{\text{'}}$取决于最大在手设备种类、数量与场地面积。新增机台数约束和宽松系数共同影响着瓶颈工序及其新增机台数的决策。

2 数学模型

2.1　假设

基于车缝生产线实际情况作出假设。假设1，初始状态下每道工序开设1个机台进行加工。假设2，各工序的标准作业时间$t_{\mathrm{s}p}$已知，由生产管理部门提供。车缝工序的顺序可调范围很小，通过工序重排提高平衡率对于车缝生产线而言机会很小，而且机台需要根据其服务的具体工序进行特别设置，因此调整后的机台对于工序具有专用性。由此，提出假设3，即工序之间的紧前/紧后关系确定且唯一，机台按工艺顺序设置。员工在机台间的移动距离与机台长度相关，而实际所用机台的长度差异在0到20 cm之间，对移动时间的影响极小，因此提出假设4，即每个机台的长度相同。假设5，员工为全技能员工，而且不考虑员工技能水平的差异。

对假设5的合理性有必要特别说明。一般认为车缝的操作难度较高，培训全技能员工的成本较高，但由于新增机台数量的限制，本研究的输出方案中大部分员工为单工序操作，少数员工在2~3道工序中操作。因此，虽然建模时作出的员工全技能假设看似严苛，但是实际上只需要对多工序操作的员工进行针对性的提前培训，使他们掌握额外的1~2个工序技能即可，不影响输出方案的可行性。

2.2　任务分配矩阵

为了描述一个批次SWIP中每个工件每一道工序的任务分配情况，引入任务分配矩阵${\mathit{A}}_p$（见式（4））。以s表示SWIP内工件数，$d$表示一批SWIP内第$d$个工件，$d=\mathrm{1,2},\cdots ,s$；${\mathit{A}}_p$的行表示SWIP内工件数，列表示机台数，每一行的非零元素表示第$d$个工件在机台$m$上由编号为$A_p\left(d,m\right)$的员工进行加工。由于机台与工序“一对一”的关系，任务分配矩阵能直观地反映每个工件在各工序上是由哪一位员工进行操作。

$$\begin{array}{c}{\mathit{A}}_p=\left[\begin{array}{cc}\begin{array}{ccc}{A}_p\left(\mathrm{1,1}\right)& A_p\left(\mathrm{1,2}\right)& \cdots \end{array}& A_p\left(\mathrm{1},M\right)\\ \begin{array}{ccc}\begin{array}{l}{A}_p\left(\mathrm{2,1}\right)\\ ⋮\\ A_p\left(s,\mathrm{1}\right)\end{array}& \begin{array}{l}{A}_p\left(\mathrm{2,2}\right)\\ ⋮\\ A_p\left(s,\mathrm{1}\right)\end{array}& \begin{array}{l}\cdots \\ \\ \cdots \end{array}\end{array}& \begin{array}{l}{A}_p\left(\mathrm{2},M\right)\\ ⋮\\ A_p\left(s,M\right)\end{array}\end{array}\right]\end{array}$$

（4）

2.3　参数定义

以固定员工数量为前提，通过新增机台和允许移动协同作业来优化生产线效率，工序数多于员工数，而机台数多于工序数，故存在员工承担不止一道工序的情况和一道工序具备多个机台的情况。因此，在确定了新增机台方案后需要决策：①每个机台服务的工序；②机台由哪一位员工看管（机台属于哪个工作站）；③各道工序中SWIP内每个工件在哪个机台上加工；④每个工件各工序的开始时间。设置的决策变量及相关参数定义如表1和2所示。

表 1  决策变量定义

Tab. 1  Definition of decision variables

决策变量	定义
$X_{jp}$	当机台$j$属于工序$p$时，$X_{jp}=1$，否则$\mathrm{为}0$
$Y_{ij}$	当$\mathrm{员}\mathrm{工}i\mathrm{操}\mathrm{作}\mathrm{机}\mathrm{台}j\mathrm{时},Y_{ij}=1,\mathrm{否}\mathrm{则}\mathrm{为}0$
$H_{kjp}$	工件$k$的第$p$道工序在机台$j$上加工时，$H_{kjp}=$1，否则为0
$Z_{kjt}$	工件$k$在机台$j$上加工开始时间为$t$时，$Z_{kjt}=$1，否则为0

表 2  相关参数定义

Tab. 2  Definitions of related parameters

参数	定义
$i$	员工编号，$i=\mathrm{1,2},\cdots ,n$
$j,l$	机台编号，$j,l=\mathrm{1,2},3,\dots ,m,m\ge n$
$p$	工序编号，$p=\mathrm{1,2},3,\dots ,P$
$k,r$	单批SWIP内工件编号
$T$	离散化时刻集合
$v$	员工移动速度，模型中忽略员工移动速度的差异
$Q_j$	在机台$j$上加工的工件集合
$D_{jl}$	机台$j$与$l$之间的距离
$t_{\mathrm{s}p}$	第$p$道工序的标准作业时间
$t_j$	机台$j$完成加工任务所花费的时间
$t_{\mathrm{w}i}$	工作站$i$完成加工任务所花费的时间
$p_j$	机台$j$所属工序编号
$M_i$	员工$i$所看管的机台集合

2.4　数学模型

以“单扎流”生产节拍最短和生产线平衡率最大为目标建立双目标整数规划模型，作为ALBP‒Ⅱ的扩展，其优化目标同样为最大化生产线工作效率，以平衡率最大化与生产节拍最小化为双目标。机台$j$完成加工任务所花费的时间如下所示：

$$t_j=\underset{k}{\mathrm{m}\mathrm{a}\mathrm{x}}\sum _{t\in T}t{Z}_{kjt}-\underset{k}{\mathrm{m}\mathrm{i}\mathrm{n}}\sum _{t\in T}t{Z}_{kjt}+t_{\mathrm{s}{p}_j}$$

（5）

式中：$\underset{k}{\mathrm{m}\mathrm{a}\mathrm{x}}\sum _{t\in T}t{Z}_{kjt}$和$\underset{k}{\mathrm{m}\mathrm{i}\mathrm{n}}\sum _{t\in T}t{Z}_{kjt}$分别为机台$j$上最迟加工工件的开始时间和最早加工工件的开始时间；$t_{\mathrm{s}{p}_j}$为机台$j$处理完所有工件的结束时间。最迟加工工件的开始时间加上机台$j$加工一个工件的标准作业时间$t_{s{p}_j}$即为机台$j$处理完所有工件的结束时间，该结束时间减去最早加工工件的开始时间（机台$j$的加工开始时间）即为机台$j$处理完所有加工任务的耗时。员工$i$所看管的机台集合为$M_i$，每一个员工代表着一个工作站，故第$i$个工作站完成加工任务所花费的时间为员工$i$处理完其看管的各机器的工作任务所消耗的时间加上其在各机器之间的移动时间，如下所示：

$$t_{\mathrm{w}i}=\sum _{j\in M_i}{t}_j+\frac{\sum D_{jl}}{v}$$

（6）

因此，目标函数如下所示：

$$\mathrm{m}\mathrm{i}\mathrm{n}F=(f_{\mathrm{1}},\mathrm{1}-f_{\mathrm{2}})$$

（7）

$$f_{\mathrm{1}}=\underset{i}{\mathrm{m}\mathrm{a}\mathrm{x}}{t}_{\mathrm{w}i}$$

（8）

$$f_{\mathrm{2}}=\frac{\sum _i{t}_{\mathrm{w}i}}{n\underset{i}{\mathrm{m}\mathrm{a}\mathrm{x}}{t}_{\mathrm{w}i}}$$

（9）

式中：$f_{\mathrm{1}}$为生产节拍；$f_{\mathrm{2}}$为生产线平衡率。

约束条件如下所示：

$$X_{jp}-H_{kjp}\ge \mathrm{0},\forall k=\mathrm{1,2},\dots ,s$$

（10）

$$\sum _k\sum _{j\in \left\{\left.j\right|X_{jp}=\mathrm{1}\right\}}{H}_{kjp}=s,\forall p=\mathrm{1,2},\dots ,P$$

（11）

$$\sum _p{X}_{jp}=\mathrm{1},\forall j=\mathrm{1,2},\dots ,m$$

（12）

$$\sum _i{Y}_{ij}=\mathrm{1},\forall j=\mathrm{1,2},\dots ,m$$

（13）

$$\sum _{t\in T}{Z}_{kjt}=\mathrm{1},\forall k,j\in \left\{\left.k,j\right|H_{kjp}=\mathrm{1}\right\}$$

（14）

$$\sum _{t\in T}t{Z}_{kjt}+t_{\mathrm{s}p}\le \sum _{t\in T}t{Z}_{\left(k+\mathrm{1}\right)jt},\forall k,j,p\in \left\{\left.k,j,p\right|H_{kjp}=H_{(k+\mathrm{1})jp}=\mathrm{1}\right\}$$

（15）

$$\underset{k}{\mathrm{m}\mathrm{a}\mathrm{x}}\sum _{t\in T}t{Z}_{kjt}+t_{\mathrm{s}{p}_j}+\frac{D_{jl}}{v}\le \underset{r}{\mathrm{m}\mathrm{i}\mathrm{n}}\sum _{t\in T}t{Z}_{rlt},$$

$$\forall j,l\in M_i,j\ne l,X_{jp}=X_{lr}=\mathrm{1},p\le r,$$

$$\forall k,r=\mathrm{1,2},\dots ,s,\forall i=\mathrm{1,2},\dots ,n$$

（16）

式（10）为决策变量$X_{jp}$与$H_{kjp}$之间的关系，表示一批SWIP内的工件可以在工序$p$包含的各个设备上进行加工；式（11）表示每道工序都必须加工完SWIP内的所有工件；式（12）表示一个机台只能处理一道工序，而一道工序可包含多个机台；式（13）表示一个机台只能由一个人操作，而一个人可以看管多个机台；式（14）为加工时间约束，任何工件的任意工序仅在一个机台的一个时刻开始；式（15）表示员工在一个机台连续加工多个工件时，前一个工件的加工结束时间不超过后一个工件的加工开始时间；式（16）表示当员工加工完一个机台的所有工件后移动到下一个机台时，在前一个机台加工最后一个工件的完成时间加上员工的移动时间不超过在下一个机台加工第一个工件的开始时间。

3 算法实现

3.1　确定新增机台方案

确定满足最大新增机台数约束的新增机台方案是求解该问题的第一步，由第1.4节的内容可知，时间宽松系数$\rho$影响着瓶颈工序的判断，制约着各瓶颈工序的新增机台数，因此可以通过遍历穷举获得满足最大新增机台约束的时间宽松系数，从而获得瓶颈工序及其新增机台数，伪代码如图2所示。

图 2  确定新增机台方案的伪代码

Fig. 2  Pseudocode for determining newly added machine scheme

3.2　遗传算法

生产线平衡和员工配置问题是NP‒hard问题，对于员工数、设备数较多的情况解析法无法求解，解决此类问题大多是由智能搜索算法实现。遗传算法（GA）作为一种全局优化的智能算法^［10-12］在该类问题求解中得到了广泛应用，本研究中利用遗传算法进行求解。

3.2.1　编码与解码

考虑到每道工序对应一个机台且新增机台所服务的工序确定，采用三层整数编码的方式表示各解。如图3所示，第一层为工序划分码，染色体长度为工序数，基因的位置$p$表示第$p$道工序，$d_p$为第$p$位基因所包含的整数，表示服务于第$p$道工序的机台属于第$d_{\mathrm{1}p}$个工作站。第二层为新增机台码，包含各新增机台所在的工作站信息，染色体长度为新增机台数，其中第$j$个基因的整数$d_{\mathrm{2}j}$表示第$j$台新增设备属于$d_{\mathrm{2}j}$工作站。第三层为工件分配码，长度为新增机台数，第$j$个基因的整数$d_{\mathrm{3}j}$表示第$j$个新增机台上分配的工件数。三层整数编码因其反映的信息特殊性而需要满足一定的约束。第一层和第二层编码基因值均为员工编号（虚拟工作站编号），因此其基因值不能超过工作站数量，而且第一层编码要求染色体内必须包含所有员工编号，即每个机台都需要划分到工作站中，不能有遗漏。第三层编码反映工件数信息，基因值须满足同一道工序内所有机台上加工的工件数不得超过SWIP数取值约束。

图 3  编码方式示例

Fig. 3  Coding scheme example

解码时，由于每个工作站只有一名员工，每道工序初始状态时拥有一个机台，综合考虑包含新增机台在内的所有机台，可获得每个机台服务的工序集合$P_j=\{p_{\mathrm{1}},p_{\mathrm{2}},\dots ,p_j\}$。由工序划分码和新增机台码可知各工作站所包含的机台集合$M_i=\left\{m_{\mathrm{1}},m_{\mathrm{2}},\dots ,m_{\epsilon }\right\}$，表示第$i$个工作站包含机台$m_{\mathrm{1}},m_{\mathrm{2}},\dots ,m_{\epsilon }$，$\epsilon$为该虚拟工作站包含的机台数。非瓶颈工序仅有一个机台，需处理一批SWIP内的所有工件，瓶颈工序具备多个机台，多个机台共同处理SWIP内的所有工件。工件分配码确定了各新增机台需要处理的工件数，故可以求得各机台上加工工件集合$Q_j=\{x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_j\}$，$x_j$表示机台$j$需要加工的工件数。一个工作站内员工处理完所有机台加工任务的时间加上其移动时间即为工作站标准作业时间，从而可求得各工作站标准作业时间集合$\Omega =\left\{t_{\mathrm{s}i}^{\text{'}}\right\},i=\mathrm{1,2},\dots ,P$，$t_{\mathrm{s}i}^{\text{'}}$的计算式如下所示：

$$t_{\mathrm{s}i}^{\text{'}}={\displaystyle \sum _j^{M_i}}{x}_j{t}_{\mathrm{s}{p}_j}+\frac{{\displaystyle \sum _{\alpha =\mathrm{1}}^{\epsilon -\mathrm{1}}}{D}_{m_{\alpha }{m}_{\alpha +\mathrm{1}}}}{v}$$

（17）

由此计算得到$f_{\mathrm{1}}$、$f_{\mathrm{2}}$，如下所示：

$$f_{\mathrm{1}}=\underset{i}{\mathrm{m}\mathrm{a}\mathrm{x}}{t}_{\mathrm{s}i}^{\text{'}}$$

（18）

$$f_{\mathrm{2}}=\frac{{\displaystyle \sum _{i=\mathrm{1}}^n}{t}_{\mathrm{s}i}^{\text{'}}}{n\underset{i}{\mathrm{m}\mathrm{a}\mathrm{x}}{t}_{si}^{\text{'}}}$$

（19）

3.2.2　遗传算子

在本研究中，目标是最小化单批SWIP的生产节拍和最大化平衡率，故适应度函数$f$确定为平衡率和生产节拍倒数的加权求和，如下所示：

$$f={\mu }_{\mathrm{1}}\frac{\mathrm{1}}{f_{\mathrm{1}}}+{\mu }_{\mathrm{2}}{f}_{\mathrm{2}}$$

（20）

式中：${\mu }_{\mathrm{1}}$、${\mu }_{\mathrm{2}}$分别表示生产节拍倒数的权重值与平衡率的权重值。子代选择采用轮盘赌策略，其中选择概率与适应度函值成正比。为了在保证全局搜索随机性的同时尽可能减少对优秀可行解的破坏，决定工作站划分的第一层编码和第二层编码的染色体采用子路径交叉策略，即随机在任一父代上选择一段基因，保持其他基因位置与值不变，在另一父代上找到这些基因的位置，按其出现顺序，交换两父代染色体中基因的位置，生成子代。决定机台加工数量的第三层编码的染色体采用单点交叉策略，即随机选择交叉点分割并交换右侧的父代染色体得到子代。三层编码的变异操作为随机选择基因变异点，对于第一、第二层编码，从可行整数取值区间内随机挑选一个不等于该点基因值的整数替换该位置基因；对于第三层编码，将变异点基因整数随机加或减固定步长。每次交叉变异后对产生的不可行子代进行修复，保证其染色体满足模型约束。

本研究中采用随机生成的方式创建初始种群，设置种群规模为200。交叉概率为0.9，变异概率为0.1，迭代次数为300。初步测试表明，遗传算法能够快速找到解决方案。

4 实例分析

4.1　算例应用

以某标杆服装企业的衬衫车缝生产线为例，该生产线为直线型单边生产线。某款衬衫有17道加工工序，生产线员工15人，各工序的标准作业时间如表3所示。原生产线中每个工作站仅有一个机台，由一名员工加工一道工序。车间允许最大新增机台数为3台，可算得时间宽松系数$\rho =\mathrm{1}$，此时瓶颈工序$\left\{\mathrm{7,8},\mathrm{11}\right\}$需要增设1个机台。2个机台之间的距离为1.15 m，SWIP的数量$s=\mathrm{8}$，假设员工的移动速度$v_{\mathrm{e}}=\mathrm{1}\mathrm{m}\cdot {\mathrm{s}}^{-\mathrm{1}}$，计算得到平均标准作业时间为34.06 s。

表 3  各工序的标准作业时间

Tab. 3  Standard time of each operation

$p$	工序名称	$t_{\mathrm{s}p}$	人员分配	$p$	工序名称	$t_{\mathrm{s}p}$	人员分配
1	纳膊	26.4	1	10	间衫脚	32.4	9
2	间纳膊	22.2	1	11	上袖口*	52.8	10
3	上领	30.6	2	12	间袖口	23.4	11
4	拉领窝捆条	27.0	3	13	车成衣唛	31.8	12
5	封领捆条	46.8	4	14	落侧骨唛	14.4	13
6	上袖	45.0	5	15	驳领	18.6	13
7	间夹圈*	47.4	6	16	驳衫脚	24.6	14
8	埋夹*	56.4	7	17	驳袖口	34.0	15
9	上衫脚	45.6	8

注：  *表示瓶颈工序。

算法的参数设置如下：种群规模200，交叉概率0.9，变异概率0.1，最大进化代数300。最终得到的工作站划分结果如表4所示，表4中7‒1、8‒1和11‒1均为工序新增的机台号，如7‒1表示第7道工序新增的机台1。进一步获得的员工任务分配矩阵如表5所示，根据第2.2节的内容，表5中的元素即员工任务分配矩阵元素，表示员工编号，该表规定了处理SWIP内各工件时各道工序的员工和机台。

表 4  工作站划分

Tab. 4  Workstation allocation

工作站/员工序号	包含机台	标准作业时间
1	｛1｝	26.40
2	｛2， 8‒1｝	46.30
3	｛3｝	30.60
4	｛4， 7‒1｝	45.45
5	｛5｝	46.80
6	｛6｝	45.00
7	｛7｝	35.55
8	｛8｝	42.30
9	｛9｝	45.60
10	｛10｝	32.40
11	｛11｝	39.60
12	｛12， 11‒1｝	40.90
13	｛13，14｝	46.20
14	｛15，16｝	43.20
15	｛17｝	34.00

表 5  员工任务分配

Tab. 5  Worker task allocation

工件号	不同机台对应的员工编号
	1	2	3	4	5	6	7	7‒1	8	8‒1
1	1	2	3	4	5	6	7		8
2	1	2	3	4	5	6	7		8
3	1	2	3	4	5	6	7		8
4	1	2	3	4	5	6	7		8
5	1	2	3	4	5	6	7		8
6	1	2	3	4	5	6	7		8
7	1	2	3	4	5	6		4		2
8	1	2	3	4	5	6		4		2
工件号	不同机台对应的员工编号
	9	10	11	11‒1	12	13	14	15	16	17
1	9	10	11		12	13	13	14	14	15
2	9	10	11		12	13	13	14	14	15
3	9	10	11		12	13	13	14	14	15
4	9	10	11		12	13	13	14	14	15
5	9	10	11		12	13	13	14	14	15
6	9	10	11		12	13	13	14	14	15
7	9	10		12	12	13	13	14	14	15
8	9	10		12	12	13	13	14	14	15

生产节拍由原来的58.6 s减少至46.8 s，生产线平衡率由原先的65%提高到了85%，计算式如下所示：

$$B=\frac{\sum _i{t}_{\mathrm{w}i}}{n\underset{i}{\mathrm{m}\mathrm{a}\mathrm{x}}{t}_{\mathrm{w}i}}\times \mathrm{100}\mathrm{\%}\approx \mathrm{85}\mathrm{\%}$$

（21）

式中：$B$为生产线平衡率。员工跨工序移动以分担瓶颈工序的生产任务，这能够有效地减小生产节拍，提高生产效率。上述任务分配方案能满足企业的实际生产需求，对于生产线机台配置与员工任务分配具有较好的指导作用。

4.2　参数分析

在实际生产中SWIP内工件数取值是员工根据经验确定，因此对SWIP内工件数取不同值时生产情况进行分析。以该算例为对象，生产节拍随SWIP内工件数的变化如图4所示，生产平衡率随SWIP内工件数的变化如图5所示。当增设机台数固定时，SWIP内工件数增大过程中，生产线节拍会先显著下降，而生产平衡率先显著提升。当超过某一值时（本算例中为5）两者的变化均趋于平缓，即使SWIP内工件数再增加，优化结果也不会进一步提升。

图 4  生产节拍随SWIP内工件数的变化

Fig. 4  Variation of takt time with SWIP quantity

图 5  生产平衡率随SWIP内工件数的变化

Fig. 5  Variation of balance rate with SWIP quantity

SWIP内工件数对应“单扎流”生产线里每“扎”的件数。适当增加SWIP内工件数有助于抑制面料质量一致性和手工作业周期变异的影响，但是SWIP内工件数仍应尽量减少。根据精益生产理论，生产线越接近于单件流，就越可以带来异常问题反应速度变快的正面影响，而过大的SWIP内工件数会造成现场管理和质量等方面的负面影响。

由上述分析可知，SWIP内工件数为整数且满足大于一件小于或等于一扎中最多包含的产品件数，该上界由车间结合实际生产给出，在该可行域内生产效率随着SWIP内工件数取值增大而提高，当到达峰值后会趋于平稳甚至下降。因此，设计基于爬山算法的贪婪搜索算法以求解最优SWIP内工件数取值，具体步骤如下所示：

（1） 以SWIP内工件数下界即$s=\mathrm{2}$为初始可行解。

（2） 计算该初始可行解，通过改进遗传算法优化线平衡方案的最优目标函数。

（3） 寻找相邻SWIP内工件数解，以步长为1增大SWIP内工件数，计算该相邻解下获得的最优目标函数值。

（4） 比较相邻解的目标函数值与当前解目标函数值的大小。若相邻解目标函数值大于当前解目标函数值，则以相邻解为最优解返回步骤（3）继续搜索。若相邻解目标函数值小于或等于当前解目标函数值，则返还当前解作为最优SWIP内工件数取值。

同样以车缝线为算例，SWIP内工件数取值为5时跳出循环，此时获得最大生产平衡率87%，以及最小生产节拍46.4 s。贪婪搜索策略结合改进遗传算法能够有效确定模型中SWIP内工件数最优取值，并获得最优SWIP内工件数取值下的最优线平衡优化方案。

5 结语

构建了考虑员工移动成本的ALBP‒Ⅱ模型，在两方面更符合实际车缝生产线：第一，结合“扎包”化流动的现实，构建了考虑员工移动成本的“单扎流”生产线员工任务分配和平衡率优化模型；第二，订单频繁切换的过程中维持团队人员稳定更有利于生产组织，因此以工作站（对应于员工）数不变前提下最小化生产节拍为优化目标，而不是最小化工作站数。模型中还考虑了与“单扎流”对应的SWIP内工件数，引入时间宽松系数判断瓶颈工序并根据最大新增机台数约束决策新增机台方案。算例显示，该模型能够给出合理高效的生产线平衡与员工配置方案，较好地解决实际车缝生产线平衡问题。

作者贡献声明

周 健：提出研究选题，设计研究思路和论文框架。

付 康：设计研究思路，实施研究过程，进行算法设计及试验，论文撰写及修改。

郭可馨：调研以及数据收集与整理，论文起草，绘图。