一类模糊环境下的单机排序模型

一类模糊环境下的单机排序模型

一类模糊环境下的单机排序模型

摘要：本文基于近年来对工件加工时间同时具有恶化和学习效应

的排序问题的研究，引入可信性空间的模糊变量，建立了模糊排序

模型。通过改进遗传算法，设计基于改进遗传算法的混合智能算法

求解模型。最后以具体算例验证了该算法的可行性和有效性。

关键词：可信性理论；排序；遗传算法；混合智能算法

一、研究背景

排序问题（scheduling problems）也称调度问题，是运筹学和组

合优化的一个重要分支。近年来，工件加工时间依赖开工时间的排

序问题受到广泛关注，其中工件加工时间具有恶化和学习效应的排

序问题受到了广泛的关注和研究。lee（2004）[1]最早考虑了两种

效应共同作用的单机模型。现实模型中的参数不一定是确定的，这

些不确定性包括随机性和模糊性。模糊集概念由zadeh（1965）提

出，已经很好地应用于解决各种实际问题方面。为测度模糊事件，

zadeh（1978）提出了可能性测度的概念。但这一理论不满足自对

偶性，而自对偶性在理论和应用中是非常重要的概念。liu和liu

（2002）[2]提出了自对偶的可信性测度概念，并于2004年建立了

可信性理论，已成为研究模糊现象的一个数学分支。

二、理论基础

设θ为非空集合，p为θ的幂集。p中任一元素称为一个事件。对

每一个事件a分配一个数cr{a}，用于表示事件发生的可信性。定

一类模糊环境下的单机排序模型

义1 若集函数cr满足以下四公理，则称之为可信性测度。公理1?

摇 （正定性）cr{θ}=1.公理2 ?摇（单调性）若a?奂b，则cr{a}

≤cr{b}.公理3 ?摇（自对偶性）对任意事件a，cr{a}+cr{ac}=1.

公理4?摇 （极大性原理）对任意满足supicr{ai}＜0.5的事件{ai}，

cr{uiai}=supicr{ai}.定义2 设θ为非空集合，p为θ的幂集，cr

为可信性测度。则称三元组（θ，p，cr）为可信性空间。定义3 将

可信性空间（θ，p，cr）到实数集的可测函数定义为模糊变量。

定义4 设ξ为可信性空间（θ，p，cr）上的模糊变量，则它的隶

属函数由可信性测度表示为：μ（x）=2cr{ξ=x}∧1，x∈r。定义

5?摇 设ξ为模糊变量，它的期望值为：e[ξ]=■cr{ξ≥r}dr-■

cr{ξ≤r}dr等式右边的两个积分至少有一个有限。

三、模型描述

记n个工件为j={1，2，l，n}。在模糊环境下，考虑这一组工件

在一台机器上加工的排序问题。首先作如下基本假设：①一组工件

在初始时刻同时准备加工，工件加工不可中断；②在同一时刻，机

器只能加工一个工件；③在一组工件加工结束期间机器不能空闲。

记工件j的实际加工位置记为jj，则π=｛r1│jr1=1，r2│jr2=2，

l，rn│jrn=n｝为实际加工序列，也就是j重新排序的结果。假设

每个工件的基本加工时间相同，记为模糊变量p0，隶属函数为μ，

它的实际加工时间表示为：pj=（p0+α（tj））（jj）a。其中，tj

是j开始加工时间；α（t）为随t增加而递增的恶化变量，在模

一类模糊环境下的单机排序模型

糊环境中，t为模糊变量，故恶化效应函数值α（t）为模糊变量；

a为学习指数，其中a=log2x，模糊参数x∈（0，100%）。由于具有

学习效应，排在后面加工的工件的实际加工时间会减少；同时，在

恶化效应的作用下，实际加工时间会随着等待时间变长。单机排序

的优化目标，是要找到一种最优的排序方法，使最大完工时间、完

工时间之和、加权完工时间之和、最大延时等目标值最小化。在给

定排序π下，记工件i的完工时间为ci=ci（π），则最大完工时间

为cmax=max{ci|i=1，2，l，n}，完工时间之和为■ci，加权完工

时间之和为■ωici，最大延时为lmax=max{ci-di|i=1，2，l，n}，

其中di为工件的i交货期。但由于加工时间为模糊变量，最大完

工时间等优化目标值不能直接进行比较，而要借助于期望值、可信

度等特征值来进行比较。即将模糊优化问题转化为等价的确定性优

化问题求解。建立模糊单机排序期望值模型，建立如下：假设我们

选取期望值评价准则。期望最大完工时间，期望完工时间之和，期

望加权完工时间之和，以及期望最大延时分别记为

e[cmax]=max{e[ci│i=1，2，l，n]，e■ci，e■ωici，

e[lmax]=max{e[ci-di]│i=1，2，l，n}。以期望值最小化的目标

代替模糊变量最小化的问题，将排序问题转化为确定性的问题解

决。

四、基于改进遗传算法的混合智能算法的模型求解

相对于确定性模型，模糊模型中含有不确定的变量使求解难度更

一类模糊环境下的单机排序模型

大，需要借助于计算机对函数进行编程模拟，并设计基于进化算法

的混合智能算法来求出最优解。遗传算法原理简单，实现便捷，求

解的过程与实际的目标问题无关，具备良好的并行能力和潜在的全

局搜索可能性。考虑到由于遗传算法本身选择压力和种群多样性保

持之间的矛盾带来的缺陷，并依据模型的特点，改进遗传算法，更

新基于改进遗传算法的混合智能算法用于求解论文提出的排序模

型。

1.编码设计。排序模型的优化，实际上就是为了找到工件的一个

最佳的加工次序，使目标函数值最小化。为了方便问题的在遗传算

法中能够被准确地描述，每一个染色体使用一个满足工件优先顺序

的正整数序列作为基因位，来描述一个可行的工件加工顺序。例如，

3个工件j={1，2，3}在1台机器上加工，工件需要满足如下的优

先顺序：2→3，即工件2要优先于工件3加工，那么，可以构筑可

行的工件加工顺序为：{1，2，3}，{2，3，1}，{2，1，3}。

2.种群初始化。已知工件数是n，首先要设定遗传算法的种群规模

为npopsize，迭代进化的上限为：iteration，交叉概率pc和变异

概率pm。每一代的种群对应npopsize个染色体v，在满足工件加

工优先顺序的前提下，每个染色体基因位对应着实际的工件编号

（c1，c2，……cn），ci=ceil（n×rand），直到染色体内的基因值

（c1，c2，……cn）互相不重复。然后把这个步骤执行npopsize

次，得到一组整数排列构成的初始群体：{v1，v2，……vnpopsize}。

一类模糊环境下的单机排序模型

3.评估适应度函数。适应度函数的构造一般都是直接选取目标函

数f（·）。本文中的目标函数需要通过模糊模拟或不确定模拟，求

出模糊的或不确定的目标函数值，将不确定的函数值转化为确定值

比较任意的两个染色体的目标函数值，较小的那个作为较优的染色

体。然后对这npopsize个个体，按照适应度函数大小进行排列，

构成一个新的有序种群v={v1，v2……vnpopsize}。根据文献[3]

设置评价序函数e（vi）=■，方便对群体中的个体进行评价。

4.遗传算子的实施。遗传算法的进化过程中，主要包括以下3个

遗传算子：选择算子，交叉算子，变异算子。这些算子对种群实施

相应的操作，主要的目的就是在维持种群多样性的同时，能够确保

种群在迭代的过程中，适应度较高的个体能够有更多的机会遗传进

入子代个体中去。①为了能够更好地对种群进行进化，选择一个合

适的选择策略是非常关键的。在实施遗传选择算子的时候，不同的

选择策略会给种群带来不同的选择压力，一般，选择压力太大的话

（如轮盘赌选择），会降低种群的多样性，并引起种群陷入早熟，

不能收敛到全局最优；选择压力不足的话（如锦标赛选择]，这会

造成种群的搜索随机性变强，算法的收敛速度慢。为了改变这种状

况，本文使用一个自适应的轮盘赌选择策略，从而平衡种群的选择

压力。②在进行交叉操作之前要预定义一个交叉概率pc，父代个体

在进行交叉操作时，要按照下述步骤重复npopsize次：根据pc从

父代个体中随机选取两个个体vi和vj，i，j=1，2，……，npopsize

一类模糊环境下的单机排序模型

进行下述的配对：（vi1，vj1），……，（vin，vjn），然后随机产生

一个系数e，e∈（0，1），执行如下的交叉操作以得到两个新的父

代个体：vi1=e×vi1+（1-e）×vj2，vj1=（1-e）×vi1+e×vj2，

然后检查vi1，vj1的可行性。如果不可行，不断重复上述步骤，

直至得到两个可行解。③在进行变异操作之前要预定义一个变异概

率pm，父代个体在进行变异操作时，在基因窜上随机选取两个变异

点，然后进行交换，并进行约束判断，从而得到一个新的可行的候

选子代个体。④对于父代的最优个体，采取精英保留策略，无条件

遗传至子代个体中，从而在维持种群多样性的同时，增大种群的选

择压力。

5.混合智能算法的求解步骤。经过了选择，交叉，变异操作后，

新产生的种群就准备进入下轮的迭代进化。整个混合遗传算法将会

在一个给定的循环迭代次数下，按照上述的步骤实施进化，本文把

上述的遗传算法描述如下：步骤1：随机初始化，产生可行的

npopsize个个体；步骤2：通过模糊模拟或不确定模拟，计算目标

函数值；步骤3：对上述的种群根据目标函数值，进行评价，得到

评价适应度函数；步骤4：依照种群约束，对整个种群内的个体进

行遗传操作；步骤5：依照给定的循环数，重复实施步骤2步骤4

之间的过程；步骤6：得到最优解。

五、数值算例

一类模糊环境下的单机排序模型

下面以一个模糊环境下的单机模型为例，目标函数为最大完工时

间最小化，具体问题如下：考虑10个工件j={1，2，l，10}。记工

件j的实际加工位置记为jj，则π{r1│jr1=1，r2│jr2=2，l，rn

│jr1=n}为实际加工序列，也就是j重新排序的结果。具体的说，

如果j1：j10分别取值为2，3，5，7，6，1，4，10，9，8，对应

π={6，1，2，7，3，5，4，10，9，8}。

设每个工件的基本加工时间p0为三角模糊变量（10，12，14），

tj是j开始加工时间；学习效应函数α（t）=0.25t；学习指数

a=log2x，x~（0.25，0.3，0.35），则每个工件的实际加工时间为：

pj=（p0+0.25tj）（jj）a。初始加工时间记为0，最大完工时间为

cmax=max{ci│i=1，2，l，10}=cπ（10），欲求解算例4.1，本文

使用了仿真编译工具matlab7.0，遗传算法的参数设定如下：群体

规模npopsize=50，交叉概率pc=0.3，变异概率pm=0.1，迭代次数

500次。应用上面的数据，通过运行本文设计的程序，得到了如下

的最优结果：最优的实际加工顺序为：（1 8 6 2 7 3 5 4 10 9），

对应最大完工时间的最小值为：20.0097。

六、小结

本文在可信性理论的基础上，关注了近年来对工件加工时间同时

具有恶化和学习效应的排序问题的研究，对排序理论这一经典的组

合优化问题展开研究，在可信性空间建立了模糊排序模型。对排序

问题的求解通常具有一定难度，模型中引入的模糊变量更增加了求

一类模糊环境下的单机排序模型

解模型的难度，本文中设计了基于改进遗传算法的混合智能算法，

并通过具体计算验证了该算法的可行性和有效性。

参考文献：

[1]wen-chiung lee. a note on deteriorating jobs and learning

in single-machine scheduling problems[j].international

journal of business and economics，2004，3（1）：83-89.

[2]liu b，and liu yk. expected value of fuzzy variable and

fuzzy expected value models[j]. ieee transactions on fuzzy

systems，2002，10（4）：445-450.

[3]候福均，吴祈宗.应用遗传算法求解模糊参数的单机调度问题

[j].北京理工大学学报，2006，26（3）：260-263.

本文来源：https://www.bwwdw.com/article/ucr4.html