Integrated multi-site aggregate production-pricing planning in a two-echelon supply chain with multiple demand classes

This paper proposes a production and differential pricing decision model in a two-echelon supply chain that involves a demand from two or more market segments. In this framework, the retailer is allowed to set different prices during the planning horizon. While integrated production-marketing management has been a key research issue in supply chain management for a long time, little attention has been given to set prices and marketing expenditures in integrated multi-site (parallel) manufacturing systems and multiple demand classes. Generally, the presence of multiple demand classes induced by different market segments may impose demand leakage and then change production plan and ordering policies throughout the supply chain system. To tackle this problem, this paper develops a novel approach in order to provide an optimal aggregate production and marketing plan by interconnecting the sales channels of the retailer and demand. A non-linear model is established to determine optimal price differentiation, marketing expenditures and production plans of manufacturing sites in a multi-period, multi-product and multi-sale channels production planning problem by maximizing total profit of the supply chain. To handle the model and obtain solutions, we propose an efficient analytical model based upon convex hulls. Finally, we apply the proposed procedure to a clothing company in order to show usefulness and significance of the model and solution method.     

Stochastic Optimization over a Pareto Set Associated with a Stochastic Multi-Objective Optimization Problem

We deal with the problem of minimizing the expectation of a real valued random function over the weakly Pareto or Pareto set associated with a Stochastic Multi-objective Optimization Problem, whose objectives are expectations of random functions. Assuming that the closed form of these expectations is difficult to obtain, we apply the Sample Average Approximation method in order to approach this problem. We prove that the Hausdorff–Pompeiu distance between the weakly Pareto sets associated with the Sample Average Approximation problem and the true weakly Pareto set converges to zero almost surely as the sample size goes to infinity, assuming that our Stochastic Multi-objective Optimization Problem is strictly convex. Then we show that every cluster point of any sequence of optimal solutions of the Sample Average Approximation problems is almost surely a true optimal solution. To handle also the non-convex case, we assume that the real objective to be minimized over the Pareto set depends on the expectations of the objectives of the Stochastic Optimization Problem, i.e. we optimize over the image space of the Stochastic Optimization Problem. Then, without any convexity hypothesis, we obtain the same type of results for the Pareto sets in the image spaces. Thus we show that the sequence of optimal values of the Sample Average Approximation problems converges almost surely to the true optimal value as the sample size goes to infinity.     

On the average performance of the adjustable RO and its use as an offline tool for multi-period production planning under uncertainty

Robust optimization (RO) is a distribution-free worst-case solution methodology designed for uncertain maximization problems via a max-min approach considering a bounded uncertainty set. It yields a feasible solution over this set with a guaranteed worst-case value. As opposed to a previous conception that RO is conservative based on optimal value analysis, we argue that in practice the uncertain parameters rarely take simultaneously the values of the worst-case scenario, and thus introduce a new performance measure based on simulated average values. To this end, we apply the adjustable RO (AARC) to a single new product multi-period production planning problem under an uncertain and bounded demand so as to maximize the total profit. The demand for the product is assumed to follow a typical life-cycle pattern, whose length is typically hard to anticipate. We suggest a novel approach to predict the production plan’s profitable cycle length, already at the outset of the planning horizon. The AARC is an offline method that is employed online and adjusted to past realizations of the demand by a linear decision rule (LDR). We compare it to an alternative offline method, aiming at maximum expected profit, applying the same LDR. Although the AARC maximizes the profit against a worst-case demand scenario, our empirical results show that the average performance of both methods is very similar. Further, AARC consistently guarantees a worst profit over the entire uncertainty set, and its model’s size is considerably smaller and thus exhibit superior performance.     

Price optimization with reference price effects: A generalized Benders’ decomposition method and a myopic heuristic approach

We consider a multi-period revenue maximization and pricing optimization problem in the presence of reference prices. We formulate the problem as a mixed integer nonlinear program and develop a generalized Benders’ decomposition algorithm to solve it. In addition, we propose a myopic heuristic and discuss the conditions under which it produces efficient solutions. We provide analytical results as well as numerical computations to illustrate the efficiency of the solution approaches as well as some managerial pricing insights.     

考虑生产计划的多周期切割问题优化研究

切割生产广泛存在于工业企业,是原材料加工的重要环节。已有文献主要关注单周期切割问题,但是切割计划也是生产计划的一部分,切割计划和生产计划应该协调优化,达到全局最优。本文研究考虑生产计划的多周期切割问题,目标是最小化运营成本,包括准备成本、切割成本、库存成本以及母材消耗成本。首先建立混合整数规划模型;提出动态规划启发式算法;最后对算例在多种情境下测试,分析成本因子变化对最优结果的影响。算法结果与CPLEX最优结果比较,平均误差为1.85%,表明算法是有效的。     

A variable neighborhood search for the network design problem with relays

Given a set of commodities to be routed over a network, the network design problem with relays involves selecting a route for each commodity and determining the location of relays where the commodities must be reprocessed at certain distance intervals. We propose a hybrid approach based on variable neighborhood search. The variable neighborhood algorithm searches for the route for each commodity and the optimal relay locations for a given set of routes are determined by an implicit enumeration algorithm. We show that dynamic programming can be used to determine the optimal relay locations for a single commodity. Dynamic programming is embedded into the implicit enumeration algorithm to solve the relay location problem optimally for multiple commodities. The special structure of the problem is leveraged for computational efficiency. In the variable neighborhood search algorithm, the routes of the current solution are perturbed and reconstructed to generate neighbor solutions using random and greedy construction heuristics. Computational experiments on three sets of problems (80 instances) show that the variable neighborhood search algorithm with optimal relay allocations outperforms all existing algorithms in the literature.     

An LP-based heuristic for two-stage capacitated facility location problems

In this paper, a linear programming based heuristic is considered for a two-stage capacitated facility location problem with single source constraints. The problem is to find the optimal locations of depots from a set of possible depot sites in order to serve customers with a given demand, the optimal assignments of customers to depots and the optimal product flow from plants to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To this end, the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxations of the problem. After each reoptimisation step, that is the recalculation of the LP solution after the addition of valid inequalities, feasible solutions are obtained from the current LP solution by applying simple heuristics. The results of extensive computational experiments are given.     

Capacitated,balanced, sequential location-allocation problems on chains and trees

This paper considers finite horizon, multiperiod, sequential, minisum location-allocation problems on chain graphs and tree networks. The demand has both deterministic and probabilistic components, and increases dynamically from period to period. The problem is to locate one additionalcapacitated facility in each of thep specified periods, and to determine the service allocations of the facilities, in order to optimally satisfy the demand on the network. In this context, two types of objective criteria or location strategies are addressed. The first is a myopic strategy in which the present period cost is minimized sequentially for each period, and the second is a discounted present worth strategy. For the chain graph, we analyze ap-facility problem under both these criteria, while for the tree graph, we analyze a 3-facility myopic problem, and a 2-facility discounted present worth problem. All these problems are nonconvex, and we specify a finite set of candidate solutions which may be compared in order to determine a global optimal solution.     

Scheduling preemptive open shops to minimize total tardiness

This article considers the problem of scheduling preemptive open shops to minimize total tardiness. The problem is known to be NP-hard. An efficient constructive heuristic is developed for solving large-sized problems. A branch-and-bound algorithm that incorporates a lower bound scheme based on the solution of an assignment problem as well as various dominance rules are presented for solving medium-sized problems. Computational results for the 2-machine case are reported. The branch-and-bound algorithm can handle problems of up to 30 jobs in size within a reasonable amount of time. The solution obtained by the heuristic has an average deviation of less than 2% from the optimal value, while the initial lower bound has an average deviation of less than 11% from the optimal value. Moreover, the heuristic finds approved optimal solutions for over 65% of the problems actually solved.     

Coherent risk measures in inventory problems

We analyze an extension of the classical multi-period, single-item, linear cost inventory problem where the objective function is a coherent risk measure. Properties of coherent risk measures allow us to offer a unifying treatment of risk averse and min–max type formulations. For the single period newsvendor problem, we show that the structure of the optimal solution of the risk averse model is similar to that of the classical expected value problem. For a finite horizon dynamic inventory model, we show that, again, the optimal policy has a similar structure as that of the expected value problem. This result carries over even to the case when there is a fixed ordering cost. We also analyze monotonicity properties of the optimal order quantity with respect to the degree of risk aversion for certain risk measures.     

A memetic algorithm for the multiperiod vehicle routing problem with profit

In this paper, we extend upon current research in the vehicle routing problem whereby labour regulations affect planning horizons, and therefore, profitability. We call this extension the multiperiod vehicle routing problem with profit (mVRPP). The goal is to determine routes for a set of vehicles that maximizes profitability from visited locations, based on the conditions that vehicles can only travel during stipulated working hours within each period in a given planning horizon and that the vehicles are only required to return to the depot at the end of the last period. We propose an effective memetic algorithm with a giant-tour representation to solve the mVRPP. To efficiently evaluate a chromosome, we develop a greedy procedure to partition a given giant-tour into individual routes, and prove that the resultant partition is optimal. We evaluate the effectiveness of our memetic algorithm with extensive experiments based on a set of modified benchmark instances. The results indicate that our approach generates high-quality solutions that are reasonably close to the best known solutions or proven optima, and significantly better than the solutions obtained using heuristics employed by professional schedulers.     

The value of virtual pooling in dual sales channel supply chains

Recently the most significant growth in online retailing has been attributed to traditional offline retailers extending their brands online. Unfortunately, there is little research addressing the value of better information in retail/e-tail organizations. To fill this gap, this paper examines how investing in the continuous monitoring of online demands and inventory positions can provide economic benefit for companies that handle both in-store and online sales. Specifically, we develop and evaluate two dynamic assignment policies that incorporate real time information to specify which of a firm’s e-fulfillment locations will handle each of its Internet sales. Computational results indicate that investing in dynamic assignment capability can reduce system cost (holding, backorder, and transportation) by as much as 8.2% over the optimal static policy. The percentage of sales occurring online plays a critical role in determining the magnitude of the benefit.     

A general method for finding the optimal threshold in discrete time

We develop an approach for solving one-sided optimal stopping problems in discrete time for general underlying Markov processes on the real line. The main idea is to transform the problem into an auxiliary problem for the ladder height variables. In case that the original problem has a one-sided solution and the auxiliary problem has a monotone structure, the corresponding myopic stopping time is optimal for the original problem as well. This elementary line of argument directly leads to a characterization of the optimal boundary in the original problem. The optimal threshold is given by the threshold of the myopic stopping time in the auxiliary problem. Supplying also a sufficient condition for our approach to work, we obtain solutions for many prominent examples in the literature, among others the problems of Novikov-Shiryaev, Shepp-Shiryaev, and the American put in option pricing under general conditions. As a further application we show that for underlying random walks (and Lévy processes in continuous time), general monotone and log-concave reward functions g lead to one-sided stopping problems.     

A capacity constrained single-facility dynamic lot-size model

A computationally efficient algorithm for a multi-period single commodity production planning problem with capacity constraints is developed. The model differs from earlier well-known studies involving concave cost functions in the introduction of production capacity constraints which need not be equal in every period. The objective is to find an optimal production schedule that minimizes the total production and inventory costs. Backlogging is not allowed. The structure of the optimal solution is characterized and then used in an efficient algorithm.     

The dynamic vehicle rescheduling problem

The pre-planned schedules of a transportation company are often disrupted by unforeseen events. As a result of a disruption, a new schedule has to be produced as soon as possible. This process is called the vehicle rescheduling problem, which aims to solve a single disruption and restore the order of transportation. However, there are multiple disruptions happening over a “planning unit” (usually a day), and all of them have to be addressed to achieve a final feasible schedule. From an operations management point of view the quality of the final solution has to be measured by the combined quality of every change over the horizon of the “planning unit”, not by evaluating the solution of each disruption as a separate problem. The problem of finding an optimal solution where all disruptions of a “planning unit” are addressed will be introduced as the dynamic vehicle rescheduling problem (DVRSP). The disruptions of the DVRSP arrive in an online manner, but giving an optimal final schedule for the “planning unit” would mean knowing all information in advance. This is not possible in a real-life scenario, which means that heuristic solution methods have to be considered. In this paper, we present a recursive and a local search algorithm to solve the DVRSP. In order to measure the quality of the solutions given by the heuristics, we introduce the so-called quasi-static DVRSP, a theoretical problem where all the disruptions are known in advance. We give two mathematical models for this quasi-static problem, and use their optimal solutions to evaluate the quality of our heuristic results. The heuristic methods for the dynamic problem are tested on different random instances.     

Dual sourcing using capacity reservation and spot market: Optimal procurement policy and heuristic parameter determination

This contribution focuses on the cost-effective management of the combined use of two procurement options: the short-term option is given by a spot market with random price, whereas the long-term alternative is characterized by a multi period capacity reservation contract with fixed purchase price and reservation level. A reservation cost, proportional with the reservation level, has to be paid for the option of receiving any amount per period up to the reservation level. A long-term decision has to be made regarding the reserved capacity level, and then it has to be decided – period by period – which quantities to procure from the two sources. Considering the multi-period problem with stochastic demand and spot price, the structure of the optimal combined purchasing policy is derived using stochastic dynamic programming. Exploiting these structural properties, an advanced heuristic is developed to determine the respective policy parameters. This heuristic is compared with two rolling-horizon approaches which use the one-period and two-period optimal solution. A comprehensive numerical study reveals that the approaches based on one-period and two-period solutions have considerable drawbacks, while the advanced heuristic performs very well compared to the optimal solution. Finally, by exploiting our numerical results we give some insights into the system’s behavior under problem parameter variations.     

Optimal inventory decisions in a multiperiod newsvendor problem with partially observed Markovian supply capacities

This paper considers a multi-period news-vendor problem with partially observed supply-capacity information which evolves as a Markovian Process. The supply capacity is fully observed by the buyer when the capacity is smaller than the buyer’s ordering quantity. Otherwise, the buyer knows that the current-period supply capacity is greater than its ordering quantity. Based on these two observations, the buyer updates the future supply-capacity forecasting accordingly. With a dynamic programming formulation, we prove the existence of an optimal ordering policy. We also prove that the optimal order quantity is greater than the myopic order quantity.     

Optimization Over the Efficient Set of Multi-objective Convex Optimal Control Problems

We consider multi-objective convex optimal control problems. First we state a relationship between the (weakly or properly) efficient set of the multi-objective problem and the solution of the problem scalarized via a convex combination of objectives through a vector of parameters (or weights). Then we establish that (i) the solution of the scalarized (parametric) problem for any given parameter vector is unique and (weakly or properly) efficient and (ii) for each solution in the (weakly or properly) efficient set, there exists at least one corresponding parameter vector for the scalarized problem yielding the same solution. Therefore the set of all parametric solutions (obtained by solving the scalarized problem) is equal to the efficient set. Next we consider an additional objective over the efficient set. Based on the main result, the new objective can instead be considered over the (parametric) solution set of the scalarized problem. For the purpose of constructing numerical methods, we point to existing solution differentiability results for parametric optimal control problems. We propose numerical methods and give an example application to illustrate our approach.     

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.     

Column generation approaches to ship scheduling with flexible cargo sizes

We present a Dantzig–Wolfe procedure for the ship scheduling problem with flexible cargo sizes. This problem is similar to the well-known pickup and delivery problem with time windows, but the cargo sizes are defined by intervals instead of by fixed values. The flexible cargo sizes have consequences for the times used in the ports because both the loading and unloading times depend on the cargo sizes. We found it computationally hard to find exact solutions to the subproblems, so our method does not guarantee to find the optimum over all solutions. To be able to say something about how good our solution is, we generate a bound on the difference between the true optimal objective and the objective in our solution. We have compared our method with an a priori column generation approach, and our computational experiments on real world cases show that our Dantzig–Wolfe approach is faster than the a priori generation of columns, and we are able to deal with larger or more loosely constrained instances. By using the techniques introduced in this paper, a more extensive set of real world cases can be solved either to optimality or within a small deviation from optimality.