Integrality in Stochastic Inventory Models Chen, Wei; Dawande, Milind; Janakiraman, Ganesh
Production and operations management,
September 2014, Letnik:
23, Številka:
9
Journal Article
Recenzirano
We study several finite‐horizon, discrete‐time, dynamic, stochastic inventory control models with integer demands: the newsvendor model, its multi‐period extension, and a single‐product, ...multi‐echelon assembly model. Equivalent linear programs are formulated for the corresponding stochastic dynamic programs, and integrality results are derived based on the total unimodularity of the constraint matrices. Specifically, for all these models, starting with integer inventory levels, we show that there exist optimal policies that are integral. For the most general single‐product, multi‐echelon assembly system model, integrality results are also derived for a practical alternative to stochastic dynamic programming, namely, rolling‐horizon optimization by a similar argument. We also present a different approach to prove integrality results for stochastic inventory models. This new approach is based on a generalization we propose for the one‐dimensional notion of piecewise linearity with integer breakpoints to higher dimensions. The usefulness of this new approach is illustrated by establishing the integrality of both the dynamic programming and rolling‐horizon optimization models of a two‐product capacitated stochastic inventory control system.
We consider the stochastic, single‐machine earliness/tardiness problem (SET), with the sequence of processing of the jobs and their due‐dates as decisions and the objective of minimizing the sum of ...the expected earliness and tardiness costs over all the jobs. In a recent paper, Baker (2014) shows the optimality of the Shortest‐Variance‐First (SVF) rule under the following two assumptions: (a) The processing duration of each job follows a normal distribution. (b) The earliness and tardiness cost parameters are the same for all the jobs. In this study, we consider problem SET under assumption (b). We generalize Baker's result by establishing the optimality of the SVF rule for more general distributions of the processing durations and a more general objective function. Specifically, we show that the SVF rule is optimal under the assumption of dilation ordering of the processing durations. Since convex ordering implies dilation ordering (under finite means), the SVF sequence is also optimal under convex ordering of the processing durations. We also study the effect of variability of the processing durations of the jobs on the optimal cost. An application of problem SET in surgical scheduling is discussed.
The Making of a Good Impression Sun, Zhen; Dawande, Milind; Janakiraman, Ganesh ...
MIS quarterly,
09/2016, Letnik:
40, Številka:
3
Journal Article
Recenzirano
In this paper, we examine information revelation designs and policies in ad exchanges that use a second-price auction mechanism. Two auction designs are studied: one-call and two-call. Under the ...one-call design, the ad exchange makes one call to all bidders at the beginning of an auction. Under the two-call design, in addition to the call to all bidders at the beginning of the auction, the exchange calls out the winning bidder at the end of the auction; this second call enables the winning bidder to match the right advertiser for the impression. Thus, the two-call design requires a higher level of technical sophistication but offers to the auction site the choice of the timing and the extent of information released to bidders about an impression.
While valuations are private to bidders, there are two possibilities as far as the information available to the ad exchange on these bidder valuations is concerned: One, the ad exchange has no reliable knowledge about bidder valuations. For this situation, we develop simple information revelation policies that do not use any knowledge of the valuations and establish their performance guarantees. Two, the ad exchange has distributional knowledge about bidder valuations. For this situation, we develop an informed heuristic that exploits this information. While the heuristic continues to offer the same performance guarantee as that of the simple policies, we show that its performance on a comprehensive test bed is near-optimal. The welfare implications of the information revelation policy of the ad exchange on other stakeholders of the ecosystem are also analyzed.
We consider the problem of optimally allocating contiguous rectangular presentation spaces in order to maximize revenues. Such problems are encountered in the arrangement of products in retail ...shelf‐space and in the design of feature advertising displays or webpages. Specifically, we allow (i) the shape of a product's presentation to have a vertical as well as a horizontal component and (ii) displays to extend across multiple shelves for in‐store presentations. Since the vertical location of the shelf on which a product is displayed affects its sales, each vertical location is assigned its own effectiveness with regard to revenue generation. The problem of maximizing the total weighted revenue of a display is strongly NP‐hard. Therefore, we decompose it into two subproblems. The first consists of allocating products to different cabinets. In the second, within each cabinet, each product's units are arranged in a contiguous rectangle and assigned a location. These subproblems are solved using an innovative approach that uses a combination of integer programming and an algorithm for the maximum‐weight independent set problem. Based on computational studies on both real‐world and simulated data, we demonstrate the efficiency and effectiveness of our approach. Specifically, the revenue generated by this scheme is within 1% of the optimum for actual data and within 5% for simulated data.
This study develops a data-driven approach to solve constrained optimization problems in which the decision maker does not have an analytic form for the objective function but knows what decision ...variables affect the function. The approach makes
direct
use of the available data, rather than first using the data to estimate the objective function and then solving the problem as a traditional optimization problem. The difficulty in first estimating the unknown objective function is that the decision maker needs to have sufficient knowledge of its properties that are necessary to guide the estimation process. Thus, our approach is appropriate for situations where such structural knowledge is absent, either because the domain is very complex or because the knowledge is deliberately hidden by a partner firm that has a vested interest in the outcome of the decision. Our approach comes with a worst-case performance guarantee that improves with the characteristics (size, pervasiveness) of the available data. We illustrate our technique on a
traffic-stream mixing
problem encountered by a supply side Internet advertising network that wishes to optimize the click revenue earned from ads. A head-to-head comparison (with the existing method used) on real data shows a significant increase (≥10%, on average) in the revenue. We also demonstrate the value of our approach under more general conditions.
The online supplement is available at
https://doi.org/10.1287/ijoc.2018.0818
.
This study develops optimal transfer pricing schemes that manage software reuse in incremental software development, namely, a development regime wherein users begin utilizing parts of the system ...that are released to them even before the system is entirely completed. In this setting, conflicts can arise between developers and users from divergent interests concerning the release of functionalities in the project. The release of functionalities is influenced by reuse, i.e., the effort spent by the development team to write code that can be reused within the same project or in future projects. For example, the development team may choose to spend extra effort to make certain portions of the system reusable because doing so could reduce the effort needed to develop the entire system. However, the additional effort spent on reuse could delay the release of certain critical functionality, making such a strategy suboptimal for the users. Thus, optimal reuse decisions for developers and users could be different. In addition, from the firm's perspective, reuse decisions must not only balance the objectives of developers and users for the current project, but reuse effort may be spent to benefit future projects. Our study also highlights the fact that reuse may not always be beneficial for the firm. To this end, we consider different instances of the user-developer conflict and provide transfer pricing schemes that operate under information asymmetry and achieve two key properties: firm-level optimality and truth revelation.
This paper was accepted by Sandra Slaughter, information systems.
We consider the problem of link scheduling in a sensor network employing a TDMA MAC protocol. Our algorithm consists of two phases. The first phase involves
edge-coloring: an assignment of a color to ...each edge in the network such that no two edges incident on the same node are assigned the same color. Our main result for the first phase is a distributed edge-coloring algorithm that needs at most
(
Δ
+
1
)
colors, where
Δ
is the maximum degree of the network. To our knowledge, this is the first distributed algorithm that can edge-color a graph using at most
(
Δ
+
1
)
colors. The second phase uses the edge-coloring solution for
link scheduling. We map each color to a unique timeslot and attempt to assign a direction of transmission along each edge such that the hidden terminal problem is avoided; an important result we obtain is a characterization of network topologies for which such an assignment exists. Next, we consider topologies for which a feasible transmission assignment does not exist for all edges, and obtain such an assignment using additional timeslots. Finally, we show that reversing the direction of transmission along every edge leads to another feasible direction of transmission. Using both the transmission assignments, we obtain a TDMA MAC schedule which enables two-way communication between every pair of adjacent sensor nodes. For acyclic topologies, we prove that at most
2
(
Δ
+
1
)
timeslots are required. Results for general topologies are demonstrated using simulations; for sparse graphs, we show that the number of timeslots required is around
2
(
Δ
+
1
)
. We show that the message and time complexity of our algorithm is
O
(
n
Δ
2
+
n
2
m
)
, where
n
is the number of nodes and
m
is the number of edges in the network. Through simulations, we demonstrate that the energy consumption of our solution increases linearly with
Δ
. We also propose extensions to account for non-ideal radio characteristics.
Although the impact of layout on the productivity of manufacturing systems is well recognized, a quantification of this impact is an issue that is often ignored or crudely approximated in practice. ...When evaluating competing layouts for a manufacturing system, the trade-off between their relative benefits and their relative costs underlines the need for a reasonably accurate comparison of the productivity offered by these potential layouts. In this paper, we argue for this approach by comparing the productivity of two well-known layouts in robotic-cell manufacturing: circular and linear.
We consider the problem of optimizing throughput in single-gripper, bufferless robotic cells that produce identical parts under the free-pickup criterion and the additive-travel-time metric. For cells with a circular layout, we show that the problem of finding an optimal 1-unit cycle is NP-hard. Our main algorithmic result is a polynomial-time 5/3-approximation algorithm for this problem. We then demonstrate that our algorithm provides near-optimal solutions by compiling its performance on an extensive test bed of practically-relevant instances. Finally, we use the algorithm to assess the increase in throughput for cells with a circular layout over those with a linear layout. We show that a circular layout offers a significant improvement in productivity and demonstrate the robustness of this improvement by examining the sensitivity with respect to changes in the design parameters of the robotic cell. Thus, our work provides operations managers with a tool to trade off the resulting increase in revenue with the additional cost of acquiring and maintaining a robot that can exploit a circular layout.
The “integrality” question for dynamic optimization models of inventory control asks if there exists an integral optimal policy, given integral initial inventory levels, capacities, and demand ...realizations. One practical implication of this question lies in whether or not full-truckload (FTL) shipping is optimal if customer demand is in integral number of truckloads. In this paper, we investigate the integrality question in single-product, multiechelon distribution systems and show that integrality holds under deterministic demand but fails to hold under stochastic demand. In distribution systems with stochastic demand, less-than-truckload (LTL) shipping can be significantly cheaper than the cost of the optimal FTL shipping policy, even in the presence of economies of scale. For instance, this occurs in settings where shipping costs are expected to increase in the future and/or inventories are more expensive to hold upstream than downstream. In such situations, our results highlight the importance of strategically positioning inventory: LTL shipments can offer a more balanced allocation of inventory across the distribution network, leading to benefits that can exceed the savings from FTL shipments due to economies of scale. However, when the cost parameters are fairly constant across time and inventory holding costs are not significantly higher upstream than downstream, then the difference between the costs of optimal FTL and optimal LTL shipping is provably marginal.
The online appendix is available at
https://doi.org/10.1287/opre.2016.1586
.
