Relaxation of Alternating Iterative Algorithms for the Cauchy Problem Associated with the Modified Helmholtz Equation

We propose two algorithms involving the relaxation of either the given Dirichlet data or the prescribed Neumann data on the over-specified boundary, in the case of the alternating iterative algorithm of Kozlov, Maz'ya and Fomin(1991) applied to Cauchy problems for the modified Helmholtz equation. A convergence proof of these relaxation methods is given, along with a stopping criterion. The numerical results obtained using these procedures, in conjunction with the boundary element method (BEM), show the numerical stability, convergence, consistency and computational efficiency of the proposed methods.     

Branching strategies to improve regularity of crew schedules in ex-urban public transit

We discuss timetables in ex-urban bus traffic that consist of many trips serviced every day together with some exceptions that do not repeat daily. Traditional optimization methods for vehicle and crew scheduling in such cases usually produce schedules that contain irregularities which are not desirable especially from the point of view of the bus drivers. We propose a solution method which improves regularity while partially integrating the vehicle and crew scheduling problems. The approach includes two phases: first we solve the LP relaxation of a set covering formulation, using column generation together with Lagrangean relaxation techniques. In a second phase, we generate integer solutions using a new combination of local branching and various versions of follow-on branching. Numerical tests with artificial and real instances show that regularity can be improved significantly with no or just a minor increase of costs.     

Design of self-regulating production control systems by Tradeoffs Programming

Self-regulating Production Control Systems (SPCSs) include production control systems such as kanban, buffered lines, base-stock, and their variations and combinations. In this work we develop and implement, for SPCS design, a new simulation-based optimization method called Tradeoffs Programming (TOP). TOP is a technique closely related to multi-objective dynamic programming that attempts to optimize inseparable problems. TOP is based on the idea that given correctly defined performance measures, many systems are nearly separable, and we can decompose the overall system using efficiency frontiers of simulated performance measures of the subsystems. We apply this technique to SPCS design and perform a number of experiments to validate and analyze our algorithm. We find TOP to be very accurate, extremely robust, and widely applicable.     

Topology optimization of continuum structures with local stress constraints

We introduce an extension of current technologies for topology optimization of continuum structures which allows for treating local stress criteria. We first consider relevant stress criteria for porous composite materials, initially by studying the stress states of the so-called rank 2 layered materials. Then, on the basis of the theoretical study of the rank 2 microstructures, we propose an empirical model that extends the power penalized stiffness model (also called SIMP for Solid Isotropic Microstructure with Penalization for inter-mediate densities). In a second part, solution aspects of topology problems are considered. To deal with the so-called ‘singularity’ phenomenon of stress constraints in topology design, an ϵ-constraint relaxation of the stress constraints is used. We describe the mathematical programming approach that is used to solve the numerical optimization problems, and show results for a number of example applications. © 1998 John Wiley & Sons, Ltd.     

Capacitated multicommodity network flow problems with piecewise linear concave costs

Lagrangian techniques have been commonly used to solve the capacitated multi-commodity network flow problem with piecewise linear concave costs. In this paper, we show that the resulting lower bounds are no better than those obtained by the linear programming relaxation and focus on developing algorithms based on the latter. For that purpose, we characterize structural properties of the optimal solution of the linear programming relaxation and propose a heuristic solution approach that uses these properties to transform the fractional solution into an integer one. Our computational experiments show the effectiveness of the algorithm.     

Decomposition of Petri nets and Lagrangian relaxation for solving routing problems for AGVs

In this paper, we propose a Lagrangian relaxation method for solving routing problems for multiple AGVs by decomposition of timed Petri nets. The AGV routing problem is represented by an optimal transition firing sequence problem for timed Petri nets. The timed Petri net is decomposed into several subnets in which the subproblem for each subnet can be easily solved by Dijkstra's algorithm. We show that each subproblem generated by each subnet is polynomially solvable. The optimality of the solution can be evaluated by the duality gap derived by the Lagrangian relaxation method. The performance of the proposed method is compared with a conventional optimisation algorithm with the penalty function method. The effectiveness of the proposed method is demonstrated.     

Sequential synthesis of type II colloidal CdTe/CdSe core-shell nanocrystals

Colloidal type II CdTe/CdSe nanocrystals were synthesized by sequential addition of a tri-n-octylphosphine telluride (TOPTe)/TOP solution and several shell-precursor solutions to a CdO/TOP solution; the shell-precursor solutions consisted of CdO and TOPSe in TOP. For the growth of the CdTe core, the TOPTe/TOP solution was swiftly added to the CdO/TOP solution at a higher temperature (300 degrees C) than the growth temperature (250 degrees C). For the growth of the CdSe shell, in contrast, the CdO/TOPSe/TOP solution was slowly added to the CdTe/TOP solution at a lower temperature than the growth temperature (200-240 degrees C). The temporal evolution of the optical properties of the growing core-shell nanocrystals was monitored in detail. During the growth of the CdSe shell, the core-shell nanocrystals exhibited interesting changes in photoluminescence (PL) properties. The highest PL efficiency (approximately 38 %) was detected from core-shell nanocrystals with a CdSe shell thickness of 0.4-0.5 nm (indicated by TEM); the formation of the first monolayer is proposed. Our synthetic approach is well suited to a practical realization of engineering materials with bandgaps in the near-IR and IR spectral ranges.     

Prediction of viscoelastic material functions from constant stress- or strain-rate experiments

To predict durability of polymeric structures an information on polymer’s long-term properties in the form of relaxation modulus and/or creep compliance is required. It is well known that determination of relaxation or creep properties from experimental data is an inverse problem, which, due to presence of experimental errors in input data, becomes ill-posed. To find a stable solution using standard integration schemes is practically impossible. In this paper we propose a “hands-on” methodology which bypasses the solution of ill-posed integral equation and allows finding long-term relaxation or creep properties from simple constant strain rate or constant stress-rate experiments performed at different temperatures. The proposed approach can be applied not only for characterization of viscoelastic materials in solid state but can also be used for prediction of time-dependent properties of polymer melts. The paper presents the detailed steps of the proposed method as well as its validation on several simulated and real experimental data. It has been shown that the proposed approach can accurately reconstruct the desired long-term time-dependent properties obtained in traditional way (i.e., from step loading).     

Material design of elastic structures using Voronoi cells

New tools for the design of metamaterials with periodic microarchitectures are presented. Initially, a two‐scale material design approach is adopted. At the structure scale, the material effective properties and their spatial distribution are obtained through a Free Material Optimization technique. At the microstructure scale, the material microarchitecture is designed by appealing to a Topology Optimization Problem (TOP). The TOP is based on the topological derivative and the level set function. The new proposed tools are used to facilitate the search of the optimal microarchitecture configuration. They consist of the following: (i) a procedure to choose an adequate shape of the unit cell domain where the TOP is formulated and shapes of Voronoi cells associated with Bravais lattices are adopted and (ii) a procedure to choose an initial material distribution within the Voronoi cell being utilized as the initial configuration for the iterative TOP.     

A Branch-and-price algorithm for placement routing for a multi-head beam-type component placement tool

We develop a branch-and-price procedure for a placement routing problem for a multi-head beam-type component placement tool. The problem is modelled as an integer programming model with a huge number of variables, each of which corresponds to a placement route. Its linear programming relaxation is solved by a column generation method. For the column generation subproblem to determine the columns to be added, we develop a dynamic programming procedure. We also propose an effective branching rule to partition the current solution space to eliminate the current fractional solution. Through experiments using real tool data, we observe that the LP relaxation solution value is noticeably close to an integer optimal solution value and hence the integer program formulation and the column generation approach are effective.     

Profit-oriented disassembly-line balancing

As product and material recovery has gained importance, disassembly volumes have increased, justifying construction of disassembly lines similar to assembly lines. Recent research on disassembly lines has focused on complete disassembly. Unlike assembly, the current industry practice involves partial disassembly with profit-maximization or cost-minimization objectives. Another difference between assembly and disassembly is that disassembly involves additional precedence relations among tasks due to processing alternatives or physical restrictions. In this study, we define and solve the profit-oriented partial disassembly-line balancing problem. We first characterize different types of precedence relations in disassembly and propose a new representation scheme that encompasses all these types. We then develop the first mixed integer programming formulation for the partial disassembly-line balancing problem, which simultaneously determines (1) the parts whose demand is to be fulfilled to generate revenue, (2) the tasks that will release the selected parts under task and station costs, (3) the number of stations that will be opened, (4) the cycle time, and (5) the balance of the disassembly line, i.e. the feasible assignment of selected tasks to stations such that various types of precedence relations are satisfied. We propose a lower- and upper-bounding scheme based on linear programming relaxation of the formulation. Computational results show that our approach provides near optimal solutions for small problems and is capable of solving larger problems with up to 320 disassembly tasks in reasonable time.     

A single-machine distributed scheduling methodology using cooperative interaction via coupling agents

This paper considers a single-machine scheduling problem where the decision authorities and information are distributed in multiple subproduction systems. Subproduction systems share the single machine and must cooperate with one another to achieve a global goal of minimizing a linear function of the completion times of the jobs; e.g., total weighted completion times. It is assumed that neither the subproduction systems nor the shared machine have complete information about the entire system. The associated scheduling problems are formulated as zero-one integer programs. The solution approach is based on Lagrangian relaxation techniques modified to require less global information. Specifically, there is no need for a global upper bound, or a single master problem that has a complete view of all the coupling constraints. The proposed methodology exhibits a promising performance when experimentally compared to the Lagrangian relaxation with a subgradient method with the added benefit that can be applied to situations with more restrictive information sharing.     

Iterative coupling of FEM and BEM in 3D transient elastodynamics

A domain decomposition approach is presented for the transient analysis of three-dimensional wave propagation problems. The subdomains are modelled using the FEM and/or the BEM, and the coupling of the subdomains is performed in an iterative manner, employing a sequential Neumann–Dirichlet interface relaxation algorithm which also allows for an independent choice of the time step length in each subdomain. The approach has been implemented for general 3D problems. In order to investigate the convergence behaviour of the proposed algorithm, using different combinations of FEM and BEM subdomains, a parametric study is performed with respect to the choice of the relaxation parameters. The validity of the proposed method is shown by means of two numerical examples, indicating the excellent accuracy and applicability of the new formulation.     

Iterative coupling of FEM and BEM in 3D transient elastodynamics

A domain decomposition approach is presented for the transient analysis of three-dimensional wave propagation problems. The subdomains are modelled using the FEM and/or the BEM, and the coupling of the subdomains is performed in an iterative manner, employing a sequential Neumann–Dirichlet interface relaxation algorithm which also allows for an independent choice of the time step length in each subdomain. The approach has been implemented for general 3D problems. In order to investigate the convergence behaviour of the proposed algorithm, using different combinations of FEM and BEM subdomains, a parametric study is performed with respect to the choice of the relaxation parameters. The validity of the proposed method is shown by means of two numerical examples, indicating the excellent accuracy and applicability of the new formulation.     

Shear Modulus in Viscoelastic Solid 4He

The complex shear modulus of solid ⁴He exhibits an anomaly in the same temperature region where torsion oscillators show a change in period. We propose that the observed stiffening of the shear modulus with decreasing temperature can be well described by the response of glassy components inside of solid ⁴He. Since glass is an anelastic material, we utilize the viscoelastic approach to describe its dynamics. The viscoelastic component possesses an increasing relaxation as temperature decreases. The response functions thus derived are identical to those obtained for a glassy, time-delayed restoring back-action. By generalizing the viscoelastic equations for stress and strain to a multiphase system of constituents, composed of patches with different damping and relaxation properties, we predict that the maximum change of the magnitude of the shear modulus and the maximum height of the dissipation peak are independent of an applied external frequency. The same response expressions allow us to calculate the temperature dependence of the shear modulus?? amplitude and dissipation. Finally, we demonstrate that a Vogel-Fulcher-Tammann (VFT) relaxation time is in agreement with available experimental data.     

Multi‐time‐step and two‐scale domain decomposition method for non‐linear structural dynamics

In this paper we propose a method to improve the means of taking into account the specific time‐scale and space‐scale characteristics in time‐dependent non‐linear problems. This method enables the use of arbitrary time steps in each subdomain: these can be coupled by prescribing continuous velocities at the interfaces, which are modelled using a dual Schur formulation. For certain subdomains, in space, we adopt a two‐scale resolution technique inspired by the multigrid methods in order to obtain the part of the solution related to small variation lengths on a refined scale and the part corresponding to large variation lengths on a coarse scale. For non‐linear problems, we propose an algorithm with a single iteration level to deal with both the non‐linear equilibrium and the two space scales thanks to a two‐grid method in which the relaxation steps are performed using a non‐linear, preconditioned conjugate gradient algorithm. Finally, we present an example which demonstrates the feasibility of the method. Copyright © 2003 John Wiley & Sons, Ltd.     

Tactical models for hierarchical capacitated lot-sizing problems with setups and changeovers

In this paper, we propose a modelling approach for the medium term planning of manufacturing systems characterized by coexisting large volume and small volume products, in which changeovers play a critical role in achieving maximum efficiency. Although the model is based upon the large time bucket paradigm, it is capable of representing start-ups by sequencing the lots of items produced in long sequences. Specifically, we consider a capacitated lot-sizing problem with parallel machines, in which the products have a three-level hierarchical structure: end items are aggregated into families, which in turn are aggregated into types. Minor set-ups and major changeovers take place when switching between families within a type or between types, respectively. The resulting mathematical programming problem is decomposed via Lagrangean relaxation, leading to sub-problems that can be solved in polynomial time. The whole approach has been validated by applying it to large size case studies drawn from the textile industry.     

Single-item production–delivery scheduling problem with stage-dependent inventory costs and due-date considerations

This paper studies an integrated scheduling problem for a single-item, make-to-order supply chain system consisting of one supplier, one capacitated transporter and one customer. Specifically, we assume the existence in the production stage of an intermediate inventory that works as a buffer to balance the production rate and the transportation speed. Jobs are first processed on a single machine in the production stage, and then delivered to the pre-specified customer by a capacitated vehicle in the delivery stage. Each job has a due date specified by the customer, and must be delivered to the customer before its due date. Moreover, it is assumed that a job that is finished before its departure date or arrives at the customer before its due date will incur a stage-dependent corresponding inventory cost (WIP inventory, finished-good inventory or customer inventory cost). The objective is to find a coordinated production and delivery schedule such that the sum of setup, delivery and inventory costs is minimised. We formulate the problem as a nonlinear model in a general way and provide some properties. We then derive a precise instance from the general model and develop a heuristic algorithm for solving this precise instance. In order to evaluate the performance of the heuristic algorithm, we propose a simple branch-and-bound (B&B) approach for small-size problems, and a lower bound based on the Lagrangian relaxation method for large-size problems. Computational experiments show that the heuristic algorithm performs well on randomly generated problems.     

On the optimal design of water distribution networks: a practical MINLP approach

We propose a practical solution method for real-world instances of a water-network optimization problem with fixed topology using a nonconvex continuous NLP (NonLinear Programming) relaxation and a MINLP (Mixed Integer NonLinear Programming) search. Our approach employs a relatively simple and accurate model that pays some attention to the requirements of the solvers that we employ. Our view is that in doing so, with the goal of calculating only good feasible solutions, complicated algorithmics can be confined to the MINLP solver. We report successful computational experience using available open-source MINLP software on problems from the literature and on difficult real-world instances. An important contribution of this paper is that the solutions obtained, besides being low cost, are immediately usable in practice because they are characterized by an allocation of diameters to pipes that leads to a correct hydraulic operation of the network. This is not the case for most of the other methods presented in the literature.