多次抢占项目调度问题的混合遗传算法
发布时间：2021-10-27 01:19
研究多次抢占式资源受限的项目调度问题,假设任意时间点可作为资源抢占节点且抢占次数不受限制,建立满足多次资源抢占的线性整数规划模型并提出改进遗传算法对其进行求解。为克服遗传算法（GA）局部搜索能力缺陷,在算法中引入禁忌搜索（TS）进一步优化子代。针对性地设计了允许多次抢占的基于工作优先级编码策略以及串行调度方案生成机制。通过测试算例集实验调试算法参数,并以标准算例集（Project Scheduling ProblemLibrary,PSPLIB）对算法进行可行性检验。实验结果表明,资源受限项目调度问题中引入多次抢占机制能有效缩减项目工期,设计的算法对问题求解效果良好。
【文章来源】：计算机工程与应用. 2019,55(06)北大核心CSCD
【文章页数】：6 页
【部分图文】：
工序关系与约束信息图
少于必要时间；约束函数（8）表示决策变量。假设一个包含11个工作的项目，工作0和工作10分别是表示开始和结束的虚拟任务，其余工作均为需要时间和可再生资源的实际工作。工作之间的网络关系与约束信息如图1所示。以工作8为例，工作8的开始以工作5和6同时完成为前提，工作8的开始时间为前序任务的最晚的结束时间，且完成工作8需要至少3个单位时间，各单位时间内供应的可更新资源不少于2个单位数量。上述小规模RCPSP，由于其网络复杂度较低，通过精确算法求得工作一次性调度下的最优方案。项目单位时间资源使用量如图2所示。从图2中可以看出，项目整体持续时间为15天，其中7天未实现资源利用最大化，精确算法虽可以求得RCPSP的最优调度方案，但是上述方案仍然有大量资源出现闲置，难以实现资源连续高效使用。由于完成项目所需的资源总量确定，项目工期会随单位时间资源利用率的降低而延长，若能提高单位时间资源利用率，就能缩短整个项目的完成时间。PRCPSP以单位时间节点作为工作抢占点，在满足资源约束和前后关系约束的前提下，允许其他满足进行条件的工作抢占当前进行工作的资源并优先进行。当采取抢占式调度方案时，能有效地避免上述资源闲置所带来的工期顺延[18]。3算法设计遗传算法是模拟生物进化过程搜索最优解的方法，算法将其求解的问题以“染色体”的形式表现，采用“适者生存”的原则对种群内染色体进行选择、交叉、变异操作，以获得高适应度子代个体。遗传算法因其本身具有强大的自适应性、可扩展性及群体进化能力被广泛应用。禁忌搜索算法属于邻域搜索算法，具有自适应的存储记忆功能。算法从一个初始可行解开始，搜索过程中通过禁忌表避免迂回搜索，同时可通过藐视准则特赦被禁忌的最优解，从而实现对?
?Pc，算法基本流程如下：BEGINParameter:Popsizeo,MaxGen,PcSet:InitPop;gen=1Compute:Fitness(gen)WHILEgen≤MaxGen;Pair:Group=Popsizeo/2Crossover:twopointMutate:tubasearchCompute:Fitness(newgen)Merge:gen=gen+newgen;Popsize=2×PopsizeoUpdate:gen=gen+1Select:Popsize=PopsizeoENDWHILEEND4算例分析结合本文模型及所提算法对所举算例进行分析。假设其工作允许抢占，但是限制其最大抢占次数为1时，其他条件不做变化，得到相应调度方案2，项目单位时间资源使用量如图3所示。调度方案2总持续天数为15，项目实现资源最大利用时间为12。相比方案1其前期资源得到了连续高效使用，实现了利用率最大化，但1_PRCPSP的项目完成时间没有得到缩减。针对此案例采用多次抢占策略做进一步优化，得到相应调度方案3，项目单位时间资源使用量如图4所示。调度方案3总持续天数为14，项目实现资源最大利用时间为11。方案3在实现资源使用的稳定性优化的同时，缩短了项目的总体完成时间。为进一步检证文中所提抢占模型及其算法可行性，采用Kolisch构建的标准算例库PSPLIB中单模式RCP-SP算例进行算法性能测试。算例中的每个工作最多有3个紧后任务，共涉及调度4种可更新资源，并限制每种资源的可用上限。算例库中算例有4种规模，以其工作数量划分分别为J30、J60、J90、J120，其中算例库已公布J30算例在非抢占情况下的精确算法最优解。本文采用J30算例作为算法的实验数据对算法进行可行性验证。遗传算法求解受算法参数影响，为保证算法求解效果，拟对交叉概率Pc和变异概率Pm进行参数调试。首先对J30中部分算例进行实验，确定算法参数。统计J30中各算例的持续时间，依据分层抽样原则，将
【参考文献】：
期刊论文
[1]求解任务可拆分多项目协同调度问题的启发式算法[J]. 王磊,聂兰顺,战德臣,王弼陡,罗刚银. 控制与决策. 2017(06)
[2]基于项目网络拆分决策的多项目协同调度问题建模[J]. 陆志强,杨超. 上海交通大学学报. 2017(02)
[3]任务可拆分的多模式多项目调度模型与算法[J]. 王伟鑫,王旭,葛显龙. 计算机集成制造系统. 2014(06)
[4]抢占式资源受限项目调度问题的遗传算法[J]. 寿涌毅,彭晓峰,李菲,赖昌涛. 浙江大学学报(工学版). 2014(08)
本文编号：3460582
【文章来源】：计算机工程与应用. 2019,55(06)北大核心CSCD
【文章页数】：6 页
【部分图文】：
工序关系与约束信息图
少于必要时间；约束函数（8）表示决策变量。假设一个包含11个工作的项目，工作0和工作10分别是表示开始和结束的虚拟任务，其余工作均为需要时间和可再生资源的实际工作。工作之间的网络关系与约束信息如图1所示。以工作8为例，工作8的开始以工作5和6同时完成为前提，工作8的开始时间为前序任务的最晚的结束时间，且完成工作8需要至少3个单位时间，各单位时间内供应的可更新资源不少于2个单位数量。上述小规模RCPSP，由于其网络复杂度较低，通过精确算法求得工作一次性调度下的最优方案。项目单位时间资源使用量如图2所示。从图2中可以看出，项目整体持续时间为15天，其中7天未实现资源利用最大化，精确算法虽可以求得RCPSP的最优调度方案，但是上述方案仍然有大量资源出现闲置，难以实现资源连续高效使用。由于完成项目所需的资源总量确定，项目工期会随单位时间资源利用率的降低而延长，若能提高单位时间资源利用率，就能缩短整个项目的完成时间。PRCPSP以单位时间节点作为工作抢占点，在满足资源约束和前后关系约束的前提下，允许其他满足进行条件的工作抢占当前进行工作的资源并优先进行。当采取抢占式调度方案时，能有效地避免上述资源闲置所带来的工期顺延[18]。3算法设计遗传算法是模拟生物进化过程搜索最优解的方法，算法将其求解的问题以“染色体”的形式表现，采用“适者生存”的原则对种群内染色体进行选择、交叉、变异操作，以获得高适应度子代个体。遗传算法因其本身具有强大的自适应性、可扩展性及群体进化能力被广泛应用。禁忌搜索算法属于邻域搜索算法，具有自适应的存储记忆功能。算法从一个初始可行解开始，搜索过程中通过禁忌表避免迂回搜索，同时可通过藐视准则特赦被禁忌的最优解，从而实现对?
?Pc，算法基本流程如下：BEGINParameter:Popsizeo,MaxGen,PcSet:InitPop;gen=1Compute:Fitness(gen)WHILEgen≤MaxGen;Pair:Group=Popsizeo/2Crossover:twopointMutate:tubasearchCompute:Fitness(newgen)Merge:gen=gen+newgen;Popsize=2×PopsizeoUpdate:gen=gen+1Select:Popsize=PopsizeoENDWHILEEND4算例分析结合本文模型及所提算法对所举算例进行分析。假设其工作允许抢占，但是限制其最大抢占次数为1时，其他条件不做变化，得到相应调度方案2，项目单位时间资源使用量如图3所示。调度方案2总持续天数为15，项目实现资源最大利用时间为12。相比方案1其前期资源得到了连续高效使用，实现了利用率最大化，但1_PRCPSP的项目完成时间没有得到缩减。针对此案例采用多次抢占策略做进一步优化，得到相应调度方案3，项目单位时间资源使用量如图4所示。调度方案3总持续天数为14，项目实现资源最大利用时间为11。方案3在实现资源使用的稳定性优化的同时，缩短了项目的总体完成时间。为进一步检证文中所提抢占模型及其算法可行性，采用Kolisch构建的标准算例库PSPLIB中单模式RCP-SP算例进行算法性能测试。算例中的每个工作最多有3个紧后任务，共涉及调度4种可更新资源，并限制每种资源的可用上限。算例库中算例有4种规模，以其工作数量划分分别为J30、J60、J90、J120，其中算例库已公布J30算例在非抢占情况下的精确算法最优解。本文采用J30算例作为算法的实验数据对算法进行可行性验证。遗传算法求解受算法参数影响，为保证算法求解效果，拟对交叉概率Pc和变异概率Pm进行参数调试。首先对J30中部分算例进行实验，确定算法参数。统计J30中各算例的持续时间，依据分层抽样原则，将
【参考文献】：
期刊论文
[1]求解任务可拆分多项目协同调度问题的启发式算法[J]. 王磊,聂兰顺,战德臣,王弼陡,罗刚银. 控制与决策. 2017(06)
[2]基于项目网络拆分决策的多项目协同调度问题建模[J]. 陆志强,杨超. 上海交通大学学报. 2017(02)
[3]任务可拆分的多模式多项目调度模型与算法[J]. 王伟鑫,王旭,葛显龙. 计算机集成制造系统. 2014(06)
[4]抢占式资源受限项目调度问题的遗传算法[J]. 寿涌毅,彭晓峰,李菲,赖昌涛. 浙江大学学报(工学版). 2014(08)
本文编号：3460582
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3460582.html
