题目基于遗传算法的作业车间成本控制优化模型

1、辽宁对外经贸学院第十一届学术研讨会题 目：基于遗传算法的作业车间成本控制优化模型学 科：管理学单 位：辽宁对外经贸学院会计系作者姓名：二一五年十一月基于遗传算法的作业车间成本控制优化模型周 瑜（辽宁对外经贸学院会计学院会计系 辽宁 大连 116052）摘要：作业车间调度问题不仅需要对最大化完工时间、最大化机器负荷等性能指标进行优化，还应该考虑作业车间的成本控制。以成本控制优化为目的，提出作业车间调度的最大化加工成本最低的性能指标，并以此为目标函数构建基于遗传算法的优化模型。采用基于工序和基于成本相结合的编码机制，并针对编码方式对交叉操作和变异操作加以改进，保证算法进化搜索过程中的种群多样性，使

2、模型成本控制优化效果得到进一步提升。通过算例的实验和仿真，验证了成本控制优化模型的可行性和有效性，为解决作业车间加工时间和加工成本的两难矛盾提供了新思路。关键字：作业车间；遗传算法；成本控制Optimization Model of Job-shop Cost Control Based on Genetic AlgorithmZHOU Yu（Liaoning University of Internaional Business and Economics, Dalian 116052, China）Abstract:The problem of job-shop scheduling no

3、t only requires optimizing the maximize completion time, the maximize machine load and so on, but also needs to considering the cost control of the workshop. This article aims the cost control optimization, and on this basis proposes the performance index of minimizing the maximum processing cost in

4、 job-shop scheduling, and takes this as the objective function to build optimization model based on the genetic algorithms. Besides that, this article applies the encoding mechanism combining the working process with the cost, and improves the encoding methods about the interlace and variance operat

5、ion, so as to ensure the population diversity in algorithm evolution searching, and make the affection of cost control optimization further improving. Through experiments and simulation examples verifying the feasibility and efficiency of cost control optimization model and providing a new path for

6、solving the problems of job machining time and processing cost.Keywords: Job-Shop; Genetic Algorithm; Cost Control0 引言车间作业安排与优化技术不仅是车间管理的重要组成部分，而且是生产综合计划的重要内容之一，在进行车间作业计划时，必然会涉及作业安排优化问题 ADDIN NE.Ref.A6695F24-8C4A-4160-9690-3D59E448B1E91。从以往的研究 ADDIN NE.Ref.A40EF840-D250-4348-BD87-12CACA8574F52-4来看，对

7、作业车间调度问题的研究主要以生产周期、作业时间等时间性能指标为优化目标，涉及车间成本控制的研究很少，但是在经济活动中，成本是衡量企业经营效果的重要指标。成本控制是指运用一定的方法对产品生产过程中构成产品成本的一切耗费，进行科学严格的计算、限制和监督 ADDIN NE.Ref.D176A5D1-3999-4641-9908-D3CE9CDBD71F5。对于车间成本控制优化的研究，魏法杰（1998）提出了一种新的“IE+ABC”成本控制系统 ADDIN NE.Ref.CE055375-4578-434A-B880-A61B0BBFCE9D6，潘全科等（2004）基于生产成本研究了作业调度问题 AD

8、DIN NE.Ref.7BBA98A9-0885-4881-B4D5-B5AF3AD98ABC7，吴秀丽等（2006）基于加工成本构建了调度优化的成本目标函数 ADDIN NE.Ref.A6DB8F12-2DF6-4B0E-BBEE-8A5EEE9BC1988等等。近年来，随着遗传算法在车间调度中的广泛应用，也逐渐被用来解决车间成本优化问题 ADDIN NE.Ref.521358F2-69B3-4EFA-B6F6-9E00736921F19-13，例如考虑加工成本和时间的柔性作业车间调度 ADDIN NE.Ref.49DB5A83-B14D-4F0A-B963-82D37C362BB514、基

9、于成本的车间调度模型及遗传算法求解 ADDIN NE.Ref.A617E0FF-6DE2-40F7-8606-F8747F64B98A15，配送调度优化模型 ADDIN NE.Ref.0D004016-D153-4826-8512-E735C9536B0816等等。遗传算法在解决车间成本控制优化问题时，其优势在于算法本身的自适应和自学习性，只要确定编码方案、适应度函数和遗传算子后，算法将利用进化过程中获得的信息自行组织搜索，并最终获得最优方案。在传统基于遗传算法的作业车间成本控制优化研究中，主要依赖基于工序的编码，或基于工序和机器相结合的编码，这种编码方式也导致了交叉操作和变异操作的方式，最终

10、的目标函数也仅能以最大化完工时间、最大化机器负荷等指标来衡量。针对车间成本控制优化问题，本文将从加工成本本身出发，采用基于工序的编码和基于成本的编码相结合的编码方式，在相对应的交叉操作和变异操作的基础上，寻求满足最大化完工时间最小和最大化加工成本最低两个目标的最优调度方案。1 作业车间成本控制优化模型构建1.1 作业车间成本控制优化问题描述作业车间成本控制问题可以用来描述，其中M表示作业车间现有的机器，为需要接受加工的工件，O代表工件工序，T为加工时间，为工件的成本。作业车间通常被假设为有台设备和个工件，每个工件包含一道或多道工序，且工序顺序是预先确定的，调度目标是为每道工序选择最适合的设备，

11、以及每台设备上各工件的最佳加工顺序，使所有工件流通时间最短，作业车间成本控制问题描述如表1所示。该加工过程还需满足以下约束条件：（1）每一时刻每台机器只能加工一个工件；（2）各工件经过准备时间即可加工，加工过程具有连续性，整个过程中机器均有效；（3）不同工件的工序没有先后约束；（4）工件间优先级相同；（5）零时刻所有工件都可被加工；（6）操作允许等待，即后面的工序操作需要等待前面完成，除非特殊说明，可以无限缓冲。（7）工序在不同机器上的加工成本具有差异性。表1 作业车间（）成本控制问题描述工件工序（，）（2，1）（3，2）（2，1）（2.5，1）（1，1）（3，2）（4，3）（2，1）（3，2

12、）（5，3.5）（1，0.8）（2，1）（3，2）（2，1）（4，3）（3，2）（2，1）（4，3）（3，2）（2，1）（1，0.8）（3，2）（5，3.5）（2，1）（3，2）1.2 模型构建对于作业车间的成本控制问题，首先需要确定车间的机器台数，工件数量，而且每个工件都将包含道基本工序，本文中用代表工件上的第道工序。对于作业车间的成本控制问题，即在某个工件（）的加工过程中，需要从加工时间和加工成本两个方面控制 ADDIN NE.Ref.EEEDFCB5-46B7-4EB8-ABFA-75AFAA02E825。 = 1 * GB3 控制加工时间，工期最短约束。车间工件的加工在时间上并不是连续

13、的，工序之间通常会有等待时间，若是工序的紧前作业集合，则只要工序还未结束，工序就不能开始进行，因此如何控制作业车间工件加工工期最短是车间作业成本控制基本要求。 = 2 * GB3 控制工件加工成本，成本最低约束。如果生产工件在不同工序的需要耗费的成本用种资源，（）的总和为。作业车间成本控制的目标是在最短工期内使的值达到最低。因此，对于个工件、台机器的作业车间成本控制问题，本文采取最大化完工时间最小、最大化加工成本最低两个性能指标，目标函数分别如下： MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTEq

14、n c * Arabic * MERGEFORMAT 1)其中表示作业车间工件数，为作业车间可以加工的机器数。2 基于改进遗传算法的作业车间成本控制优化模型设计2.1 编码策略在传统的作业车间调度模型中，基于遗传算法的编码过程通常是基于工序进行的。这种基于工序的编码方式主要是编码来处理生产调度问题的参数，所以需要将它们表示成遗传空间按一定结构组成的染色体，由染色体的进化寻找模型的最有决策。但基于工序的编码方式具有一定的局限性，由Adams，Balas和Zawack共同提出了基于机器的移动瓶颈启发算法，通过将将机器相继排列，在每次空闲的机器中识别瓶颈机器，并通过瓶颈机器的顺序完成调度。将基于工序

15、和机器两种编码方式相结合也成为了目前遗传算法研究车间调度问题最为流行的方法。本文需要从工期和成本两个方面约束车间作业过程，因此需要将这种编码的方式灵活运用。在工件的加工过程中必然产生成本，而且每个工件在不同机器上得成本各不相同，因此可以由基于不同工序产生的成本代替基于机器的编码方式，形成基于工序和成本相结合的编码方式。基于工序的编码是用基因的编码方式来完成调度方案。基因由染色体组成，每组染色体构成工件的工序，而且同一工件的所有工序采用同一工件序号表示。因此，根据染色体的排序就可以决定工件在不同机器上得加工顺序。因为基因的组合总是在可约束范围内，解码过程将通过根据染色体转化而形成一定秩序的工序表

16、，从而生成调度方案。本文中采用基于工序和成本相结合的编码方式，类似于基于机器的编码方式，在编码过程中不考虑某件机器，而仅从加工成本出发，即这种编码方式也实现全部由染色体控制。通过引入基于成本的编码方式，可以保证基因串在多次交叉后产生可行解，同时获得成本最低的调度方案。用表示基因串，表示工序成本，基于成本编码的基因串如表2所示：表2 基于成本编码的基因串方案基因串NB1BNB2BPB1BCB1BCB3BCB6BCB2BCB4BCB5BPB2BCB6BCB3BCB4BCB1BCB5BCB2B2.2 适应度函数适应度函数是成本控制优化算法进化过程的内部依据，其基本原理是利用种群中每个个体的适应度值进

17、行搜索。在目标函数已经确定的前提下，适应度函数的设置应简单、有效，这样不仅减少时间和计算空间的复杂性，而且能得到更优的效果。作业车间成本控制优化的目标函数包含两个方面，所以，适应度函数也应该包含两方面的内容。根据免疫遗传算法适应度的计算公式： MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTEqn c * Arabic * MERGEFORMAT 2)保证了各个适应度值之间的差异性，取足够大的正数，可以认为是整个种群的规模。本文中引入免疫遗传算法的适应度计算法则，变换后得到作业车间成本控制优化算法的适

18、应度函数： MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTEqn c * Arabic * MERGEFORMAT 3)其中为作业车间的机器数，、分别为最大化完工时间最小、成本控制最低两个性能指标的权重，且。为避免算法过程的过早收敛，保持种群个体的多样性，需要将适应度函数做一定的尺度变换，通常有线性尺度变换、幂函数尺度变换以及指数制度变换等方法。本文中选取线性尺度变换法，如公式（5）所示： MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERG

19、EFORMAT ( SEQ MTEqn c * Arabic * MERGEFORMAT 4)为变换后的新适应度， 、为变换系数，其值的确定参考公式（6）。 MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTEqn c * Arabic * MERGEFORMAT 5)根据试验经验，的取值范围可在之间 ADDIN NE.Ref.4F911504-310F-4C0A-AAB2-026D0FEAF5D4。2.3 遗传算子（1）选择操作。选择操作以适应度为基础，备选集中的每个个体都具有一定的选择概率，这种概率

20、取决于个体的适应度及其分布规律。遗传算子的选择操作通常用轮盘赌法则进行，首先设定一定的适应度值，对于第和个个体，如果满足条件（为当前种群规模）： MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn h * MERGEFORMAT ( SEQ MTEqn c * Arabic * MERGEFORMAT 6)那么种群中将选择第个个体进行计划，第个个体被淘汰。通过轮盘赌法则，适应度越高的个体进行进化的概率越大，其个体特征更容易遗传到子代中去。（2）交叉操作。交叉操作是遗传算法是遗传算法中最常用、最重要的运算，是两个相互配对的染色体按某种方式相互交换其部分基

21、因，然后产生新的子代个体。在遗传算法的交叉操作中，通常包含单点交叉、多点交叉、均匀交叉以及线性次序交叉等方式。本文将选择最为常用的单点交叉，依据编码方式的不同，作业车间成本控制交叉操作也将包含基于工序的交叉和基于成本的交叉两种方式。基于工序的交叉首先需要选定两个父代染色体，分别用PB1B、PB2B表示，以3个工件，3道工序的染色体为例，则两个父代染色体的如下所示：PB1BOB11BOB21BOB12BOB23BOB31BOB22BOB13BOB33BOB32BPB2BOB21BOB11BOB22BOB13BOB32BOB23BOB12BOB31BOB33B假设PB1B向子代提供第一个工件的3道

22、工序、，PB2B向子代提供第二个工件的3道工序、，在子代染色体中分别保持所提供工序原有位置不变。用OF（Offspring）表示子代 ，则产生的两个新染色体如下表示：OFB1BOB11BOB21BOB12BOB22BOB32BOB23BOB13BOB31BOB33BOFB2BOB21BOB11BOB22BOB12BOB31BOB23BOB13BOB33BOB32B基于成本的交叉与基于机器的交叉相类似，假设3个工件不同工序在不同的机器上的加工成本具有差异性。同样以的染色体为例，各道工序在不同机器上的加工成本用随机整数表示，则初始父代PB1B、PB2B如下所示：PB1BOBijBOB11BOB21

23、BOB12BOB23BOB31BOB22BOB13BOB33BOB32BCBijBj123223212PB2BOBijBOB21BOB11BOB22BOB13BOB32BOB23BOB12BOB31BOB33BCBijB132222332随机选取任一位置作为交叉点，在交叉点前相同工序由于需要交换机器而互换成本，交叉点后也是同样操作。对于PB1B、PB2B，选择所有工序的中间位置作为交叉点，即PB1B的和PB2B的，则产生两个新的子代染色体如下所示：OFB1BOBijBOB11BOB21BOB12BOB23BOB31BOB22BOB13BOB33BOB32BCBijB313223222OFB2B

24、OBijBOB21BOB11BOB22BOB13BOB32BOB23BOB12BOB31BOB33BCBijB212222331两种单点交叉方式的共同作用是对两个相互配对的父代染色体PB1B、PB2B按照不同的方式交换部分基因，在形成新子代个体的同时在解空间进行有效搜索，而且避免了对有效模式的破坏。（3）变异操作。变异操作是另外一种子代变异过程，子个体变量以很小的概率或步长发生转变，防止在适应度不再变化的情况下出现过早收敛。变异操作的本质是局部随机搜索，与选择、交叉操作结合保证遗传算法的有效性，使遗传算法具有局部的随机搜索能力，实现算法的全局收敛。变异操作有实值变异、二进制变异等方式，本文选取

25、二进制变异。在操作过程中，种群中选择一定比例的个体以概率发生变异，将染色体中任意选取的两个位置基因互换，从而产生新个体淘汰种群中适应度低的个体。2.4 迭代终止条件遗传算法的迭代终止条件，通常有以下三种判断标准：种群中个体适应度值超过预先设置值；种群中个体适应度的平均值超过设定值；直接设定迭代数。在实际的应用过程中，可以通过不同的方法设定迭代终止条件，本文选取连续两代种群中个体适应度平均值的差值作为迭代的终止条件。设定最够小的常数，根据Himmeblau判断准则，本文的迭代终止条件如公式（8）所示： MACROBUTTON MTPlaceRef * MERGEFORMAT SEQ MTEqn

26、h * MERGEFORMAT ( SEQ MTEqn c * Arabic * MERGEFORMAT 7)其中：为种群规模大小，表示遗传代数，为根据成本控制系统优化要求的精度给出适当小的常数。3 作业车间成本控制优化算例3.1 算例选择对于作业车间成本控制遗传算法的应用，本文选取具有8个工件，6台加工机器的某作业车间作为算例，对算法性能进行测算。在算例中，每个工件分别包含3道工序，各个工序可以在指定的某几台机器上进行加工，选择不同的加工机器也构成了相应的成本差异性，具体加工时间和加工成本如表3所示：表3 作业车间成本控制优化算例工件工序（，）（2，1）（3，2）（2，1）（2.5，1）（1

27、，1）（3，2）（4，3）（2，1）（3，2）（5，3.5）（1，0.5）（2，1）（3，2）（2，1）（4，3）（3，2）（2，1）（4，3）（3，2）（2，1）（1，1）（3，2）（4，2.5）（2，1）（3，2）（4，3）（2，1）（1，1）（2.5，2）（1，1）（4，3）（4，3）（1，1）（2，1）（3，2）（1, 2）（3，2）（1，0.5）（1，1）（2，1）（2，1）（3，3）（3，2）（2，2）（1，2）（3，2）（1，0.5）（3，2）（2，2）（2，1）（1，1）（1，1）（3，2）（2.5，1）（2，1）（2，2）（1，1）（2，1）（2，1）（2，2）（4，3）（1

28、，1）（2，1）（3，2）（1，1）（4，3）（2，3）（2，2）（2，1）（1，0.5）（1，1）（3，2）（2，1）（3，2）（4，3）（1，1）（2，2）（3.5，2）（1，1）（3，2）（4，3）（1，1）（1，0.5）（2，2）（1，1）（3，2）（4，3）（2，1）（2，2）（1，1）（3，2）（2.5，2）（3，2）（2，2）（4，3）（1，1）（2，2）（3，3）（2，1）（2，2）3.2 算例结果分析在Windows 7操作环境下，CPU主频为双核2.5GHz，内存2.0GB，依据MATLAB7.0平台编写遗传算法进化程序，计算作业车间的加工时间和加工成本的分布。对于参数的选

29、取：种群规模，交叉概率，变异概率，迭代终止条件，实验次数设定为20。在种群个体的代与代适应度均值之差与代适应度均值比值的绝对值低于0.01时，算法达到收敛条件。对于算例的成本控制优化效果，为增强本文基于工序和成本相结合编码方式与传统方式的比较，本文对传统纯基于工序编码以及纯基于成本编码的两种遗传方式分别进行计算，对比结果显示如表4所示：表4 算法结果比较编码方式基于工序的编码基于成本的编码本文的编码最佳平均最佳平均最佳平均89.51011.5893638.533.53531.533.25从表4的结果可以看出，如果仅基于工序编码的遗传算法最大化完工时间最好为8，加工成本为36；仅基于成本编码的遗

30、传算法最大化完工时间最好为10，加工成本为33.5；本文基于工序和基于成本相结合的编码方式，最大化完工时间为8，加工成本为31.5。纯基于工序编码的算法在改善加工时间的指标上表现较好，同理纯基于成本编码的算法可以更好地提升作业车间成本控制效果，但二者相结合的编码方式在获得作业车间加工时间最小的同时，还可以使加工成本得到更进一步的优化。综合表现，基于工序和成本相结合的编码方式不仅可以缩短最大化完工时间，而且能降低最大化完工成本，其性能比基于单一编码方式的传统遗传算法更为先进。与此同时，本文改进的遗传算法在计算性能上也得到一定的提升，算法的收敛性能得到提高，收敛曲线如图1和图2所示。图1 与基于工

31、序编码的传统遗传算法的比较图2 与基于成本编码的传统遗传算法的比较综合图1和图2的迭代次数，传统遗传算法在迭代75次以后能得到最优结果，本文算法在迭代55次后就可以得到最优结果。从收敛曲线的比较中可以看出，本文算法在收敛性能上表现为收敛得更早、更快，而且通过较少的迭代次数就能得出最优的结果。仿真结果表明，对于作业车间的加工时间和加工成本可以在一定程度上共同改进，二者的矛盾性可以通过改进的算法得到缓和。4 结论本文基于遗传算法构建作业车间成本控制优化模型，并选取相应的算例对模型的成本优化性能进行测算。对于作业车间成本控制优化问题，构建了以最大化完工时间最小、最大化加工成本最低两个性能指标为目标的

32、优化模型。在传统基于工序编码和基于机器编码等方式的基础上，提出了基于工序和基于成本相结合的编码方式，并选取了基于工序和基于成本的新型交叉算子，为模型的优化操作提供了算法上的改进。算例实验结果表明模型在解决作业车间成本控制优化问题上具有比传统遗传算法更先进的性能，可以保证在完工时间最短的情况下持续降低作业车间成本。作业车间成本控制与加工时间在一定程度上具有两难性，但通过选择合理的调度方案可以使二者在一定范围得到共同优化，本文的模型为有效解决作业车间成本优化提供了新的理论方法。但是在实际的作业车间加工过程中，成本控制涉及的因素具有多样性，包括车间加工条件、外界环境、人为管理等等，给工件加工成本的确

33、定也带来难度。在进一步的研究中，需要对车间成本控制中工件成本的确定方法、作业车间柔性特征对加工成本的影响以及加工意外状况造成的成本变化等问题进行研究，使得这种基于先进算法的模型成为解决作业车间实际问题的有利工具。 ADDIN NE.Bib参考文献：1 张人千，魏法杰，谭甄. 基于成本的车间作业优化模型及实证研究J. 中国管理科学. 2002(5): 75-78.2 Rohlder T R, Scudder G D. Comparing performance measures in dynamic job shops: economics vs. time J. International J

34、ournal of Production Economics. 1993, 32(2): 169-183.3 R S L. Scheduling a single machine to maximize net present valuesJ. International Journal of Production Research. 1991, 29(6): 1141-1160.4 刘晓霞，谢里阳，陶泽，等. 基于生产费用的柔性作业车间调度优化J. 东北大学学报(自然科学版). 2008(4): 561-564.5 李蕊爱. 现代企业成本控制研究M. 北京: 中国商业出版社, 2010.6 魏法杰，王丹. 车间成本控制IE+ABC方法的应用研究J. 中国管理科学. 1998(2): 29-37.7 潘全科，王化明，孙志峻，等. 基于生产成本的作业调度J. 南京航空航天大学学报. 2004(1): 121-124.8 吴秀丽，孙树栋，郝京辉，等. 面向成本的车间调度优化模型研究J. 机械科学与技术. 2006(4): 421-425.9 Guimaraes K F, Fernandes M A. An Approa