基于优先补偿权在生产计划中的一种规划模型算法

陈本士

哈尔滨德强商务学院，黑龙江哈尔滨 150025

基于优先补偿权在生产计划中的一种规划模型算法

陈本士

哈尔滨德强商务学院，黑龙江哈尔滨 150025

本文针对有限生产能力和一定的市场需求量情况下的生产计划，建立一种规划模型，提出了优先补偿权和优先生产权准则，并在这两个准则下取得最优解。这一算法的提出，对此类实际问题的解决，具有一定的可操作性。

需求量；优先补偿权；规划模型

生产企业的生产计划必须依据工厂的生产能力、市场需求量来制定。在不同时间内生产企业的生产能力、市场需求不同，同时不能产生大量库存。所以制定计划时必须综合考虑诸多因素，以最大收益原则来制定。本文从一个实际问题出发，提出一种解决此类问题的解决方法。

1 一个生产计划的实际问题

在文献[1]中给出了如下一个数学建模问题：某厂拥有4台磨床（1月、5月各停工一台）、3台卧式钻床（2月停工维修二台，6月维修一台）、2台立式钻床（4月、5月各停工维修一台）、一台镗床（3月停工维修）和一台刨床（6月停工维修一台），用以生产7种产品记作p1至p7。工厂收益规定为产品售价减去原材料之剩余。每种产品的单价的收益及所需各机床的加工工时（以小时计）见文献，这里不再赘述。

每种产品存货最多可到100件，存费每件每月为0.5。现在无存货，要求到6月底每种产品存货50件。工厂每周工作6天，可假设每月仅有24个工作日，每班8小时，不需要考虑排列等待加工的问题，为使收益最大，工厂应如何安排各种产品的产量？

2 问题的一般化与求解模型

我们将问题一般化如下：某工厂生产n种产品Wi（i=1，2，…n），每种产品的价格为Pi（i=1，2，…n），而生产每种Wi需要m道加工过程Gj（j=1,2,…m），加工一件Wi所需Gj工时为tij（i=1，2，…n；j=1,2,…m）现在已知有r个时间段Tk（k=1,2,…r）内，各种产品Wi（i=1，2，…n）在各时间段Tk（k=1,2,…r）的市场容量Zik（i=1，2，…n；k=1,2,…r），并且时间段Tk（k=1,2,…r）内每种产品Wi（i=1，2，…n）的最大存货量为Cki（k=1,2,…r；i=1，2，…n）。且Tk内每件 Wi存货费为 Dki（k=1,2,…r；i=1，2，…n）。现在无存货 ，加工过程不考虑排队问题，为使效益最大，工厂如何安排各段时间的生产计划？

我们假设Tk内Wi的计划生产量为Xki（k=1,2,…r；i=1，2，…n），Tk内 Wi的计划生产存货量为 Yki（k=1,2,…r；i=1，2，…n），总收益为Q。则可建立如下目标函数：

其中 ，Xki＜Zki;Yki＜Gki

问题的求解就是定出各时间段的计划生产量和存货量，使得目标函数值最大，也就是最优解。制定计划必须综合考虑各个时间段的生产能力、市场容量和最大库存来确定。我们给出一种基于优先补偿和优先生产原则的规划方法：

优先补偿原则：

在需要补偿的情况下，优先补偿单个产品效益大、耗工时最小的产品，产品效益优先权值可有如下公式计算：

补偿产品效益优先权值=单个产品收益÷单个产品所需该工时﹣存货费÷单个产品所需该工时

优先补偿原则：

在某种生产能力不足情况下，根据生产任务优先生产单位工时效益最大的产品，优先生产权计算如下：

权值=单个产品收益÷单个产品所需该过程工时

具体算法步骤如下：

第一步：计算出各时间段各个加工过程的最大生产能力Nkj（k=1,2,…r；j=1,2,…m）。

第二步：计算各时间段内满足市场容量所需的各个加工过程的生产能力 Rkj（k=1,2,…r；j=1,2,…m）。

第三步：计算各时间段各个加工过程的最大生产能力与所需生产能力之差Skj=Nkj–Rkj。得到一个反映生产能力满足市场容量情况的二维数据，正者为剩余生产能力，负者为不足生产能力，可讨论所影响的产品能否由上个时间段补偿。

第四步：考虑到T1和Tm时间段的特殊性（T1的所缺产品不能由上个时间段补偿；Tm库存需要一定的生产能力），我们先对这两个时间段进行如下处理：如果T1出现某加工过程生产能力不足，必然导致有些产品不能生产，则依据优先生产权顺序进行贪婪生产，得到T1时段的初次生产计划x1i，将此计划作为虚拟的市场需求，算出新的生产能力差值，处理后T1时段的负值应变为零或数值较小（不足以生产一件产品）的正值；Tm时间段的库存可加入该时段市场容量作为一个虚拟的市场容量，由此市场容量算出所需生产能力并算出新的生产能力差值。经过处理得到一个新的生产能力情况的二维数据R‘kj。R‘kj中未出现负值的表明该时间段生产能力过剩，将市场容量作为生产计划量。

第五步：从此二维数据出发，依据优先补偿准则从上到下把R‘kj中负值所影响的未能生产的产品贪婪的由最近的上一时段该加工过程剩余生产能力生产产品补偿，我们给出如下的处理步骤：

步骤1：搜索所有负值及负值影响产品，算出各产品的优先生产权和优先补偿权，以优先生产权顺序及当月市场需求进行贪婪的生产，直至无法得到满足，得出这几种产品的计划生产量。再搜索该负值能否由最近的上一时段进行补偿，如果能够补偿，则根据优先补偿原则进行贪婪补偿（数量不能超过最大库存），直至不足以补偿或者全部补偿，再根据各产品补偿数量算出新的生产能力差值，如出现新的负值是由补偿造成的，暂不考虑，留作下一轮补偿。

步骤2：搜索T1中的数据如果出现负值，则使用该加工过程的产品必然不能全部生产，根据效益优先原则，优先生产效益高、低工时消耗的产品（参照第四步），并算出新的生产能力差值。

步骤3：重复步骤1、2处理过程，直到所有数据为正，即可得到各时间段计划生产量，由各月份补偿数量得到库存量，问题得以求解。

3 算例分析及实现

根据上面提出的模型，我们对开始提出的问题按以下算法进行求解：

第一步：计算最大生产能力：Nij=第i个月第j种机床数目×工作日×日工作时间，将所得数据填入表一各数据单元（含3个单元格）中左上单元格中。

第二步：计算各月内满足市场容量所需的各个加工过程的生产能力 ：Rij= Zki×tij(k=1,2,…r；j=1,2,…m ； i=1，2，…n)，将所得数据填入表一各数据单元（含三个单元格）中左下单元格中。

第三步：计算各月份最大生产能力和市场容量所需生产能力的差值：Skj=Nkj–Rkj。所得数据填入表1各数据单元（含3个单元格）中右侧单元格中。

表1

第四步：一月份磨床为负，所影响的产品有P1、P2、P5、P6、P7，算出这几种产品的优先生产权值，优先权顺序为：P6、P5、P1、P2、P7，依此顺序优先安排这几种产品生产任务为：X16=200，X15=800，X11=500，X12=888，X17=0，一月份其它产品均能满足，则一月份初步计划为 ：X1i=（500，888，300，300，800，200，0）。作为新的生产需求算出新的生产能力需求及差值，填入表2；六月份除完成生产任务还要有一定库存，将六月份库存任务加入六月份生产计划，算出新的生产能力需求及差值填入表2，则六月份生产任务暂定为X6i=（550，550，150，350，1150，250，110）。二维表中未出现负值的月份生产能力过剩，将市场需求直接作为生产计划量。

表2

第五步：

1）从表2出发从上到下找到第一个负值为-91，为3月份镗床不足。所影响的产品为P1、P2、P4、P5、P7，但由于镗床生产能力为0，即这几种产品一个也不能按优先生产顺序生产，必须全部由上个月份补偿，则算出几种产品优先补偿顺序为P1、P2、P5、P4、P7，依据此顺序和生产任务及最大库存由2月份进行贪婪补偿，补偿数量分别为：X21补=100，X22补=100，X24补=0，X25补=100，X27补=100。根据此补偿需求算出新的生产能力需求及差值（产生新的生产能力不足暂不考虑），填入表3。则得到此次处理的2、3月份初步生产计划：X2i=（700，600，200，0，500，300，250）；X3i=（0，0，0，0，0，400，0）。在向下找到第2个负值为-64.5，为6月份刨床不足。和上面做同样处理，得到5月份补偿六月份的产品及数量为：X53补=100，X55补=100，X57补=100，算出新的需求及差值，得到的数据填入表3，得到5、6月份暂时生产计划为：X5i=（0，100，600，100，1100，300，100）；X6i=（550，550，0，350，0，550，0）。

表3

2）考察到1月份没有出现负值，则进行第二轮处理。

3）从表3出发从上到下找到的第一个负值为-66，为2月份水平钻床不足，所影响的产品有P1、P3、P7。算出这几种产品的优先生产权值，优先权顺序为：P1、P3、，依此顺序优先安排这几种产品生产任务为：X21=700，X23=200，X27=140，2月份其它产品均能满足，则2月份计划为：X2i=（700，600，200，0，500，300，150）。在根据优先补偿顺序进行补偿，计算时因为P1、P3已满足计划，则由一月份补偿P7不足，X17补=100作为新的生产需求算出新的生产能力需求及差值，填入表四。

4）考察到1月份磨床生产能力又出现负值，重复第四步对1月份的处理办法，得到结果为P7无法由1月份补偿。1月份计划量仍为 X1i=（500，888，300，300，800，200，0）。

5）经过以上处理的数据已经没有负值，问题得到解决，各月份生产计划量为：

其中补偿生产产生的库存为：

4 结论

本文在解决此实际问题中，提出了一种基于优先补偿权和优先生产权准则下的规划模型，为解决此类实际问题找到了一种较为通用的算法，该算法可以方便的用于程序实现，具有一定的实用价值。

[1]李清，钱颂迪.运筹学[M].北京：清华大学.

[2]秦宣云.基于优先缺货权的工厂生产计划的动态规划模型 [J].长沙：系统工程，2002.

[T-9]

A

1674-6708（2010）22-0211-02