Scheduling a Single Server in a Two-machine Flow Shop

We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem. This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup times are equal and there are two distinct due dates. This problem is solved in O(n ³) time when all job processing times on the first machine are equal, and it is solved in O(n ⁴) time when all processing times on the second machine are equal. Received November 20, 2001; revised October 18, 2002 Published online: January 16, 2003     

On the Complexity of Non-preemptive Shop Scheduling with Two Jobs

In this note, we investigate the time complexity of non-preemptive shop scheduling problems with two jobs. First we study mixed shop scheduling where one job has a fixed order of operations and the operations of the other job may be executed in arbitrary order. This problem is shown to be binary NP-complete with respect to all traditional optimality criteria even if distinct operations of the same job require different machines. Moreover, we devise a pseudo-polynomial time algorithm which solves the problem with respect to all non-decreasing objective functions. Finally, when the job with fixed order of operations may visit a machine more than once, the problem becomes unary NP-complete. Then we discuss shop scheduling with two jobs having chain-like routings. It is shown that the problem is unary NP-complete with respect to all traditional optimality criteria even if one of the jobs has fixed order of operations and the jobs cannot visit a machine twice. Received July 28, 2001; revised May 15, 2002 Published online: July 26, 2002     

Semi On-Line Scheduling on Two Identical Machines

This paper investigates two different semi on-line scheduling problems on a two-machine system. In the first case, we assume that all jobs have their processing times in between p and rp . In the second case, we assume that the largest processing time is known in advance. We show that one has a best possible algorithm with worst case ratio 4/3 while LS is still the best possible for the other problem with ratio which is still in the worst case . Received: February 23, 1998; revised August 5, 1998     

Tighter Bounds on Preemptive Job Shop Scheduling with Two Machines

We consider the preemptive job shop scheduling problem with two machines, with the objective to minimize the makespan. We present an algorithm that finds a schedule of length at most P _max/2 greater than the optimal schedule length, where P _max is the length of the longest job. Received June 13, 2000     

Computation of Lagrange Multipliers for Linear Least Squares Problems with Equality Constraints

Received December 21, 2000; revised June 7, 2001     

An Adaptive Routing Algorithm for WK-Recursive Topologies

This paper presents an easy and straightforward routing algorithm for WK-recursive topologies. The algorithm, based on adaptive routing, takes advantage of the geometric properties of such topologies. Once a source node S and destination node D have been determined for a message communication, they characterize, at some level l, two virtual nodes and that respectively contain S but not D and D but not S. Such virtual nodes characterize other (where is the node degree for a fixed topology) virtual nodes of the same level that contain neither S nor D. Consequently, it is possible to locate triangles whose vertices are these virtual nodes with property to share the same path, called the self-routing path, directly connecting to . When the self-routing path is unavailable to transmit a message from S to D because of deadlock, fault, and congestion conditions, the routing strategy can follow what we call the triangle rule to deliver it. The proposed communication scheme has the advantage that 1) it is the same for all three conditions; 2) each node of a WK-recursive network, to transmit messages, does not require any information about their presence or location. Furthermore, this routing algorithm is able to tolerate up to faulty links. Received: July 19, 1998; revised May 17, 1999     

A New Well-Solvable Class of PNS Problems

A manufacturing system consists of operating units which convert their input materials into their output materials. In the problem of designing a process network, we have to find a suitable network of operating units which produces the desired products from the given raw materials. If we consider this process network design problem from a structural point of view, then we obtain a combinatorial optimization problem called the Process Network Synthesis or (PNS) problem. It is known that the PNS problem is NP-complete. Here, a new method is presented to reduce the solution of some more difficult PNS problems to the solution of simpler ones, and using this method, a new well-solvable class of PNS problems is established. Received February 12, 1999; revised October 24, 2000     

A Dual Framework for Lower Bounds of the Quadratic Assignment Problem Based on Linearization

A dual framework allowing the comparison of various bounds for the quadratic assignment problem (QAP) based on linearization, e.g. the bounds of Adams and Johnson, Carraresi and Malucelli, and Hahn and Grant, is presented. We discuss the differences of these bounds and propose a new and more general bounding procedure based on the dual of the linearization of Adams and Johnson. The new procedure has been applied to problems of dimension up to , and the computational results indicate that the new bound competes well with existing linearization bounds and yields a good trade off between computation time and bound quality. Received: February 5, 1999; revised August 24, 1999     

High-Order Time-Accurate Parallel Schemes for Parabolic Singularly Perturbed Problems with Convection

The first boundary value problem for a singularly perturbed parabolic equation of convection-diffusion type on an interval is studied. For the approximation of the boundary value problem we use earlier developed finite difference schemes, ɛ-uniformly of a high order of accuracy with respect to time, based on defect correction. New in this paper is the introduction of a partitioning of the domain for these ɛ-uniform schemes. We determine the conditions under which the difference schemes, applied independently on subdomains may accelerate (ɛ-uniformly) the solution of the boundary value problem without losing the accuracy of the original schemes. Hence, the simultaneous solution on subdomains can in principle be used for parallelization of the computational method. Received December 3, 1999; revised April 20, 2000     

Iterative Methods for Linear Complementarity Problems with Interval Data

A ] and an interval vector [b]. If all A∈[A] are H-matrices with positive diagonal elements, these methods are all convergent to the same interval vector [x ^*]. This interval vector includes the solution x of the linear complementarity problem defined by any fixed A∈[A] and any fixed b∈[b]. If all A∈[A] are M-matrices, then we will show, that [x ^*] is optimal in a precisely defined sense. We also consider modifications of those methods, which under certain assumptions on the starting vector deliver nested sequences converging to [x ^*]. We close our paper with some examples which illustrate our theoretical results. Received October 7, 2002; revised April 15, 2003 Published online: June 23, 2003 RID="*" ID="*" Dedicated to U. Kulisch on the occasion of his 70th birthday. We are grateful to the referee who has given a series of valuable comments.     

A Numerical Method to Verify the Elliptic Eigenvalue Problems Including a Uniqueness Property

We propose a numerical method to enclose the eigenvalues and eigenfunctions of second-order elliptic operators with local uniqueness. We numerically construct a set containing eigenpairs which satisfies the hypothesis of Banach's fixed point theorem in a certain Sobolev space by using a finite element approximation and constructive error estimates. We then prove the local uniqueness separately of eigenvalues and eigenfunctions. This local uniqueness assures the simplicity of the eigenvalue. Numerical examples are presented. Received: November 2, 1998; revised June 5, 1999     

An Adaptive Time Step Procedure for a Parabolic Problem with Blow-up

In this paper we introduce and analyze a fully discrete approximation for a parabolic problem with a nonlinear boundary condition which implies that the solutions blow up in finite time. We use standard linear elements with mass lumping for the space variable. For the time discretization we write the problem in an equivalent form which is obtained by introducing an appropriate time re-scaling and then, we use explicit Runge-Kutta methods for this equivalent problem. In order to motivate our procedure we present it first in the case of a simple ordinary differential equation and show how the blow up time is approximated in this case. We obtain necessary and sufficient conditions for the blow-up of the numerical solution and prove that the numerical blow-up time converges to the continuous one. We also study, for the explicit Euler approximation, the localization of blow-up points for the numerical scheme. Received October 4, 2001; revised March 27, 2002 Published online: July 8, 2002     

A Robust Smoother for Convection-Diffusion Problems with Closed Characteristics

In this paper we analyze a model problem for the convection-diffusion equation where the reduced problem has closed characteristics. A full upwinding finite difference scheme is used to discretize the problem. Additionally to the strength of the convection, an arbitrary amount of crosswind-diffusion can be added on the discrete level. We present a smoother which is robust w.r.t. the strength of convection and the amount of crosswind-diffusion. It is of Gauss–Seidel type using a downwind ordering. To handle the cyclic dependencies a frequency-filtering algorithm is used. The algorithm is of nearly optimal complexity ?(n log n). It is proved that it fulfills a robust smoothing property.     

Dynamic Programming Revisited: Improving Knapsack Algorithms

The contribution of this paper is twofold: At first an improved dynamic programming algorithm for the bounded knapsack problem is given. It decreases the running time for an instance with n items and capacity c from to , which is the same pseudopolynomial complexity as usually given for the 0--1 knapsack problem. In the second part a general approach based on dynamic programming is presented to reduce the storage requirements for combinatorial optimization problems where it is computationally more expensive to compute the explicit solution structure than the optimal solution value. Among other applications of this scheme it is shown that the 0--1 knapsack problem as well as the bounded knapsack problem can be solved in time and space. Received: October 15, 1998; revised March 10, 1999     

On the Stability of the Direct Elimination Method for Equality Constrained Least Squares Problems

A backward error analysis of the direct elimination method for linear equality constrained least squares problems is presented. It is proved that the solution computed by the method is the exact solution of a perturbed problem and bounds for data perturbations are given. The numerical stability of the method is related to the way in which the constraints are used to eliminate variables and these theoretical conclusions are confirmed by a numerical example. Received February 15, 1999; revised December 10, 1999     

Some Comments on Sequencing with Controllable Processing Times

Received March 30, 2001; revised October 22, 2001     

A New Multisection Technique in Interval Methods for Global Optimization

A new multisection technique in interval methods for global optimization is investigated, and numerical tests demonstrate that the efficiency of the underlying global optimization method can be improved substantially. The heuristic rule is based on experiences that suggest the subdivision of the current subinterval into a larger number of pieces only if it is located in the neighbourhood of a minimizer point. An estimator of the proximity of a subinterval to the region of attraction to a minimizer point is utilized. According to the numerical study made, the new multisection strategies seem to be indispensable, and can improve both the computational and the memory complexity substantially. Received May 31, 1999; revised January 20, 2000     

Acquisition of Complex Model Knowledge by Domain Theory-Controlled Generalization

Nearly all three-dimensional reconstruction methods lack proper model knowledge that reflects the scene. Model knowledge is required in order to reduce ambiguities which occur during the reconstruction process. It must comprise the scene and is therefore complex, and additionally difficult to acquire. In this paper we present an approach for the learning of complex model knowledge. A (large) sample set of three-dimensionally acquired buildings represented as graphs is generalized by the use of background knowledge. The background knowledge entails domain-specific knowledge and is utilized for the search guidance during the generalization process of EXRES. The generalization result is a distribution of relevant patterns which reduces ambiguities occurring in 3D object reconstruction (here: buildings). Three different applications for the 3D reconstruction of buildings from aerial images are executed whereas binary relations of so-called building atoms, namely tertiary nodes and faces, and building models are learned. These applications are evaluated based on (a) the estimated empirical generalization error and (b) the use of information coding theory and statistics by comparing the learned knowledge with non-available a priori knowledge. Received: June 3, 1998; revised November 5, 1998     

Descent Iterations for Improving Approximate Eigenpairs of Polynomial Eigenvalue Problems with General Complex Matrices

In this paper, we consider descent iterations with line search for improving an approximate eigenvalue and a corresponding approximate eigenvector of polynomial eigenvalue problems with general complex matrices, where an approximate eigenpair was obtained by some method. The polynomial eigenvalue problem is written as a system of complex nonlinear equations with nondifferentiable normalized condition. Convergence theorems for iterations are established. Finally, some numerical examples are presented to demonstrate the effectiveness of the iterative methods. Received April 9, 2001; revised October 2, 2001 Published online February 18, 2002