A Robust Genetic Algorithm for Resource Allocation in Project Scheduling

Genetic algorithms have been applied to many different optimization problems and they are one of the most promising metaheuristics. However, there are few published studies concerning the design of efficient genetic algorithms for resource allocation in project scheduling. In this work we present a robust genetic algorithm for the single-mode resource constrained project scheduling problem. We propose a new representation for the solutions, based on the standard activity list representation and develop new crossover techniques with good performance in a wide sample of projects. Through an extensive computational experiment, using standard sets of project instances, we evaluate our genetic algorithm and demonstrate that our approach outperforms the best algorithms appearing in the literature.     

广义优先关系约束下Max-npv项目调度问题及其遗传算法

以往Max-npv项目调度问题的研究都假定活动之间的关系为单一结束-开始类型,现实中活动之间关系复杂多变,因此,将广义优先关系引入Max-npv项目调度问题中,构建了广义优先关系约束下的Max-npv项目调度模型。针对该优化模型设计了一种双层遗传算法,外层遗传算法负责任务执行模式的优化,内层遗传算法负责任务调度的优化。在内层遗传算法中,采用任务开始时间之差作为新的编码方式,大大简化了交叉变异算子,针对网络图中的环状结构设计了修复算子,确保了编码的有效性。通过一个算例对算法进行了测试,实验结果验证了算法的有效性。     

项目鲁棒调度的资源分配启发式算法研究

合理的资源配置是提高项目调度鲁棒性一种有效的方法。本文针对项目鲁棒调度问题,提出了Max-PRUA资源分配启发式算法,以期通过生成鲁棒性高的资源分配方案来提高调度计划的鲁棒性。本算法设计了最大化利用优先关系和不可避免弧传递资源的资源分配两项策略来传递最大资源量,以减少由额外约束传递的资源量,降低对项目调度鲁棒性的影响。为寻优最优资源分配方案,配合局部搜索算法,本算法构建了动态活动组GRA,通过对组内活动顺序重排以生成多种资源分配方案,以利于从解空间中寻优出最佳的鲁棒性方案。最后通过大量的仿真实验验证和与其它算法进行比较,结果表明本算法对于不同规模和不同因素影响的项目均有较好的适应性,生成的资源分配方案对调度计划鲁棒性影响较小,是一种有效的算法。     

供应链环境下跨组织的PCPSP问题研究

在供应链环境下研究跨组织的资源受限项目调度问题,从项目调度整体效用最大化角度,考虑工期、成本和资源均衡对项目调度的影响。构建并剖析供应链环境下跨组织的资源受限项目调度模型,利用正态云模型中云滴的随机性与稳定性的特征改进遗传算法中交叉算子与变异算子的设置方式,并对模型进行数据模拟和算例分析。结果表明,以工期-成本-资源均衡为优化目标,不仅可实现供应链环境下跨组织的资源受限项目调度的效用最大化,且可缩短项目工期、降低成本并提高资源的利用率。     

可抢占条件下的项目调度研究综述

可抢占条件下的项目调度通过暂时中断某些活动的执行,释放资源给更重要的活动,从而优化项目的工期、成本等绩效指标。可抢占项目调度问题以其重要的理论价值和应用背景,受到了学界和业界的广泛关注。对国内外可抢占项目调度的研究成果进行了系统性总结与梳理,综述了可抢占项目调度问题的数学模型及其求解算法,总结了可抢占项目调度问题的一些扩展问题和应用情况,最后指出了未来进一步的研究方向。     

A Hybrid Genetic Algorithm for the Single Machine Scheduling Problem

A hybrid genetic algorithm (HGA) is proposed for the single machine, single stage, scheduling problem in a sequence dependent setup time environment within a fixed planning horizon (SSSDP). It incorporates the elitist ranking method, genetic operators, and a hill-climbing technique in each searching area. To improve the performance and efficiency, hill climbing is performed by uniting the Wagner-Whitin Algorithm with the problem-specific knowledge. The objective of the HGA is to minimize the sum of setup cost, inventory cost, and backlog cost. The HGA is able to obtain a superior solution, if it is not optimal, in a reasonable time. The computational results of this algorithm on real life SSSDP problems are promising. In our test cases, the HGA performed up to 50% better than the Just-In-Time heuristics and 30% better than the complete batching heuristics.     

遗传算法对车间作业调度的研究

应用遗传算法对车间作业调度问题进行研究,针对ＪＳＳＰ的具体特性,文中提出变异函数和二次编码的思想,获得较好的仿真结果。     

求解资源约束项目调度问题的启发式算法综述

本文综述了求解RCPSP的启发式算法.首先在对各种优先权规则进行归纳的基础上,概述基于优先权规则的RCPSP启发式算法研究现状;其次,综述项目进度的表述方式及常用超启发式策略,汇总求解RCPSP的超启发式算法的研究成果.此外,简要介绍除上述两大类启发式算法之外的其他几种启发式算法;最后,对全文进行总结,并指出该领域几个有希望的研究方向.     

基于遗传算法的物流配送车辆调度问题研究

研究使用遗传算法求解物流配送组织过程中车辆调度问题 .通过把时间窗约束和车辆容量约束转嫁到最小费用目标函数中去 ,建立适合于遗传算法的车辆调度模型 .阐述放回式随机复制算子和适应度函数 ,设计描述行驶线路的染色体结构、初始群体生成方法、独特的交叉算子和交换变异算子 ,构造完整的遗传算法 .并给出算例 ,验证调度模型和遗传算法 .     

A Constraint-Based Method for Project Scheduling with Time Windows

This paper presents a heuristic algorithm for solving RCPSP/max, the resource constrained project scheduling problem with generalized precedence relations. The algorithm relies, at its core, on a constraint satisfaction problem solving (CSP) search procedure, which generates a consistent set of activity start times by incrementally removing resource conflicts from an otherwise temporally feasible solution. Key to the effectiveness of the CSP search procedure is its heuristic strategy for conflict selection. A conflict sampling method biased toward selection of minimal conflict sets that involve activities with higher-capacity requests is introduced, and coupled with a non-deterministic choice heuristic to guide the base conflict resolution process. This CSP search is then embedded within a larger iterative-sampling search framework to broaden search space coverage and promote solution optimization. The efficacy of the overall heuristic algorithm is demonstrated empirically on a large set of previously studied RCPSP/max benchmark problems.     

A Tabu Search Approach for the Resource Constrained Project Scheduling Problem

An appropriate tabu search implementation is designed to solve the resource constrained project scheduling problem. This approach uses well defined move strategies and a structured neighbourhood, defines appropriate tabu status and tenure and takes account of objective function approximation to speed up the search process. A sound understanding of the problem has helped in many ways in designing and enhancing the tabu search methodology. The method uses diversification, intensification and handles infeasibility via strategic oscillation.The above methodology is tested on existing problems from the literature and also on parametrically generated problems with encouraging results. For comparison of results, optimal solutions are used in the former and lower bounds obtained by Lagrangian heuristics are used in the latter.     

多品种柔性生产企业的订单调度模型及其遗传算法

以订单总完工时间最小和订单平均流程时间最小为目标函数,利用改进的多目标遗传算法生成了多品种订单调度模型.为解决组合模型的指数爆炸问题,提出了一种按规则分配订单以及订单中各作业排序相结合的集成调度思想;以一种整数和字母组合的编码方法用于可行解的表达,并在每个分目标的进化过程中,对选择、交叉、变异算子以及精英解保留策略重新进行设计,保证了解的分布性和均匀性;同时还提出了一种新的终止条件,将精英种群与分目标的子种群进行合并,从而加快收敛的速度.以典型的订单生产企业为例进行仿真实验,实验结果表明,应用该算法可以获得满意的Pareto解集.     

Local Search for Vehicle Routing and Scheduling Problems: Review and Conceptual Integration

Local search and local search-based metaheuristics are currently the only available methods for obtaining good solutions to large vehicle routing and scheduling problems. In this paper we provide a review of both classical and modern local search neighborhoods for this class of problems. The intention of this paper is not only to give an overview but to classify and analyze the structure of different neighborhoods. The analysis is based on a formal representation of VRSP solutions given by a unifying giant-tour model. We describe neighborhoods implicitly by a set of transformations called moves and show how moves can be decomposed further into partial moves. The search method has to compose these partial moves into a complete move in an efficient way. The goal is to find a local best neighbor and to reach a local optimum as quickly as possible. This can be achieved by search methods, which do not scan all neighbor solutions explicitly. Our analysis shows how the properties of the partial moves and the constraints of the VRSP influences the choice of an appropriate search technique.     

A Genetic Approach for Solving a Scheduling Problem in a Robotized Analytical System

We consider a robotized analytical system in which a chemical treatment has to be performed on a given set of identical samples. The objective is to carry out the chemical treatment on the whole set of samples in the shortest possible time. All constraints have to be satisfied since a modification of the chemical process could create unexpected reactions.We have developed a new robust method governed by a genetic algorithm to solve this scheduling problem. The crossover mechanism of this evolutionary method is based on an extension of the uniform crossover introduced by Syswerda (1989).The proposed approach can be adapted to other combinatorial problems where decisions, based on rules, have to be taken at each step of a constructive method.     

改进的混合算法求解车间作业调度问题

车间作业调度问题是个典型的NP-hard问题,为了更有效的解决车间作业调度问题,提出了一种改进的混合算法(IGASA).算法设计了一种基于当前最优解的免疫算子,算子对当前最优个体中选取运行时间最少的一台机器上的工件顺序当作疫苗,并用车间调度问题的图论模型解释了此算子的合理性.最后通过大量实验证明改进的混合算法的性能的优越性,从而证明设计的免疫算子是有意义的.     

基于遗传算法的项目经理评价

本文根据自然进化规则，把项目经理视为评价系统，项目经理所要满足的要求视为系统环境，用遗传算法的方法评价项目经理，力求提出一种比较客观科学的、且可以定量分析的项目经理的评价方法。     

Heuristic Techniques for Single Line Train Scheduling

Optimising a train schedule on a single line track is known to be NP-Hard with respect to the number of conflicts in the schedule. This makes it difficult to determine optimum solutions to real life problems in reasonable time and raises the need for good heuristic techniques. The heuristics applied and compared in this paper are a local search heuristic with an improved neighbourhood structure, genetic algorithms, tabu search and two hybrid algorithms. When no time constraints are enforced on solution time, the genetic and hybrid algorithms were within five percent of the optimal solution for at least ninety percent of the test problems.     

活动执行时间可提前的多模式反应性项目调度优化

研究不确定活动工期下活动执行时间可提前的多模式反应性项目调度问题。首先对反应性研究现状进行综述;其次建立以最小化反应性总成本为目标的优化模型;随后基于问题特点设计禁忌搜索算法;最后通过具体案例分析关键参数对反应性成本的影响,并得出结论:执行时间提前得到的反应性成本及完工时间明显低于执行时间不可提前的结果;随着项目推进,总成本及影响的活动数量总体上呈减小趋势,但项目完工时间在某些时刻维持不变;对于工期增加较大的活动,将其本身或紧前活动提前启动,或将其转换至活动工期较短的模式可降低反应性成本。研究可为不确定环境下反应性计划制定提供决策支持。     

一种基于局部搜索算子的遗传算法

为了提高遗传算法的收敛速度及局部搜索能力,设计了一种基于优良模式的局部搜索算子.同时对传统免疫算法中基于浓度的选择算子进行了改进,设计了一种基于适应度值和浓度的混合选择算子,从而有效的阻止了算法出现"早熟"现象.进一步给出了算法的步骤,并利用有限马尔可夫链证明了该算法的收敛性,最后通过对四个经典测试算法性能的函数的数字仿真,说明该算法对多峰值函数优化问题明显优于基本遗传算法.     

动态空间调度的混合遗传算法

提出了一种基于混合遗传算法的动态空间调度方法。首先利用遗传算法产生多个可行的分段调度序列,再采用动态决定分段位置的启发式算法——平均最大空闲矩形策略对遗传算法产生的调度序列进行解码。同时以完工时间和平台利用率的加权和作为适应度函数,充分考虑了空间调度问题所特有的动态性和时空关联性。遗传进化过程收敛后得到近似最优解,实现了调度方案的全局优化。对船厂实际生产数据进行了实证分析以及与其它算法的对比分析,证明了所提方法在空间调度问题上的有效性和实用性。