“非流水型n×m排序问题”简便方法的改进

一、问题的提出《排序问题》是运筹学中的一个问题.它可表述为:“n个不同零件需在m台设备上加工,怎样安排零件的加工顺序,使加工所耗的总工时最少?”这一问题,由于加工顺序的编排受多种因素的制约,情况异常复杂,因此,寻找最优排序方案非常困难.只有少数几种简单的情形,它才得到了完善的解决.其中主要有:1.当m=2时,即n种不同零件在两台设备上加工,且工艺顺序相同,或各零件在加工时所通过的设备顺序相同.这种问题的优化,已由Johnson于1954年提出了解决的方法.Johnson规则是:“如果各零件都需先在设备A上加工,然后转入设备B上加工,那末若加工时间短的工序是在A设备上进行的,则安排其零件先加工。

A hybrid algorithm based on tabu search and large neighbourhood search for car sequencing problem

The car sequencing problem(CSP)concerns a production sequence of different types of cars in the mixed-model assembly line.A hybrid algorithm is proposed to find an assembly sequence of CSP with minimum violations.Firstly,the hybrid algorithm is based on the tabu search and large neighborhood search(TLNS),servicing as the framework.Moreover,two components are incorporated into the hybrid algorithm.One is the parallel constructive heuristic(PCH)that is used to construct a set of initial solutions and find some high quality solutions,and the other is the small neighborhood search(SNS)which is designed to improve the new constructed solutions.The computational results show that the proposed hybrid algorithm(PCH+TLNS+SNS)obtains100best known values out of109public instances,among these89instances get their best known values with100%success rate.By comparing with the well-known related algorithms,computational results demonstrate the effectiveness,efficiency and robustness of the proposed algorithm.

Deterministic and randomized scheduling problems under the lp norm on two identical machines

Parallel machine scheduling problems, which are important discrete optimization problems, may occur in many applications. For example, load balancing in network communication channel assignment, parallel processing in large-size computing, task arrangement in flexible manufacturing systems, etc., are multiprocessor scheduling problem. In the traditional parallel machine scheduling problems, it is assumed that the problems are considered in offline or online environment. But in practice, problems are often not really offline or online but somehow in-between. This means that, with respect to the online problem, some further information about the tasks is available, which allows the improvement of the performance of the best possible algorithms. Problems of this class are called semi-online ones. In this paper, the semi-online problem P2|decr|lp (p>1) is considered where jobs come in non-increasing order of their processing times and the objective is to minimize the sum of the lp norm of every machine’s load. It is shown that LS algorithm is optimal for any lp norm, which extends the results known in the literature. Furthermore, randomized lower bounds for the problems P2|online|lp and P2|decr|lp are presented.

Solving chemical dynamic optimization problems with ranking-based differential evolution algorithms

Dynamic optimization problems(DOPs) described by differential equations are often encountered in chemical engineering. Deterministic techniques based on mathematic programming become invalid when the models are non-differentiable or explicit mathematical descriptions do not exist. Recently, evolutionary algorithms are gaining popularity for DOPs as they can be used as robust alternatives when the deterministic techniques are invalid. In this article, a technology named ranking-based mutation operator(RMO) is presented to enhance the previous differential evolution(DE) algorithms to solve DOPs using control vector parameterization. In the RMO, better individuals have higher probabilities to produce offspring, which is helpful for the performance enhancement of DE algorithms. Three DE-RMO algorithms are designed by incorporating the RMO. The three DE-RMO algorithms and their three original DE algorithms are applied to solve four constrained DOPs from the literature. Our simulation results indicate that DE-RMO algorithms exhibit better performance than previous non-ranking DE algorithms and other four evolutionary algorithms.

Efficient Security Sequencing Problem over Insecure Channel Based on Homomorphic Encryption

In the field of sequencing of secret number,an important problem is how to establish an efficient and secure protocol for sorting the secret number.As a powerful tool in solving privacy sequencing problems,secure multipart computation is more and more popular in anonymous voting and online auction.In the present study,related secure computation protocol for sequencing problem is not many by far.In order to improve the efficiency and safety,we propose a security sequencing protocol based on homomorphic encryption.We also give analysis of correctness and security to highlight its feasibility.

An integer multi-objective optimization model and an enhanced non-dominated sorting genetic algorithm for contraflow scheduling problem

To determine the onset and duration of contraflow evacuation, a multi-objective optimization(MOO) model is proposed to explicitly consider both the total system evacuation time and the operation cost. A solution algorithm that enhances the popular evolutionary algorithm NSGA-II is proposed to solve the model. The algorithm incorporates preliminary results as prior information and includes a meta-model as an alternative to evaluation by simulation. Numerical analysis of a case study suggests that the proposed formulation and solution algorithm are valid, and the enhanced NSGA-II outperforms the original algorithm in both convergence to the true Pareto-optimal set and solution diversity.

Non-dominated sorting quantum particle swarm optimization and its application in cognitive radio spectrum allocation

In order to solve discrete multi-objective optimization problems, a non-dominated sorting quantum particle swarm optimization (NSQPSO) based on non-dominated sorting and quantum particle swarm optimization is proposed, and the performance of the NSQPSO is evaluated through five classical benchmark functions. The quantum particle swarm optimization (QPSO) applies the quantum computing theory to particle swarm optimization, and thus has the advantages of both quantum computing theory and particle swarm optimization, so it has a faster convergence rate and a more accurate convergence value. Therefore, QPSO is used as the evolutionary method of the proposed NSQPSO. Also NSQPSO is used to solve cognitive radio spectrum allocation problem. The methods to complete spectrum allocation in previous literature only consider one objective, i.e. network utilization or fairness, but the proposed NSQPSO method, can consider both network utilization and fairness simultaneously through obtaining Pareto front solutions. Cognitive radio systems can select one solution from the Pareto front solutions according to the weight of network reward and fairness. If one weight is unit and the other is zero, then it becomes single objective optimization, so the proposed NSQPSO method has a much wider application range. The experimental research results show that the NSQPS can obtain the same non-dominated solutions as exhaustive search but takes much less time in small dimensions; while in large dimensions, where the problem cannot be solved by exhaustive search, the NSQPSO can still solve the problem, which proves the effectiveness of NSQPSO.

Advanced User-Based Interaction Model in Cloud

With the increasing popularity of cloud computing, there is an increased de mand for cloud resources in cloud. It has be come even more urgent to find solutions to improve resource utilization. From the per spective of a cloud consumer, a cloud applica tion processes a large information flow in volving user actions that access resources, but little work has so far been devoted to research from the perspective of the interaction be tween the user and the cloud application. In this paper, we analyze the interaction in detail, and propose a general mathematical interac tion model to formulate the challenge pertain ing to storage resource allocation as an opti mization problem, focusing on minimizing both the user＇s cost and server＇s consumption. A potential response mechanism is then de signed based on the interaction model. Fur thermore, the proposed model is used to ex plore strategies when multiple users access the same file simultaneously. Additionally, an improved queuing system, namely M/ G~ oo queue with standby, is introduced. Finally, an evaluation is presented to verify the interac- tion model.

NSGA Ⅱ based multi-objective homing trajectory planning of parafoil system

Homing trajectory planning is a core task of autonomous homing of parafoil system.This work analyzes and establishes a simplified kinematic mathematical model,and regards the homing trajectory planning problem as a kind of multi-objective optimization problem.Being different from traditional ways of transforming the multi-objective optimization into a single objective optimization by weighting factors,this work applies an improved non-dominated sorting genetic algorithm Ⅱ(NSGA Ⅱ) to solve it directly by means of optimizing multi-objective functions simultaneously.In the improved NSGA Ⅱ,the chaos initialization and a crowding distance based population trimming method were introduced to overcome the prematurity of population,the penalty function was used in handling constraints,and the optimal solution was selected according to the method of fuzzy set theory.Simulation results of three different schemes designed according to various practical engineering requirements show that the improved NSGA Ⅱ can effectively obtain the Pareto optimal solution set under different weighting with outstanding convergence and stability,and provide a new train of thoughts to design homing trajectory of parafoil system.

Best compromising crashworthiness design of automotive S-rail using TOPSIS and modified NSGAⅡ

In order to reduce both the weight of vehicles and the damage of occupants in a crash event simultaneously, it is necessary to perform a multi-objective optimal design of the automotive energy absorbing components. Modified non-dominated sorting genetic algorithm II(NSGA II) was used for multi-objective optimization of automotive S-rail considering absorbed energy(E), peak crushing force(Fmax) and mass of the structure(W) as three conflicting objective functions. In the multi-objective optimization problem(MOP), E and Fmax are defined by polynomial models extracted using the software GEvo M based on train and test data obtained from numerical simulation of quasi-static crushing of the S-rail using ABAQUS. Finally, the nearest to ideal point(NIP)method and technique for ordering preferences by similarity to ideal solution(TOPSIS) method are used to find the some trade-off optimum design points from all non-dominated optimum design points represented by the Pareto fronts. Results represent that the optimum design point obtained from TOPSIS method exhibits better trade-off in comparison with that of optimum design point obtained from NIP method.

SWITCHING AND SEQUENCING AVAILABLE THERAPIES SO AS TO MAXIMIZE A PATIENT＇S EXPECTED TOTAL LIFETIME

This paper has focused on applying mathematical techniques to address fundamental question in therapy planning when to switch, and how to sequence therapies. We consider switching and sequencing available therapies so as to maximize a patient＇s expected total lifetime. We assume knowledge only about the lifetime distributions induced by the therapies. We discuss a specialization of this model that is tailored to a frequently reoccurring type of management problem, where our goal is to determine the best timing for testing and treatment decisions for patients with ischemic heart disease. Typically, decisions are made with an overall, goal of maximizing the patient＇s expected lifetime or quality-adjusted lifetime.