Machine Criticality Measures and Subproblem Solution Procedures in Shifting Bottleneck Methods: A Computational Study

We examine the effects of different machine criticality measures (MCMs) and subproblem solution procedures (SSPs) on the performance of Shifting Bottleneck (SB) methods for the problem of minimizing maximum lateness in a job shop. Extensive computational experiments show that for problems with balanced workloads and random routeings simple MCMs and SSPs can be used without affecting solution quality. Routeing structure affects the performance of the SB method significantly. We also find that, contrary to some previous studies, the problem of maintaining feasibility in the SB method is significant.     

The nonlinear programming method of Wilson,Han, and Powell with an augmented Lagrangian type line search function

Summary The paper represents an outcome of an extensive comparative study of nonlinear optimization algorithms. This study indicates that quadratic approximation methods which are characterized by solving a sequence of quadratic subproblems recursively, belong to the most efficient and reliable nonlinear programming algorithms available at present. The purpose of this paper is to analyse the theoretical convergence properties and to investigate the numerical performance in more detail. In Part 1, the exactL ₁-penalty function of Han and Powell is replaced by a differentiable augmented Lagrange function for the line search computation to be able to prove the global convergence and to show that the steplength one is chosen in the neighbourhood of a solution. In Part 2, the quadratic subproblem is exchanged by a linear least squares problem to improve the efficiency, and to test the dependence of the performance from different solution methods for the quadratic or least squares subproblem.     

Randomly generating test problems for fuzzy relational equations

Fuzzy relational equations play an important role in fuzzy set theory and fuzzy logic systems. To compare and evaluate the accuracy and efficiency of various solution methods proposed for solving systems of fuzzy relational equations as well as the associated optimization problems, a test problem random generator for systems of fuzzy relational equations is needed. In this paper, procedures for generating test problems of fuzzy relational equations with the sup-T{\mathcal{T}} composition are proposed for the cases of sup-T_M{\mathcal{T}_M}, sup-T_P{\mathcal{T}_P}, and sup-T_L{\mathcal{T}_L } compositions. It is shown that the test problems generated by the proposed procedures are consistent. Some properties are discussed to show that the proposed procedures randomly generate systems of fuzzy relational equations with various number of minimal solutions. Numerical examples are included to illustrate the proposed procedures.     

Weighted median algorithms for L1 approximation

The weighted median problem arises as a subproblem in certain multivariate optimization problems, includingL ₁ approximation. Three algorithms for the weighted median problem are presented and the relationships between them are discussed. We report on computational experience with these algorithms and on their use in the context of multivariateL ₁ approximation.This work was supported in part by National Science Foundation Grant CCR-8713893 and in part by a grant from The City University of New York PSC-CUNY Research Award program.     

Strong Stability and Non-smooth Data Error Estimates for Discretizations of Linear Parabolic Problems

We study smoothing properties of discretizations of a linear parabolic initial boundary value problem with a possibly non-selfadjoint elliptic operator. The solution at time t > 0 of this problem, as well as its time derivatives, are in L _r for initial values in L _s even when r > s. We show that similar strong stability results hold for discrete solutions obtained by discretizing in space by linear finite elements and in time by a class of A()-stable implicit rational multistep methods (including single step methods as a special case) with good smoothing properties, as well as for certain combinations of single step methods. Most of our results are derived from the corresponding L ₂-bounds, shown by semigroup techniques, together with a discrete Gagliardo-Nirenberg inequality, and generalize previously known estimates with respect to admissible problems and time discretization methods. Our techniques make it possible to obtain, e.g., supremum norm error estimates for initial data which are only required to be in L ₁.     

A parallel multisplitting solution of the least squares problem

The linear least squares problem, min_x∥Ax − b∥₂, is solved by applying a multisplitting (MS) strategy in which the system matrix is decomposed by columns into p blocks. The b and x vectors are partitioned consistently with the matrix decomposition. The global least squares problem is then replaced by a sequence of local least squares problems which can be solved in parallel by MS. In MS the solutions to the local problems are recombined using weighting matrices to pick out the appropriate components of each subproblem solution. A new two-stage algorithm which optimizes the global update each iteration is also given. For this algorithm the updates are obtained by finding the optimal update with respect to the weights of the recombination. For the least squares problem presented, the global update optimization can also be formulated as a least squares problem of dimension p. Theoretical results are presented which prove the convergence of the iterations. Numerical results which detail the iteration behavior relative to subproblem size, convergence criteria and recombination techniques are given. The two-stage MS strategy is shown to be effective for near-separable problems. © 1998 John Wiley & Sons, Ltd.     

Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops

In this paper, we consider a modified shifting bottleneck heuristic for complex job shops. The considered job shop environment contains parallel batching machines, machines with sequence-dependent setup times and reentrant process flows. Semiconductor wafer fabrication facilities (Wafer Fabs) are typical examples for manufacturing systems with these characteristics. Our primary performance measure is total weighted tardiness (TWT). The shifting bottleneck heuristic uses a disjunctive graph to decompose the overall scheduling into scheduling problems for single tool groups. The scheduling algorithms for these scheduling problems are called subproblem solution procedures (SSPs). In previous research, only subproblem solution procedures based on dispatching rules have been considered. In this paper, we are interested in how much we can gain in terms of TWT if we apply more sophisticated subproblem solution procedures like genetic algorithms for parallel machine scheduling. We conduct simulation experiments in a dynamic job shop environment in order to assess the performance of the suggested subproblem solution procedures. It turns out that using near to optimal subproblem solution procedures leads in many situations to improved results compared to dispatching-based subproblem solution procedures.     

Strong solutions to the Keller‐Segel system with the weak Ln /2 initial data and its application to the blow‐up rate

We shall show an exact time interval for the existence of local strong solutions to the Keller‐Segel system with the initial data u₀ in L^{n /2}_w (?ⁿ), the weak L^{n /2}‐space on ?ⁿ. If ‖u₀‖ is sufficiently small, then our solution exists globally in time. Our motivation to construct solutions in L^{n /2}_w (?ⁿ) stems from obtaining a self‐similar solution which does not belong to any usual L^p(?ⁿ). Furthermore, the characterization of local existence of solutions gives us an explicit blow‐up rate of ‖u (t)‖ for n /2 < p < ∞ as t → T_max, where T_max denotes the maximal existence time (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A hybrid radial basis functions collocation technique to numerically solve fractional advection–diffusion models

In this work, we propose a hybrid radial basis functions (RBFs) collocation technique for the numerical solution of fractional advection–diffusion models. In the formulation of hybrid RBFs (HRBFs), there exist shape parameter (c* ) and weight parameter (ϵ) that control numerical accuracy and stability. For these parameters, an adaptive algorithm is developed and validated. The proposed HRBFs method is tested for numerical solutions of some fractional Black–Sholes and diffusion models. Numerical simulations performed for several benchmark problems verified the proposed method accuracy and efficiency. The quantitative analysis is made in terms of L_∞, L₂, L_rms , and L_rel error norms as well as number of nodes N over space domain and time-step δt. Numerical convergence in space and time is also studied for the proposed method. The unconditional stability of the proposed HRBFs scheme is obtained using the von Neumann methodology. It is observed that the HRBFs method circumvented the ill-conditioning problem greatly, a major issue in the Kansa method.     

A surrogate and Lagrangian approach to constrained network problems

This paper presents the use of surrogate constraints and Lagrange multipliers to generate advanced starting solutions to constrained network problems. The surrogate constraint approach is used to generate a singly constrained network problem which is solved using the algorithm of Glover, Karney, Klingman and Russell [13]. In addition, we test the use of the Lagrangian function to generate advanced starting solutions. In the Lagrangian approach, the subproblems are capacitated network problems which can be solved using very efficient algorithms.The surrogate constraint approach is implemented using the multiplier update procedure of Held, Wolfe and Crowder [16]. The procedure is modified to include a search in a single direction to prevent periodic regression of the solution. We also introduce a reoptimization procedure which allows the solution from thekth subproblem to be used as the starting point for the next surrogate problem for which it is infeasible once the new surrogate constraint is adjoined.The algorithms are tested under a variety of conditions including: large-scale problems, number and structure of the non-network constraints, and the density of the non-network constraint coefficients.The testing clearly demonstrates that both the surrogate constraint and Langrange multipliers generate advanced starting solutions which greatly improve the computational effort required to generate an optimal solution to the constrained network problem. The testing demonstrates that the extra effort required to solve the singly constrained network subproblems of the surrogate constraints approach yields an improved advanced starting point as compared to the Lagrangian approach. It is further demonstrated that both of the relaxation approaches are much more computationally efficient than solving the problem from the beginning with a linear programming algorithm.     

Reoptimizing the 0-1 knapsack problem

In this paper we study the problem where an optimal solution of a knapsack problem on n items is known and a very small number k of new items arrive. The objective is to find an optimal solution of the knapsack problem with n+k items, given an optimal solution on the n items (reoptimization of the knapsack problem). We show that this problem, even in the case k=1, is NP-hard and that, in order to have effective heuristics, it is necessary to consider not only the items included in the previously optimal solution and the new items, but also the discarded items. Then, we design a general algorithm that makes use, for the solution of a subproblem, of an α-approximation algorithm known for the knapsack problem. We prove that this algorithm has a worst-case performance bound of , which is always greater than α, and therefore that this algorithm always outperforms the corresponding α-approximation algorithm applied from scratch on the n+k items. We show that this bound is tight when the classical Ext-Greedy algorithm and the algorithm are used to solve the subproblem. We also show that there exist classes of instances on which the running time of the reoptimization algorithm is smaller than the running time of an equivalent PTAS and FPTAS.     

Improving benders decomposition using a genetic algorithm

We develop and investigate the performance of a hybrid solution framework for solving mixed-integer linear programming problems. Benders decomposition and a genetic algorithm are combined to develop a framework to compute feasible solutions. We decompose the problem into a master problem and a subproblem. A genetic algorithm along with a heuristic are used to obtain feasible solutions to the master problem, whereas the subproblem is solved to optimality using a linear programming solver. Over successive iterations the master problem is refined by adding cutting planes that are implied by the subproblem. We compare the performance of the approach against a standard Benders decomposition approach as well as against a stand-alone solver (Cplex) on MIPLIB test problems.     

A primal-dual augmented Lagrangian

Nonlinearly constrained optimization problems can be solved by minimizing a sequence of simpler unconstrained or linearly constrained subproblems. In this paper, we consider the formulation of subproblems in which the objective function is a generalization of the Hestenes-Powell augmented Lagrangian function. The main feature of the generalized function is that it is minimized with respect to both the primal and the dual variables simultaneously. The benefits of this approach include: (i) the ability to control the quality of the dual variables during the solution of the subproblem; (ii) the availability of improved dual estimates on early termination of the subproblem; and (iii) the ability to regularize the subproblem by imposing explicit bounds on the dual variables. We propose two primal-dual variants of conventional primal methods: a primal-dual bound constrained Lagrangian (pdBCL) method and a primal-dual ℓ ₁ linearly constrained Lagrangian (pdℓ ₁LCL) method. Finally, a new sequential quadratic programming (pdSQP) method is proposed that uses the primal-dual augmented Lagrangian as a merit function.     

On quasilinear parabolic evolution equations in weighted L p -spaces

In this paper we develop a geometric theory for quasilinear parabolic problems in weighted L _p -spaces. We prove existence and uniqueness of solutions as well as the continuous dependence on the initial data. Moreover, we make use of a regularization effect for quasilinear parabolic equations to study the ω-limit sets and the long-time behaviour of the solutions. These techniques are applied to a free boundary value problem. The results in this paper are mainly based on maximal regularity tools in (weighted) L _p -spaces.     

Solitary wave solutions of the MRLW equation using radial basis functions

In this study, traveling wave solutions of the modified regularized long wave (MRLW) equation are simulated by using the meshless method based on collocation with well‐known radial basis functions. The method is tested for three test problems which are single solitary wave motion, interaction of two solitary waves and interaction of three solitary waves. Invariant values for all test problems are calculated, also L₂, L_∞ norms and values of the absolute error for single solitary wave motion are calculated. Numerical results by using the meshless method with different radial basis functions are presented. Figures of wave motions for all test problems are shown. Altogether, meshless methods with radial basis functions solve the MRLW equation very satisfactorily.© 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 235–247, 2012     

Spectral parameter power series for arbitrary order linear differential equations

Let L be the n‐th order linear differential operator Ly=?₀y⁽ⁿ⁾+?₁y^(n?1)+?+?_ny with variable coefficients. A representation is given for n linearly independent solutions of Ly=λry as power series in λ, generalizing the SPPS (spectral parameter power series) solution that has been previously developed for n=2. The coefficient functions in these series are obtained by recursively iterating a simple integration process, beginning with a solution system for λ=0. It is shown how to obtain such an initializing system working upwards from equations of lower order. The values of the successive derivatives of the power series solutions at the basepoint of integration are given, which provides a technique for numerical solution of n‐th order initial value problems and spectral problems.     

Periodic problems and problems with discontinuities for nonlinear parabolic equations

In this paper we study nonlinear parabolic equations using the method of upper and lower solutions. Using truncation and penalization techniques and results from the theory of operators of monotone type, we prove the existence of a periodic solution between an upper and a lower solution. Then with some monotonicity conditions we prove the existence of extremal solutions in the order interval defined by an upper and a lower solution. Finally we consider problems with discontinuities and we show that their solution set is a compact R -set in (CT, L ²(Z)).     

Zur Abhängigkeit der Lösung von ut + (h(u))x = 0 von ihren Anfangswerten

The above equation has some remarkable properties. In general a global solution exists in a weak sense only, and this solution is not reversible in time. Furthermore it is known, that the solutions for different initial values can coincide for all t ? t₀ > 0, and the set of the initial values with this property is convex. Conditions assuring that this set contains only one element are given. This means a weak form of time-reversibility. As a global solution exists only in the weak sense, the classical question concerning dependence of the solution on the initial values needs some modification. This problem is dealt with in suitable L₁-norms. It is shown, that the L₁-norm of the difference of two weak solutions with respect to the space variable does not increase in time.     

Numerical solution of the Rosenau–KdV–RLW equation by operator splitting techniques based on B‐spline collocation method

In the present study, the operator splitting techniques based on the quintic B‐spline collocation finite element method are presented for calculating the numerical solutions of the Rosenau–KdV–RLW equation. Two test problems having exact solutions have been considered. To demonstrate the efficiency and accuracy of the present methods, the error norms L₂ and L_∞ with the discrete mass Q and energy E conservative properties have been calculated. The results obtained by the method have been compared with the exact solution of each problem and other numerical results in the literature, and also found to be in good agreement with each other. A Fourier stability analysis of each presented method is also investigated.