An exact algorithm for the batch sequencing problem in a two-machine flow shop with limited buffer

This paper deals with the problem of makespan minimization in a flow shop with two machines when the input buffer of the second machine can only host a limited number of parts. Here we analyze the problem in the context of batch processing, i.e., when identical parts must be processed consecutively. We propose an exact branch-and-bound algorithm, in which the bounds exploit the batching nature of the problem. Extensive computational results show the effectiveness of the approach, and allow us to compare it with a previous heuristic approach. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 141–164, 1998     

A single-machine replacement model with learning

The replacement or upgrade of productive resources over time is an important decision for a manufacturing organization. The type of technology used in the productive resources determines how effectively the manufacturing operations can support the product and marketing strategy of the organization. Increasing operating costs (cost of maintenance, labor, and depreciation) over time force manufacturing organizations to periodically consider replacement or upgrade of their existing productive resources. We assume that there is a setup cost associated with the replacement of a machine, and that the setup cost is a nonincreasing function of the number of replacements made so far due to learning in setups. The operating cost of a newer machine is assumed to be lower than the operating cost of an older machine in any given period, except perhaps in the first period of operation of the new machine when the cost could be unusually high due to higher initial depreciation. A forward dynamic programming algorithm is developed which can be used to solve finite-horizon problems. We develop procedures to find decision and forecast horizons such that choices made during the decision horizon based only on information over the forecast horizon are also optimal for any longer horizon problem. Thus, we are able to obtain optimal results for what is effectively an infinite-horizon problem while only requiring data over a finite period of time. We present a numerical example to illustrate the decision/forecast horizon procedure, as well as a study of the effects of considering learning in making a series of machine replacement decisions. © 1993 John Wiley & Sons. Inc.     

Suboptimality of equal lot sizes for finite-horizon problems

We consider the problem of determining optimal lot sizes in continuous time for finite-horizon problems with stationary parameters. Using the average cost criterion, earlier researchers concluded that the optimal lot sizes should be equal. Using the conceptually rigorous discounted cash flow analysis, we show that equal lot sizes are optimal only when the finite horizon is an integral multiple of the optimal reorder interval for the infinite-horizon problem or, trivially, when the discount rate is zero. In all other cases, optimal lot sizes are either monotonically increasing or decreasing. Our characterization of the optimal policy is also useful in determining optimal lot sizes. © 1994 John Wiley & Sons, Inc.     

Continuous-time markov decision processes with nonzero terminal reward

In this article we consider a continuous-time Markov decision process with a denumerable state space and nonzero terminal rewards. We first establish the necessary and sufficient optimality condition without any restriction on the cost functions. The necessary condition is derived through the Pontryagin maximum principle and the sufficient condition, by the inherent structure of the problem. We introduce a dynamic programming approximation algorithm for the finite-horizon problem. As the time between discrete points decreases, the optimal policy of the discretized problem converges to that of the continuous-time problem in the sense of weak convergence. For the infinite-horizon problem, a successive approximation method is introduced as an alternative to a policy iteration method.     

On parallel machine replacement problems with general replacement cost functions and stochastic deterioration

The parallel machine replacement problem consists of finding a minimum cost replacement policy for a finite population of economically interdependent machines. In this paper, we formulate a stochastic version of the problem and analyze the structure of optimal policies under general classes of replacement cost functions. We prove that for problems with arbitrary cost functions, there can be optimal policies where a machine is replaced only if all machines in worse states are replaced (Worse Cluster Replacement Rule). We then show that, for problems with replacement cost functions exhibiting nonincreasing marginal costs, there are optimal policies such that, in any stage, machines in the same state are either all kept or all replaced (No‐Splitting Rule). We also present an example that shows that economies of scale in replacement costs do not guarantee optimal policies that satisfy the No‐Splitting Rule. These results lead to the fundamental insight that replacement decisions are driven by marginal costs, and not by economies of scale as suggested in the literature. Finally, we describe how the optimal policy structure, i.e., the No‐Splitting and Worse Cluster Replacement Rules, can be used to reduce the computational effort required to obtain optimal replacement policies. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

A primal-dual cutting-plane algorithm for all-integer programming

The integer programming literature contains many algorithms for solving all-integer programming problems but, in general, existing algorithms are less than satisfactory even in solving problems of modest size. In this paper we present a new technique for solving the all-integer, integer programming problem. This algorithm is a hybrid (i.e., primal-dual) cutting-plane method which alternates between a primal-feasible stage related to Young's simplified primal algorithm, and a dual-infeasible stage related to Gomory's dual all-integer algorithm. We present the results of computational testing.     

Application of perturbation analysis to a class of periodic review (s,S) inventory systems

In this article we apply perturbation analysis (PA), combined with conditional Monte Carlo, to obtain derivative estimators of the expected cost per period with respect to s and S, for a class of periodic review (s, S) inventory systems with full backlogging, linear holding and shortage costs, and where the arrivals of demands follow a renewal process. We first develop the general form of four different estimators of the gradient for the finite-horizon case, and prove that they are unbiased. We next consider the problem of implementing our estimators, and develop efficient methodologies for the infinite-horizon case. For the case of exponentially distributed demand interarrival times, we implement our estimators using a single sample path. Generally distributed interarrival times are modeled as phase-type distributions, and the implementation of this more general case requires a number of additional off-line simulations. The resulting estimators are still efficient and practical, provided that the number of phases is not too large. We conclude by reporting the results of simulation experiments. The results provide further validity of our methodology and also indicate that our estimators have very low variance. © 1994 John Wiley & Sons, Inc.     

Analytic solution for the nucleolus of a three‐player cooperative game

The nucleolus solution for cooperative games in characteristic function form is usually computed numerically by solving a sequence of linear programing (LP) problems, or by solving a single, but very large‐scale, LP problem. This article proposes an algebraic method to compute the nucleolus solution analytically (i.e., in closed‐form) for a three‐player cooperative game in characteristic function form. We first consider cooperative games with empty core and derive a formula to compute the nucleolus solution. Next, we examine cooperative games with nonempty core and calculate the nucleolus solution analytically for five possible cases arising from the relationship among the value functions of different coalitions. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Scheduling to minimize the total compression and late costs

We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 67–82, 1998     

Optimal production growth for the machine loading problem

This paper investigates a production growth logistics system for the machine loading problem (generalized transportation model), with a linear cost structure and minimum levels on total machine hours (resources) and product types (demands). An algorithm is provided for tracing the production growth path of this system, viz. in determining the optimal machine loading schedule of machines for product types, when the volumes of (i) total machine hours, and (ii) the total amount of product types are increased either individually for each total or simultaneously for both. Extensions of this methodology, when (i) the costs of production are convex and piecewise linear, and (ii) when the costs are nonconvex due to quantity discounts, and (iii) when there are upper bounds for productions are also discussed. Finally, a “goal-programming” production growth model where the specified demands are treated as just goals and not as absolute quantities to be satisfied is also considered.     

Scheduling parallel dedicated machines with the speeding‐up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two‐machine problem is NP‐hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst‐case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple‐choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Application of generalized benders decomposition to a nonlinear distribution system design problem

The Benders decomposition method has been successfully applied to a classic multistage, multiproduct distribution-system design problem with fixed and linear variable costs. In other applications, however, distribution-center variable throughput costs often show nonlinearity due to economies of scale. This article extends the standard problem formulation to a nonlinear distribution-system design problem and incorporates the generalized Benders decomposition method in an efficient solution algorithm. Approximate dual prices are generated by solving linear instead of concave subproblems. Thereafter these prices are adjusted to induce a more accurate representation of the concave cost function before they are incorporated in the Benders cuts, which are used to generate new binary solutions. The computational results are encouraging.     

Scheduling and lot streaming in two‐machine open shops with no‐wait in process

We study the problem of minimizing the makespan in no‐wait two‐machine open shops producing multiple products using lot streaming. In no‐wait open shop scheduling, sublot sizes are necessarily consistent; i.e., they remain the same over all machines. This intractable problem requires finding sublot sizes, a product sequence for each machine, and a machine sequence for each product. We develop a dynamic programming algorithm to generate all the dominant schedule profiles for each product that are required to formulate the open shop problem as a generalized traveling salesman problem. This problem is equivalent to a classical traveling salesman problem with a pseudopolynomial number of cities. We develop and test a computationally efficient heuristic for the open shop problem. Our results indicate that solutions can quickly be found for two machine open shops with up to 50 products. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Determining optimal growth paths in logistics operations

This paper considers a logistics system modelled as a transportation problem with a linear cost structure and lower bounds on supply from each origin and to each destination. We provide an algorithm for obtaining the growth path of such a system, i. e., determining the optimum shipment patterns and supply levels from origins and to destinations, when the total volume handled in the system is increased. Extensions of the procedure for the case when the costs of supplying are convex and piecewise linear and for solving transportation problems that are not in “standard form” are discussed. A procedure is provided for determining optimal plant capacities when the market requirements have prespecified growth rates. A goal programming growth model where the minimum requirements are treated as goals rather than as absolute requirements is also formulated.     

Equipment replacement under technological change

For infinite-horizon replacement economy problems it is common practice to truncate the problem at some finite horizon. We develop bounds on the error due to such a truncation. These bounds differ from previous results in that they include both revenues and costs. Bounds are illustrated through a numerical example from a real case in vehicle replacement. © 1994 John Wiley & Sons, Inc.     

A note on combined job selection and sequencing problems

We investigate the solvability of two single‐machine scheduling problems when the objective is to identify among all job subsets with cardinality k,1≤k≤n, the one that has the minimum objective function value. For the single‐machine minimum maximum lateness problem, we conclude that the problem is solvable in O(n²) time using the proposed REMOVE algorithm. This algorithm can also be used as an alternative to Moore's algorithm to solve the minimum number of tardy jobs problem by actually solving the hierarchical problem in which the objective is to minimize the maximum lateness subject to the minimum number of tardy jobs. We then show that the REMOVE algorithm cannot be used to solve the general case of the single‐machine total‐weighted completion time problem; we derive sufficient conditions among the job parameters so that the total weighted completion time problem becomes solvable in O(n²) time. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 449–453, 2013     

Minimizing weighted mean absolute deviation of flow times in single machine systems

We discuss the problem of scheduling several jobs on a single machine with the objective of minimizing the weighted mean absolute deviation of flow times around the weighted mean flow time. We first show that the optimal schedule is W-shaped. For the unweighted case, we show that all optimal schedules are V-shaped. This characterization enables us to show that the problem is NP-hard. We then provide a pseudopolynomial algorithm for the unweighted problem. Finally, we consider three heuristic algorithms for the unweighted problem and report computational experience with these algorithms. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 297–311, 1998     

Performance of heuristics for the uncapacitated lot-size problem

Although the uncapacitated lot-size problem can be solved optimally very efficiently, heuristics are often used instead in practice. Recent research on the performance of these heuristics has focused on worst-case analysis and empirical testing. This article extends earlier worst-case results, for several of the commonly used heuristics, to more specific problem classes to obtain a better understanding of when a heuristic can be expected to perform well and when it is likely to perform poorly. In particular, we obtain bounds for the finite-horizon problem (earlier results all assume an infinite horizon) and for problems in which demand is (i) constant, and (ii) bounded from above or below. We also show how the heuristics can be classified into three categories, with heuristics in each category using similar rules to construct feasible production schedules. Using this categorization, our analysis reveals that a small change in the definition of a heuristic can often have a significant impact on its performance. © 1992 John Wiley & Sons, Inc.     

Detection of minimal forecast horizons in dynamic programs with multiple indicators of the future

Many sequential planning problems can be represented as a shortest path problem in an acyclic network. This includes all deterministic dynamic programs as well as certain stochastic sequential decision problems. In this article, we identify a large class of shortest path problems for which a general efficient algorithm for the simultaneous solution and detection of minimal forecast horizons is developed. Detection of a such minimal forecast horizons is essential when accurate information regarding various relevant parameters is obtained progressively, i.e., when the initial information is restricted to a limited horizon of “future” stages only. We describe five classes of planning problems which can be efficiently addressed by the general algorithm. These classes deal with multi-item joint replenishment systems, combined inventory and routing problems, machine scheduling issues, single item stochastic inventory settings and routing problems in the plane and in space. © 1996 John Wiley & Sons, Inc.     

Single machine sequencing with linear models of release dates

The paper deals with a problem of scheduling a set of jobs on a single machine. Before a job is released for processing, it must undergo some preprocessing treatment that consumes resources. It is assumed that the release date of a job is a linear decreasing continuous function of the amount of a locally and globally constrained, continuously divisible resource (e.g., energy, catalyzer, financial outlay, gas). The problem is to find a sequence of jobs and a resource allocation that will minimize the maximum job completion time. Such a problem appears, for example, in the ingot preheating and hot-rolling process in steel mills. It is shown that the problem is strongly NP-hard. Some polynomially solvable cases of the problem and approximate algorithms with both experimental and worst-case analysis are presented. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 99–113, 1998