Analysis of supply contracts with total minimum commitment

In this paper we analyze a supply contract for a single product that specifies that the cumulative orders placed by a buyer, over a finite horizon, be at least as large as a (contracted upon) given quantity. We assume that the demand for the product is uncertain, and the buyer places orders periodically. We derive the optimal purchase policy for the buyer for a given total minimum quantity commitment and a discounted price. We show that the policy is characterized by the order-up-to levels of the corresponding finite horizon and a single-period standard newsboy problem with no commitment but with discounted price. We show that this policy can be computed easily. We can use this to evaluate any discount schedule characterized by a set of (price discount, minimum commitment) pairs.     

Finite-horizon equipment replacement analysis

The optimal solution to the infinite-horizon equipment replacement problem with stationary costs is to continually replace an asset at its economic life. The economic life is the age that minimizes the Equivalent Annual Cost (EAC), which includes purchase, operating and maintenance costs less salvage values. We explore the question of whether this is a good policy for the finite-horizon problem, which occurs when companies only require an asset for a specified length of time, usually to fulfill a specific contract. We identify cases, according to capital costs, operating costs, and the interest rate, when this policy is good and when it deviates significantly from optimal. Furthermore, we provide a bound on the minimum number of times that an asset is retained at its economic life over a finite horizon. This is facilitated through a new dynamic-programming formulation to the problem based on the integer-knapsack problem with nonlinear costs. The bound can be derived from any feasible solution, although we provide a closed-form solution for the case of convex EAC values.     

Improving a supplier's quantity discount gain from many different buyers

We consider the pricing and inventory decisions of a vendor who supplies a single product to multiple heterogeneous buyers. The problem is analyzed as a Stackelberg game in which the vendor acts as the leader by announcing its pricing policy to all the buyers in advance and the buyers act as followers by choosing their order quantity and the sassociated purchasing price independently under the vendors' pricing scheme. We propose in this paper a pricing policy for the vendor that offers price discounts based on the percentage increase from a buyers' order quantity before discount. The proposed policy is defined as a discrete all-unit quantity discount schedule with many break points. We show that: (i) the proposed policy offers a higher price discount to a buyer ordering a larger quantity and hence complies with general fair trade laws; (ii) an explicit solution is obtained for the vendors' optimal decision; and (iii) although suppliers in reality normally offer price discounts based on a buyers' unit increase in order quantity, the proposed policy is superior for the vendor when there are many different buyers. Other benefits of the proposed pricing policy are demonstrated by numerical examples.     

Spread time considerations in operational fixed job scheduling

In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times.     

On discrete lot streaming in no-wait flow shops

Lot streaming is the process of splitting a job or lot to allow overlapping between successive operations in a multistage production system. This use of transfer lots usually results in a substantially shorter makespan for the corresponding schedule. In this paper, we study the discrete lot streaming problem for a single job in no-wait flow shops. We present a new linear programming formulation for the problem. We show that the optimal solutions are the same for the m ×2 case with or without no-wait constraints. We also present a fast, polynomial-time solution method for this case. For the general case, we prove that any solution which is 'close' to the continuous optimal solution will be a good approximation for the discrete problem. This property allows us to present two quickly obtainable approximations of very good quality.     

Integrated Project Scheduling and Material Planning with Variable Activity Duration and Rewards

Integrating project scheduling and material ordering adds more realism to project scheduling and considers additional trade-offs that could lead to reductions in the overall project cost. In this paper we review the evolution of the integrated problem, and investigate the impact of treating the activity duration as a decision variable on the activities schedule and materials plan. The effects of introducing rewards (penalties) for early (late) completion as well as materials quantity discounts on the project schedule and cost are also considered- These additions provide scheduling flexibility that might lead to further reduction in the project's total cost or makespan. Considering the various project costs, we found that there exists an optimal schedule that either starts as early as possible (ai time zero) or completes as late as possible. We also show that if the project starts at time zero, then its duration cannot be longer than that for the case where the schedule ends as late as possible. Ft is also shown that the material ordering policy does not follow the Wagner and Whitin model when activity duration is variable or in the presence of quantity discounts. These results have led to modeling and solving the problem in a more efficient manner. Extensive computational work shows the validity of the model and the solution approach.     

The complexity of routing in hierarchical PNNI networks

We study the complexity of computing a route in a hierarchical PNNI network, with H levels of hierarchy, in which N nodes are grouped into clusters at each level. We determine cluster sizes that minimize an upper bound on the total time for all the path computations required to compute a route. Our model casts the problem as a nonlinear convex optimization problem, and employs nonlinear duality theory. We derive explicit closed form upper bounds on the minimum total path computation time, as a function of N, for H=2 and H=3, and show how the upper bound, and the optimal cluster sizes, can be computed for any H. We provide a conjecture on the complexity of PNNI routing for any H, and use this conjecture to determine the limit of the complexity as H→∞. We also prove that the minimum total path computation time is a non-increasing function of H. Our results provide counterexamples to a claim by Van Mieghem that a related top-down hierarchical routing method has lower computational complexity.     

Optimality conditions for shakedown design of trusses

This paper deals with optimal shakedown design of truss structures constituted by elastic perfectly plastic material. The design problem is formulated by means of a statical approach on the grounds of the shakedown lower bound theorem, and by means of a kinematical approach on the grounds of the shakedown upper bound theorem. In both cases two different types of design problem are formulated: one searches for the minimum volume design whose shakedown limit load is assigned; the other searches for the maximum shakedown limit load design whose volume is assigned. The Kuhn-Tucker equations of the four problems here above mentioned are found by utilizing a variational approach; these equations prove the equivalence of the two types of design problem and provide useful information on the structure behaviour in optimality conditions. A suitable computational procedure of iterative type devoted to the reaching of the minimum volume design is presented. It is shown that the design obtained by this technique is the optimal one, since it satisfies the optimality conditions of the relevant search problem. In the typical step of this technique the dependency of the elastic response on the design variables is approximately taken into account. In the application stage a numerical example, aimed at utilizing this special technique, is presented.     

Dynamic rationing and ordering policies for multiple demand classes

In this paper, we study the dynamic rationing problem for multiple demand classes with Poisson demands. We first consider a multi-period problem with zero lead time and show that the optimal rationing and ordering policies are, respectively, the dynamic rationing policy and the base stock policy. We then extend this model to a non-zero lead time and show that there is no simple optimal structure for this extended problem. A myopic policy and a lower bound are proposed. The numerical results show that the dynamic rationing policy outperforms the static rationing policy and its performance is very close to the optimal policy under a wide range of operating conditions.     

Dynamic pricing for multiple class deterministic demand fulfillment

We consider how a firm should allocate inventory to multiple customer classes that differ based on the price they pay and their willingness to incur delay in fulfillment of their demand. The problem is set in a deterministic demand, economic-order-quantity-like environment with holding, backorder, lost demand and setup costs. The firm either fulfills demand or offers a price discount to induce the demand to wait for fulfillment from the next reorder. We determine the optimal policy and discuss how changes in various parameters affect profitability, customer service, and operational measures such as order frequency and base stock levels. We compare the results to a policy that only rations inventory without dynamic discounting and to a policy that only provides discounts. Through the comparison, we observe that dynamic pricing can be seen as a combination of a pricing mechanism which determines demand and an allocation mechanism that differentiates between customer classes, serving each ones needs. We show that if lower-value customers are distinguished by accepting reduced service, it is possible that both high and low-value customer classes see better levels of service under the optimal policy than under a discounting only policy. In addition we demonstrate the applicability of the results to a stochastic version of the problem.     

A SINGULAR-ARC APPROXIMATION TO A DYNAMIC SAILPLANE FLIGHT PATH OPTIMIZATION PROBLEM

A dynamic sailplane performance problem is investigated using optimal control theory. The problem is to minimize the total flight time between successive thermals subject to zero altitude loss. From the original nonlinear optimal control problem, a singular linear/quadratic problem is derived and solved.

A relationship between the original optimal control problem and a certain parameter optimization problem is explored, and it is shown that the solution to this parameter optimization provides a lower bound for the minimum flight time of the original optimal control problem. The parameter optimization solution is adopted as the reference trajectory for the linear/quadratic problem. Finally, the linear/quadratic problem is shown to provide a good approximation to the original optimal control problem at a small fraction of the computing cost.     

Economic Lot Scheduling for Two-Product Problem

In this paper we propose an algorithm for the two-product single machine Economic Lot Scheduling Problem (ELSP). Past research on this problem has relied heavily on the assumption that both products are produced cyclically. In particular Boctor's algorithm provides optimal solution to the two-product problem under such assumption. We first simplify Boctor's algorithm and then propose an algorithm which allows for the unequal cycle time for the more frequently manufactured product. We show that the cost corresponding to our solution is either less than 1.015 times the cost obtained from the Independent Solution, which is a lower bound of the optimal solution, or is better than that obtained by Boctor's algorithm. An example is used to show that the difference in cost can be as much as 24%.     

Dynamic vs static pricing in a make-to-stock queue with partially controlled production

We consider a capacitated make-to-stock production system that offers a product to a market of price-sensitive users. The production process is partially controlled. On the one hand, the decision-maker controls the production of a single facility. On the other hand, an uncontrolled flow of items arrives at the stock. Such a situation occurs in several contexts; for example, when there is a return flow of products or a fixed delivery contract. We model the system as a make-to-stock queue with lost sales. We address the static pricing problem and the dynamic pricing problem with the objective of maximizing the average profit over an infinite horizon. For both problems, we characterize the optimal production and pricing policy. We also obtain analytical results for the static pricing problem. From numerical results, we show that dynamic pricing might be much more beneficial when the production is not totally controlled.      

A simple linear heuristic for the service constrained random yield problem

We consider the problem of setting order quantities for purchased components subject to uncertainty in the delivery amounts. Assuming the periodic production volumes (demands)to be known and constant, we model this as a random yield problem with the objective of minimizing average inventory cost subject to a service level constraint over the infinite horizon. We first demonstrate that under conditions of random yield, conventional definitions of service can be inappropriate. Then we refine the definition of service for random yield cases and use this to formulate an optimization model. Exact solution of this model proves to be computationally impractical and, as we show, the common heuristic of inflating demands by a constant proportion is not robustly accurate. Therefore, we develop a new heuristic, which we term the linear inflation policy, that specifies a linear function for the inflation factors. Numerical tests indicate that this heuristic can substantially outperform the traditional constant inflation policy and works well relative to a lower bound on the optimal solution on a range of examples.     

Scheduling about an unrestricted common due windowwith arbitrary earliness/tardiness penalty rates

We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due window to minimize total weighted earliness and tardiness cost. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. Earliness or tardiness cost is assessed when a job completes outside the due window, which may be an instant in time or a time increment defining acceptable job completion. In this paper we present properties that characterize the structure of an optimal schedule, present a lower bound, propose a two-step branch and bound algorithm, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for medium-sized problem instances.     

Single machine scheduling problem with batch setups involving positional deterioration effects and multiple rate-modifying activities

This article considers a single machine scheduling problem with batch setups, positional deterioration effects, and multiple optional rate-modifying activities to minimize the total completion time. This problem is formulated as an integer quadratic programming problem. In view of the complexity of optimally solving this problem, a two-phase heuristic algorithm is proposed where an optimal but non-integer solution is obtained in the first phase by solving a continuous relaxed version of the problem. This solution serves as a lower bound for the optimal value of the total completion time. The second phase of the algorithm generates an integer solution using a simple rounding scheme that is optimum or very close to optimum for this problem. Empirical evaluation and comparison with an existing heuristic algorithm show that the proposed heuristic algorithm is substantially more effective in solving large-size problem instances.     

PERFORMANCE OF A MYOPIC LOT SIZE POLICY WITH LEARNING IN SETUPS

We consider the problem of lot sizing when learning results in decreasing setup costs. Finding optimal lot sizes requires information about future setup costs and also the horizon length, which can be difficult to forecast. We analyze an intuitively appealing and well known myopic policy (Part Period Balancing). This policy sets the current lot size such that the current setup cost equals the holding cost for the current lot. It is easy to implement and does not require information on future setup costs. It is shown that the number of setups in the myopic policy is at most one greater than the optimal number of setups. Using this bound, we show that the myopic policy costs no more than 6/(3 + min(l, 1.5R)) times the optimal cost, where R is the ratio of the minimum setup cost to the initial setup cost. Computational experiments show that its average performance is good even for horizons as short as eight times the initial reorder interval. Further, our study shows that the average performance improves with R.     

Optimal price and maximum deal size on group-buying websites for sellers with finite capacity

This paper presents an analytical model for sellers with finite capacity to optimise their price and maximum deal size limit on group-buying websites. For the general demand functions that satisfy some mild regularity conditions, the optimal strategies and the corresponding deal parameters are characterised. The optimal strategies demonstrate that deep online discounts (selling products below the cost or even selling products for free) can be optimal if the maximum deal size is used strategically. Moreover, deep discounts can be beneficial even if the capacity is tight, which explains the use of deep discounts commonly observed in practice. Our results also provide the operators of group-buying websites with useful suggestions on how to induce sellers to offer deep discounts. Sensitivity analysis with regard to the minimum deal size and capacity is provided. Our analysis shows that counter-intuitively selling out capacity may not always be optimal, even if the amount of capacity cannot satisfy the unconstrained optimal sales quantity online. Finally, we extend the model to consider offline prices being sellers’ decisions and discuss the robustness of the optimal strategies when the demand is stochastic.     

Periodic-review inventory systems with random yield and demand: Bounds and heuristics

We revisit the infinite-horizon decision problem of a single-stage single-item periodic-review inventory system under uncertain yield and demand. It is known that under some mild conditions the optimal replenishment policy is of the threshold type: an order is placed if and only if the starting inventory is below a threshold value. Although the structure of the optimal policy is well known, there has been little discussion about the optimal order quantities and the order threshold. In this paper, we construct upper and lower bounds for the optimal threshold value and the optimal order quantities through solving one-period problems with different cost parameters. These bounds provide interesting insights into the impact of yield uncertainty on the optimal policy. Heuristics are developed based on these bounds. Detailed computational studies show that, under some conditions, the performance of the heuristics is very close to that of the optimal solution and better than that of existing heuristics in the literature.