Optimal allocation and processing time decisions on non-identical parallel CNC machines: ϵ-constraint approach

When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. In this paper, we deal with making optimal machine-job assignments and processing time decisions so as to minimize total manufacturing cost while the makespan being upper bounded by a known value, denoted as ?-constraint approach for a bicriteria problem. We then give optimality properties for the resulting single criterion problem. We provide alternative methods to compute cost lower bounds for partial schedules, which are used in developing an exact (branch and bound) algorithm. For the cases where the exact algorithm is not efficient in terms of computation time, we present a recovering beam search algorithm equipped with an improvement search procedure. In order to find improving search directions, the improvement search algorithm uses the proposed cost bounding properties. Computational results show that our lower bounding methods in branch and bound algorithm achieve a significant reduction in the search tree size that we need to traverse. Also, our recovering beam search and improvement search heuristics achieve solutions within 1% of the optimum on the average while they spent much less computational effort than the exact algorithm.     

Lower bounds for the earliness–tardiness scheduling problem on parallel machines with distinct due dates

This paper addresses the parallel machine scheduling problem in which the jobs have distinct due dates with earliness and tardiness costs. New lower bounds are proposed for the problem, they can be classed into two families. First, two assignment-based lower bounds for the one-machine problem are generalized for the parallel machine case. Second, a time-indexed formulation of the problem is investigated in order to derive efficient lower bounds throught column generation or Lagrangean relaxation. A simple local search algorithm is also presented in order to derive an upper bound. Computational experiments compare these bounds for both the one machine and parallel machine problems and show that the gap between upper and lower bounds is about 1.5%.     

Fast computation of bounds for two-terminal network reliability

In this paper, an algorithm for the fast computation of network reliability bounds is proposed. The evaluation of the network reliability is an intractable problem for very large networks, and hence approximate solutions based on reliability bounds have assumed importance. The proposed bounds computation algorithm is based on an efficient BDD representation of the reliability graph model and a novel search technique to find important minpaths/mincuts to quickly reduce the gap between the reliability upper and lower bounds. Furthermore, our algorithm allows the control of the gap between the two bounds by controlling the overall execution time. Therefore, a trade-off between prediction accuracy and computational resources can be easily made in our approach. The numerical results are presented for large real example reliability graphs to show the efficacy of our approach.     

A dynamic bounding algorithm for approximating multi-state two-terminal reliability

This paper modifies Jane and Laih’s (2008) exact and direct algorithm to provide sequences of upper bounds and lower bounds that converge to the NP-hard multi-state two-terminal reliability. Advantages of the modified algorithm include (1) it does not require a priori the lower and/or upper boundary points of the network, (2) it derives a series of increasing lower bounds and a series of decreasing upper bounds simultaneously, guaranteed to enclose the exact reliability value, and (3) trade-off between accuracy and execution time can be made to ensure an exact difference between the upper and lower bounds within an acceptable time. Examples are analyzed to illustrate the bounding algorithm, and to compare the bounding algorithm with existing algorithms. Computational experiments on a large network are conducted to realize the performance of the bounding algorithm.     

Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines. The aim of the article is to develop a Lagrangian heuristic to obtain good solutions to this problem and good lower bounds to certify the quality of solutions. Based on a strong reformulation of the problem as a shortest path problem, the Lagrangian relaxation is applied to the demand constraints (flow constraint) and the relaxed problem is decomposed per period and per machine. The subgradient optimization method is used to update the Lagrangian multipliers. A primal heuristic, based on transfers of production, is designed to generate feasible solutions (upper bounds). Computational results using data from the literature are presented and show that our method is efficient, produces lower bounds of good quality and competitive upper bounds, when compared with the bounds produced by another method from the literature and by high-performance MIP software.     

The two-machine total completion time flow shop problem

In this paper we study the NP-hard scheduling problem of minimizing total completion time in a two-machine flow shop. Five known lower bounds are discussed and two new ones are presented. A new dominance criterion is also proposed. Several versions of a branch and bound method are derived by applying, both individually and combined, these lower bounds. A heuristic procedure is also presented that uses a constructive O(n²) time method, which computes a good starting solution, together with a neighborhood search based on pairwise interchanges. Computational results show that the exact method can handle problems of up to 30 jobs in size within a reasonable amount of time and that the heuristic procedure has an average error of less than 0.5% from the optimal value and less than 2.7% from the lower bound.     

A branch and search algorithm for a class of nonlinear knapsack problems

This paper discusses a class of nonlinear knapsack problems where the objective function is quadratic. The method is a branch and search procedure which includes an efficient algorithm to find the continuous (relaxed) solution and a reduction rule which computes tight lower and upper bounds on the integer variables.     

Lower bounds on the pathwidth of some grid-like graphs

We present proofs of lower bounds on the node search number of some grid-like graphs including two-dimensional grids, cylinders, tori and a variation we call “orb-webs”. Node search number is equivalent to pathwidth and vertex separation, which are all important graph parameters. Since matching upper bounds are not difficult to obtain, this implies that the pathwidth of these graphs is easily computed, because the bounds are simple functions of the graph dimensions. We also show matching upper and lower bounds on the node search number of equidimensional tori which are one less than the obvious upper bound.     

A reduction dynamic programming algorithm for the bi-objective integer knapsack problem

This paper presents a backward state reduction dynamic programming algorithm for generating the exact Pareto frontier for the bi-objective integer knapsack problem. The algorithm is developed addressing a reduced problem built after applying variable fixing techniques based on the core concept. First, an approximate core is obtained by eliminating dominated items. Second, the items included in the approximate core are subject to the reduction of the upper bounds by applying a set of weighted-sum functions associated with the efficient extreme solutions of the linear relaxation of the multi-objective integer knapsack problem. Third, the items are classified according to the values of their upper bounds; items with zero upper bounds can be eliminated. Finally, the remaining items are used to form a mixed network with different upper bounds. The numerical results obtained from different types of bi-objective instances show the effectiveness of the mixed network and associated dynamic programming algorithm.     

A recursive exact algorithm for weighted two-dimensional cutting

Gilmore and Gomory's algorithm is one of the better actually known exact algorithms for solving unconstrained guillotine two-dimensional cutting problems. Herz's algorithm is more effective, but only for the unweighted case. We propose a new exact algorithm adequate for both weighted and unweighted cases, which is more powerful than both algorithms. The algorithm uses dynamic programming procedures and one-dimensional knapsack problem to obtain efficient lower and upper bounds and important optimality criteria which permit a significant branching cut in a recursive tree-search procedure. Recursivity, computational power, adequateness to parallel implementations, and generalization for solving constrained two-dimensional cutting problems, are some important features of the new algorithm.     

A theoretical comparison between the simplex method and the basic line search algorithm

A theoretical comparison between the simplex method (SM) and the basic line search method (BLSA) is presented. The explicit formulae for the upper and lower bounds in the BLSA are provided using SM. Further, it is shown that both methods are operationally equivalent.     

New reliability bounds for coherent systems

In 1970, Esary and Proschan proposed simple formulae for the system reliability lower bound and system reliability upper bound. Their formulae of reliability bounds have been classic and have been incorporated into almost all recent textbooks on reliability. In this paper, we decompose a coherent system into several consecutive-k-out-of-n : F(G) systems, and then based upon their exact formulae for system reliabilities, we develop new formulae for both reliability lower bound and reliability upper bound for the coherent system. In addition, we show that the new proposed reliability bounds are superior to those of Esary and Proschan for all coherent systems when the minimal cut/path sets have elements in common. Numerical results are reported, compared and discussed for various systems.     

An Inexact SQP Newton Method for Convex SC<Superscript>1</Superscript> Minimization Problems

In this paper, we present a globally and superlinearly convergent inexact SQP Newton method for solving large scale convex SC ¹ minimization problems under mild conditions. In particular, the BD-regularity assumption made by Pang and Qi in Journal of Optimization Theory and Applications, 85 (1995), pp. 633–648 is replaced by a much more realistic assumption. Our numerical experiments conducted on least squares semidefinite programming with lower and upper bounds demonstrate that our inexact SQP Newton method is much more efficient than its exact version and is competitive with existing methods when the number of simple constraints is very large.     

双线性非协调有限元逼近的梯度恢复后验误差估计

给出了二阶椭圆方程的双线性非协调有限元逼近的梯度恢复后验误差估计.该误差估计是在Q_1非协调元上得到的,并给出了误差的上下界.进一步证明该误差估计在拟一致网格上是渐进精确地.证明依赖于clement插值和Helmholtz分解,数值结果验证了理论的正确性.     

Overflow and losses in a network queue with a self-similar input

This paper considers a discrete time queuing system that models a communication network multiplexer which is fed by a self-similar packet traffic. The model has a finite buffer of size h, a number of servers with unit service time, and an input traffic which is an aggregation of independent source-active periods having Pareto-distributed lengths and arriving as Poisson batches. The new asymptotic upper and lower bounds to the buffer-overflow and packet-loss probabilities P are obtained. The bounds give an exact asymptotic of log P/log h when h → to ∞. These bounds decay algebraically slow with buffer-size growth and exponentially fast with excess of channel capacity over traffic rate. Such behavior of the probabilities shows that one can better combat traffic losses in communication networks by increasing channel capacity rather than buffer size. A comparison of the obtained bounds and the known upper and lower bounds is done. This revised version was published online in June 2006 with corrections to the Cover Date.     

Scatter search for project scheduling with resource availability cost

This paper considers a project scheduling problem with the objective of minimizing resource availability costs, taking into account a deadline for the project and precedence relations among the activities. Exact methods have been proposed for solving this problem, but we are not aware of existing heuristic methods. Scatter search is used to tackle this problem, and our implementation incorporates advanced strategies such as dynamic updating of the reference set, the use of frequency-based memory within the diversification generator, and a combination method based on path relinking. We also analyze the merit of employing a subset of different types when combining solutions. Extensive computational experiments involving more than 2400 instances are performed. For small instances, the performance of the proposed procedure is compared to optimal solutions generated by an exact cutting plane algorithm and upper and lower bounds from the literature. For medium and larger size instances, we developed simple multi-start heuristics and comparative results are reported.     

An exact algorithm for the network pricing problem

This work focuses on an improved exact algorithm for addressing an NP-hard network pricing problem. The method involves an efficient and partial generation of candidate solutions, a recursive scheme for generating improved upper bounds, and a column generation procedure for solving the network-structured subproblems. Its efficiency is assessed against both randomly generated instances involving three distinct topologies as well as instances based on real life situations in telecommunication and freight transportation.     

GUARANTEED BOUNDS FOR THE SOLUTION OF THE WAVE EQUATION

Abstract

Numerical solution of the wave equation in the form of close lower and upper bounds provides a secure a posteriori error estimate that can be used for efficient accuracy control. The method considered in this paper uses some monotone properties of the differential operator in the wave equation to construct bounds for the solution in the form of trigonometric polynomials of x. Aspects of the numerical implementation, the accuracy of the computed bounds and some numerical examples are discussed.     

A Posteriori Error Estimators of Gradient Recovery Type for Elliptic Obstacle Problems

In this paper, we present a posteriori error estimates of gradient recovery type for elliptic obstacle problems. The a posteriori error estimates provide both lower and upper error bounds. It is shown to be equivalent to the discretization error in an energy type norm for general meshes. Furthermore, when the solution is smooth and the mesh is uniform, it is shown to be asymptotically exact. Some numerical results which demonstrate the theoretical results are also reported in this paper.     

A Branch-and-price algorithm for a Vehicle Routing Problem with Cross-Docking

n this paper, we propose a reformulation and a Branch-and-price (BP) algorithm for the Vehicle Routing Problem with Cross-Docking (VRPCD). Our computational results indicate that the reformulation provides bounds much stronger than network flow bounds from previous studies. As a consequence, when BP and a Linear Programming based Branch-and-bound (LPBB) method (that relies on the network flow formulation) are run for the same restricted time limit, BP clearly dominates LPBB in terms of the quality of lower and upper bounds found during the search.