Order acceptance and scheduling on two identical parallel machines

We study the order acceptance and scheduling problem on two identical parallel machines. At the beginning of the planning horizon, a firm receives a set of customer orders, each of which has a revenue value, processing time, due date, and tardiness weight. The firm needs to select orders to accept and schedule the accepted orders on two identical parallel machines so as to maximize the total profit. The problem is intractable, so we develop two heuristics and an exact algorithm based on some optimal properties and the Lagrangian relaxation technique. We evaluate the performance of the proposed solution methods via computational experiments. The computational results show that the heuristics are efficient and effective in approximately solving large-sized instances of the problem, while the exact algorithm can only solve small-sized instances.     

A stochastic programming approach for planning horizons of infinite horizon capacity planning problems

Planning horizon is a key issue in production planning. Different from previous approaches based on Markov Decision Processes, we study the planning horizon of capacity planning problems within the framework of stochastic programming. We first consider an infinite horizon stochastic capacity planning model involving a single resource, linear cost structure, and discrete distributions for general stochastic cost and demand data (non-Markovian and non-stationary). We give sufficient conditions for the existence of an optimal solution. Furthermore, we study the monotonicity property of the finite horizon approximation of the original problem. We show that, the optimal objective value and solution of the finite horizon approximation problem will converge to the optimal objective value and solution of the infinite horizon problem, when the time horizon goes to infinity. These convergence results, together with the integrality of decision variables, imply the existence of a planning horizon. We also develop a useful formula to calculate an upper bound on the planning horizon. Then by decomposition, we show the existence of a planning horizon for a class of very general stochastic capacity planning problems, which have complicated decision structure.     

On upper bounds of sequential stochastic production planning problems

In this paper we consider a class of problems that determine production, inventory and work force levels for a firm in order to meet fluctuating demand requirements. A production planning problem arises because of the need to match, at the firm level, supply and demand efficiently. In practice, the two common approaches to counter demand uncertainties are (i) carrying a constant safety stock from period to period, and (ii) planning with a rolling horizon. Under the rolling horizon (or sequential) strategy the planning model is repeatedly solved, usually at the end of every time period, as new information becomes available and is used to update the model parameters. The costs associated with a rolling horizon strategy are hard to compute a priori because the solution of the model in any intermediate time period depends on the actual demands of the previous periods.In this paper we derive two a priori upper bounds on the costs for a class of production planning problems under the rolling horizon strategy. These upper bounds are derived by establishing correspondences between the rolling horizon problems and related deterministic programs. One of the upper bounds is obtained through Lagrangian relaxation of the service level constraint. We propose refinements to the non-Lagrangian bounds and present limited computational results. Extensions of the main results to the multiple item problems are also discussed. The results of this paper are intended to support production managers in estimating the production costs and value of demand information under a rolling horizon strategy.     

Optimal Pricing and Production Planning for Multi-product Multi-period Systems with Backorders

In this paper, we develop models for production planning with coordinated dynamic pricing. The application that motivated this research is manufacturing pricing, where the products are non-perishable assets and can be stored to fulfill the future demands. We assume that the firm does not change the price list very frequently. However, the developed model and its solution strategy have the capability to handle the general case of manufacturing systems with frequent time-varying price lists. We consider a multi-product capacitated setting and introduce a demand-based model, where the demand is a function of the price. The key parts of the model are that the planning horizon is discrete-time multi-period, and backorders are allowed. As a result of this, the problem becomes a nonlinear programming problem with the nonlinearities in both the objective function and some constraints. We develop an algorithm which computes the optimal production and pricing policy on a finite time horizon. We illustrate the application of the algorithm through a detailed numerical example.     

A Horizon Sensitivity Simulation of a Multistage Linear Programming Aggregate Operations Model

A firm that uses an aggregate operations planning model faces an important problem. Because it is multiperiod, solutions of a model with different horizon lengths can result in significantly different decisions, especially if aggregate shortages are allowed. This study illustrates methods of reducing the horizon length effects of a general linear programming model used by a plastic product manufacturer. As shown, that model originally had solutions of dubious value because of horizon effects. These effects were greatly reduced by eliminating aggregate shortages, but that precluded their use during peak seasonal demands. A more effective method was to penalize shortages during only the last period of a horizon. This improved the model's solutions without increasing its complexity, and also made it acceptable to responsible managers. Similar benefits should occur to users of analogous operations models which allow aggregate inventory shortages.     

Optimal pricing and inventory policies with reliable and random-yield suppliers: characterization and comparison

In this paper, we study the joint pricing and inventory replenishment problem for a periodic-review inventory system with random demand and dual suppliers, one of the suppliers is reliable but more expensive, the other supplier is less expensive but is unreliable with random yield. We characterize the firm’s optimal policies that simultaneously determine the optimal ordering and pricing decisions in each period over a finite planning horizon, and investigate the impacts of supply source diversification and supplier reliability on the firm and on its customers. We show that having source diversification or higher reliability of suppliers not only increases the firm’s expected profit, but also results in a lower optimal selling price, thus they benefit both the firm and its customers.     

Flexible capacity strategy with multiple market periods under demand uncertainty and investment constraint

We establish a flexible capacity strategy model with multiple market periods under demand uncertainty and investment constraints. In the model, a firm makes its capacity decision under a financial budget constraint at the beginning of the planning horizon which embraces n market periods. In each market period, the firm goes through three decision-making stages: the safety production stage, the additional production stage and the optimal sales stage. We formulate the problem and obtain the optimal capacity, the optimal safety production, the optimal additional production and the optimal sales of each market period under different situations. We find that there are two thresholds for the unit capacity cost. When the capacity cost is very low, the optimal capacity is determined by its financial budget; when the capacity cost is very high, the firm keeps its optimal capacity at its safety production level; and when the cost is in between of the two thresholds, the optimal capacity is determined by the capacity cost, the number of market periods and the unit cost of additional production. Further, we explore the endogenous safety production level. We verify the conditions under which the firm has different optimal safety production levels. Finally, we prove that the firm can benefit from the investment only when the designed planning horizon is longer than a threshold. Moreover, we also derive the formulae for the above three thresholds.     

Optimal pricing in a diffusion model with concave price-dependent market potential

Using optimal control theory, a diffusion model of new product acceptance is studied. We consider a profit-maximizing firm faced with the problem of determining its optimal pricing policy under the assumption that the total market potential is a concave decreasing function of price. For an infinite planning horizon it is shown by phase portrait analysis that the optimal price is steadily increasing and converging to a saddle point equilibrium.     

Managing capacity flexibility in make-to-order production environments

This paper addresses the problem of managing flexible production capacity in a make-to-order (MTO) manufacturing environment. We present a multi-period capacity management model where we distinguish between process flexibility (the ability to produce multiple products on multiple production lines) and operational flexibility (the ability to dynamically change capacity allocations among different product families over time). For operational flexibility, we consider two polices: a fixed allocation policy where the capacity allocations are fixed throughout the planning horizon and a dynamic allocation policy where the capacity allocations change from period to period. The former approach is modeled as a single-stage stochastic program and solved using a cutting-plane method. The latter approach is modeled as a multi-stage stochastic program and a sampling-based decomposition method is presented to identify a feasible policy and assess the quality of that policy. A computational experiment quantifies the benefits of operational flexibility and demonstrates that it is most beneficial when the demand and capacity are well-balanced and the demand variability is high. Additionally, our results reveal that myopic operating policies may lead a firm to adopt more process flexibility and form denser flexibility configuration chains. That is, process flexibility may be over-valued in the literature since it is assumed that a firm will operate optimally after the process flexibility decision. We also show that the value of process flexibility increases with the number of periods in the planning horizon if an optimal operating policy is employed. This result is reversed if a myopic allocation policy is adopted instead.     

Horizon Valuations for Mathematical Programming in Financial Planning

Using a linear programming model for the financial planning of an organization requires the specification of a horizon date and a valuation of the firm at that date. Given perfect information about future opportunities, an exact valuation procedure should lead to the same optimal solution of the model regardless of the choice of horizon date. Even in the absence of perfect information, conventional valuations fall far shorter of this ideal than they need to. It is shown that for a modest increase in the size of the linear programme, better valuations can be achieved and, most importantly, valuations which consider the impact on the value of the firm of post horizon constraints and liabilities as well as post-horizon opportunities.     

Optimal advertising pulsation policies: a dynamic programming approach

This study formulates and solves an advertising pulsation problem for a monopolistic firm using dynamic programming (DP). The firm aims at maximising profit through an optimal allocation of the advertising budget in terms of rectangular pulses over a finite planning horizon. Aggregate sales response to the advertising effort is assumed to be governed by a modified version of the Vidale–Wolfe model in continuous time proposed by Little. Using a numerical example in which a planning horizon of one year is divided into one, two through ten equal time periods, computing routines are developed to solve 150 DP problems. Computational results show among other findings that the performance yielded by the DP policy dominates the uniform advertising policy (constant spending) for a concave advertising response function and the advertising pulsing policy (turning advertising on and off) for a linear or convex response function.     

Stock repurchase with an adaptive reservation price: A study of the greedy policy

We consider the problem of stock repurchase over a finite time horizon. We assume that a firm has a reservation price for the stock, which is the highest price that the firm is willing to pay to repurchase its own stock. We characterize the optimal policy for the trader to maximize the total number of shares that they can buy over a fixed time horizon. In particular, we study a greedy policy, which involves in each period buying a quantity that drives stock price to the reservation price.     

Competitive production scheduling: A two-firm,noncooperative finite dynamic game

In this paper, we study the production scheduling problem in a competitive environment. Two firms produce the same product and compete in a market. The demand is random and so is the production capacity of each firm, due to random breakdowns. We consider a finite planning horizon. The scheduling problem is formulated as a finite dynamic game. Algorithms are developed to determine the security, hazard, and Nash policies. Numerical examples are discussed. A single-firm optimization model is also analyzed and it is observed that the production control policy from the single-firm optimization model may not perform well in a competitive environment.     

Joint replacement in an operational planning phase

We consider the problem of combining replacements of multiple components in an operational planning phase. Within an infinite or finite time horizon, decisions concerning replacement of components are made at discrete time epochs. The optimal solution of this problem is limited to only a small number of components. We present a heuristic rolling horizon approach that decomposes the problem; at each decision epoch an initial plan is made that addresses components separately, and subsequently a deviation from this plan is allowed to enable joint replacement. This approach provides insight into why certain actions are taken. The time needed to determine an action at a certain epoch is only quadratic in the number of components. After dealing with harmonisation and horizon effects, our approach yields average costs less than 1% above the minimum value.     

Finite-time dividend-ruin models

We consider the finite-time horizon dividend-ruin model where the firm pays out dividends to its shareholders according to a dividend-barrier strategy and becomes ruined when the firm’s asset value falls below the default threshold. The asset value process is modeled as a restricted Geometric Brownian process with an upper reflecting (dividend) barrier and a lower absorbing (ruin) barrier. Analytical solutions to the value function of the restricted asset value process are provided. We also solve for the survival probability and the expected present value of future dividend payouts over a given time horizon. The sensitivities of the firm asset value and dividend payouts to the dividend barrier, volatility of the firm asset value and firm’s credit quality are also examined.     

Capital renewal as a real option

We consider the timing of replacement of obsolete subsystems within an extensive, complex infrastructure. Such replacement action, known as capital renewal, must balance uncertainty about future profitability against uncertainty about future renewal costs. Treating renewal investments as real options, we derive an optimal solution to the infinite horizon version of this problem and determine the total present value of an institution’s capital renewal options. We investigate the sensitivity of the infinite horizon solution to variations in key problem parameters and highlight the system scenarios in which timely renewal activity is most profitable. For finite horizon renewal planning, we show that our solution performs better than a policy of constant periodic renewals if more than two renewal cycles are completed.     

Reinforcement learning for joint pricing,lead-time and scheduling decisions in make-to-order systems

The paper investigates a problem faced by a make-to-order (MTO) firm that has the ability to reject or accept orders, and set prices and lead-times to influence demands. Inventory holding costs for early completed orders, tardiness costs for late delivery orders, order rejection costs, manufacturing variable costs, and fixed costs are considered. In order to maximize the expected profits in an infinite planning horizon with stochastic demands, the firm needs to make decisions from the following aspects: which orders to accept or reject, the trade-off between price and lead-time, and the potential for increased demand against capacity constraints. We model the problem as a Semi-Markov Decision Problem (SMDP) and develop a reinforcement learning (RL) based Q-learning algorithm (QLA) for the problem. In addition, we build a discrete-event simulation model to validate the performance of the QLA, and compare the experimental results with two benchmark policies, the First-Come-First-Serve (FCFS) policy and a threshold heuristic policy. It is shown that the QLA outperforms the existing policies.     

Pricing and lot-sizing for a deteriorating item in a periodic review inventory system with shortages

We consider a single product that is, subject to continuous decay, a multivariate demand function of price and time, shortages allowed and completely backlogged in a periodic review inventory system in which the selling price is allowed to adjust upward or downward periodically. The objective of this paper is to determine the periodic selling price and lot-size over multiperiod planning horizon so that the total discount profit is maximized. The proposed model can be used as an add-in optimizer like an advanced planning system in an enterprise resource planning system that coordinates distinct functions within a firm. Particular attention is placed on investigating the effect of periodic pricing jointly with shortages on the total discount profit. The problem is formulated as a bivariate optimization model solved by dynamic programming techniques coupled with an iterative search process. An intensive numerical study shows that the periodic pricing is superior to the fixed pricing in profit maximization. It also clarifies that shortages strategy can be an effective cost control mechanism for managing deterioration inventory.     

A stochastic partially reversible investment problem on a finite time-horizon: Free-boundary analysis

We study a continuous-time, finite horizon, stochastic partially reversible investment problem for a firm producing a single good in a market with frictions. The production capacity is modeled as a one-dimensional, time-homogeneous, linear diffusion controlled by a bounded variation process which represents the cumulative investment–disinvestment strategy. We associate to the investment–disinvestment problem a zero-sum optimal stopping game and characterize its value function through a free-boundary problem with two moving boundaries. These are continuous, bounded and monotone curves that solve a system of non-linear integral equations of Volterra type. The optimal investment–disinvestment strategy is then shown to be a diffusion reflected at the two boundaries.     

Model and algorithms for multi-period sea cargo mix problem

In this paper, we consider the sea cargo mix problem in international ocean container shipping industry. We describe the characteristics of the cargo mix problem for the carrier in a multi-period planning horizon, and formulate it as a multi-dimensional multiple knapsack problem (MDMKP). In particular, the MDMKP is an optimization model that maximizes the total profit generated by all freight bookings accepted in a multi-period planning horizon subject to the limited shipping capacities. We propose two heuristic algorithms that can solve large scale problems with tens of thousands of decision variables in a short time. Finally, numerical experiments on a wide range of randomly generated problem instances are conducted to demonstrate the efficiency of the algorithms.