考虑工件恶化效应和加工时间可控的装配作业车间调度问题研究*

芦 艺

(河南工学院,河南 新乡 453003)

近几十年来,车间调度问题一直是制造领域的研究热点。传统车间调度问题中不同工件间相互独立,不存在先后加工约束。然而,在实际生产中,很多装配型产品发动机、模具等的不同工件间具有一定的层级结构。针对这类产品的车间调度问题,部分学者称之为装配作业车间调度问题(Assembly Job-shop Scheduling Problem, AJSP)[1-3]。AJSP具有传统车间调度问题的特点,同时又增加了工件间先后加工约束,使得问题的复杂程度更高。

为了简化问题,现有文献对AJSP做了很多假设,使得理论研究与实际应用存在较大偏差。例如,现有文献中工件的加工时间大多被认为是固定已知的,然而在实际生产中,机器运行磨损、工件恶化效应、工人学习效应等因素的存在使得工件的加工时间并非恒定不变。近年来,考虑工件恶化效应的车间调度问题受到学者们的关注[4-6]。在这些文献中,通常将工序的实际加工时间假定为开始时间或加工位置的线性函数。除此之外,现实生产中工件的加工时间还取决于其所分配的资源数量,如能源、资金、劳动力等,即通过调整工件所在机器上资源分配的数量,可以控制工件的加工时间。近年来,越来越多的学者开始关注该类问题的研究[7-11]。尽管如此,目前考虑工件恶化效应和加工时间可控的车间调度问题大多被单独进行研究,很少文献综合考虑二者对车间调度性能的影响。

综上所述,本文在AJSP中同时引入工件恶化效应和加工时间可控对车间调度性能的影响,使问题更加贴近现实生产环境。设计一种混合遗传算法,以优化车间内工件的最大完工时间,并通过大量仿真实验验证算法的有效性。

在装配作业车间中,每个产品都可由一个树形结构来表示,如图1所示。根据工序在树上的位置,将其分为0型、1型和2型。例如:叶子节点上的工序被视为0型,对应产品的零件;根节点上的工序被视为2型,对应最终产品;其他工序均被视为1型,对应产品制造过程中的装配体。图1中:A-2表示产品A的工序2,它既不是根节点也不是叶子节点,属于1型工序;B-1处于根节点,属于2型工序;B-2处于叶子节点,属于0型工序。此外,在产品树上,1型或2型工序还拥有子代工序和后代工序,如B-1的子代工序为B-2、B-3和B-4,后代工序为B-2、B-3、B-4、B-5和B-6;A-2的子代工序和后代工序相同,均为A-5和A-6;A-4的子代工序和后代工序均为A-7。

图1 产品A和B的树形结构

根据产品的制造需求,装配作业车间内配置了具有不同功能的制造单元。在每个制造单元中,机器具有相同的功能,工人具有相同的技能水平。每道工序的加工包含两类加工时间,即基本加工时间和实际加工时间。前者由工序所在机器上分配的工人数量决定,后者由工序的开始时间决定。本文所研究问题的最终目标是通过合理分配制造资源(机器和工人),安排机器上工件的加工顺序,以优化车间内工件的最大完工时间,如式(1)所示,式中Cmax为车间内所有工件的最大完工时间,Cij为工序工件i的第j道工序(Oij)完工时间。

minCmax=max(Cij)

(1)

对于上述问题,存在以下假设条件:

(1) 车间内工件一旦开始,其加工过程不允许被中断。

(2) 每台机器同时只能加工一个工件。

(3) 任何工件一旦开始加工,不能被重新分配给另一台机器。

(4) 工件加工过程中工人不允许被转移。

(5) 忽略机器的安装时间和工人的移动时间。

(7) 实际加工时间是工序开始时间的单调递增函数,即pij=pijm+αSij。式中,pij为工序Oij的实际加工时间,α为恶化率,Sij为工序Oij的开始时间。

根据问题描述可知,本文需同时考虑工件恶化效应和加工时间可控这两个现实因素,这使得问题的求解难度大大增加。遗传算法是求解车间调度问题的经典算法之一,其内在机理是模仿自然界中“优胜劣汰、适者生存”的遗传进化过程,以获得问题的最优解。求解时,首先生成初始染色体种群,该种群中每条染色体对应问题的一个解,然后通过对种群不断地执行选择、交叉、变异等遗传操作,直到算法满足终止条件(例如,最大迭代次数),并输出最优结果。本文针对所研究问题的特点,对遗传算法进行有针对性的设计,并将其与变邻域搜索算法相结合,获得一种混合遗传算法。

2.1 调度解表示

根据前述,本文算法设计的首要任务是对染色体进行编码来表示每个调度解。针对问题的特点,将每条染色体分为三个部分:第一部分表示工人分配方案,第二部分表示工序排序方案,第三部分表示机器分配方案。在第一部分中,根据车间内制造单元的数量将染色体分成若干段,每段长度等于相应制造单元内机器的数量,其基因值为每台机器分配工人的数量;第二部分和第三部分的长度相同,均等于车间内的工序总数,第二部分元素值为工序的编号,其排列顺序表示工序在机器上的加工顺序,第三部分元素值为工序所分配的机器的编号,表示为每道工序加工所分配的机器。

2.2 种群初始化

基于上述调度解的表示方法,本文采用随机初始化的方式获得初始种群。对于第一部分,每个元素值在取值范围内任取数值,但每个制造单元内工人总数不能超过该单元能够容纳人数的上限;对于第二部分,将所有工序随机排列获得工序排序方案;对于第三部分,分别从每道工序的可加工机器集合内随机选择一台机器。

2.3 修复算子

由上述种群初始化方法可知,初始种群中每个调度解的工人分配段和机器分配段总是在规定范围内取值,因此总是可行的。然而,由于工件层级结构的存在,工序排序段中极有可能出现违背工件先后加工约束的情况。对此,本文采用文献[12]中的自顶向下递归调整修复算子,从而获得可行的初始调度解。

2.4 遗传算子

2.4.1 选择算子

采用经典的轮盘赌方法对染色体进行选择操作,从而将优秀个体保留至下一代,同时淘汰种群中的劣质个体。

2.4.2 交叉算子

交叉算子的主要目的是将两个父代个体中部分编码进行交换来获得两个新个体,对应生物的繁衍过程。对于工人分配部分,首先随机选择一个制造单元,然后在父代个体间交换所选制造单元对应的基因块内的元素值。工序排序部分采用文献[12]中的交叉方法,即任选一个1型或2型工序,从父代个体中将该工序的所有后代工序提取出来,得到两个工序集,然后将这两个工序集内的元素进行互换,将互换后的元素重新填入父代个体,从而得到两个新个体。机器分配部分采用两点交叉的方法,即首先随机选择染色体上的两个位置,然后将两个父代个体所选位置间的元素值进行交换,得到两个新个体。

2.4.3 变异算子

变异算子的主要目的是通过随机改变染色体中部分编码的值来获得一个新个体,对应生物的突变过程。对于任意个体,工人分配部分和机器分配部分均采用单点变异的方法,即在染色体上随机选择一个变异位置,然后从元素取值范围内任选一个不同值替代原来值。工序排序部分采用文献[12]的基于可行域的变异方法。在该方法中,变异基因可以在不违反工序优先级的情况下,在一定范围内随机改变其位置。

2.5 变邻域搜索算法

遗传算法具有良好的全局搜索能力,但是其局部搜索能力较弱,容易出现早熟收敛。对此,本文在算法中嵌入一种变邻域搜索算法,增强算法局部搜索能力。考虑到算法计算速度和求解质量间的平衡,变邻域搜索算法仅作用于最优个体。根据问题的特点,设计以下三种邻域结构:

(1) 邻域结构N1:在候选解的第一部分中随机选择一个制造单元,随机排列该单元内的元素顺序。

(2) 邻域结构N2:在候选解的第二部分中随机选择若干元素,随机排列被选元素的顺序,然后运用2.3节中的修复算子获得可行解。

(3) 邻域结构N3:在候选解的第三部分中随机选择一个元素,从该元素对应工序的可加工机器集合中选择一台不同的机器替代原来的机器。

基于上述三种邻域结构,本文变邻域搜索算法的步骤如下:

步骤1 将当前种群内最优个体设置为初始解s,初始化邻域结构个数lmax←3和当前迭代次数t←1,并设置终止迭代次数tmax。

步骤2 设置计数器l←1

步骤3 执行振动操作。若l=1,将邻域结构N1作用于s,得到新解s′;若l=2,将邻域结构N2作用于s,得到新解s′;若l=3,将邻域结构N3作用于s,得到新解s′。

步骤4 执行局部搜索操作。将s′作为局部搜索的初始解,得到新解s″。

步骤5 若s″优于s,则s←s″,并设置l←1;否则设置l←l+1。

步骤6 若l>lmax,设置t←t+1,运行至步骤7;否则,运行至步骤3。

步骤7 若t>tmax,运行至步骤8;否则,运行至步骤2。

步骤8 变邻域搜索算法终止。

步骤4中局部搜索操作采用文献[13]中的阈值接受法,步骤如下:

步骤1 将振动操作中得到的新解s′作为初始解,初始化阈值λ←0,当前迭代次数μ←1及标记位θ←1,并设置终止迭代次数μmax。

步骤2 若θ=1,将邻域结构N1和N2同时作用于s′,得到新解s″;若θ=0,将邻域结构N1和N3同时作用于s′,得到新解s″。

步骤3 若Cmax(s″)-Cmax(s′)≤λ,则s′←s″;否则设置θ←|θ-1|。

步骤4 设置μ←μ+1。若μ>μmax,则s″←s′,运行至步骤5;否则,运行至步骤2。

步骤5 局部搜索终止。

假设某车间内有六种产品(C,D,E,F,G,H)需要生产,这里只列出产品F的树形结构,如图2所示。制造单元的资源分配如表1所示,各台机器上的初始工人数量为[3,5,5,3,4,4,4,3,3,3,4,2,4,3]。工序的最大加工时间服从[2,25]间的均匀分布。为了评价算法的性能,基于Compaq visual fortran软件,将本文提出的HGA算法运行在WINXP下搭载Intel(R) Pentium(R) CPU G2030 @ 3.00GHz、2GB主存的PC机上,算法均独立运行10次获得计算结果。

表1 制造单元资源分配情况

为了验证算法的优越性,将本文所提出的HGA算法与文献[1]提出的GA-R算法进行比较。两种算法参数设置为:种群规模为100,最大迭代次数为1000,交叉率为0.8,变异率为0.2,此外,HGA算法中变邻域搜索算法的终止迭代次数tmax和局部搜索操作的终止迭代次数μmax均为10。为了充分比较两种算法,表2针对μ和α的不同取值下的40个算例进行仿真。由对比数据可以看出,HGA算法在29个算例中的计算结果优于GA-R算法(由粗体表示)。算法结果对比曲线如图3所示,可以看出:(1) 对于给定的α值,μ值越大,工件的基本加工时间越小,从而使得车间内工件的最大完工时间越小;(2) 对于一个固定的μ值,随着α值的增大,车间受到恶化效应的影响越大,从而使得工件最大完工时间越大。

图2 产品F的树形结构

图3 算法结果对比曲线

表2 算法计算结果

本文针对一类同时考虑工件恶化效应和加工时间可控的装配作业车间调度问题进行研究。为了优化车间内工件最大完工时间,提出了一种混合遗传算法。根据问题的特点,对遗传算子进行一系列设计,并在遗传算法中嵌入了变邻域搜索算法,以提高求解的性能。仿真数据表明,HGA算法在求解本文问题上是有效的。

考虑到现实生产环境,工人的移动时间和操作之间的安装时间均应该纳入问题。此外,文中假设工人在车间具有相同的技能水平,但实际生产中是不可能的,这也将在未来的研究中予以考虑。

(责任编辑杨文忠)

推荐访问:作业 工件 调度