This paper presents a unified approach forbottleneckcapacity expansion problems. In the bottleneck capacity expansion problem, BCEP, we are given a finite ground set E, a family Fof feasible subsets of E and a nonnegative real capacity ĉefor all e ∈ E. Moreover, we are given monotone increasing cost functions f e for increasing the capacity of the elements e ∈ E as well as a budget B. The task is to determine new capacities ce ≥ ĉe such that the objective function given by maxF∈F mine∈F ce is maximized under the sideconstraint that the overall expansion cost does not exceed the budget B.We introduce an algebraic model for defining the overall expansion cost and for formulating the budget constraint. This models allows to capturevarious types of budget constraints in one general model.Moreover, wediscuss solution approaches for the general bottleneck capacityexpansion problem. For an important subclass of bottleneck capacity expansion problems we propose algorithms which perform a strongly polynomial number ofsteps. In this manner we generalize and improve a recent result ofZhang et al. [15].

In this paper, we consider a repair-cost limit replacement problem with imperfect repair and develop a graphical method to determine the optimal repair-cost limit which minimizes the expected cost per unit time in the steady-state, using the Lorenz transform of the underlying repair-cost distribution function. The method proposed can be applied to an estimation problem of the optimal repair-cost limit from empirical repair-cost data. Numerical examples are devoted to examine asymptotic properties of the non-parametric estimator for the optimal repair-cost limit.

A Levy jump process is a continuous-time, real-valued stochasticprocess which has independent and stationary increments, with no Browniancomponent. We study some of the fundamental properties of Levy jumpprocesses and develop (s,S) inventory models for them. Of particularinterest to us is the gamma-distributed Levy process, in which the demandthat occurs in a fixed period of time has a gamma distribution.We study the relevant properties of these processes, and we develop aquadratically convergent algorithm for finding optimal (s,S) policies. Wedevelop a simpler heuristic policy and derive a bound on its relative cost. For the gamma-distributed Levy process this bound is 7.9% ifbackordering unfilled demand is at least twice as expensive as holdinginventory.Most easily-computed (s,S) inventory policies assume theinventory position to be uniform and assume that there is no overshoot. Ourtests indicate that these assumptions are dangerous when the coefficient ofvariation of the demand that occurs in the reorder interval is less than one. This is often the case for low-demand parts that experience sporadic orspiky demand. As long as the coefficient of variation of the demand thatoccurs in one reorder interval is at least one, and the service level isreasonably high, all of the polices we tested work very well. However evenin this region it is often the case that the standard Hadley–Whitin costfunction fails to have a local minimum.

This paper is devoted to the following version of the single machine preemptive scheduling problem of minimizing the weighted number of late jobs. A processing time, a release date, a due date and a weight of each job are given. Certain jobs are specified to be completed in time, i.e., their due dates are assigned to be deadlines, while the other jobs are allowed to be completed after their due dates. The release/due date intervals are nested, i.e., no two of them overlap (either they have at most one common point or one covers the other). Necessary and sufficient conditions for the completion of all jobs in time are considered, and an O(nlogn) algorithm (where n is the number of jobs) is proposed for solving the problem of minimizing the weighted number of late jobs in case of oppositely ordered processing times and weights.

We present here models and algorithms for the construction of efficient path systems, robust to possible variations of the characteristics of the network. We propose some interpretations of these models and proceed to numerical experimentations of the related algorithms. We conclude with a discussion of the way those concepts may be applied to the design of a Public Transportation System.

We study the problem of scheduling jobs on a serial batching machineto minimize total tardiness. Jobs of the same batch start and arecompleted simultaneously and the length of a batch equals the sum ofthe processing times of its jobs. When a new batch starts, a constantsetup time s occurs. This problem 1| s-batch| ∑Ti isknown to be NP-Hard in the ordinary sense. In this paper we show thatit is solvable in pseudopolynomial time by dynamic programming.

For a given partial solution,the partial inverse problem is to modify the coefficientssuch that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum.In this paper, we show that the partial inverseassignment problem and the partial inverse minimum cut problem are NP-hard ifthere are bound constraints on the changes of coefficients.

The simple plant location problem (SPLP) is considered and a genetic algorithm is proposed to solve this problem. By using the developed algorithm it is possible to solve SPLP with more than 1000 facility sites and customers. Computational results are presented and compared to dual based algorithms.