PCB组装车间多目标分批调度模型

王爱豪++孔珍珠

摘要：文章建立了印制电路板（PCB）组装车间分批优化调度数学模型，基于企业订单式生产方式（MTO）特点，构建了以生产成本、库存费用和交期延迟惩罚费用为目标的多目标分批调度模型，在模型的约束上充分考虑了《劳动法》规定的加班时长、《交易合同》中交期延迟惩罚以及PCB组装过程的一些因素，很好地描述了PCB组装分批调度问题，从而实现PCB组装分批优化调度问题的支持。

Abstract： PCB assembly batch scheduling mathematical model is built. The model on basis of production research in reality is built with minimizing total production cost as objective. The provision of work time in "Labor Law"， delivery delay punishment in "Business Contract" and other restricts in PCB assembly are well considered as constraints of the model. The assemble time of each process is confirmed from real production. A matrix is used to express the relations well between sub-batches， processes and machines， so PCB assembly batch scheduling problem is well described by the model.

關键词：印刷电路板；多目标；分批调度

Key words： printed circuit board；make-to-order；batch scheduling

中图分类号：F273；F224 文献标识码：A 文章编号：1006-4311（2018）02-0224-04

0 引言

随着全球化市场经济竞争日趋激烈，客户需求多样化和个性化特征日趋明显，为了适应新的需求环境，避免市场风险，提高企业自身的竞争力，不少电子制造企业从传统的备货式生产方式（Make-to-Stock，MTS）转变为订单式生产方式（Make-to-Order，MTO）。

在MTO生产模式下，许多原始设备制造商（OEM）主要专注于产品的设计和销售，而将PCB组装部分外包。根据相关资料统计，中国PCB组装企业的平均利润不超过7%[2]。

在不增加生产资源的条件下，对生产进行分批调度可以改变生产进程，合适的分批可以很明显地改善生产设备利用率和加工周期，极大提高生产效率[3]。台湾学者Low等[10]研究了生产车间批量调度分批调度的优点。对等量分批和不等量分批进行了对比研究。苑丽红等[11]在区分批量准备时间基础上，研究了作业车间批量作业计划中的批次作业计划策略问题，但没有指出如何确定最佳的子批数量。

为实现PCB组装车间分批优化调度，文章考虑企业实际生产能力和交货延迟惩罚等因素，以生产成本、交货延迟惩罚和库存费用为目标函数，建立PCB组装批量调度数学模型。

1 问题描述与建模

1.1 问题描述

PCB组装批量调度问题可以描述为：在PCB组装过程中，有N种PCB组装任务Ni（i=1，2，3，…，N）在M台机器Mj（j=1，2，3，…，M）上进行组装，第i种PCB的数量为ni（i=1，2，3，…，N），每种PCB需要经过多道工序加工，且每种PCB组装的工序流程是确定的。需在满足各种约束的情况下，对批量的PCB任务进行分批，划分批次和批量大小，并确定各批次的加工机器以及在各机器上的组装顺序，使目标函数最小化。基于JST企业生产实际情况，文章的优化目标是整个PCB组装周期内的生产成本、交货延迟惩罚费用、库存费用之和最小。

在批量调度问题的研究中，依据分批原则，将每一种工件分成若干小批量，每一小批工件称为子批，子批的数量、大小和加工顺序是决定批量调度性能最为关键的“三要素”[12]。目前，批量调度问题被分为三大类，即单产品无能力约束批量问题、单产品有能力约束批量问题和多产品有能力约束批量问题。单产品无能力约束问题的研究为多产品能力受限以及其它更加复杂批量问题研究的前提和基础，该问题模型的建立比较简单，易于求解和优化。一些复杂的批量调度问题，例如：能力受限的单产品批量问题、能力受限的多产品、多阶段批量问题，通常可以分解成基础的批量问题，通过求解基础批量问题得到原问题的下界，再经过调整得到性能较好的满意解，很多学者进行了相关研究[13-17]。能力受限批量问题的求解过程和求解算法的时间复杂度要比无能力受限批量问题高很多。多产品有能力约束批量问题不仅受到生产能力约束，而且产品种类不止一种，问题复杂度很高，是强NP-hard问题。

1.2 问题描述

文章基于企业生产调研数据，考虑企业实际生产能力和交货延迟惩罚等因素，以生产成本、交货延迟惩罚和库存费用为目标函数，建立PCB组装批量调度模型。在企业实际生产过程中，调度人员会依据实际情况，在生产能力不足时，会采用加班策略满足生产需求，即在《劳动法》的相关规定下，安排员工、设备进行额外加班来完成生产任务。基于准时生产（Just In Time，JIT）的思想，在恰当的时间生产出恰当的产品，把产品库存视为一种浪费，产品提前完工会产生库存费用。在产品提前完工后，企业会将完工产品暂时存储在仓库中，等到交期时间才能交货，在存储过程中会产生库存费用。因此，以生产成本、交期延迟惩罚费用和库存费用之和最小为目标，追求利润最大化，这也正是企业最为关注的问题。endprint

企业员工、机器正常工作时间的成本是确定的，可根据企业长期的生产数据来进行核算，文章用CR来表示，在模型中只考虑企业所有人员和设备都正常工作时的单位时间成本，不考虑只有部分人员和设备工作的单位时间成本。

企业采用加班策略平衡生产计划和生产能力时，按照《劳动法》的相关规定，每人每天的加班时间最多不超过3h，每月最多不得超过36h，并且加班工资不得低于正常工资的150%。在文章的模型中加班的单位时间成本为Co，文章对加班的时间约束做出如下假定：

①仅考虑每天延长工作时间的加班模式，不考虑节假日加班的情况；

②每天加班时间可为1h、2h或3h，当所需加班时间不足1小时时，按照1小时来算；

③生产的持续时间按天计算，不考虑非整数活动天数的情况。每人每天正常工作时间为8h，考虑加班，每人每天最多工作时间为11h；

④假设每个月的标准工作时间为22个工作日，每人在20个工作日内的加班时间不得超过36h。

通过企业的《产销合同》相关条款了解到，如不能按期交货，需支付违约金。文章在模型中对交期延迟惩罚费用进行量化，采用τi表示某PCB任务i交货延迟的单位时间惩罚成本。当PCB价格越高时，对应地，如果出现交期延迟，则单位时间惩罚成本会越高。

PCB的存储方式相对简单，按照普通物料存储方式进行保管即可。根据JST企业仓库库存资料，获取PCBi的单位时间库存费用为λi。

在PCB组装过程中，有N种PCB组装任务在M台机器上进行组装，每种PCB需要经过多道工序加工，且每种PCB组装的工序流程已知。在机器和资源条件一定的情况下，对批量的PCB任务进行分批，划分批次和批量大小，并确定各批次的加工机器以及在各机器上的组装顺序，使整个生产周期内的生产成本、交货延迟惩罚费用、库存费用之和最小。

在PCB组装批量调度问题中，文章同时假设模型的建立满足以下基本条件：

①生产成本主要包含员工、机器正常工作和加班工作的成本，不考虑机器的折旧和维修成本；

②库存费用主要是PCB存储成本，不考虑物料搬运、盘点等成本；

③假设仓库容量无穷大，任何一种PCB在提前完工后都能存储到仓库；

④任何PCB的工序路线和加工时间是确定的；

⑤PCB组装过程不考虑突发事件的发生，组装过程不能中断；

⑥机器的开启、停止时间以及PCB组装过程中的上下料时间均算入工序加工时间；

⑦每台机器同一时刻只能组装一种PCB；

⑧整个生产过程中不考虑周末或节假日加班，交期延迟时间以天为单位进行计算。

基于上述假设，建立PCB组装车间批量调度模型。调度目标是：生产周期内生产成本、交货延迟惩罚费用、库存费用之和最小，建立如下模型：

式中：

A，D，I—分别表示生产周期内生产成本，交货延迟惩罚费用和库存费用；

i，j—PCB组装任务的编号；i，j=1，2，…，n，且i≠j；

k，h—组装设备的编号，k，h=1，2，…，M，且k≠h；

b，b'—PCB子批次序号；

Sibk，Sibh—表示PCBi的子批b在设备k和h上的组装开始时间；

Sjb'k—表示PCBj的子批b'在设备k上的组装开始时间；

Pibk，Pibh—表示PCBi的子批b在设备k和设备h上的组装时间；

Eibk—表示PCBi的子批b在设备k上的组装结束时间；

xibk—0-1变量，1表示PCBi的子批b在设备k上组装，否则为0；

xibjb'k—0-1變量，1表示在设备k上PCBi的子批b先于PCBj的子批b'进行组装，否则为0；

yibhk—0-1变量，1表示PCBi的子批b在设备h上的组装先于设备k，否则为0；

Si—表示PCBi的子批数量；

R—表示t时间段内的基本工作时间；

Z—表示t时间段内允许的最长加班时间；

Ut—表示t时间段内的实际工作时间；

Vt—表示t时间段内的实际加班时间；

CR—表示基本工作时间段的单位时间生产费用；

CO—表示加班时间段的单位时间加班费用；

τi—表示PCBi交货延迟的单位时间惩罚费用；

λi—PCBi的单位时间库存费用；

Qit—表示PCBi在t时间段内的加工时间；

Qibt—表示PCBi的子批b在t时间段内的加工时间；

Wi—表示PCBi的交货延迟时间长短；

Li—表示PCBi的提前完工时间长短；

T—各PCB任务组装完成的总时间，由多个时间段t组成；

Ci—PCBi的实际完工时间；

Di—PCBi的交期；

Pi—PCBi的工序数量。

其中，公式（2）和公式（3）是正常工作时间和加班时间约束；公式（4）表示PCBi是否是延迟交货；公式（5）表示PCBi是否是提前完工；公式（6）是PCB的组装工艺顺序约束，确保PCBi按照工序先后顺序完成组装；公式（7）是设备有效性约束，确保机器k上的PCB按照“先进先出（First In， First Out，FIFO）”的原则进行组装；公式（8）确保各PCB都完成了组装；公式（9）是组装能力约束，确保组装能力能满足组装任务需求；公式（10）表示一个PCB组装任务至少需要在一台机器上进行组装。

2 目标函数关系推理

PCB组装车间批量调度模型的目标是使得生产周期内生产成本、交货延迟惩罚费用、库存费用之和最小。通过对三者之间的关系进行研究，给出了引理1和推论1，找出了目标函数中所有极小值点，并构建出了基于目标函数的双层调度方案。endprint

引理1：完工延遲惩罚费用D是关于加班时间Vt的非增阶梯函数。完工延迟惩罚费用D与生产成本A（包含正常工作费用和加班费用）之和是关于加班时间Vt的阶梯递增函数。

证明：为了证明引理1，考虑某个调度方案一开始没有使用加班时间，然后增加加班时间的情况。假设至少有一个工件完工有延迟，工件j是所有延迟完工工件中延迟时间最短的工件，γj表示工件j的完工延迟时间。加班时间从0增加到γj过程中，完工延迟惩罚费用不会有任何减少。当加班时间等于γj时，工件j恰好在交期时间内完工，完工延迟惩罚费用会减少τj，τj表示工件j的完工延迟惩罚费用。针对完工延迟工件继续增加加班时间，将会得到总的延迟惩罚费用与加班时间之间的函数关系，如图1所示，其中δ（j）表示在不改变工件j完工延迟状态情况下，可增加的最长加班时间，延迟惩罚费用是关于加班时间的非增阶梯函数。

文章的生产成本包含正常工作费用和加班费用两部分。表示正常工作时间段的单位时间生产费用，按照《劳动法》的相关规定，企业每天的正常工作时长是8h，因此每天的正常工作费用是一个固定值。单位加班时间费用为Co，是一个常数，加班费用与加班时间是线性关系，那么完工延迟惩罚费用与加班费用之和与加班时间的函数关系也是线性关系，结合图1中完工延迟惩罚费用与加班时间的函数关系，得到如图2所示的函数关系。延迟惩罚费用与生产成本之和是关于加班时间的阶梯递增函数。

另外，在调度方案确定后，采用增加加班时间，没有改变工件的分批和加工顺序，对已经提前完工的工件不会有影响，提前完工的工件数量和时间不会因此而减少。因此，增加加班时间不会改变库存费用，即库存费用与加班时间是非关联的，不构成任何函数关系。由此得到总费用F，生产成本A，完工延迟惩罚费D，库存费用I随加班时间增加的函数关系，如图3所示。

推论1：合理地采用加班策略可以有效减少总成本。总成本函数F的所有极小值点对应的加班时间VT=∑Wi，其中p为完工延迟的工件数量。

证明：基于引理1的延迟惩罚费用与生产成本之和关于加班时间的阶梯递增函数关系，在有工件完工延迟的调度方案中，随着加班时间逐步增加，库存费用不会发生改变，当加班时间等于所有延迟完工工件中延迟最短的时间，该工件完工不再延迟，不会再产生完工延迟惩罚费用，总成本函数图像会出现“断点”，该“断点”所对应的总成本是梯度函数的第一个极小值点。同理，如此重复，可以找到梯度函数的其它所有极小值点，极小值点的个数等于完工延迟的工件数量p，且极小值点所对应的加班时间VT=∑Wi。很显然，这些极值点中的最小值就是总成本函数的最小值。

3 总结

文章建立了PCB组装批量调度数学模型。PCB组装批量调度问题是典型的作业车间批量调度问题，但又具有其独特性和复杂性。文章基于对实际生产企业的生产调研，对通用的PCB组装批量调度模型进行了改进，以总生产成本最小化为目标函数，在模型的约束条件上充分考虑了《劳动法》规定的加班时长、《交易合同》中交期延迟惩罚等因素以及PCB组装过程的一些限制条件，结合具体生产数据确定各工序组装时间，并采用矩阵方式对批量划分后的子批PCB、工序以及机器设备间的关系进行了合理表达，建立的数学模型很好地描述了PCB组装批量调度问题。基于引理1和推论1，文章以生产成本、交货延迟惩罚费用和库存费用组成的总成本F为目标函数进行求解时，可以构建出相应的调度方案。

参考文献：

[1]杜轩，李宗斌，高新勤，闫利军.基于遗传算法的转塔式贴片机贴装过程优化[J].西安交通大学学报，2008，42（3）：295-299.

[2]Ho W， Ji P. A genetic algorithm approach to optimizing component placement and retrieval sequence for chip shooter machines [J]. International Journal of Advanced Manufacturing Technology， 2006， 28（5-6）：556-560.

[3]Ammons， JC， Carlyle M， et al. Component allocation to balance workload in printed circuit card assembly systems[J]. IIE Transactions， 1997， 29（4），265-275.

[4]Lapierre SD， Debargis L， Soumis F. Balancing printed circuit board assembly line systems [J]. International Journal of Production Research.2000， 38（16）：3899-3911.

[5]Ellis KP， Bhoja， S. Optimization of the assignment of circuit cards to assembly lines in electronics assembly[J]. International Journal of Production Research， 2002，40（11）， 2609-2631.

[6]Ho W， Ji P. Optimal production planning for PCB assembly [M]. London： Springer， 2007.

[7]Wu YZ， Ji P. A scheduling problem for PCB assembly： a case with multiple lines[J]. International journal of advanced manufacturing technology， 2009，43（11-12）：1189-1201.endprint

[8]Pavlov VV. Structural simulation in CALS technology [M]. Moscow： Science Press， 2006.

[9]李宗斌.先進制造中多色集合理论的研究及应用[M].北京：中国水利水电出版社，2005.

[10]Low Chinyao， Hsu Chih-Ming， Huang Kai-I. Benefits of lot splitting in job-shop scheduling [J]. International Journal of Advanced Manufacturing Technology， 2004， 24（9-10）：773-780.

[11]苑丽红，崔广才.基于遗传算法的柔性车间批量调度研究[J].长春理工大学学报.

[12]EI-Najdawi M K. Job-splitting heuristic for lot-size scheduling in multi-stage， multi-product production processes[J]. European Journal of Operational Research， 1994，75（2）：365-377.

[13]Bao Z， Ren X， Yang Y， et al. Multi-objective integration of flexible collaborative planning and fuzzy flexible lot-splitting scheduling based on the Pareto optimal[J]. International Journal of Hybrid Information Technology， 2015，8（7）：305-318.

[14]Wang L， Chen Y， Chen T， et al. A hybrid flowshop scheduling model considering dedicated machines and lot-splitting for the solar cell industry[J]. International Journal of Systems Science， 2014，45（10）：2055-2071.

[15]Xu X， Li L， Fan L， et al. Hybrid discrete differential evolution algorithm for lot splitting with capacity constraints in flexible job scheduling[J]. Mathematical Problems in Engineering， 2013.

[16]Pimentel C， Alvelos F P E， Duarte A， et al. Exact and heuristic approaches for lot splitting and scheduling on identical parallel machines[J]. International Journal of Manufacturing Technology and Management， 2011，22（1）：39-57.

[17]Bai J， Gong Y， Wang N， et al. Multi-objective flexible Job Shop scheduling with lot-splitting[J]. Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems， Cims， 2010，16（2）：396-403.endprint