基于部件指派的多状态系统可靠度优化研究

针对一般二态系统假设的不足,提出了多状态系统条件下的可靠度优化指派问题。该问题以系统可靠度最大化为优化目标,在考虑部件分配成本和总分派成本预算的前提下,对多状态系统下不同状态对应的性能水平的进行了分析,给出了基于通用生成函数的多状态系统的可靠度评估方法。根据指派问题的组合优化的特性和多状态系统可靠性评估的特点,对传统遗传算法的适应度函数进行了改进,设计了基于整数编码的遗传算法,该算法具有离散变量的设计灵活性和强大的搜索性能。算例实验表明,本文设计的优化算法具有较好的求解质量,同时算法的运行时间也得到了大幅的缩短。本研究为多状态系统的可靠度优化提供了一条可借鉴的思路。     

供给总量限定需求区间约束型运输问题——时限费用优化模型与算法

本文目的是为建立与运输问题有关的决策支持系统提供方便.本文建立了供给总量限定需求区间约束型运输问题的对时限与费用两个目标进行优化的多目标规划模型,给出了求解模型的算法,并举例说明了算法的应用.该算法能求得问题的最优解,并具有易于编程实现、收敛性好等优点.数值实验表明该算法有较高的计算效率,可用于求解某些类型的指派问题.     

多因素指派模型全局优化问题研究

基于多因素资源优化分配问题的不确定性,建立基于区间数型下的不确定多因素指派模型,给出模型建立的理论依据与全局优化算法,拓展区间数型多因素指派模型,解决了不确定条件下多因素资源优化分配问题.考虑多因素影响,基于任务完成效率,以5类任务多因素分配问题为例,获得了指派模型全局优化的解.为不确定条件下资源优化分配问题的研究拓宽了决策途径.     

飞机维修短期计划模型及其算法研究

目前对于飞机维修计划的研究,大都通过精确算法一次性完成周期内所有飞机的排班优化。本文在分析传统数学规划模型的基础上,以最大化利用两次维修之间的可用飞行时间为目标,构造了飞机维修计划优化模型。然后提出了求解此模型的启发式两阶段分解算法,第一阶段优先完成需维修飞机的任务指派,第二阶段再完成余下飞机的任务指派。利用航空公司真实数据进行的数值试验表明,两阶段分解算法能够显著提高模型的求解效率和质量,可以有效求解大规模飞机维修计划制定问题。     

基于主子阵算法的n-2n型指派计算工具的实现

主要在研究周良泽的指派求解理论和主子阵算法基础上,设计一种n-2n指派问题求解的实现方案,最后用Java语言实现一个可视化的通用计算工具,并调试运行.结果证明,该实现方案效率高,结果易于理解.     

广义指派问题及其在军事装备运输中的推广应用

军事装备中的运输问题复杂多样,如何建立数学模型是寻求优化方案的关键.本文首先将最优线性指派模型推广到广义指派模型并给出其两种算法,其次对带有时间约束的运输问题进行建模,并设法将其转化为广义指派问题来处理,从而为这类运输问题提供了一种有效可行的算法.     

LC1约束规划问题的超线性收敛ODE型信赖域算法

本文对带线性等式约束的LC^1优化问题提出了一个新的ODE型信赖域算法，它在每一次迭代时，不必求解带信赖域界的子问题，仅解一线性方程组而求得试验步。从而可以降低计算的复杂性，提高计算效率，在一定的条件下，文中还证明了该算法是超线性收敛的。     

求解指派问题的一个算法

为了便于建立与指派问题有关的决策支持系统，本给出了一个求解指派问题的数值算法，证明了算法的理论依据。该算法能求得问题的最优解，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

项目多技能人力资源指派与调度混合算法

研究多技能人力资源在项目活动上的指派与调度问题.首先,从问题特点出发,把原始问题分解为指派问题子模型和调度问题子模型.然后,对项目活动间的重叠关系进行识别,将其转化为对指派问题的有效约束,构建数学规划与约束规划相结合的混合算法对问题求解,并采用CPLEX编程实现.研究表明,算法可有效缩减指派问题的可行域,快速地找到问题的近优解,从而提高多技能人力资源的使用效率,是求解项目多技能人力资源指派与调度问题的一个有效方法.     

分配小于人数和任务数的指派问题的反点算法

摘要：本文对从 个人中派出 个人去完成 项任务中的 项任务使总效率最高这类指派问题给出了新算法,通过对这类指派问题引入了反点的概念,讨论了反点所具有的一些性质并证明了相关结论,利用这些结论找到了通过增加反点来解决此类指派问题的反点算法。     

A cross entropy approach to design of reliable networks

One of the most important parameters determining the performance of communication networks is network reliability. The network reliability strongly depends on not only topological layout of the communication networks but also reliability and availability of the communication facilities. The selection of optimal network topology is an NP-hard problem so that computation time of enumeration-based methods grows exponentially with network size. This paper presents a new solution approach based on cross-entropy method, called NCE, to design of communication networks. The design problem is to find a network topology with minimum cost such that all-terminal reliability is not less than a given level of reliability. To investigate the effectiveness of the proposed NCE, comparisons with other heuristic approaches given in the literature for the design problem are carried out in a three-stage experimental study. Computational results show that NCE is an effective heuristic approach to design of reliable networks.     

Multi-Path Approach for Reliability-Redundancy Allocation Using a Scaling Method

The reliability-redundancy allocation problem is an optimization problem that achieves better system reliability by determining levels of component redundancies and reliabilities simultaneously. The problem is classified with the hardest problems in the reliability optimization field because the decision variables are mixed-integer and the system reliability function is nonlinear, non-separable, and non-convex. Thus, iterative heuristics are highly recommended for solving the problem due to their reasonable solution quality and relatively short computation time. At present, most iterative heuristics use sensitivity factors to select an appropriate variable which significantly improves the system reliability. The sensitivity factor represents the impact amount of each variable to the system reliability at a designated iteration. However, these heuristics are inefficient in terms of solution quality and computation time because the sensitivity factor calculations are performed only at integer variables. It results in degradation of the exploration and growth in the number of subsequent continuous nonlinear programming (NLP) subproblems. To overcome the drawbacks of existing iterative heuristics, we propose a new scaling method based on the multi-path iterative heuristics introduced by Ha (2004). The scaling method is able to compute sensitivity factors for all decision variables and results in a decreased number of NLP subproblems. In addition, the approximation heuristic for NLP subproblems helps to avoid redundant computation of NLP subproblems caused by outlined solution candidates. Numerical experimental results show that the proposed heuristic is superior to the best existing heuristic in terms of solution quality and computation time.     

A self-tuning heuristic for the design of communication networks

This paper addresses the design of communication networks that has a large application area. The problem is to design a minimum cost network subject to a given reliability level. Complexity of the problem is twofold: (1) finding a minimum-cost network topology that every pair of nodes can communicate with each other and (2) computing overall reliability to provide the reliability constraint. Over the last two decades, metaheuristic algorithms have been widely applied to solve this problem due to its NP-hardness. In this study, a self-tuning heuristic (STH), which is a new approach free from parameter tuning, is applied to the design of communication networks. Extensive computational results confirm that STH generates superior solutions to the problem in comparison to some well-known local search metaheuristics, and also more sophisticated metaheuristics proposed in the literature. The practical advantage of STH lies in both its effectiveness and simplicity in application to the design problem.     

Reducing mean flow time in permutation flow shop

This paper deals with the traditional permutation flow shop scheduling problem with the objective of minimizing mean flowtime, therefore reducing in-process inventory. A new heuristic method is proposed for the scheduling problem solution. The proposed heuristic is compared with the best one considered in the literature. Experimental results show that the new heuristic provides better solutions regarding both the solution quality and computational effort.     

A high quality solution constructive heuristic for flow shop sequencing

This paper addresses the flow shop sequencing problem. Following an investigation of the problem characteristics, a property of this scheduling problem is presented, and is used for the development of a new constructive heuristic with the objective of minimizing the total time to complete the schedule (makespan). The new method, denoted by N&M, is compared with the best constructive heuristic reported in the literature, named NEH. Results from computational experience have shown that for problems having up to 10 machines and 100 jobs, the new heuristic outperforms, on average, the NEH heuristic. There is no significant difference regarding computation effort for both NEH and N&M heuristics.     

Effective algorithm and heuristic for the generalized assignment problem

We present new Branch-and-Bound algorithm for the generalized assignment problem. A standard subgradient method (SM), used at each node of the decision tree to solve the Lagrangian dual, provides an upper bound. Our key contribution in this paper is a new heuristic, applied at each iteration of the SM, which tries to exploit the solution of the relaxed problem, by solving a smaller generalized assignment problem. The feasible solution found is then subjected to a solution improvement heuristic. We consider processing the root node as a Lagrangian heuristic. Computational comparisons are made with new existing methods.     

Scheduling multi-stage parallel-processor services to minimize average response time

The problem of scheduling on a multi-stage parallel-processor architecture in computer centres is addressed with the objective of minimizing average completion time of a set of requests. The problem is modelled as a flexible flowshop problem for which few heuristics exist in the flowshop scheduling literature. A new three-phase heuristic is proposed in this paper. An extensive computational experiment has been conducted to compare the performance of the existing heuristics and the proposed heuristic. The results indicate that the proposed heuristic significantly outperforms the existing ones. More specifically, the overall average error of the best existing heuristic is about five times that of the proposed heuristic while the overall average CPU time of the proposed heuristic is about half of the best existing one. More importantly, as the number of requests increases, the CPU time of the proposed heuristic decreases considerably (compared to the best existing heuristic) while the ratio of the error (of the best existing to the proposed heuristic) of about five times remains almost the same.     

Another heuristic for minimizing total average cycle stock subject to practical constraints

This paper considers the setting of reorder intervals of a population of items for minimizing the total average cycle stock subject to a limit on the total number of replenishments per unit time, and a restricted set of possible intervals. Silver and Moon have investigated the problem with the use of dynamic programming, and they also proposed a heuristic for solving it. This paper presents a new 0-1 linear programming approach to the problem. Based upon the solution of the relaxed 0-1 linear programming formulation, a simple heuristic is proposed to solve the reorder problem. Limited numerical results using realistic test examples indicate that the new heuristic performed very well for each example.     

A fuzzy greedy heuristic for permutation flow-shop scheduling

This paper describes a polynomial-time heuristic for the permutation flow-shop scheduling problem with the makespan criterion. The proposed method consists of two phases: arranging the jobs in priority order and then constructing a sequence. A fuzzy greedy evaluation function is employed to prioritize the jobs for incorporating into the construction phase of the heuristic. Computational experiments using standard benchmark problems indicate an improvement of the new heuristic over the well-known Nawaz, Enscore and Ham (NEH) heuristic. It will be seen that the NEH heuristic is a special case of our more general heuristic.     

Enhanced migrating birds optimization algorithm for the permutation flow shop problem with sequence dependent setup times

This paper presents an enhanced migrating bird optimization (MBO) algorithm and a new heuristic for solving a scheduling problem. The proposed approaches are applied to a permutation flowshop with sequence dependent setup times and the objective of minimizing the makespan. In order to augment the MBOs intensification capacity, an original problem specific heuristic is introduced. An adapted neighborhood, a tabu list, a restart mechanism and an original process for selecting a new leader also improved the MBO’s behavior. Using benchmarks from the literature, the resulting enhanced MBO (EMBO) gives state-of-the-art results when compared with other algorithms reference. A statistical analysis of the numerical experiments confirms the relative efficiency and effectiveness of both EMBO and the new heuristic.