Throughput Optimization in Constant Travel‐Time Dual Gripper Robotic Cells with Parallel Machines

Constant travel‐time robotic cells with a single gripper robot and with one or more machines at each processing stage have been studied in the literature. By contrast, cells with a dual gripper robot, although more productive, have so far received scant attention, perhaps due to their inherent complexity. We consider the problem of scheduling operations in dual gripper robotic cells that produce identical parts. The objective is to find a cyclic sequence of robot moves that minimizes the long‐run average time to produce a part or, equivalently, maximizes the throughput. We provide a structural analysis of cells with one or more machines per processing stage to obtain first a lower bound on the throughput and, subsequently, an optimal solution under conditions that are common in practice. We illustrate our analysis on two cells implemented at a semiconductor equipment manufacturer and offer managerial insights for assessing the potential productivity gains from the use of dual gripper robots.     

PRODUCT OFFERING,PRICING, AND MAKE‐TO‐STOCK/MAKE‐TO‐ORDER DECISIONS WITH SHARED CAPACITY

In an era of mass customization, many firms continue to expand their product lines to remain competitive. These broader product lines may help to increase market share and may allow higher prices to be charged, but they also cause challenges associated with diseconomies of scope. To investigate this tradeoff, we considered a monopolist who faces demand curves, which for each of its potential products, decline with both price and response time (time to deliver the product). The firm must decide which products to offer, how to price them, whether each should be make‐to‐stock (mts) or make‐to‐order (mto), and how often to produce them. The offered products share a single manufacturing facility. Setup times introduce disceonomies of scope and setup costs introduce economies of scale. We provide motivating problem scenarios, model the monopolist's problem as a non‐linear, integer programming problem, characterize of the optimal policy, develop near‐optimal procedures, and discuss managerial insights.     

Duality Approaches to Economic Lot‐Sizing Games

Sharing common production, resources, and services to reduce cost are important for not for profit operations due to limited and mission‐oriented budget and effective cost allocation mechanisms are essential for encouraging effective collaborations. In this study, we illustrate how rigorous methodologies can be developed to derive effective cost allocations to facilitate sustainable collaborations in not for profit operations by modeling the cost allocation problem arising from an economic lot‐sizing (ELS) setting as a cooperative game. Specifically, we consider the economic lot‐sizing (ELS) game with general concave ordering cost. In this cooperative game, multiple retailers form a coalition by placing joint orders to a single supplier in order to reduce ordering cost. When both the inventory holding cost and backlogging cost are linear functions, it can be shown that the core of this game is non‐empty. The main contribution of this study is to show that a core allocation can be computed in polynomial time under the assumption that all retailers have the same cost parameters. Our approach is based on linear programming (LP) duality. More specifically, we study an integer programming formulation for the ELS problem and show that its LP relaxation admits zero integrality gap, which makes it possible to analyze the ELS game by using LP duality. We show that there exists an optimal dual solution that defines an allocation in the core. An interesting feature of our approach is that it is not necessarily true that every optimal dual solution defines a core allocation. This is in contrast to the duality approach for other known cooperative games in the literature.     

Flexible Backup Supply and the Management of Lead‐Time Uncertainty

We consider replenishment decisions for a constant rate demand environment from a supplier with uncertain lead times. We study the potential use of a flexible backup supplier as an emergency response to accurate lead‐time information arriving at (or close after) the beginning of the demand interval and well after an original order with the stochastic lead‐time supplier has been placed. The emergency response decisions involve whether to order and how much from the flexible backup supplier, with the objective of minimizing the cost of meeting demand. We derive the optimal emergency‐response policy and clearly outline its implications on the optimized safety lead time of the original order placement and on the cost of meeting demand. We examine the impact on the use of the flexible backup supplier of factors like the arrival time of accurate lead‐time information and the response lead time of the backup supplier. We further study the potential benefits of the use of the flexible backup supplier in a dual role: as one of the two suppliers in a redundant supply system assigned to originally meet the demand and as an emergency response to later‐arriving lead‐time information. Our numerical studies illustrate the benefits from the use of the flexible backup supplier as an emergency response, but for reasonable purchase premiums and short lead times of flexible backup supply options, their use in a dual (regular and emergency response) role often leads to improved performance over safety lead‐time single and uncertain lead‐time supplier‐replenishment strategies. The benefits of the backup supply options are accentuated the higher the lead‐time uncertainty of the stochastic lead‐time supplier is.     

Hard‐to‐Solve Bimatrix Games

The Lemke–Howson algorithm is the classical method for finding one Nash equilibrium of a bimatrix game. This paper presents a class of square bimatrix games for which this algorithm takes, even in the best case, an exponential number of steps in the dimension d of the game. Using polytope theory, the games are constructed using pairs of dual cyclic polytopes with 2d suitably labeled facets in d‐space. The construction is extended to nonsquare games where, in addition to exponentially long Lemke–Howson computations, finding an equilibrium by support enumeration takes on average exponential time.     

Allocation of Returned Products among Different Recovery Options through an Opportunity Cost–Based Dynamic Approach*

In a make‐to‐order product recovery environment, we consider the allocation decision for returned products decision under stochastic demand of a firm with three options: refurbishing to resell, parts harvesting, and recycling. We formulate the problem as a multiperiod Markov decision process (MDP) and present a linear programming (LP) approximation that provides an upper bound on the optimal objective function value of the MDP model. We then present two solution approaches to the MDP using the LP solution: a static approach that uses the LP solution directly and a dynamic approach that adopts a revenue management perspective and employs bid‐price controls technique where the LP is resolved after each demand arrival. We calculate the bid prices based on the shadow price interpretation of the dual variables for the inventory constraints and accept a demand if the marginal value is higher than the bid price. Since the need for solving the LP at each demand arrival requires a very efficient solution procedure, we present a transportation problem formulation of the LP via variable redefinitions and develop a one‐pass optimal solution procedure for it. We carry out an extensive numerical analysis to compare the two approaches and find that the dynamic approach provides better performance in all of the tested scenarios. Furthermore, the solutions obtained are within 2% of the upper bound on the optimal objective function value of the MDP model.     

In‐Store Experiments to Determine the Impact of Price on Sales

This paper describes an experimentation methodology to measure how demand varies with price and the results of its application at a toy retailer. The same product is assigned different price‐points in different store panels and the resulting sales are used to estimate a demand curve. We use a variant of the k‐median problem to form store panels that control for differences between stores and produce results that are representative of the entire chain. We use the estimated demand curve to find a price that maximizes profit. Our experiment yielded the unexpected result that demand increases with price in some cases. We present likely reasons for this finding from our discussions with retail managers. Our methodology can be used to analyze the effect of several marketing and promotional levers employed in a retail store besides pricing.     

Inventory Control when the Lead‐time Changes

A single‐echelon inventory system with continuous review and Poisson demand is considered. There are standard linear holding and backorder costs but no ordering or set‐up costs. We study a change in the lead‐time, which is rather typical in connection with application of a Just‐In‐Time philosophy. Our main focus is a lead‐time decrease but we also consider a lead‐time increase. Due to the lead‐time change, the optimal steady state solution will also, in general, change. We consider the transient problem of minimizing the costs when bringing the system from its original steady state to the new steady state.     

Distributed Decision‐Making in Supply Chains and Private E‐Marketplaces

This paper develops a distributed decision‐making framework for the players in a supply chain or a private e‐marketplace to collaboratively arrive at a global Pareto‐optimal solution. In this model, no player has complete knowledge about all the costs and constraints of the other players. The decision‐making framework employs an iterative procedure, based on the Integer L‐shaped method, in which a master problem is solved to propose global solutions, and each player uses his local problems to construct feasibility and optimality cuts on the master problem. The master problem is modeled as a mixed‐integer program, and the players' local problems are formulated as linear programs. Collaborative planning scenarios in private e‐marketplaces and in supply chains were formulated and solved for test data. The results show that this distributed model is able to achieve near‐optimal solutions considerably faster than the traditional centralized approach.     

Optimal Reserve Prices in Name‐Your‐Own‐Price Auctions with Bidding and Channel Options

Few papers have explored the optimal reserve prices in the name‐your‐own‐price (NYOP) channel with bidding options in a multiple channel environment. In this paper, we investigate a double‐bid business model in which the consumers can bid twice in the NYOP channel, and compare it with the single‐bid case. We also study the impact of adding a retailer‐own list‐price channel on the optimal reserve prices. This paper focuses on achieving some basic understanding on the potential gain of adding a second bid option to a single‐bid system and on the potential benefits of adding a list‐price channel by the NYOP retailer. We show that a double‐bid scenario can outperform a single‐bid scenario in both single‐channel and dual‐channel situations. The optimal reserve price in the double‐bid scenario is no less than that in the single‐bid case. Furthermore, the addition of a retailer‐own list‐price channel could push up the reserve prices in both single‐bid and double‐bid scenarios.     

Efficient Multi‐Attribute Multi‐Unit Auctions for B2B E‐Commerce Logistics

This study is the first proposing allocatively efficient multi‐attribute auctions for the procurement of multiple items. In the B2B e‐commerce logistics problem (ELP), the e‐commerce platform is the shipper generating a large number of online orders between product sellers and buyers, and third‐party logistics (3PL) providers are carriers that can deliver these online orders. This study focuses on the ELP with multiple attributes (ELP‐MA), which is generally the problem of matching the shipper's online orders and 3PL providers given that price and other attributes are jointly evaluated. We develop a one‐sided Vickrey–Clarke–Groves (O‐VCG) auction for the ELP‐MA. The O‐VCG auction leads to incentive compatibility (on the sell side), allocative efficiency, budget balance, and individual rationality. We next introduce the concept of universally unsatisfied set to construct a primal‐dual algorithm, also called the primal‐dual Vickrey (PDV) auction. We prove that the O‐VCG auction can be viewed as a single‐attribute multi‐unit forward Vickrey (SA‐MFV) auction. Both PDV and SA‐MFV auctions realize VCG payments and truthful bidding for general valuations. This result reveals the underlying link not only between single‐attribute and multi‐attribute auctions, but between static and dynamic auctions in a multi‐attribute setting.     

Competing on Time: An Integrated Framework to Optimize Dynamic Time‐to‐Market and Production Decisions

This study develops a comprehensive framework to optimize new product introduction timing and subsequent production decisions faced by a component supplier. Prior to market entry, the supplier performs process design activities, which improve manufacturing yield and the chances of getting qualified for the customer's product. However, a long delay in market entry allows competitors to enter the market and pass the customer's qualification process before the supplier, reducing the supplier's share of the customer's business. After entering the market and if qualified, the supplier also needs to decide how much to produce for a finite planning horizon by considering several factors such as manufacturing yield and stochastic demand, both of which depend on the earlier time‐to‐market decision. To capture this dependency, we develop a sequential, nested, two‐stage decision framework to optimize the time‐to‐market and production decisions in relation to each other. We show that the supplier's optimal market entry and qualification timing decision need to be revised in real time based on the number of qualified competitors at the time of market‐entry decision. We establish the optimality of a threshold policy. Following this policy, at the beginning of each decision epoch, the supplier should optimally stop preparing for qualification and decide whether to enter the market if her order among qualified competitors exceeds a predetermined threshold. We also prove that the supplier's optimal production policy is a state‐dependent, base‐stock policy, which depends on the time‐to‐market and qualification decisions. The proposed framework also enables a firm to quantify how market conditions (such as price and competitor entry behavior) and operating conditions (such as the rate of learning and inventory/production‐related costs) affect time‐to‐market strategy and post‐entry production decisions.     

Replenishment Policies for Multi‐Product Stochastic Inventory Systems with Correlated Demand and Joint‐Replenishment Costs

This study analyzes optimal replenishment policies that minimize expected discounted cost of multi‐product stochastic inventory systems. The distinguishing feature of the multi‐product inventory system that we analyze is the existence of correlated demand and joint‐replenishment costs across multiple products. Our objective is to understand the structure of the optimal policy and use this structure to construct a heuristic method that can solve problems set in real‐world sizes/dimensions. Using an MDP formulation we first compute the optimal policy. The optimal policy can only be computed for problems with a small number of product types due to the curse of dimensionality. Hence, using the insight gained from the optimal policy, we propose a class of policies that captures the impact of demand correlation on the structure of the optimal policy. We call this class (s, c, d, S)‐policies, and also develop an algorithm to compute good policies in this class, for large multi‐product problems. Finally using an exhaustive set of computational examples we show that policies in this class very closely approximate the optimal policy and can outperform policies analyzed in prior literature which assume independent demand. We have also included examples that illustrate performance under the average cost objective.     

Inventory Rationing in a Make‐to‐Stock System with Batch Production and Lost Sales

We address an inventory rationing problem in a lost sales make‐to‐stock (MTS) production system with batch ordering and multiple demand classes. Each production order contains a single batch of a fixed lot size and the processing time of each batch is random. Assuming that there is at most one order outstanding at any point in time, we first address the case with the general production time distribution. We show that the optimal order policy is characterized by a reorder point and the optimal rationing policy is characterized by time‐dependent rationing levels. We then approximate the production time distribution with a phase‐type distribution and show that the optimal policy can be characterized by a reorder point and state‐dependent rationing levels. Using the Erlang production time distribution, we generalize the model to a tandem MTS system in which there may be multiple outstanding orders. We introduce a state‐transformation approach to perform the structural analysis and show that both the reorder point and rationing levels are state dependent. We show the monotonicity of the optimal reorder point and rationing levels for the outstanding orders, and generate new theoretical and managerial insights from the research findings.     

Heuristics for Base‐Stock Levels in Multi‐Echelon Distribution Networks

We study inventory optimization for locally controlled, continuous‐review distribution systems with stochastic customer demands. Each node follows a base‐stock policy and a first‐come, first‐served allocation policy. We develop two heuristics, the recursive optimization (RO) heuristic and the decomposition‐aggregation (DA) heuristic, to approximate the optimal base‐stock levels of all the locations in the system. The RO heuristic applies a bottom‐up approach that sequentially solves single‐variable, convex problems for each location. The DA heuristic decomposes the distribution system into multiple serial systems, solves for the base‐stock levels of these systems using the newsvendor heuristic of Shang and Song (2003), and then aggregates the serial systems back into the distribution system using a procedure we call “backorder matching.” A key advantage of the DA heuristic is that it does not require any evaluation of the cost function (a computationally costly operation that requires numerical convolution). We show that, for both RO and DA, changing some of the parameters, such as leadtime, unit backordering cost, and demand rate, of a location has an impact only on its own local base‐stock level and its upstream locations’ local base‐stock levels. An extensive numerical study shows that both heuristics perform well, with the RO heuristic providing more accurate results and the DA heuristic consuming less computation time. We show that both RO and DA are asymptotically optimal along multiple dimensions for two‐echelon distribution systems. Finally, we show that, with minor changes, both RO and DA are applicable to the balanced allocation policy.     

Strong Duality for a Multiple‐Good Monopolist

We characterize optimal mechanisms for the multiple‐good monopoly problem and provide a framework to find them. We show that a mechanism is optimal if and only if a measure μ derived from the buyer's type distribution satisfies certain stochastic dominance conditions. This measure expresses the marginal change in the seller's revenue under marginal changes in the rent paid to subsets of buyer types. As a corollary, we characterize the optimality of grand‐bundling mechanisms, strengthening several results in the literature, where only sufficient optimality conditions have been derived. As an application, we show that the optimal mechanism for n independent uniform items each supported on [c,c+1] is a grand‐bundling mechanism, as long as c is sufficiently large, extending Pavlov's result for two items Pavlov, 2011. At the same time, our characterization also implies that, for all c and for all sufficiently large n, the optimal mechanism for n independent uniform items supported on [c,c+1] is not a grand‐bundling mechanism.     

Priority Rules for Multi‐Task Due‐Date Scheduling under Varying Processing Costs

We study the scheduling of multiple tasks under varying processing costs and derive a priority rule for optimal scheduling policies. Each task has a due date, and a non‐completion penalty cost is incurred if the task is not completely processed before its due date. We assume that the task arrival process is stochastic and the processing rate is capacitated. Our work is motivated by both traditional and emerging application domains, such as construction industry and freelance consulting industry. We establish the optimality of Shorter Slack time and Longer remaining Processing time (SSLP) principle that determines the priority among active tasks. Based on the derived structural properties, we also propose an effective cost‐balancing heuristic policy and demonstrate the efficacy of the proposed policy through extensive numerical experiments. We believe our results provide operators/managers valuable insights on how to devise effective service scheduling policies under varying costs.     

Tight Revenue Bounds With Possibilistic Beliefs and Level‐k Rationality

Mechanism design enables a social planner to obtain a desired outcome by leveraging the players' rationality and their beliefs. It is thus a fundamental, but yet unproven, intuition that the higher the level of rationality of the players, the better the set of obtainable outcomes. In this paper, we prove this fundamental intuition for players with possibilistic beliefs, a model long considered in epistemic game theory. Specifically, • We define a sequence of monotonically increasing revenue benchmarks for single‐good auctions, G⁰≤G¹≤G²≤⋯, where each Gⁱ is defined over the players' beliefs and G⁰ is the second‐highest valuation (i.e., the revenue benchmark achieved by the second‐price mechanism). • We (1) construct a single, interim individually rational, auction mechanism that, without any clue about the rationality level of the players, guarantees revenue G^k if all players have rationality levels ≥k+1, and (2) prove that no such mechanism can guarantee revenue even close to G^k when at least two players are at most level‐k rational.     

Experimental Results Indicating Lattice‐Dependent Policies May Be Optimal for General Assemble‐To‐Order Systems

We consider an assemble‐to‐order (ATO) system with multiple products, multiple components which may be demanded in different quantities by different products, possible batch ordering of components, random lead times, and lost sales. We model the system as an infinite‐horizon Markov decision process under the average cost criterion. A control policy specifies when a batch of components should be produced, and whether an arriving demand for each product should be satisfied. Previous work has shown that a lattice‐dependent base‐stock and lattice‐dependent rationing (LBLR) policy is an optimal stationary policy for a special case of the ATO model presented here (the generalized M‐system). In this study, we conduct numerical experiments to evaluate the use of an LBLR policy for our general ATO model as a heuristic, comparing it to two other heuristics from the literature: a state‐dependent base‐stock and state‐dependent rationing (SBSR) policy, and a fixed base‐stock and fixed rationing (FBFR) policy. Remarkably, LBLR yields the globally optimal cost in each of more than 22,500 instances of the general problem, outperforming SBSR and FBFR with respect to both objective value (by up to 2.6% and 4.8%, respectively) and computation time (by up to three orders and one order of magnitude, respectively) in 350 of these instances (those on which we compare the heuristics). LBLR and SBSR perform significantly better than FBFR when replenishment batch sizes imperfectly match the component requirements of the most valuable or most highly demanded product. In addition, LBLR substantially outperforms SBSR if it is crucial to hold a significant amount of inventory that must be rationed.     

Optimal Inventory Control with Retail Pre‐Packs

A pre‐pack is a collection of items used in retail distribution. By grouping multiple units of one or more stock keeping units (SKU), distribution and handling costs can be reduced; however, ordering flexibility at the retail outlet is limited. This paper studies an inventory system at a retail level where both pre‐packs and individual items (at additional handling cost) can be ordered. For a single‐SKU, single‐period problem, we show that the optimal policy is to order into a “band” with as few individual units as possible. For the multi‐period problem with modular demand, the band policy is still optimal, and the steady‐state distribution of the target inventory position possesses a semi‐uniform structure, which greatly facilitates the computation of optimal policies and approximations under general demand. For the multi‐SKU case, the optimal policy has a generalized band structure. Our numerical results show that pre‐pack use is beneficial when facing stable and complementary demands, and substantial handling savings at the distribution center. The cost premium of using simple policies, such as strict base‐stock and batch‐ordering (pre‐packs only), can be substantial for medium parameter ranges.