A quadra-directional decomposition heuristic for a two-dimensional,non-equidistant machine-cell location problem

After the development of numerous cell formation techniques, machine-cell location (MCL) problems have been the focus of many researchers in cellular manufacturing systems. With the cost cutting strategy, locating machines within the cell itself has not only been the major concern of management, but also the location of cells with respect to each other on a spatial coordinate system to minimize the transportation cost or job movement costs. For lack of being able to solve a large problem optimally, a number of heuristics have been developed for one-dimensional machine and MCL problems. The problem still exists for locating machine-cells on spatial coordinates, which has been addressed in this research. The location coordinates have been decomposed into four movements, backward, forward, upward and downward; and the MCL problem is formulated as a linear combination of these four decomposed (partitioned) objective functions subject to other boundary conditions. A quadra-directional decomposition heuristic (QDDH) is developed to find a sub-optimal solution to the MCL problem. The decomposition procedure for four objective functions is presented and the performance of the heuristic is tested on a set of well-known data. Empirical tests show that the solution procedure produces efficient, good quality solutions for different sizes of the problem instances.     

The dynamic linear exponential Gaussian team problem

The dynamic team problem for a linear system with Gaussian noise, exponential of a quadratic performance index, and one-step delayed sharing information pattern is considered. It is shown, via dynamic programming, that the multistage problem can be decomposed into a series of static team problems. Moreover, the optimal policy of theith team member at timekis an affine function of both the one-step predicted Kalman filter estimate and theith team member's observation at timek. Efficient algorithms are available for determining the gains of this affine controller. This model and solution are applied to an approximate resource allocation problem associated with a defense network, and a numerical example is discussed.     

A genetic algorithm approach to cellular manufacturing systems

A genetic algorithm (GA) metaheuristic-based cell formation procedure is presented in this paper. The cell formation problem solved here is to simultaneously group machines and part-families into cells so that intercellular movements are minimized. An option for considering the minimization of cell load variation is included and another, which combines minimization of intercellular movements and cell load-variation, exists. The algorithm solves this problem through improving a cell configuration using the GA metaheuristic. The designer is allowed to specify the number of cells required a priori and impose lower and upper bounds on cell size. This makes the GA scheme flexible for solving the cell formation problems. The solution procedure was found to perform well on tested large-scale problems and published data sets. Moreover, the proposed procedure compares very favorably to a well-known algorithm, and another TSP-based heuristic available in the literature. The results of computational tests presented are very encouraging.     

Solving a furnace loading problem

This paper presents a heuristic solution procedure for the furnace loading problem in metallurgical industry. The problem is decomposed into two stages: ingot order selection and candidate ingot loading. The 2-stage problems are then iteratively solved. It is shown that practical sized problems can be efficiently solved using the proposed approach.     

A mathematical programming model for manufacturing cell formation to develop multiple configurations

This paper presents and analyses a mathematical model for the design of manufacturing cells which considers two conflicting objectives such as the heterogeneity of cells and the intercell moves. A genetic algorithm (GA) based solution methodology is developed for the model which is also solved using an optimization package. The model is suitable for getting multiple potential solutions in a structured way for the cell formation problem by making a trade-off between the two objectives, instead of reaching at a single negotiating solution. This model provides the decision maker the flexibility of choosing a suitable cell design from different alternatives by considering the practical constraints. A part assignment heuristic is also developed by which part-families can be identified and is integrated with the GA based solution procedure. A comparison of the proposed method is made with other seven methods using 36 problems from the literature. Grouping efficacy is the basis for comparison and it is found to give reasonably good results.     

用于间歇化工过程最优设计的遗传算法

间歇化工过程的最优设计问题是一类复杂且难以求解的组合优化问题。通过把这类问题分解为只包含离散变量的主导问题和只含连续变量的子问题,把遗传算法和线性规划法结合起来对其进行求解。并在算法中引入了一类新的算子,显著地提高了收敛概率、算例表明,该方法可以避免直接求解过程的复杂性和困难,并且具有很好的全局收敛性。     

Genetic algorithm and large neighbourhood search to solve the cell formation problem

We first introduce a local search procedure to solve the cell formation problem where each cell includes at least one machine and one part. The procedure applies sequentially an intensification strategy to improve locally a current solution and a diversification strategy destroying more extensively a current solution to recover a new one. To search more extensively the feasible domain, a hybrid method is specified where the local search procedure is used to improve each offspring solution generated with a steady state genetic algorithm. The numerical results using 35 most widely used benchmark problems indicate that the line search procedure can reduce to 1% the average gap to the best-known solutions of the problems using an average solution time of 0.64 s. The hybrid method can reach the best-known solution for 31 of the 35 benchmark problems, and improve the best-known solution of three others, but using more computational effort.     

Decomposing and Solving Timetabling Constraint Networks

The binary version of the school timetabling (STT) problem is a real‐world example of a constraint network that includes only constraints of inequality. A new and useful representation for this real‐world problem, the STT_Grid, leads to a generic decomposition technique. The paper presents proofs of necessary and sufficient conditions for the existence of a solution to decomposed STT_Grids. The decomposition procedure is of low enough complexity to be practical for large problems, such as a real‐world high school.
To test the decomposition approach, a typical high school was analyzed and used as a model for generating STT_Grids of various sizes. Experiments were conducted to test the difficulty of large STT networks and their solution by decomposition. The experimental results show that the decomposition procedure enables the solution of large STT_Grids (620 variables for a real school) in reasonable time. The constraint network of a typical STT_Grid is sparse and belongs to the class of easy problems. Still, due to the sizes of STTs, good constraint satisfaction problem search techniques (i.e., BackJumping and ForwardChecking) do not terminate in reasonable times for STT_Grids that are larger than 300 variables.     

On solving unreliable planar location problems

In this paper, we generalize conventional P-median location problems by considering the unreliability of facilities. The unreliable location problem is defined by introducing the probability that a facility may become inactive. We proposed efficient solution methods to determine locations of these facilities in the unreliable location model. Space-filling curve-based algorithms are developed to determine initial locations of these facilities. The unreliable P-median location problem is then decomposed to P 1-median location problems; each problem is solved to the optimum. A bounding procedure is used to monitor the iterative search, and to provide a consistent basis for termination. Extensive computational tests have indicated that the heuristics are efficient and effective for solving unreliable location problems.Scope and purposeThis paper addresses an important class of location problems, where p unreliable facilities are to be located on the plane, so as to minimize the expected travel distance or related transportation cost between the customers and their nearest available facilities. The unreliable location problem is defined by introducing the probability that a facility may become inactive. Potential application of the unreliable location problem is found in numerous areas. The facilities to be located can be fire station or emergency shelter, where it fails to provide service during some time window, due to the capacity or resource constraints. Alternatively, the facilities can be telecommunication posts or logistic/distribution centers, where the service is unavailable due to breakdown, repair, shutdown of unknown causes. In this paper, we prescribed heuristic procedures to determine the location of new facilities in the unreliable location problems. The numerical study of 2800 randomly generated instances has shown that these solution procedures are both efficient and effective, in terms of computational time and solution quality.     

Static team problems--Part II: Affine control laws, projections, algorithms, and the LEGT problem

Team problems over the set of affine team control laws are solved as constrained parameter optimization problems. This methodology eases both the notational and computational difficulties. For the LQGT (linear-quadratic-Gaussian team) and the LEGT (linear-exponential-Gaussian team) problems, the constrained parameter optimization approach leads to the representation of the optimal team control gains as explicit projections of the optimal centralized gains. The projection representation offers insight into the team solution and suggests an algorithm for computing the optimal gains for the LEGT problem. The LEGT problem behavior is compared to LQGT behavior for an example which consists of a static team with garbled decision implementation.     

A heuristic sequencing procedure for sequential solution of decomposed optimal design problems

The efficiency of designing a large-scale structure with many variables can often be increased by decomposing the design problem into less complex sub-problems. This article presents heuristic procedures of determining an appropriate design sequence to solve decomposed structural optimization problems using a sequential design (single-pass) strategy. One heuristic procedure exploits the monotonicity of a global constraint, which is included in all the sub-problems. Another procedure is based on the coupling strength of interactions between sub-problems, obtaining the appropriate design sequence and then verifying it with monotonicity analysis. The procedures are applied to two types of structural design problems; the metric for sequencing decomposed sub-problems can be obtained analytically for one design problem and numerically for another one. As a result, the sequencing procedures lead to satisfactory solutions at low computational cost, indicating their value for industrial product development.     

Empirical investigation of the benefits of partial Lamarckianism

Genetic algorithms (GAs) are very efficient at exploring the entire search space; however, they are relatively poor at finding the precise local optimal solution in the region in which the algorithm converges. Hybrid GAs are the combination of improvement procedures, which are good at finding local optima, and GAs. There are two basic strategies for using hybrid GAs. In the first, Lamarckian learning, the genetic representation is updated to match the solution found by the improvement procedure. In the second, Baldwinian learning, improvement procedures are used to change the fitness landscape, but the solution that is found is not encoded back into the genetic string. This paper examines the issue of using partial Lamarckianism (i.e., the updating of the genetic representation for only a percentage of the individuals), as compared to pure Lamarckian and pure Baldwinian learning in hybrid GAs. Multiple instances of five bounded nonlinear problems, the location-allocation problem, and the cell formation problem were used as test problems in an empirical investigation. Neither a pure Lamarckian nor a pure Baldwinian search strategy was found to consistently lead to quicker convergence of the GA to the best known solution for the series of test problems. Based on a minimax criterion (i.e., minimizing the worst case performance across all test problem instances), the 20% and 40% partial Lamarckianism search strategies yielded the best mixture of solution quality and computational efficiency.     

A novel approach to determine cell formation,intracellular machine layout and cell layout in the CMS problem based on TOPSIS method

This paper deals with the cellular manufacturing system (CMS) that is based on group technology (GT) concepts. CMS is defined as identifying the similar parts that are processed on the same machines and then grouping them as a cell. The most proposed models for solving CMS problems are focused on cell formation and intracellular machine layout problem while cell layout is considered in few papers. In this paper we apply the multiple attribute decision making (MADM) concept and propose a two-stage method that leads to determine cell formation, intracellular machine layout and cell layout as three basic steps in the design of CMS. In this method, an initial solution is obtained from technique for order preference by similarity to the ideal solution (TOPSIS) and then this solution is improved. The results of the proposed method are compared with well-known approaches that are introduced in literature. These comparisons show that the proposed method offers good solutions for the CMS problem. The computational results are also reported.     

Optimal power distribution control for a network of fuel cell stacks

In power networks, where multiple fuel cell stacks are employed in a series-parallel configuration to deliver the required power, optimal sharing of the power demand between different stacks is an important problem. This is because the total current collectively produced by all the stacks is directly proportional to the fuel utilization, through stoichiometry. As a result, one would like to produce the required power while minimizing the total current produced. In this paper, an optimization formulation is proposed for this power distribution control problem. An algorithm that identifies the globally optimal solution for this problem is developed. Through an analysis of the KKT conditions, the solution to the optimization problem is decomposed into off-line and on-line computations. The on-line computations reduce to solving a nonlinear equation. For an application with a specific V–I function derived from data, we show that analytical solutions exist for on-line computations. We also discuss the wider applicability of the proposed approach for similar problems in other domains.     

Numerical and computational efficiency of solvers for two-phase problems

We consider two-phase flow problems, modelled by the Cahn–Hilliard equation. In this work, the nonlinear fourth-order equation is decomposed into a system of two coupled second-order equations for the concentration and the chemical potential.We analyse solution methods based on an approximate two-by-two block factorization of the Jacobian of the nonlinear discrete problem. We propose a preconditioning technique that reduces the problem of solving the non-symmetric discrete Cahn–Hilliard system to a problem of solving systems with symmetric positive definite matrices where off-the-shelf multilevel and multigrid algorithms are directly applicable. The resulting solution methods exhibit optimal convergence and computational complexity properties and are suitable for parallel implementation.We illustrate the efficiency of the proposed methods by various numerical experiments, including parallel results for large scale three dimensional problems.     

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.     

Large-scale convex optimal control problems: time decomposition,incentive coordination, and parallel algorithm

A parallel algorithm based on time decomposition and incentive coordination is developed for long-horizon optimal control problems. This is done by first decomposing the original problem into subproblems with shorter time horizon, and then using the incentive coordination scheme to coordinate the interaction of subproblems. For strictly convex problems it is proved that the decomposed problem with linear incentive coordination is equivalent to the original problem, in the sense that each optimal solution of the decomposed problem produces one global optimal solution of the original problem and vice versa. In other words, linear incentive terms are sufficient in this case and impose no additional computation burden on the subproblems. The high-level parameter optimization problem is shown to be nonconvex, despite the uniqueness of the optimal solution and the convexity of the original problem. Nevertheless, the high-level problem has no local minimum, even though it is nonconvex. A parallel algorithm based on a prediction method is developed, and a numerical example is used to demonstrate the feasibility of the approach     

Manufacturing cell formation using an improved P-median model

The p-median model objective function is modified for the cell formation problem to minimize the variability between parts in a group by considering part similarity to all other parts in the group instead of similarity to an arbitrary median. The heuristic vertex substitution method for solution of the part grouping problem is adapted for this objective function and then modified to provide improved starting points. The theoretical lower bound for the heuristic is developed and shown to be valid for all solutions. Worst case run time is shown to be O(n²) or O(n³) for distance matrix or network inputs respectively. Tests on published problems show that the proposed p-median model method provides as good or better objective function value (OFV) than the OFV of a p-median model in which parts are grouped to an arbitrary median. Likewise the new p-median model is shown, for these published problems, to give as good or better OFV than the algorithms reported by the original authors of the problem. The test problems suggest that other measures of solution quality such as bottlenecks and duplicate machines in addition to OFV become important measures of solution quality for dense problems.     

Stability analysis and stabilization of systems presenting nested saturations

This note addresses the problems of stability analysis and stabilization of systems presenting nested saturations. Depending on the open-loop stability assumption, the global stability analysis and stabilization problems are considered. In the (local) analysis problem, the objective is the determination of estimates of the basin of attraction of the system. Considering the stabilization problem, the goal is to design a set of gains in order to enlarge the basin of attraction of the closed-loop system. Based on the modelling of the system presenting nested saturations as a linear system with dead-zone nested nonlinearities and the use of a generalized sector condition, linear matrix inequality (LMI) stability conditions are formulated. From these conditions, convex optimization strategies are proposed to solve both problems.     

Event‐triggered probabilistic robust control of linear systems with input constrains: By scenario optimization approach

This paper addresses the problem of probabilistic robust stabilization for uncertain systems subject to input saturation. A new probabilistic solution framework for robust control analysis and synthesis problems is addressed by a scenario optimization approach, in which the uncertainties are not assumed to be norm bounded. Furthermore, by expressing the saturated linear feedback law on a convex hull of a group of auxiliary linear feedback laws, we establish conditions under which the closed‐loop system is probabilistic stable. Based on these conditions, the problem of designing the state feedback gains for achieving the largest size of the domain of attraction is formulated and solved as a constrained optimization problem with linear matrix inequality constraints. The results are then illustrated by a numerical example.