基于人工蜂群的空间资源受限项目调度算法

张　波，靳金涛

(1.中国电子进出口总公司，北京　100036; 2.中国电子科技集团公司第五十四研究所,河北 石家庄　050081)



基于人工蜂群的空间资源受限项目调度算法

张波1，靳金涛2

(1.中国电子进出口总公司，北京100036; 2.中国电子科技集团公司第五十四研究所,河北 石家庄050081)

空间资源调度问题在满足时间和空间资源约束的前提下，追求项目工期最短以及空间资源利用的最大化，针对该问题对空间资源进行抽象，建立数学模型，在配置空间理论基础上，提出基于人工蜂群的时空资源受限项目调度算法。对不同规模的问题实例采用不同的算法进行对比，结果表明本文算法在相对较短时间内可以获得较优的调度方案。

空间资源；空间配置；人工蜂群

0　引　言

受资源约束的项目调度问题追求在资源最大化利用的前提下项目工期最短，包含空间资源的调度问题广泛存在于建筑、船舶制造等领域，因此采用有效算法解决该类调度问题对提高生产效率有重要意义。

本文以飞机制造为背景，通过分析飞机建造时分段制造的整个流程，建立以分段为作业对象，制造平台为场地空间的空间资源约束的项目调度模型。提出一种基于人工蜂群的资源约束调度算法，在同时满足时空资源约束的情况下形成较优的调度方案，并对算法进行仿真测试。

1　问题描述与解决方法

1.1问题描述

本文研究的是资源受限项目调度问题[1-2]，具体以飞机建造中分段制造为背景，将其看作一个时空资源受限的项目调度问题，将每一个分段的制造看作项目中的子任务，任务间存在约束关系，任务制造时有时间和空间的约束，求解在满足约束的前提下的最短项目工期。为了更加准确的描述该模型，首先需要定义概念如下：

定义1空间资源：在加工生产时放置分段对象的二维场地资源，主要包括可划分性、可更新性，即可将场地资源划分为更小的空间，在释放后可继续使用。

图1　作业对象

定义2作业对象：在项目中使用资源的最小实体，将其抽象为二维空间内的凸多边形。如图1所示。

b1表示一个作业对象，该对象用逆时针顶点集合{A、B、C、D、E}来表示，使用左下角的A为其表示点。

1.2受资源约束的项目调度模型

空间资源受限项目调度问题是已经研究较多的一种资源调度模型[3-4]，而本文所提出的较大不同处在于资源类型的不同，在某一项目中共包含有J个任务j(j=1,2,…,J)，设任务j的工期为dj。每一项任务在执行时需要满足两种约束。其一，任务的执行顺序约束，若记Pj是任务j的紧前任务集合，则对任一任务i∈Pj，在所有的任务结束后，任务j才可以开始执行。其二，任务执行时使用的资源约束，在该模型中我们只考虑空间资源，所使用的第k(k=1,2,…,K)种资源的上限为Rk，而执行任务j需要第k种空间资源量为rjk。该问题的优化目标是使项目总工期最短。此问题可建立如下概念性数学模型：

minFTj

(1)

s.t.FTj-FTi≥dj,∀i∈Pj

(2)

(3)

BLi∩BLj=φ,∀t

(4)

其中：FTj是第j(j=1,2,…,J)个任务的完成时间，A(t)是[t,t+1)时刻正在加工的任务的集合，BLi为作业对象对场地的占用。式(1)表示优化目标为项目工期最短，式(2)表示任务间的紧前关系约束，式(3)表示任务执行时所需要的所有资源都要满足空间资源的约束，式(4)则表示了空间资源在使用时不可交叉使用的特点。

2　基于人工蜂群思想的空间资源调度算法

2.1ABC算法求解MRCPSP问题

ABC算法通过模仿现实生活中蜜蜂种群通过彼此间的协作而以一种极高的效率从食物源中采集花蜜来实现的一种群体智慧算法，将这种群体智慧的最小搜索模型分为食物源、被雇佣的蜜蜂和未被雇佣的蜜蜂，通过他们之间的信息交换进而最大限度的找到食物源的位置。寻找食物源的过程算法如下所示：

算法输入：Population_Size(种群规模)、Max_Trial(食物源被采蜜次数)

算法流程：

初始化

Food_Number = Population_Size/2

For i=1 to Food_Number

随机初始化食物源i，将食物源i形式化为优先权向量

Triali=0

End For

迭代

For i=1 to Food_Number

计算每一个食物源i的适应度函数值

End For

===============雇佣蜂工作===============

For i=1 to Food_Number

从食物源i的向量表示中随机选择一个维度d

从所有食物源中随机选择食物源k

生成候选食物源并选择其位置

如果食物源优于原食物源那么替代它，否则原食物源Triali++继续迭代

End For

===============跟随蜂工作===============

计算每个食物源被选择的概率并采用轮盘赌的形式选择一个食物源

For i=1 to Food_Number

从食物源i的向量表示中随机选择一个维度d

从所有食物源中随机选择食物源k

生成候选食物源并选择其位置

如果食物源优于原食物源那么替代它，否则原食物源Triali++继续迭代

End For

(侦查蜂工作)

For i=1 to Food_Number

如果食物源i达到最大迭代次数

随机初始化食物源i

Triali=0

End For

记录此次迭代过程的最优食物源信息

结束迭代(当满足迭代结束条件时)

返回最优食物源。

2.2食物源的表示

2.3适应度函数的表示

项目调度问题的优化目标为工期最短，通过使用其倒数与人工蜂群中适应度函数联系起来，用如下公式来表示：

(5)

在对食物源使用位置向量进行表示后，为了求解MRCPSP问题，这里需要一个由N个任务组成的调度计划。利用食物源的位置优先权向量采用串行调度生成方法产生一个可行的调度方案。

2.4资源分配算法

本文提出的问题模型中的资源约束为空间资源，这种资源不同于常见的离散资源，对该类资源的分配需要采用基于配置空间理论[5]的相关算法，如图2所示。

图2　空间资源的分配流程

场内配置空间指任务可在场内放置的位置区域，首先将作业对象的一个顶点与空间资源的一个顶点重合，且此时不发生资源冲突，通过左右移动、上下移动的方法计算出该任务在场地内所有可放置的区域，该区域使用逆时针的坐标点集合来标识。

可配置空间计算完成后，选择其中一个区域来放置作业对象便成了最后的步骤，由于空间资源是一种连续资源无法使用穷举，所以采用最大残余空间利用规则，即使不同的任务尽量摆放的紧密，尽可能少的产生零碎空间，具体方法在JunliZheng[6]的文章中有描述。

2.5食物源更新

每次迭代都会生成新的食物源，通过计算新食物源的适应值以此来决定候选食物源是否会被采用，生成公式如下所示：

νid=xid+ω1rid(xid-xkd)

(6)

其中xid为向量xi中第d位，xkd为向量xk的第d位，rid为[-1,1]上的随机数，ω1为未知数，用来控制食物源每次微调的幅度。

雇佣蜂在探索到新的食物源后会与跟随蜂分享，而跟随蜂采用轮盘赌算法来选择是否采用该雇佣蜂提供的食物源位置，具体算法见公式(7)。

(7)

νid=xid+ω2rid(xid-xkd)

(8)

这里ω2用来控制雇佣蜂所提供信息的重要性，在每一次的迭代过程中其最优解都会保存下来，这样在经过有限次迭代后，全局最优解也会被保存下来。

3　实验分析

3.1测试数据

本文所提出的为空间资源受限时的问题模型，根据模型的需要编写nProgen，用于生成模型所需要的问题集，为了消除数据的偶然性，对每种规模的测试均生成10种测试集，通过求其平均值以此消除数据的偶然性。

3.2参数训练

人工蜂群算法在计算时与迭代次数、种群数量以及候选食物源与当前食物源的差异(即w1、w2的取值)有很大关系。为了寻找在迭代次数与种群数量固定时w1与w2的最佳取值，设计一组实验，种群数量为50，迭代次数为25时的实验效果(如图3所示)。

图3　参数训练

该结果展示出w1与w2的不同组合对实验结果的影响，通过该组实验发现，w1与w2分别在取值区间[0.7,0.9]、[1.1,1.3]时可达到较好的性能。

3.3比较试验

为了验证该算法的有效性，采用传统的随机采样算法进行对比，设置不同的作业数量，在不同的任务数量下比较其效果和效率，具体数据如表1所示。

表1　与随机采样算法的对比结果

结论

以飞机建造中分段制造为背景研究了时空资源受限时的项目调度问题，并将该问题模型抽象，形成准确描述的数学模型，对该模型进行分析，通过模拟蜂群群体寻找蜂蜜的过程提出一种基于人工蜂群的资源受限项目调度算法，并通过大量数据对该算法的性能进行实验，证明该算法在时间和空间上都达到了较好的效果。

[1]Hurink,J.L,Kok A.L,Paulus,JJ.Decomposition method for project scheduling with spatial resources[J].Research report.University of Twente,The Netherlands,2006.

[2]Park C,Chung K.H,Park J.H,et al.A spatial scheduling application at the block paint shop in shipbuilding: the HYPOS project[J].Production Planning & Control,2002,13(4):342-354.

[3]Ghada E.K,Andre L,DianeR.Integrated production and material handling scheduling using mathematical programming and constraint programming[J].European JournalofOperationalResearch,2006,175: 1818-1832.

[4]Raj P,Rajiv K.S.Solving spatial scheduling problem: an analytical approach[J].Proceeding of the 37th International Conference on Computers and Industrial Engineering,2007:2002-2011.

[5]Lee K.J,Lee J.K,Choi S.Y.A Spatial Scheduling System and its Application to Shipbuilding: DAS-CURVE[J].Expert System with Application,1996:10(3/4):311-324.

[6]JunliZheng,Zhibin Jiang,Qiangchen,Qunting Liu.Spatial scheduling algorithm minimizingmakespan at block assembly shop in shipbuilding.International Journal of Production Research,15 April,2011,2351-2371.

Spatial-Resource constrained project scheduling algorithm based on artificial bee colony

ZHANG Bo1, JIN Jin-tao2

(1.ChinaNationalElectronicsImport&ExportCorporation,Beijing100036,China;2.The54thResearchInstituteofCETC,ShijiazhuangHebei050081,China)

Spatial-Resource constrained project scheduling problem pursues minimal makespan and maximal resource utilization that satisfy traditional restrictions in resource capacity and due dates. In order to solve this typical problem a mathematical model was proposed.On the basis of theory in configuration space, a multi-resource constrained project scheduling algorithm based on artificial bee colony was provided. An experiment compared with the different algorithms in the corresponding data scale is made and the result shows that relatively good performance and higher efficiency can be achieved in a short computational time.

Spatial-Resource; Configuration space; Artificial bee colony

2016-01-15

张波(1979-)，男，内蒙古呼和浩特人，博士，主要研究方向：通信工程，项目管理，运筹学，系统工程.

Email：zhangbo@ceiec.com.cn

1001-9383(2016)02-0006-06

TP391

A