裴小兵++何倩男

摘要： 为了满足市场的快速变化、降低生产成本，车间调度成为生产的关键环节。为解决作业车间分批调度问题，本文在企业资金收益率最大化、物料周转速度最快的情况下，建立以生产周期、交货期满意度为指标的数学模型，并提出一种将DE算法与BBO算法相结合的多目标优化算法模型。最后经过实例仿真，求得的结果证明了算法的有效性。

Abstract： In order to meet the rapid change of the market， reduce production cost， the workshop scheduling becomes the key link in the process of production. In order to solve the job shop scheduling， this paper establishes a mathematical model based on the production cycle and the satisfaction of the delivery time in the case of the maximum rate of return on capital and the fastest rate of material turnover and proposes a multi-objective optimization model based on combining DE algorithm with BBO （Biogeography-Based optimization） algorithm. Finally， through the instance simulation， experimental results proves the effectiveness of this algorithm.

關键词： BBO算法；子批量；作业车间；分批；调度

Key words： BBO algorithm；sub-batch；job-shop；lot-splitting；scheduling

中图分类号：TH165 文献标识码：A 文章编号：1006-4311（2017）07-0065-03

0 引言

随着激烈的市场竞争和客户对产品多样性的需求，以“小批量、多品种”为特征的均衡生产已然成为主流生产模式，即柔性生产模式。

以往文献多集中于单目标批量生产的研究，常见以费用最小为优化目标（Song，2005[1]），但费用相对于生产批量的变化是一个静态指标，并不能作为衡量批量是否最优的标准（裴小兵，2015[2]），且实际生产过程中的情况复杂多变。潘全科（2004）[3]等研究表明：在作业车间中，对工件进行分批加工，可有效减少后续设备空闲等待时间，缩短生产周期，提高整体效率，但并未提出分批的解决方案；而后等量分批方法（曾强，2012[4]）、柔性分批方法被相继提出（Jia，2014[5]），但由于各子批批量等量分割，使得其无法根据设备的负载大小进行柔性调度，容易造成生产失衡。因而，使用柔性分批方法的学者较多，可使子批工艺路线选取及加工排序同时得到优化。

文中结合批量变动法的思想，建立了以最早完工时间、交货期满意度等为指标的数学模型，采用批量编码方法，解决工件划分和子批量大小问题。最后，进行实例验证。

1 多目标柔性作业车间调度问

1.1 问题描述

多目标柔性作业车间调度问题可以描述为：有N种工件在k台机器上进行加工，每种工件有SPi个，并且包含道工序，能加工某一工序的机器至少有一台，且同一工序的加工时间因机器的性能不同而发生变化。

1.2 数学模型

在分批调度问题中，过大或过小的批量都会导致较长的生产时间。当批量过大时，造成当前机床加工时间过长，后续机床处于空闲等待状态，拉长整个生产周期；当批量过小时，批次增多，会导致设备换模频繁，降低效率。因此，本文也考虑子批量这一因素对车间调度性能的影响。本文结合批量变动法的思想，从生产周期、交货期满意度、制造成本这三个方面来建立数学模型。其中，制造成本由加工成本、搬运成本、库存成本、批量启动成本来度量，这里假设设备按照加工工艺流程进行布局，减少搬运距离和搬运次数，所以不考虑搬运成本；库存成本指工件子批加工之前的等待成本。生产周期用工件的最大完成时间f1度量；交货期满意度用拖期惩罚f2来衡量；制造成本用f3度量。假定设备利用率很高，且所有工件在零时刻均可以被加工且设备一旦启动直到全部工序完成才能停下，则数学模型及其约束条件如下：

2 生物地理学优化算法

2008年Dan Simon提出生物地理学优化（Biogeography-Based optimization，BBO）算法，该算法虽然在迭代初期由于迁移操作的特殊性收敛快速，但在迭代后期由于各岛屿的信息趋于不变，变异操作效果不大使得算法的开采能力较差，极易陷入局部最优，本文用DE算法的变异算子代替BBO算法的随机变异，不仅改善了变异效果且能增加种群多样性，避免早熟现象，从而保证整体算法的有效性。改进的BBO算法流程如图1所示。

3 实例仿真

算法在Intel（R） Core（TM） i3-2310M CPU @ 2.10GHz、2.00G内存，Windows 7环境下运行，并采用C++ 语言编程。其中，主要的运行参数为：岛屿数量100，迭代次数为200，移入率和移出率的函数最大值I=E=1，变异概率0.01，试验运行5次。为验证该算法的性能，本文以一个 8×6规模作业车间分批调度实例来进行仿真实验。

某汽车公司一条生产线有8台机床，要生产6种零件，每种零件批量为10，每种零件包含三道工序，每道工序都有三台不同的可选机床进行加工，如表1所示。

为了验证算法的性能，本文将此调度问题分为非等量分批、等量分批及不分批三种情况，解决同一个调度问题，非等量分批方案比等量分批和不分批方案更能有效地平衡机床负荷、缩短生产周期，提高生产效率，減少加工成本。非等量分批方案的甘特图如图2所示。该方案将工件分成了10批，其中B、C、D、E四种工件分别分为2（7，3），2（6，4），2（4，6），2（3，7）个子批，A、F两种工件不分批，黑色部分表示批次启动时间。

4 结束语

①本文针对多目标作业车间分批调度问题的特点，提出用DE变异策略改进的BBO算法及与之相适应的编码方法。算法利用机床的负载能力、工序的加工时间对工件进行非等量分批处理，使其工艺路线和加工顺序同时得到优化。通过实例仿真，对其性能进行分析，也证明了算法的可行性。

②从甘特图中可以看出，分批意味着机床的换模次数会增多，可能会造成生产周期的延长。如果改变现有资源，缩短换模时间（一般当换模时间减少为原来的1/n时，则批量可减少为原来的1/n），在生产周期最短的目标下，还可以增加子批批次。

参考文献：

[1]Song Y， Chan GH. Single item lot-sizing problems with backlogging on a single machine at a finite production rate[J].EurJOperRes2005；161（1）：191-202.

[2]裴小兵，谭林林.基于eM_plant的作业车间生产批量优化研究[J].系统仿真学报，2015，27（7）：1458-1467.

[3]潘全科，朱剑英.多工艺路线的批量生产调度优化[J].机械工程学报，2004，40（4）：36-39.

[4]曾强，杨育，程博，等.平顺移动下等量分批FJSP多目标优化研究[J].系统仿真学报，2012（5）：1046-1052.

[5]Shuai Jia， ZhiHua Hu. Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem [J]. Computers & Operations Research， 2014（47）：11-26.

[6]白俊杰，龚毅光，王宁生，等.多目标柔性作业车间分批优化调度[J].计算机集成制造系统，2010，16（2）：396-403.