Exact optimal solutions of the minisum facility and transfer points location problems on a network

We consider hierarchical facility location problems on a network called Multiple Location of Transfer Points (MLTP) and Facility and Transfer Points Location Problem (FTPLP), where q facilities and p transfer points are located and each customer goes to one of the facilities directly or via one of the transfer points. In FTPLP, we need to find an optimal location of both the facilities and the transfer points while the location of facilities is given in MLTP. Although good heuristics have been proposed for the minisum MLTP and FTPLP, no exact optimal solution has been tested due to the size of the problems. We show that the minisum MLTP can be formulated as a p‐median problem, which leads to obtaining an optimal solution. We also present a new formulation of FTPLP and an enumeration‐based approach to solve the problems with a single facility.     

Cooperative load balancing in distributed systems

A serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. In this paper, we formulate the static load‐balancing problem in single class job distributed systems as a cooperative game among computers. The computers comprising the distributed system are modeled as M/M/1 queueing systems. It is shown that the Nash bargaining solution (NBS) provides an optimal solution (operation point) for the distributed system and it is also a fair solution. We propose a cooperative load‐balancing game and present the structure of NBS. For this game an algorithm for computing NBS is derived. We show that the fairness index is always equal to 1 using NBS, which means that the solution is fair to all jobs. Finally, the performance of our cooperative load‐balancing scheme is compared with that of other existing schemes. Copyright © 2008 John Wiley & Sons, Ltd.     

Application of the Hirsch Generic Convergence Statement to the Set‐Point Regulation of Excitable‐Transparent‐Monotone Systems

Monotone systems are dynamical systems whose solutions preserve an ordering, relative to the initial data. This paper focuses on the set‐point regulation problem for excitable‐transparent‐monotone single‐input single‐output systems with well‐defined static characteristics. The suggested technique for designing a static feedback controller is inspired from the Hirsch Theorem for monotone autonomous systems. It is shown that the closed‐loop system is strongly monotone and its generic solution converges to the desired set‐point. A remark is given on the application of the suggested design methodology to delay systems, as well as to systems with reaction‐diffusion equations. A simulation example from the biological world demonstrates the effectiveness of the proposed control strategy in real applications.     

Model and algorithm for bilevel multisized terminal location‐routing problem for the last mile delivery

The last mile delivery is regarded as one of the most expensive but least efficient stretches in the business‐to‐customer supply chain. Designing the last mile delivery system in a lean way is crucial to serve customers efficiently and economically. To address this issue, we propose a bilevel multisized terminal location‐routing problem (BL‐MSTLRP) with simultaneous home delivery and customer's pickup services. The solution method is proposed by combining genetic algorithm (GA) and simulated annealing (SA), called self‐adaptive SGA. Studies for designing the last mile delivery system in a real‐world environment indicate the validity of the proposed model based on the comparison of different scenarios. Numerical experiments are also conducted to evaluate the performance of the presented SGA. Computational results show that the hybrid approach efficiently solves the BL‐MSTLRP.     

IS A MIXED DESIGN OF OBSERVER‐CONTROLLERS FOR TIME‐DELAY SYSTEMS INTERESTING?

This paper deals with H∞ observer‐based feedback control for linear time‐delay systems, in the framework of delay independent stability. We will propose a new LMI solution to observer‐controller design that ensures a disturbance attenuation level for the controlled output as well as for the state estimation error, which is an open problem. This will be compared with a well‐known solution and with a usual strategy in control which consists in designing the observer and the controller separately. Our aim is to try to bring a positive answer to the following question: is there an interest to solve the problem in a single (unique) formulation or should we design separately the observer and the controller? An application to a wind tunnel model is provided to emphasize the interest of the given results, particularly in comparison with existing results on H∞ observer‐based control.     

Implementation of mixed precision in solving systems of linear equations on the Cell processor

This paper describes the design concepts behind implementations of mixed‐precision linear algebra routines targeted for the Cell processor. It describes in detail the implementation of code to solve linear system of equations using Gaussian elimination in single precision with iterative refinement of the solution to the full double‐precision accuracy. By utilizing this approach the algorithm achieves close to an order of magnitude higher performance on the Cell processor than the performance offered by the standard double‐precision algorithm. The code is effectively an implementation of the high‐performance LINPACK benchmark, as it meets all of the requirements concerning the problem being solved and the numerical properties of the solution. Copyright © 2007 John Wiley & Sons, Ltd.     

A genetic algorithm for the uncapacitated single allocation planar hub location problem

Given a set of n interacting points in a network, the hub location problem determines location of the hubs (transfer points) and assigns spokes (origin and destination points) to hubs so as to minimize the total transportation cost. In this study, we deal with the uncapacitated single allocation planar hub location problem (PHLP). In this problem, all flow between pairs of spokes goes through hubs, capacities of hubs are infinite, they can be located anywhere on the plane and are fully connected, and each spoke must be assigned to only one hub. We propose a mathematical formulation and a genetic algorithm (PHLGA) to solve PHLP in reasonable time. We test PHLGA on simulated and real life data sets. We compare our results with optimal solution and analyze results for special cases of PHLP for which the solution behavior can be predicted. Moreover, PHLGA results for the AP and CAB data set are compared with other heuristics.     

Global robust output regulation of multivariable systems with nonlinear exosystem

It is well known that multi‐input, multi‐output nature of nonlinear system and generalized exosystem have posed some challenges to output regulation theory. Recently, the global robust output regulation problem for a class of multivariable nonlinear system subject to a linear neutrally stable exosystem has been studied. It has been shown that a linear internal model‐based state feedback control law can lead to the solution of previous problem. In this paper, we will further study the global robust output regulation problem of the system subject to a nonlinear exosystem. By utilizing nonlinear internal model design and decomposing the multi‐input control problem into several single‐input control problems, we will solve the problem by recursive control law design. The theoretical result is applied to the non‐harmonic load torque disturbance rejection problem of a surface‐mounted permanent magnet synchronous motor. Copyright © 2016 John Wiley & Sons, Ltd.     

Covering a line segment with variable radius discs

The paper addresses the problem of locating sensors with a circular field of view so that a given line segment is under full surveillance, which is termed as the disc covering problem on a line. The cost of each sensor includes a fixed component f, and a variable component that is a convex function of the diameter of the field-of-view area. When only one type of sensor or, in general, one type of disc, is available, then a simple polynomial algorithm solves the problem. When there are different types of sensors, the problem becomes hard. A branch-and-bound algorithm as well as an efficient heuristic are developed for the special case in which the variable cost component of each sensor is proportional to the square of the measure of the field-of-view area. The heuristic very often obtains the optimal solution as shown in extensive computational testing.     

Robust adaptive learning control for nonlinear systems with extended matching unstructured uncertainties

The exponential output tracking problem for a class of single‐input, single‐output uncertain nonlinear systems, including systems with extended matching unstructured uncertainties and without a well‐defined global relative degree, is addressed. Conditions on the uncertain system dynamics are derived, which allow us to design a state‐feedback learning control achieving semi‐global exponential output tracking of sufficiently smooth and periodic reference signals of known period, while guaranteeing ??₂ and ??_∞ transient performances during the learning phase. The application of the proposed learning approach to the position tracking control problem for uncertain permanent magnet step motors with non‐sinusoidal flux distribution and uncertain position‐dependent load torque allows us to provide a solution to a yet unsolved problem. Copyright © 2011 John Wiley & Sons, Ltd.     

Real‐time model predictive control based on dual gradient projection: Theory and fixed‐point FPGA implementation

This paper proposes a method to design robust model predictive control (MPC) laws for discrete‐time linear systems with hard mixed constraints on states and inputs, in case of only an inexact solution of the associated quadratic program is available, because of real‐time requirements. By using a recently proposed dual gradient‐projection algorithm, it is proved that the discrepancy of the optimal control law as compared with the obtained one is bounded even if the solver is implemented in fixed‐point arithmetic. By defining an alternative MPC problem with tightened constraints, a feasible solution is obtained for the original MPC problem, which guarantees recursive feasibility and asymptotic stability of the closed‐loop system with respect to a set including the origin, also considering the presence of external disturbances. The proposed MPC law is implemented on a field‐programmable gate array in order to show the practical applicability of the method. Copyright © 2016 John Wiley & Sons, Ltd.     

Improved heuristics for the regenerator location problem

Telecommunication systems use optical signals to transmit information. The strength of a signal in an optical network deteriorates and loses power as it goes farther from the source, mainly due to attenuation. Therefore, to enable the signal to arrive its intended destination with good quality, it is necessary to regenerate the signal periodically using regenerators. These components are relatively expensive and therefore it is desirable to deploy as few of them as possible in the network. In the regenerator location problem (RLP), we are given an undirected graph, positive edge lengths, and a parameter specifying the maximum length that a signal can travel before its quality deteriorates and regeneration is required. The problem consists in determining paths that connect all pairs of nodes in the graph and, if necessary, locating single regenerators in some of those nodes such that the signal never travels more than the maximum allowed distance without traversing a regenerator node. In this paper, we present new implementations of previous heuristics and two new heuristics—a GRASP and a biased random‐key genetic algorithm—for the RLP. Computational experiments comparing the proposed solution procedures with previous heuristics described in the literature illustrate the efficiency and effectiveness of our methods.     

Enhancing CLP branch and bound techniques for scheduling problems

In this paper, we propose a constraint logic programming (CLP) approach to the solution of a job shop scheduling problem in the field of production planning in orthopaedic hospital departments. A pure CLP on finite domain (CLP(FD)) approach to the problem has been developed, leading to disappointing results. In fact, although CLP(FD) has been recognized as a suitable tool for solving combinatorial problems, it presents some drawbacks for optimization problems. The main reason concerns the fact that CLP(FD) solvers do not effectively handle the objective function and cost‐based reasoning through the simple branch and bound scheme they embed. Therefore, we have proposed an improvement of the standard CLP branch and bound algorithm by exploiting some well‐known operations research results. The branch and bound we integrate in a CLP environment is based on the optimal solution of a relaxation of the original problem. In particular, the relaxation used for the job shop scheduling problem considered is the well‐known shifted bottleneck procedure considering single machine problems. The idea is to decompose the original problem into subproblems and solve each of them independently. Clearly, the solutions of each subproblem may violate constraints among different subproblems which are not taken into account. However, these solutions can be exploited in order to improve the pruning of the search space and to guide the search by defining cost‐based heuristics. The resulting algorithm achieves a significant improvement with respect to the pure CLP(FD) approach that enables the solution of problems which are one order of magnitude greater than those solved by a pure CLP(FD) algorithm. In addition, the resulting code is less dependent on the input data configuration. Copyright © 2001 John Wiley & Sons, Ltd.     

Ejection chain moves for automatic neighborhood synthesis in constrained cardinality‐minimization problems

In this paper, we deal with the problem of automatically synthesizing “good” neighborhoods for a specific class of problems, namely constrained cardinality‐minimization problems. Exploiting the peculiarity of the objective function of such problems, we develop automatic ejection chain moves that define neighborhood structures to be explored with a black‐box solver. In particular, starting from a formulation of a cardinality‐minimization problem and a feasible solution, our procedure automatically detects the “entities” involved in the problem and learns the strength of the relationships among them. This information is then used to define the characteristics of our moves that consist in ejecting one entity at a time from the solution. If one of such moves results in an infeasible solution, then feasibility is recovered by performing an additional step based on the solution of an auxiliary problem. The computational results show that, when assessed on four well‐known constrained cardinality‐minimization problems, our approach outperforms both a black‐box mixed integer programming solver and a state‐of‐the‐art model‐based neighborhood search procedure with respect to both solution quality and computing times.     

A grouped storage method for minimizing relocations in block stacking systems

When storage and retrieval times of inventories are uncertain and the storage space for the inventories is limited, it is an important problem to assign the inventories to storage spaces so that the total expected number of relocations is minimized. This paper addresses a dynamic location problem as well as a static location problem. Mathematical models are proposed for obtaining the optimal solution. To overcome the excessive computational time of optimizing methods, a genetic algorithm is suggested. Also, simple heuristic rules are suggested to solve the dynamic location problem. Performance of various solution methods are compared with each other. Received: June 2005 / Accepted: December 2005     

Sensitivity analysis in the single-machine scheduling problem with max–min criterion

In this paper, the single‐machine scheduling problem 1∣prec∣f_max is considered. It is one of the most general scheduling problems for which an efficient, polynomial algorithm has been developed. It is always possible to calculate quickly one optimal solution (a sequence of jobs) in that problem. However, the set of all optimal solutions may contain a lot of other sequences, so it is important to give a full characterization of that set. This paper consists of two parts. In the first part, some sufficient and necessary conditions of optimality of a given solution to the problem 1∣prec∣f_max are proved. In the second part, an application of these conditions to the sensitivity analysis is presented.     

On an integrated approach to resilient transportation systems in emergency situations

In this paper we present an integrated approach to the evacuation problem under an emergency situation for transportation systems. The approach is based on a view that a service system has two subsystems: infrastructure and substance. The approach attempts to integrate infrastructure design and substance flow planning to improve the evacuation performance. Without loss of generality, we restrict infrastructure design to reconstruction of a damaged road with two attributes of the road: capacity and travel time, we restrict substance flow planning to the contraflow method, and we consider the evacuation problem with single source and single destination. Further, we apply the discrete variable Particle Swarm Optimization and RelaxIV to solve the problem model. The overall objective function in the problem model is a minimum transportation time. Since recovery of a damaged transportation (damaged road in this case) is implied in our problem, the proposed approach has some significant implication to resilience engineering of a service system as well. An example is studied to show the effectiveness of our approach; in particular it is shown that an integrated solution is significantly better than the solution with only the contraflow method.

     

Optimization of dependently controlled jump rates of JLQG problem

The Jump Linear Quadratic Gaussian (JLQG) model is well studied due to its wide applications. However, JLQG with controlled jump rates are rarely researched, while the existing studies usually impose an assumption that jump rates are independent and separately controlled. In practical systems, their jump rates may not be independent of each other. In this paper, we consider a continuous‐time JLQG model with dependently controlled jump rates and formulate it as a two‐level control problem. The low‐level problem is a standard JLQG problem, thus we focus on solution of high‐level problem. We propose a Markov decision process‐based approach to calculate performance gradient with respect to jump rates control variable and develop a gradient‐based optimization algorithm. We present an application of manufacturing system to illustrate the main results of this paper. Copyright © 2009 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

有约束竞争选址问题的降阶回溯算法

有约束竞争选址问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时或是无法求得最优解或是求解速度慢.针对现有算法的缺点,首先在这个经典问题的基础上进行修改,构建了一个新的数学模型;接着对该模型的数学性质进行研究,并在数学性质的基础上提出了上下界算法和降阶子算法对问题进行降阶,达到了缩减问题搜索解空间的目的,降阶的过程中既有单个的降阶,也有成批的降阶;然后在前面的基础上设计了一个回溯子算法来求解问题的最优解;最后通过两个示例分析更清楚地阐述该算法的原理,结果证明该算法可以较快求得最优解.     

智能网络磁盘集群存储系统设计与实现

集群系统实现单一用户访问点的常用方法是设置一个前端机统一进行用户请求的转发，这种方法很好地解决了集群的单一入口问题，但容易引起单点失效，性能也难扩展。提出一种新的网络存储集群系统，集群的可扩展性、可用性均获得了增强，实验证明，这是一种实用的有效的网络存储集群解决方案。