基于时序片段评价的数据分配算法

数据分配是研究数据如何分布到多个物理节点的NP-Complete问题.给出数据分配算法的数学模型,提出基于时序片段评价的数据分配算法--DATE.该算法利用数据在短时域访问量分布不均的特点,将多目标优化问题转化为单一目标求解,采用蜜蜂算法(collective Honey bee behavior)调整参数并反馈算法结果,以实现系统负载均衡.随机实验结果表明,DATE相比于同类Random,round-robin,Bubba算法在系统总时段均衡ET、系统时段内均衡值ES、系统最大波峰值EM 3个指标中表现更优.     

加工时间可控的炼钢调度问题两阶段模型及优化算法

炼钢-精炼-连铸是钢铁产品的关键生产工序,其有效的调度对生产过程中减少热能消耗、提高生产效率具有重要意义.根据生产过程中工序加工时间可控性和主要工艺约束提出了分散搜索(scattcr scarch,SS)算法和数学规划相结合的两阶段求解算法.第1阶段应用SS算法基于各阶段正常的加工时间,确定炼钢-精炼生产阶段各设备的加工炉次集和各炉次的加工顺序.第2阶段将SS求得的解转化为时间约束网络图,建立了以炉次等待设备时间和设备等待炉次时间及最大完成时间最小为调度目标,工序加工时间可控的混合整数规划模型,应用CPLEX求解模型确定各炉次的加工时间和开始时间.基于国内某钢铁企业炼钢-精炼-连铸生产过程的实绩生成了14个不同规模的测试案例,对钢厂生产实绩效果与本文两阶段求解算法的优化效果进行了对比,分析了不同等待时间权重对两阶段算法性能的影响,并与采用遗传局域搜索(gcnctic local search,GLS)算法与数学规划相结合的求解算法的优化效果进行了比较.实验结果表明本文给出的模型和两阶段求解算法对加工时间可控的炼钢-精炼-连铸调度问题的优化效果很好.     

基于关键路径疫苗的免疫遗传算法求解JSP问题

车间作业调度是决定工件加工顺序以及分配相应设备的过程,合理的调度方案能提高设备利用率.针对单件车间调度问题,采用免疫遗传算法进行调度方案求解.基于关键路径的思想,提出一种新的疫苗提取和接种方法.疫苗提取时,取种群中最优个体的关键路径信息作为疫苗,接种时,依据该疫苗信息修改待接种个体各机器上的工件安排顺序,从而继承最优个体关键路径上的信息,提高个体适应度,加速算法寻优过程.通过对标准测试案例的求解,以及与其他算法的比较,结果表明关键路径疫苗技术是有效的.     

求解柔性流水车间调度问题的高效分布估算算法

针对最小化最大完工时间的柔性流水车间调度,利用事件建模思想,线性化0-1混合整数规划模型,使得小规模调度问题通过Cplex可以准确求解,同时设计了高效分布估算算法来求解大规模调度问题.该算法采用的是一种新颖的随机规则解码方式,工件排序按选定的规则安排而机器按概率随机分配.针对分布估算算法中的概率模型不能随种群中个体各位置上工件的更新而自动调整的缺点,提出了自适应调整概率模型,该概率模型能提高分布估算算法的收敛质量和速度.同时为提高算法局部搜索能力和防止算法陷入局部最优,设计了局部搜索和重启机制.最后,采用实验设计方法校验了高效分布估算算法参数的最佳组合.算例和实例测试结果都表明本文提出的高效分布估算算法在求解质量和稳定性上均优于遗传算法、引力搜索算法和经典分布估算算法.     

模糊环境下的差异作业单机批调度优化问题的研究*

针对现实生产制造系统中存在的时间参数模糊化问题,本文用梯形模糊数表征时间参数,给出了一种具有模糊加工时间和模糊批次间隔的、以最小化制造跨度为目标的模糊差异作业单机批调度问题模型。在对模糊差异作业单机批调度问题进行有效求解方面,针对基本粒子群算法容易陷入局部最优的问题,本文给出了一种基于遗传操作的混合粒子群算法,利用遗传算法思想对粒子进行交叉、变异操作,增强了算法跳出局部最优的能力。仿真实验验证了该算法具有可行性和有效性。     

随机性参数分布式量化估计及其最优比特分配

本文研究总比特率给定下随机向量参数分布式量化估计及其最优比特分配问题.与现有文献大都假定每个传感器的量化比特率给定而不是最优分配下研究随机性参数的分布式量化估计问题不同的是,本文将综合考虑最优量化器、最优估计器算法以及给定总比特率下的最优比特分配问题.针对向量状态标量观测模型,首先借助现有文献给出基于量化观测的最优估计器及其误差协方差阵形式表达,其次得到各传感器的渐近最优量化器实际为著名的Lloyd-max量化器,且各传感器的渐近最优量化级数与信噪比成正比,同时引入一种次优的求解非负整数比特率的方法.考虑到当传感器数目比较大时,初始的最优估计器算法运算量很大,设计了一种渐近等价的迭代量化估计器算法,其计算负担大大减轻,且对于存在延迟或丢包的网络环境亦适用,增强了算法的鲁棒性.仿真结果表明,本文提出的最优比特分配方案估计性能明显优于一般的均匀比特分配方案.     

一种新的混合生产调度问题的优化求解

研究了一种新的生产调度问题的优化问题,针对这种新的调度模式,设计了一种两层遗传算法进行优化求解。算法采用了上下两层共同进化,上层遗传算法优化产品生产过程中每类产品对应每台设备所生产的物料类型的分配,下层遗传退火算法优化了所有产品子批量的一个排序。在算法的求解过程中,引入了针对该问题的一个新的批量加工时间计算方法来求得最大完成时间指标的值。最后通过系统仿真论证了算法以及批量完工时间计算的有效性。     

改进并行粒子群算法用于冷却水系统节能优化

针对冷却水系统优化问题提出一种改进并行粒子群(IPPSO)算法,以系统能耗最小为优化目标,以系统中各设备的运行参数为优化变量进行求解.在该算法中,采用随机和混沌序列机制分别对两个种群的粒子进行初始化,使两种群在产生初期便具有不同特征;并根据两种群特点,采用不同惯性权重改进策略,提高算法搜索能力;同时利用一种新迁移算子对...     

一种基于P学习的分布式并行多任务分配算法

并行多任务分配是多agent系统中极具挑战性的课题, 主要面向资源分配、灾害应急管理等应用需求, 研究如何把一组待求解任务分配给相应的agent联盟去执行. 本文提出了一种基于自组织、自学习agent的分布式并行多任务分配算法, 该算法引入P学习设计了单agent寻找任务的学习模型, 并给出了agent之间通信和协商策略. 对比实验说明该算法不仅能快速寻找到每个任务的求解联盟, 而且能明确给出联盟中各agent成员的实际资源承担量, 从而可以为实际的控制和决策任务提供有价值的参考依据.     

考虑多成本约束的柔性作业车间制造资源动态分配模型

针对柔性作业车间多周期生产的设备和人力资源的协同分配问题,从成本的视角对其进行研究.综合考虑设备加工成本、人力成本、工件运输成本、库存成本、拖期成本以及外协成本等成本目标,构建考虑多成本约束的柔性作业车间制造资源动态分配模型,设计基于遗传算法的模型求解方法;最后以一个10台设备、10位工人、5个产品、3周期阶段的生产需求构造算例,给出各阶段制造资源优化分配方案和成本结果,验证了模型与算法的有效性.     

Decentralized capacity allocation of a single-facility with fuzzy demand

Capacity allocation under uncertainty environment is an important decision problem in manufacturing. The decentralized capacity allocation of a single-facility among different organizations with fuzzy demand is investigated in this paper. The objective and demand of each organization are assumed to be private information that other organizations and the facility cannot access to. In addition, we assume organizations have limited view of the capacity and loading of the facility. First, fuzzy optimization models associated with each organization and the facility are set up. Then, based on fuzzy theory, the fuzzy optimization models are converted into parametric programming models and subsequently an interactive algorithm is proposed to solve those parametric programming models. The extra benefit of this algorithm is that the whole solving process is amenable to decentralized implementation. Finally, experimental results illustrate the effectiveness of this work under two levels of information sharing: capacity information of the facility unknown to organizations and capacity information of the facility partially known to organizations.     

不确定条件下配送回收中心选址配送问题研究

针对制造商、零售商、一个废弃处理中心和多个配送回收中心构成的闭环供应链,解决模糊随机环境下的配送回收中心选址配送问题。引用模糊随机理论处理产品回收率和可再利用率随机变量,以成本最低和碳排放最小为双重目标,以设施能力,设施间流量以及设施数量为约束,建立多目标闭环供应链配送回收中心选址配送模型。改进了全局-局部-邻域粒子群算法,设计了基于优先级的全局-局部-邻域粒子群算法方案,并用案例验证了模型及算法的有效性和先进性。     

MEC联合资源分配与计算卸载的效益

针对资源受限的移动边缘计算(MEC)卸载问题,提出一种基于遗传算法优化的卸载决策与计算资源分配方法(GAO).建立联合时延、能耗以及卸载费用的系统卸载效益模型,提出最小资源分配阈值;引入改进的遗传算法求解效益最大化问题,针对该问题提出一种两段式的染色体结构和遗传算子.进行仿真实验,对比分析随机卸载决策与平均计算资源分配...     

Combination of genetic network programming and knapsack problem to support record clustering on distributed databases

This research involves implementation of genetic network programming (GNP) and standard dynamic programming to solve the knapsack problem (KP) as a decision support system for record clustering in distributed databases. Fragment allocation with storage capacity limitation problem is a background of the proposed method. The problem of storage capacity is to distribute sets of fragments into several sites (clusters). Total amount of fragments in each site must not exceed the capacity of site, while the distribution process must keep the relation (similarity) between fragments within each site. The objective is to distribute big data to certain sites with the limited amount of capacities by considering the similarity of distributed data in each site. To solve this problem, GNP is used to extract rules from big data by considering characteristics (value ranges) of each attribute in a dataset. The proposed method also provides partial random rule extraction method in GNP to discover frequent patterns in a database for improving the clustering algorithm, especially for large data problems. The concept of KP is applied to the storage capacity problem and standard dynamic programming is used to distribute rules to each site by considering similarity (value) and data amount (weight) related to each rule to match the site capacities. From the simulation results, it is clarified that the proposed method shows some advantages over the conventional clustering algorithms, therefore, the proposed method provides a new clustering method with an additional storage capacity problem.     

A global shooting algorithm for the facility location and capacity acquisition problem on a line with dense demand

This paper describes the development of an exact allocation-based solution algorithm for the facility location and capacity acquisition problem (LCAP) on a line with dense demand data. Initially, the n-facility problem on a line is studied and formulated as a dynamic programming model in the allocation decision space. Next, we cast this dynamic programming formulation as a two-point boundary value problem and provide conditions for the existence and uniqueness of solutions. We derive sufficient conditions for non-empty service regions and necessary conditions for interior facility locations. We develop an efficient exact shooting algorithm to solve the problem as an initial value problem and illustrate on an example. A computational study is conducted to study the effect of demand density and other problem parameters on the solutions.     

Solution method for the location planning problem of logistics park with variable capacity

In this paper we study a logistics park location planning problem in which the capacity of the logistics park is determined by the sectors used to establish it in an open site. Since the size of each sector is not necessarily the same in every potential site, the capacity of the logistics park is thus variable, which makes this problem different from the traditional location problems in which the capacity of each facility is fixed. The task of this problem is to determine the location of the logistics parks, the sectors to be used to establish the logistics park in each open site, and the allocation of customers to the established logistics parks so as to minimize the total costs for establishing the logistics parks and supplying the demands of customers. The size mode is introduced to deal with the nonlinear establishment cost function and consequently this problem is formulated as an integer linear programming (ILP) model. Since CPLEX can only solve the ILP model with small-size problems, a tabu search (TS) hybrid with filter and fan (F&F) is presented to obtain near optimal solutions. In the hybrid algorithm, the TS is used to improve the solution by changing the allocation of customers to open sites while the F&F is used to further improve the solution by adjusting the status of sites (i.e., open or closed). In addition, an elite solution pool is constructed to store good solutions found in the searching history. Whenever the hybrid algorithm is trapped in local minima, a new start solution will be generated from the elite pool so as to improve the search diversity. To evaluate the performance of the proposed hybrid TS method, the column generation (CG) method with an acceleration strategy is developed to provide tight lower bounds. Computational results showed that the proposed hybrid algorithm can obtain optimal solutions for most of the small size problems and satisfactory near-optimal solutions with comparison to lower bounds for large size problems.     

A multi-objective facility location model with batch arrivals: two parameter-tuned meta-heuristic algorithms

Many research works in mathematical modeling of the facility location problem have been carried out in discrete and continuous optimization area to obtain the optimum number of required facilities along with the relevant allocation processes. This paper proposes a new multi-objective facility-location problem within the batch arrival queuing framework. Three objective functions are considered: (I) minimizing the weighted sum of the waiting and the traveling times, (II) minimizing the maximum idle time pertinent to each facility, and (III) minimizing the total cost associated with the opened facilities. In this way, the best combination of the facilities is determined in the sense of economical, equilibrium, and enhancing service quality viewpoints. As the model is shown strongly NP-hard, two meta-heuristic algorithms, namely genetic algorithm (GA) and simulated annealing (SA) are proposed to solve the model. Not only new coding is developed in these solution algorithms, but also a random search algorithm is proposed to justify the efficiency of both algorithms. Since the solution-quality of all meta-heuristic algorithms severely depends on their parameters, design of experiments and response surface methodologies have been utilized to calibrate the parameters of both algorithms. Finally, computational results obtained by implementing both algorithms on several problems of different sizes demonstrate the performances of the proposed methodology.     

蚁群算法求解分布式系统任务分配问题

蚁群算法是受自然界蚂蚁觅食过程中,基于信息素的最短路径搜索食物行为的启发提出的一种智能优化算法.研究表明,在求解复杂优化问题方面该算法具有一定的优越性.任务分配问题是一类典型的组合优化问题.应用蚁群算法来解决多处理器分布式系统上的任务分配问题,一个任务只能分配给一个处理器处理,而一个处理器可以处理多个任务,其中每个处理器都有固定成本和能力限制.仿真结果表明,该算法比禁忌搜索和随机方法具有更好的求解能力.     

多层级设施选址-路径规划问题建模及算法

基于有向图对物流网络多层级设施选址-路径规划问题,建立混合整数规划数学模型,提出量子进化算法与遗传算法协同的双智能算法集成求解方案.量子进化算法解决设施选址和设施分配,遗传算法进行路径规划,并提出可达配送区域的搜索策略和路径长度为权重的设施分配优化策略以提高算法效率.实例测试表明,所提出的数学模型和组合智能算法是可行而有效的,可为多层级设施选址-路径规划问题提供理论与方法指导.     

System reliability maximization for a computer network by finding the optimal two-class allocation subject to budget

In the real world, a computer/communication system is usually modeled as a capacitated-flow network since each transmission line (resp. facility) denoted by an edge (resp. node) has multiple capacities. System reliability is thus defined to be a probability that d units of data are transmitted successfully from a source node to a sink node. From the perspective of quality management, system reliability is a critical performance indicator of the computer network. This paper focuses on maximizing system reliability for the computer network by finding the optimal two-class allocation subject to a budget, in which the two-class allocation is to allocate exactly one transmission line (resp. facility) to each edge (resp. node). In addition, allocating transmission lines and facilities to the computer network involves an allocation cost where the cost for allocating a transmission line depends on its length. For solving the addressed problem, a genetic algorithm based method is proposed, in which system reliability is evaluated in terms of minimal paths and state-space decomposition. Several experimental results demonstrate that the proposed algorithm can be executed in a reasonable time and has better computational efficiency than several popular soft computing algorithms.