区域集群下板材订单配置模型及算法研究

针对集群企业板材资源滞留、无法共享、加工旺季材料短缺等问题,依据区域板材特性和区域企业集群地理相关优势,建立以减少需求方板材订单采购费用最小化为目标的板材订单分配模型,采用以粒子群、免疫算法相结合的混合调度算法。计算过程中,将订单分配对应企业编号作为免疫系统的抗体基因,通过比较适应度函数解与订单预算成本的关系,将抗体群区分为支配解与非支配解,提高算法对抗原的免疫能力和最优解的选择概率。最后以板材订单分配实例进行试验仿真,分别采用PSO算法与IA-PSO算法进行试验对比,对平台上6家订单发布企业寻找合适地理位置相近和价格相对低廉的供应商。试验结果表明,IA-PSO算法能够有效地解决区域集群内板材订单的匹配问题,并且在寻找价格更低和位置更合适的供应商上更有优势。     

Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints

This paper considers a single machine scheduling problem with the learning effect and multiple availability constraints that minimizes the total completion time. To solve this problem, a new binary integer programming model is presented, and a branch-and-bound algorithm is also developed for solving the given problem optimally. Since the problem is strongly NP-hard, to find the near-optimal solution for large-sized problems within a reasonable time, two meta-heuristics; namely, genetic algorithm and simulated annealing are developed. Finally, the computational results are provided to compare the result of the binary integer programming, branch-and-bound algorithm, genetic algorithm and simulated annealing. Then, the efficiency of the proposed algorithms is discussed.     

Study on multi-objective optimization of flow allocation in a multi-commodity stochastic-flow network with unreliable nodes

A long distance transportation problem was abstracted to a resource flow allocation problem upon a stochastic-flow network with unreliable nodes. The objectives were the probability that transmission was successful and transportation cost. In order to solve constructed model, a multi-objective genetic algorithm was propounded. Tested by examples, the algorithm well solved the flow allocation problem in a stochastic-flow network.     

An effective ant colony optimization algorithm (ACO) for multi-objective resource allocation problem (MORAP)

The multi-objective resource allocation problem (MORAP) addresses the important issue which seeks to find the expected objectives by allocating the limited amount of resource to various activates. Resources may be manpower, assets, raw material or anything else in limited supply which can be used to accomplish the goals. The goals may be objectives (i.e., minimizing costs, or maximizing efficiency) usually driven by specific future needs. In this paper, in order to obtain a set of Pareto solution efficiently, we proposed a modified version of ant colony optimization (ACO), in this algorithm we try to increase the efficiency of algorithm by increasing the learning of ants. Effectiveness and efficiency of proposed algorithm was validated by comparing the result of ACO with hybrid genetic algorithm (hGA) which was applied to MORAP later.     

QoS and energy consumption aware service composition and optimal-selection based on Pareto group leader algorithm in cloud manufacturing system

Service composition and optimal selection (SCOS) is one of the key issues for implementing a cloud manufacturing system. Exiting works on SCOS are primarily based on quality of service (QoS) to provide high-quality service for user. Few works have been delivered on providing both high-quality and low-energy consumption service. Therefore, this article studies the problem of SCOS based on QoS and energy consumption (QoS-EnCon). First, the model of multi-objective service composition was established; the evaluation of QoS and energy consumption (EnCon) were investigated, as well as a dimensionless QoS objective function. In order to solve the multi-objective SCOS problem effectively, then a novel globe optimization algorithm, named group leader algorithm (GLA), was introduced. In GLA, the influence of the leaders in social groups is used as an inspiration for the evolutionary technology which is design into group architecture. Then, the mapping from the solution (i.e., a composed service execute path) of SCOS problem to a GLA solution is investigated, and a new multi-objective optimization algorithm (i.e., GLA-Pareto) based on the combination of the idea of Pareto solution and GLA is proposed for addressing the SCOS problem. The key operators for implementing the Pareto-GA are designed. The results of the case study illustrated that compared with enumeration method, genetic algorithm (GA), and particle swarm optimization, the proposed GLA-Pareto has better performance for addressing the SCOS problem in cloud manufacturing system.     

Multi-objective simulation-based evolutionary algorithm for an aircraft spare parts allocation problem

Simulation optimization has received considerable attention from both simulation researchers and practitioners. In this study, we develop a solution framework which integrates multi-objective evolutionary algorithm (MOEA) with multi-objective computing budget allocation (MOCBA) method for the multi-objective simulation optimization problem. We apply it on a multi-objective aircraft spare parts allocation problem to find a set of non-dominated solutions. The problem has three features: huge search space, multi-objective, and high variability. To address these difficulties, the solution framework employs simulation to estimate the performance, MOEA to search for the more promising designs, and MOCBA algorithm to identify the non-dominated designs and efficiently allocate the simulation budget. Some computational experiments are carried out to test the effectiveness and performance of the proposed solution framework.     

A multi-objective lead time control problem in multi-stage assembly systems using genetic algorithms

In this paper, we develop a multi-objective model to optimally control the lead time of a multi-stage assembly system, using genetic algorithms. The multi-stage assembly system is modelled as an open queueing network. It is assumed that the product order arrives according to a Poisson process. In each service station, there is either one or infinite number of servers (machines) with exponentially distributed processing time, in which the service rate (capacity) is controllable. The optimal service control is decided at the beginning of the time horizon. The transport times between the service stations are independent random variables with generalized Erlang distributions. The problem is formulated as a multi-objective optimal control problem that involves four conflicting objective functions. The objective functions are the total operating costs of the system per period (to be minimized), the average lead time (min), the variance of the lead time (min) and the probability that the manufacturing lead time does not exceed a certain threshold (max). Finally, we apply a genetic algorithm with double strings using continuous relaxation based on reference solution updating (GADSCRRSU) to solve this multi-objective problem, using goal attainment formulation. The results are also compared against the results of a discrete-time approximation technique to show the efficiency of the proposed genetic algorithm approach.     

煤炭码头船货匹配下泊位动态分配多目标优化模型及算法

本文针对输出型煤炭码头船货匹配下泊位动态分配问题,构建了堆场-取装线-泊位-船舶联合分配优化数学模型,并设计了采用仿真推演策略解码的遗传算法求解。首先,综合考虑船舶、泊位、堆场、取装线、煤种、航道开放时间和装船作业规则等要素,以船舶在港时间最短和作业效率最大为目标建立了相应的多约束多目标优化模型。然后,综合多目标优化、遗传算法以及仿真推演技术,设计了相应的遗传算法求解,包括:组合式编码、采用仿真推演策略的解码方法,追加了具有合法性检查的染色体生成算法,设计了采用多种策略的遗传操作等。最后实例表明,本算法的执行效率高而且优化效果好。     

A heuristic method for non-homogeneous redundancy optimization of series-parallel multi-state systems

This paper develops an efficient heuristic to solve the non-homogeneous redundancy allocation problem for multi-state series-parallel systems. Non identical components can be used in parallel to improve the system availability by providing redundancy in subsystems. Multiple component choices are available for each subsystem. The components are binary and chosen from a list of products available on the market, and are characterized in terms of their cost, performance and availability. The objective is to determine the minimal-cost series-parallel system structure subject to a multi-state availability constraint. System availability is represented by a multi-state availability function, which extends the binary-state availability. This function is defined as the ability to satisfy consumer demand that is represented as a piecewise cumulative load curve. A fast procedure is used, based on universal generating function, to evaluate the multi-state system availability. The proposed heuristic approach is based on a combination of space partitioning, genetic algorithms (GA) and tabu search (TS). After dividing the search space into a set of disjoint subsets, this approach uses GA to select the subspaces, and applies TS to each selected subspace. The design problem, solved in this study, has been previously analyzed using GA. Numerical results for the test problems from previous research are reported, and larger test problems are randomly generated. These results show that the proposed approach is efficient both in terms of both of solution quality and computational time, as compared to existing approaches.     

Multi-objective redundancy allocation optimization using a variable neighborhood search algorithm

A variable neighborhood search (VNS) algorithm has been developed to solve the multiple objective redundancy allocation problems (MORAP). The single objective RAP is to select the proper combination and redundancy levels of components to meet system level constraints, and to optimize the specified objective function. In practice, the need to consider two or more conflicting objectives simultaneously increases nowadays in order to assure managers or designers’ demand. Amongst all system level objectives, maximizing system reliability is the most studied and important one, while system weight or system cost minimization are two other popular objectives to consider. According to the authors’ experience, VNS has successfully solved the single objective RAP (Liang and Chen, Reliab. Eng. Syst. Saf. 92:323–331, 2007; Liang et al., IMA J. Manag. Math. 18:135–155, 2007). Therefore, this study aims at extending the single objective VNS algorithm to a multiple objective version for solving multiple objective redundancy allocation problems. A new selection strategy of base solutions that balances the intensity and diversity of the approximated Pareto front is introduced. The performance of the proposed multi-objective VNS algorithm (MOVNS) is verified by testing on three sets of complex instances with 5, 14 and 14 subsystems respectively. While comparing to the leading heuristics in the literature, the results show that MOVNS is able to generate more non-dominated solutions in a very efficient manner, and performs competitively in all performance measure categories. In other words, computational results reveal the advantages and benefits of VNS on solving multi-objective RAP.     

A simulated annealing based genetic local search algorithm for multi-objective multicast routing problems

This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.     

Solving a new stochastic multi-mode p-hub covering location problem considering risk by a novel multi-objective algorithm

In this paper, we develop a novel stochastic multi-objective multi-mode transportation model for hub covering location problem under uncertainty. The transportation time between each pair of nodes is an uncertain parameter and also is influenced by a risk factor in the network. We extend the traditional comprehensive hub location problem by considering two new objective functions. So, our multi-objective model includes (i) minimization of total current investment costs and (ii) minimization of maximum transportation time between each origin–destination pair in the network. Besides, a novel multi-objective imperialist competitive algorithm (MOICA) is proposed to obtain the Pareto-optimal solutions of the problem. The performance of the proposed solution algorithm is compared with two well-known meta-heuristics, namely, non-dominated sorting genetic algorithm (NSGA-II) and Pareto archive evolution strategy (PAES). Computational results show that MOICA outperforms the other meta-heuristics.     

A new multi-objective self-organizing optimization algorithm (MOSOA) for spatial optimization problems

Spatial planning is an important and complex activity. It includes land use planning and resource allocation as basic components. An abundance of papers can be found in the literature related to each one of these two aspects separately. On the contrary, a much smaller number of research reports deal with both aspects simultaneously. This paper presents an innovative evolutionary algorithm for treating combined land use planning and resource allocation problems. The new algorithm performs optimization on a cellular automaton domain, applying suitable transition rules on the individual neighbourhoods. The optimization process is multi-objective, based on non-domination criteria and self-organizing. It produces a Pareto front thus offering an advantage to the decision maker, in comparison to methods based on weighted-sum objective functions. Moreover, the present multi-objective self-organizing algorithm (MOSOA) can handle both local and global spatial constraints. A combined land use and water allocation problem is treated, in order to illustrate the cellular automaton optimization approach. Water is allocated after pumping from an aquifer, thus contributing a nonlinearity to the objective function. The problem is bi-objective aiming at (a) the minimization of soil and groundwater pollution and (b) the maximization of economic profit. An ecological and a socioeconomic constraint are imposed: (a) Groundwater levels at selected places are kept above prescribed thresholds. (b) Land use quota is predefined. MOSOA is compared to a standard multi-objective genetic algorithm and is shown to yield better results both with respect to the Pareto front and to the degree of compactness. The latter is a highly desirable feature of a land use pattern. In the land use literature, compactness is part of the objective function or of the constraints. In contrast, the present approach renders compactness as an emergent result.     

基于支配强度的NSGA Ⅱ改进算法在研究生招生面试分组中的应用

针对研究生招生面试分组这一NP难问题,提出了一种以分组遗传算法(GGA)和基于支配强度的改进NSGA Ⅱ算法为基础的混合多目标分组遗传算法。通过基于矩阵编码的多交叉/多变异算子、次精英化的初始化种群策略以及改进的帕累托支配关系,解决了经典NSGA Ⅱ算法在该问题中的收敛速度慢、易陷入局部最优的问题。仿真实验结果表明,该方法只需进行较少代数(不超过100代)的进化,即可获得最优解集,满足了快速分组的用户偏好。     

Heuristic approaches to determine base-stock levels in a serial supply chain with a single objective and with multiple objectives

This paper deals with the problem of determination of installation base-stock levels in a serial supply chain. The problem is treated first as a single-objective inventory-cost optimization problem, and subsequently as a multi-objective optimization problem by considering two cost components, namely, holding costs and shortage costs. Variants of genetic algorithms are proposed to determine the best base-stock levels in the single-objective case. All variants, especially random-key gene-wise genetic algorithm (RKGGA), show an excellent performance, in terms of convergence to the best base-stock levels across a variety of supply chain settings, with minimum computational effort. Heuristics to obtain base-stock levels are proposed, and heuristic solutions are introduced in the initial population of the RKGGA to expedite the convergence of the genetic search process. To deal with the multi-objective supply-chain inventory optimization problem, a simple multi-objective genetic algorithm is proposed to obtain a set of non-dominated solutions.     

基于遗传算法的多目标柔性工作车间调度问题求解

本文针对柔性工作车间调度问题给出了一个有意义的综合目标尽可能缩短制造周期的同时尽可能的减少机器负荷。由于传统遗传算法在多目标柔性工作车间调度问题上的局限性，我们提出了一种改进遗传算法：首先，我们给出了针对综合目标的工序调度算法获得初始集合；接着，针对柔性工作车间调度问题的特点，我们在常用的基于工序顺序的编码方法上融入了基于机器分配的编码方法，并据此设计了相应的交叉变异操作；最后借鉴了物种进化现象中的环境迁移思想设计了解决多目标优化问题的迁移操作。实验结果表明，改进的遗传算法在多目标柔性工作车间调度问题的解决上要优于传统遗传算法。     

A probability maximization model based on rough approximation and its application to the inventory problem

In the present paper, we concentrate on dealing with a class of multi-objective programming problems with random coefficients and present its application to the multi-item inventory problem. The P-model is proposed to obtain the maximum probability of the objective functions and rough approximation is applied to deal with the feasible set with random parameters. The fuzzy programming technique and genetic algorithm are then applied to solve the crisp programming problem. Finally, the application to Auchan’s inventory system is given in order to show the efficiency of the proposed models and algorithms.     

Effects of diversity control in single-objective and multi-objective genetic algorithms

This paper covers an investigation on the effects of diversity control in the search performances of single-objective and multi-objective genetic algorithms. The diversity control is achieved by means of eliminating duplicated individuals in the population and dictating the survival of non-elite individuals via either a deterministic or a stochastic selection scheme. In the case of single-objective genetic algorithm, onemax and royal road R ₁ functions are used during benchmarking. In contrast, various multi-objective benchmark problems with specific characteristics are utilised in the case of multi-objective genetic algorithm. The results indicate that the use of diversity control with a correct parameter setting helps to prevent premature convergence in single-objective optimisation. Furthermore, the use of diversity control also promotes the emergence of multi-objective solutions that are close to the true Pareto optimal solutions while maintaining a uniform solution distribution along the Pareto front.     

基于种群自适应调整的多目标差分进化算法

为提高已有多目标进化算法在求解复杂多目标优化问题上的收敛性和解集分布性,提出一种基于种群自适应调整的多目标差分进化算法。该算法设计一个种群扩增策略,它在决策空间生成一些新个体帮助搜索更优的非支配解;设计了一个种群收缩策略,它依据对非支配解集的贡献程度淘汰较差的个体以减少计算负荷,并预留一些空间给新的带有种群多样性的扰动个体;引入精英学习策略,防止算法陷入局部收敛。通过典型的多目标优化函数对算法进行测试验证,结果表明所提算法相对于其他算法具有明显的优势,其性能优越,能够在保证良好收敛性的同时,使获得的Pareto最优解集具有更均匀的分布性和更广的覆盖范围,尤其适合于高维复杂多目标优化问题的求解。     

Multi-objective open shop scheduling by considering human error and preventive maintenance

This study presents an open shop scheduling model by considering human error and preventive maintenance. The proposed mathematical model takes into account conflicting objective functions including makespan, human error and machine availability. In order to find the optimum scheduling, human error, maintenance and production factors are considered, simultaneously. Human error is measured by Human Error Assessment and Reduction Technique (HEART). Three metaheuristic methods including non-dominated sorting genetic algorithm-II (NSGA-II), multi-objective particle swarm optimization (MOPSO) and strength Pareto evolutionary algorithm II (SPEA-II) are developed to find near-optimal solution. The Taguchi method is applied by adjusting parameters of metaheuristic algorithms. Several illustrative examples and a real case study (auto spare parts manufacturer) are applied to show the applicability of the multi-objective mixed integer nonlinear programming model. The proposed approach of this study may be used for similar open shop problems with minor modifications.