Lagrangian relaxation hybrid with evolutionary algorithm for short-term generation scheduling

Short-term generation scheduling is an important function in daily operational planning of power systems. It is defined as optimal scheduling of power generators over a scheduling period while respecting various generator constraints and system constraints. Objective of the problem includes costs associated with energy production, start-up cost and shut-down cost along with profits. The resulting problem is a large scale nonlinear mixed-integer optimization problem for which there is no exact solution technique available. The solution to the problem can be obtained only by complete enumeration, often at the cost of a prohibitively computation time requirement for realistic power systems. This paper presents a hybrid algorithm which combines Lagrangian Relaxation (LR) together with Evolutionary Algorithm (EA) to solve the problem in cooperative and competitive energy environments. Simulation studies were carried out on different systems containing various numbers of units. The outcomes from different algorithms are compared with that from the proposed hybrid algorithm and the advantages of the proposed algorithm are briefly discussed.     

Supply chain planning and scheduling integration using Lagrangian decomposition in a knowledge management environment

The integration of planning and scheduling decisions in rigorous mathematical models usually results in large scale problems. In order to tackle the problem complexity, decomposition techniques based on duality and information flows between a master and a set of subproblems are widely applied. In this sense, ontologies improve information sharing and communication in enterprises and can even represent holistic mathematical models facilitating the use of analytic tools and providing higher flexibility for model building. In this work, we exploit this ontologies’ capability to address the optimal integration of planning and scheduling using a Lagrangian decomposition approach. Scheduling/planning sub-problems are created for each facility/supply chain entity and their dual solution information is shared by means of the ontological framework. Two case studies based on a STN representation of supply chain planning and scheduling models are presented to emphasize the advantages and limitations of the proposed approach.     

p-Median and p-dispersion problems: A bi-criteria analysis

Given a collection of n locations and a symmetric measure of distance (difference) between each pair of locations, we seek to identify (select) a subset of p locations so as to achieve two distinct objectives. The first objective is to use the selected locations as centers (medians) of p groups that would partition the entire collection and minimize the total distance between the locations and their respective group medians. The second objective is to maximize the minimum distance (diversity) among the selected locations themselves. We study this problem as a multi-objective optimization problem and propose an iterative algorithm to obtain its non-dominated frontier. At each iteration we construct and solve a 0–1 integer programming problem. Through a computational experiment we show that this algorithm is computationally effective for small to medium size instances of the problem. We also propose a Lagrangian heuristic algorithm for solving larger instances of this problem.     

A three-dimensional FE analysis of large deformations for impact loadings using tetrahedral elements

 A three-dimensional dynamic program for the anaysis of large deformations in contact-penetration problems is developed using the finite element Lagrangian method with explicit time integration. By incorporating a tetrahedral element, which allows a single-point integration without a special hourglass control scheme, this program can be more effective to the present problem. The position code algorithm is used to search contact surface. Eroding surfaces are also considered. The defense node algorithm was slightly modified for the calculation of contact forces. A study of obliquity effects on metallic plate perforation and ricochet processes in thin plates impacted by a sphere was conducted. It is well simulated that on separation of two parts of the sphere, the portion still within the crater tends to perforate, while the portion in contact with the plate surface ricochets. This deformation pattern is observed in experiments, especially at high obliquities. A long rod that impacts an oblique steel plate at high impact velocity was also simulated in order to study the dynamics of the rod caused by the three dimensional asymmetric contact. The agreement between simulated and experimental results is quite good. Fracture phenomena occuring at high obliquity deserves further investigations. Received: 20 February 2002 / Accepted: 20 September 2002     

On the determination of optimal transition profile of a stepped bar in tension or in torsion by BEM

The objective is to have uniformly distributed tangential stresses on the transition profile of a stepped bar subjected to tensile and torsional loading using an axisymmetric boundary element formulation. The transition curve is represented by the Langragian interpolation polynomial with progressive degrees to avoid shape distortion during the optimization procedure. The calculated result is compared with that obtained by fluid dynamics given in the literature. It is seen that the transition curve obtained in this paper is reasonable.     

A continuum-based modeling of MEMS devices for estimating their resonant frequencies

A continuum-based modeling of coupled electrostatics-structure interactions is presented for the frequency computations of MEMS devices. The present general formulation of electrostatics accounting for free space is validated first by specializing it to one-dimensional uniform motion of conducting surfaces and comparing the resulting electrostatics to conventional lumped models. The general coupled electrostatics-structure interactions are then applied for the prediction of resonant frequencies of MEMS devices due to bias-voltage changes and temperature variations. Comparisons of predicted resonant frequencies obtained by the present coupled electrostatics-structure interaction models with experimental results available in the literature demonstrate that the proposed continuum-based interaction modeling yields high-confidence predictions of resonant frequencies of MEMS devices.     

用保形样条方法求解非定常对流扩散方程

在欧拉-拉格朗日分裂方法的基础上,本文发展了一种固定网格上的欧拉-拉格朗日分裂方法.保形样条方法(SPSM)被用来解决倒特征线插值问题.通过求解几个有精确解的例子,说明SPSM方法的解是单调无振荡的,并且数值耗散也是比较小的.     

An efficient heuristic for scheduling batches of parts in a flexible flow system

Flexible manufacturing systems (FMSs) are a class of automated systems that can be used to improve productivity in batch manufacturing. Four stages of decision making have been defined for an FMS—the design, planning, scheduling, and control stages. This research focuses on the planning stage, and specifically in the area of scheduling batches of parts through the system.The literature to date on the FMS planning stage has mostly focused on the machine grouping, tool loading, and parttype selection problems. Our research carries the literature a step further by addressing the problem of scheduling batches of parts. Due to the use of serial-access material-handling systems in many FMSs, the batch-scheduling problem is modeled for a flexible flow system (FFS). This model explicitly accounts for setup times between batches that are dependent on their processing sequence.A heuristic procedure is developed for this batch-scheduling problem—the Maximum Savings (MS) heuristic. The MS heuristic is based upon the savings in time associated with a particular sequence and selecting the one with the maximum savings. It uses a two-phase method, with the savings being calculated in phase I, while a branch-and-bound procedure is employed to seek the best heuristic solution in phase II. Extensive computational results are provided for a wide variety of problems. The results show that the MS heuristic provides good-quality solutions.     

New quadratic models for the maximum weighted cut problem

New quadratic models are proposed to improve the upper-bound estimates in the maximum weighted cut problem. They are found by two original methods for deriving redundant quadratic constraints. A well-known linear model is shown to follow from the models proposed. Recommendations on how to develop its strengthened analogs are given. This study is partially sponsored from the grant UM2-2574-KV-03 (CRDF Cooperative Grants Program). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 63—75, January–February 2006.     

Real-world extensions to scheduling algorithms based on lagrangian relaxation

Recently, efficient scheduling algorithms based on Lagrangian relaxation have been proposed for scheduling parallel machine systems and job shops. In this article, we develop real-world extensions to these scheduling methods. In the first part of the paper, we consider the problem of scheduling single operation jobs on parallel identical machines and extend the methodology to handle multiple classes of jobs, taking into account setup times and setup costs. The proposed methodology uses Lagrangian relaxation and simulated annealing in a hybrid framework. In the second part of the paper, we consider a Lagrangian relaxation based method for scheduling job shops and extend it to obtain a scheduling methodology for a real-world flexible manufacturing system with centralized material handling. This research was supported in part by the Office of Naval Research and the Department of Science and Technology grant N00014-93-1017.