基于启发式算法实现生产线物料准时化配送

顾晨阳

上海交通大学机械工程与动力学院,上海 200240



基于启发式算法实现生产线物料准时化配送

顾晨阳

上海交通大学机械工程与动力学院,上海 200240

本文结合公司当前的物料配送系统，指出其目前存在的问题，提出了一套启发式算法。首先以生产节拍为基本单位，设置一个生产周期，以此分别计算出物料的需求量、配送车辆的车辆数、配送周期、以及配送人员的等待时间。然后求出最短的配送人员等待时间，以此状态下的生产周期作为实际配送的生产周期，从而展开物料配送。 最后本文结合公司的实际问题，运用启发式算法求解出实现准时化配送的方案。

物料配送准时化启发式算法生产节拍

1　公司生产线及物料配送介绍

1.1概述

F公司是一家生产多功能复印机的制造型企业。其生产线布局如图1所示，为直线型布局，主要分为一条主装配线和两条子部品装配线。同时在生产线附近设置有一个线边仓库，生产线的发料是通过这个线边仓库完成的。

F公司的生产车间采用物料集中配送的方式进行配送，即根据生产计划，提前一天准备第二天生产所需的原材料和零部件，将其送至线边仓库，然后等到第二天生产线正常工作时，物料配送人员根据料车所载物料的不同，对不同工位同时进行发料。

配送车辆：R型多功能复印机的生产线上的物料配送料车，尺寸为100 cm*100 cm*55 cm。

工位(料台)：F公司的工位可分为3部分：料台，操作台以及周转箱放置区域。生产线工作人员将料台上的物料消耗完以后会将空的周转箱放在工位最下方的周转箱放置区域，物料配送人员在发料完毕以后，会回收周转箱。

1.2问题分析

F公司目前的配送模式，采用的是一种较为粗放式的配送模式，物料中心首先根据生产计划，结合制造BOM，计算出第二天一天物料的需求总量，之后在生产开始之前将这部分的物料从仓库中划分出来，并送往生产线附近的线边仓库。

而接下去的物料配送任务就分配给配送人员，只要求配送人员当天将这些物料全部配送至相关工位即可。但是如何配送、一次配送多少数量，哪些种类却没有给出明确的规定。因此配送人员只能根据各自的喜好来进行配送，有些配送人员为了避免频繁的配送劳动，采取的是过量配送；有些配送人员为了贪图配送简便，每次只配送一种或者几种物料，将一辆料车的物料完毕之后再换另外的几种物料配送，所以生产线经常因为物料短缺发生停线。

图1　生产线布局Fig.1　The Layout of Production Line

图2　配送车辆Fig.2　Distribution Vehicle

图3　工位Fig.3　Station

实际上，F公司生产线物料配送的混乱，是由于对配送人员不正确的配送方式和配送方法造成的，而究其根本，是由于F公司的物流部门的管理不当，缺少用科学的方法来管理生产线的物料配送模式，正是由于F公司对于物料配送没有一个系统、详细的规定和计划，使得配送人员没有作业指导书可以依靠，只能凭借经验和喜好，随心随意的进行配送，进而导致了整个配送系统的混乱。

2　启发式算法

首先对整个生产线进行划分，分成若干个区域。然后以生产节拍为基本单位设置一个生产周期TS，再根据该生产周期，结合制造BOM计算出在该生产周期内，各生产区域需要的物料种类和数量；其次，根据物料的需求量计算出配送这些物料需要的车辆数，由于大多数情况下是非整车配送，因此需要以平衡配送人员的劳动强度以及配送车辆的高装载率为约束，用以提高配送的效率；第三，在配送车辆以高装载率配送的前提下，计算出配送车辆的配送周期，然后根据生产周期来调整配送车辆的发车顺序，计算出配送人员的等待时间；最后，累计所有配送人员的等待时间，以此总等待时间ΔT最小为目标函数，最终找出最适合的生产周期，以达到人员利用率最高的生产线物料准时化配送的目标。启发式算法的流程如图5所示。

第一步：计算一个生产周期内各个区域对物料的总需求量。当以生产节拍C为基本单位设定好一个生产周期TS=n*C后，可以结合制造BOM计算出各个区域在生产周期TS内的物料的需求量Di，计算公式如下：

(1)

dij—表示在区域i内，种类为j的物料的需求量

Ei—表示区域i用于堆放物料区域的空间容量

图4　启发式算法流程图

第二步：计算一个生产周期内各区域需要的配料车辆的车辆数。由于在一个生产周期在对一个区域进行配送所需的配送车辆的车次的多少，取决于该生产周期内物料需求量的多少，在大多数情况下，物料的需求量大于一辆配送车辆的容载量，但不等于一辆配送车辆容载量的整数倍。在这种情况下，不但需要多辆配送车辆进行整车配送，同时也需要一辆配送车辆进行非整车配送。同时，由于配送的物料量存在差异，这对配送人员意味着配送时的劳动强度存在差异，因此配送人员在配送物料时需要不断地适应变化的工作量，这样就很容易使得配送人员产生心理和生理上的疲劳，最终导致发生配送错误的情况。基于以上的考虑，首先计算出配料车辆的车辆数，计算公式如下：

(2)

Ni—表示区域i所需的配送车辆

Qi—表示一辆配送车辆的容载量

其次，需要对配送车辆的情况进行约束，为了平衡配送人员的劳动强度，同时为了提高效率，也要满足配送车辆的高搭载率，需要对式(2)进行约束，如下所示：

(3)

η—表示配送车辆的搭载率

A—表示现有配送车辆数量

Mi—表示区域i对配送人员的需求量

B—表示配送人员数量

第三步：计算各区域的配送车辆的配送周期。一辆配送车辆进行一次物料配送的配送周期主要由配料时间、发料时间以及仓库到工位间的往返行程时间构成，其计算公式如下：

(4)

Tik—表示区域i中第k辆配送车辆的配送周期

Tikp—表示区域i中第k辆配送车辆的配料时间

Tikf—表示区域i中第k辆配送车辆的发料时间

Tikx—表示区域i中第k辆配送车辆的行程时间

Sik—表示区域i中第k辆配送车辆的实际配送量

μ—表示单件物料配料时的时间系数

ρ—表示单件物料发料时的时间系数

di—表示仓库到区域i的行车距离

ν—表示配送车辆的行进速度

第四步：计算配送人员的等待时间。在计算出配送车辆的配送周期以后，将其与生产周期相比较，会出现以下几种情况：

情况一：配送周期大于生产周期，在此情况下，将无法完成对物料的准时化配送，所以此情况是不被允许的。

情况二：配送周期小于生产周期,这种情况首先满足的了准时化配送的基本要求。在此基础上，同一区域内，如果任意两个配送周期叠加以后的时间大于一个生产周期的时间，那么表示这些配送车辆必须同时出发进行物料配送，否则将无法在当前生产周期结束之前将下一生产周期需要的物料全部配送。所以在此情况下，每一辆配送车辆都需要配备一个配送人员，因此要计算该区域内配送人员的等待时间，只要将一个生产周期的时间减去一个配送周期的时间就可以得出配送该车辆的人员的等待时间，然后将所有的等待时间求和，其计算公式如下：

(5)

情况三：在配送周期小于生产周期的基础上，在同一区域内，如果有两个或者两个以上的配送周期叠加以后的时间小于一个生产周期的时间，那么表示所有的配送车辆没有必要同时出发进行物料配送，那么可以是一个配送人员将一辆配送车辆的物料配送完毕后对第二辆的配送车辆的物料再进行配送。在这种情况下，需要对所有的配送车辆进行组合，尽可能地减少同时配送的情况，从而减少配送人员的等待时间，提高劳动效率。所以该区域内的等待时间可以根据以下计算公式得出：

(6)

zi—表示区域i需要进行同时配送的的最少车辆数

第五步：计算整个生产线的配送人员的总等待时间。在得出所有区域的等待时间之后，就可以很快的计算出生产线所有配送人员的总等待时间。计算公式如下：

(7)

3　实际应用

首先结合F公司实际情况对相关参数进行数字化定义：

①生产节拍：120秒。

②配送车辆行进速度：1 m/s。

③物料根据外观尺寸的大小划分为大中小三类，分别对应4、2、1个标准空间单位。

④每个工位料台的堆放容量为40标准单位，每辆料车的堆放容量为100标准单位。

⑤将生产线划分为5个区域，具体布局以及料车行进路线如图6所示。具体距离如表1所示。

图5　生产线布局Fig.5　The Layout of Production Line

Table 1Material distribution route list of different production area

线边仓库至区域路径距离区域1O→P→A21m区域2O→P→A→B31m区域3O→P→C21m区域4O→P→C→D29m区域5O→P→C→D→E37m

计算：

第一步：首先各生产周期下各个区域的物料需求，如表2所示。

从表2可以得知，在生产周期为600秒的情况下，区域1中，一个生产周期内所需物料的体积为245个标准单位，超过了该区域的容量，因此在接下去的计算过程中，将去除对生产周期为600秒时的计算。

表2　Ts=120、240、360、480、600秒时物料需求量

第二步：计算配送车辆的车辆数。

由于每辆配送车辆的容量为100标准单位，那么在计算出物料需求量的情况下可以很快的得出配送车辆的车辆数，但是由于在一般情况下，物料需求量不为配送车辆容量的整数倍，那么势必需要考虑到车辆搭载率的问题。为了减少配送人员在心理上和生理上的疲劳，平衡不同配送车辆的搭载率是在计算车辆的同时需要考核的一个指标。在将同一区域的配送车辆搭载率均衡化后，搭载率过低的情况将被去除。配送车辆的车辆数以及搭载率均衡化后的结果如表3所示。

表3Ts=120、240、360、480秒时配送周期及平均搭载率

Tabel 3Distribution vehicles and average carrying rate when Ts=120、240、360、480 s

区域各生产周期下的配送车辆的车辆数及平均搭载率Ts=120sTs=240sTs=360sTs=480s车辆数搭载率车辆数搭载率车辆数搭载率车辆数搭载率1149%198%273.5%298%2148%196%272%296%3174%274%374%398.7%4172%272%372%396%5173%273%373%397.3%

由表3可知，当生产周期为120秒时，区域1与区域2的车辆搭载率只有49%与48%，这说明配送车辆始终输入半空载状态，车辆的利用率非常低。这样配送并不合理，所以在接下去的计算过程中，将去除对生产周期设置为120秒时的计算。

第三步：计算配送车辆的配送周期。

对于单辆配送车辆的配送周期，主要由三部分组成，即配料时间，发料时间以及从仓库至工位的往返时间。配料时间与发料时间与需求物料的种类和数量有关；仓库至工位的往返时间与途中的路径长短有关。具体结果如表4所示：

由表4可知，当生产周期为240秒时，区域1与区域2的配送车辆的配送周期分别为332.2秒和318.2秒，都超过了生产周期，因此接下去的计算步骤，将去除生产周期为240秒时的计算。

第四步：计算配送人员的等待时间。

由于配送周期的不同，对于计算配送人员等待时间的计算公式也有所不同，因此首先需要判断的是各个区域中，是否存在任意两个或者两个以上的配送周期相加以后的时间大于生产周期的情况发生。从表4可以得出，而当生产周期为480秒时，区域2，4，5中，任意两辆配送车辆的配送周期相加都小于生产周期，所以区域1中的两辆配送车辆只要依次配送即可，区域4，5中，只需两辆配送车辆同时配送，等配送完毕之后再配送剩余的物料。因此，配送人员的等待时间如表5所示：

表4　Ts=240、360、480秒时配送周期

表5　Ts=360、480秒时配送人员等待时间

从表5可知，在生产周期为480秒时，在区域2，4，5中，由于配送车辆不必要同时进行物料配送，相对应的可以减少配送人员的数量，同时由于有的配送人员需要在一个生产周期内对两辆配送车辆进行配送，所以等待时间也会相应减少。所以与生产周期为360秒的情形比较，在生产周期为480秒情况下，配送人员减少两名，配送人员的等待时间减少28秒。所以将生产周期设置为480秒(四倍生产节拍)，配送人员的等待时间最短，为1702.7秒。

4　效果确认

经过第三节的计算，我们得出将生产周期设置为480秒(四倍生产节拍)时，本文提出的准时化配送模式的效率将达到最大值。为了验证本文提出的准时化配送模式的效果，本节将通过配送车辆数、配送车辆搭载率、配送人员数量、配送人员利用率(即实际工作时间/制度工作时间)等指标对F公司原有的配送模式与本文提出的准时化配送模式进行比较。由于原有的配送模式时有发生断料与物料呆滞现象，准时化配送的前提就是杜绝断料与物料呆滞，所以本节不就这两方面进行比较。

图6　两种配送模式下配送车辆数和平均搭载率的比较

Fig.6Comparison of the quantity of distribution vehicle and average carry rate from the 2 distribution pattern

从图7中可以看出，与原有配送模式相比较，准时化配送模式下配送车辆的车辆数只需要13辆就可以完成配送任务。从平均搭载率方面，虽然原有配送模式下的搭载率较高，但这是因为配送人员为了减少工作时间，每次配送都是过载配送，这里存在着物料损坏的隐患，所以准时化配送模式下97%的搭载率相对合理。

图7　两种配送模式下配送人员数和平均利用率的比较

Fig.7Comparison of the quantity of distribution person and average utilization rate from the 2 distribution pattern

从图8中可以看出，在原有配送模式下需要16个配送人员完成的配送任务，在准时化配送模式下只需要10名配送人员就可以完成配送工作，节约了公司的人力成本。人员利用率方面，也从原有的52%提高到了69%，这也大大提高了员工的工作效率。

所以综合各个方面，本文提出的准时化配送模式相对于原有的配送模式，在各个方面都所有改善，为公司降低了成本，提高了企业竞争力。

5　结论

本文以F公司内物料配送为研究对象，分析目前存在的问题，建立准时化配送模型，采用启发式算法对其进行求解，最后通过实例验证了该算法的可行性和有效性，为国内制造型企业实现准时化物料配送提供了参考。

[1]党立伟.离散型生产系统准时化物料配送方法的优化研究[D].上海交通大学，2013.

[2]蔡苗.混流装配线上物料配送系统的研究[D].机械科学研究总院，2007.

[3]Robin Hanson, Anna Brolin. A comparison of kitting and continuous supply in in-plant materials supply[J]. International Journal of Production Research, 2013,51(4):979-992.

[4]Castillo I,Peters BA. Unit load and material-handling considerations in facility layout design[J]. International Journal of Production Research, SEP 2002,40(13):2955-2989.

Based on the Heuristic Algorithm to Achieve the Production Line Material on-time Delivery

GuChenyang

SchoolofMechanicalEngineering,ShanghaiJiaoTongUniversity,Shanghai200240

in this paper, combined with the company's current material distribution system, pointed out the existing problems, and put forward a set of heuristic algorithm. First, the production of the beat as the basic unit, set up a production cycle, in order to calculate the demand for the material, the number of vehicles distribution vehicles, distribution cycle, as well as the waiting time for the delivery personnel. Then find the shortest delivery personnel waiting time, in order to state the production cycle as the actual distribution of the production cycle, so as to expand the distribution of materials. Finally, this paper combined with the actual problems of company, using heuristic algorithm to solve the realization of the project on time distribution.

Material distributionPunctualityHeuristic algorithmProduction rhythm

1006-8244(2016)01-040-06

U116.1

B