UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Three essays in operations management Hermel, Dror Z. 2013

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata


24-ubc_2013_fall_hermel_dror.pdf [ 979.45kB ]
JSON: 24-1.0102461.json
JSON-LD: 24-1.0102461-ld.json
RDF/XML (Pretty): 24-1.0102461-rdf.xml
RDF/JSON: 24-1.0102461-rdf.json
Turtle: 24-1.0102461-turtle.txt
N-Triples: 24-1.0102461-rdf-ntriples.txt
Original Record: 24-1.0102461-source.json
Full Text

Full Text

Three Essays in Operations ManagementbyDror Z. HermelA THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFDoctor of PhilosophyinTHE FACULTY OF GRADUATE STUDIES(Business Administration)The University Of British Columbia(Vancouver)September 2013c? Dror Z. Hermel, 2013AbstractThis dissertation addresses three topics in the domain of operations management.First we study the problem of profit allocation in a supply chain using a bargain-ing approach. We present a novel framework for the analysis of this problem.The application of our framework results in a prescription for the required profitallocations. We prove that in a setting where all supply chain agents can communi-cate, possibly coordinating their actions, the allocation prescribed by our bargain-ing framework coincides with the Shapley value of a cooperative game associatedwith the setting. Next, we study revenue management in the presence of strategicconsumers, who face some uncertainty regarding the product valuation. We show,contradictory to the main stream of the literature regarding strategic consumers,that under certain circumstances, the retailer may prefer facing strategic consumersrather than myopic ones. Finally, we study the issue of cross-dock operations man-agement at a shift-level. We target the main gap identified in the literature for thisissue, and present a holistic framework for the allocation of cross-dock resourcesto processing of containers and freight. We show, using simulated data that ourapproach outperforms current practices.iiPrefaceChapter 2 is co-authored by Daniel Granot and Mahesh Nagarajan. Chapter 3 isco-authored by Benny Mantin and was edited based on helpful comments fromYossi Aviv. Chapter 4 is co-authored by Nicole Adler , Hamed Hasheminia, andMichael J. Fry. In all chapters I was the main contributor. I was responsible fordeveloping the models, carrying out analysis and reporting the results, as presentedin this dissertation. Chapters 3 and 4 benefited from insightful editing commentssuggested by my advisors. All chapters will be reformatted and submitted forpublication in academic peer reviewed journals.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Bargaining For Supply Chain Profit Allocation . . . . . . . . . . . . 42.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 The Bargaining Model and Analysis . . . . . . . . . . . . . . . . 72.2.1 Illustrative Example . . . . . . . . . . . . . . . . . . . . 82.2.2 Non-pivotal Agents Cannot Communicate . . . . . . . . . 82.2.3 Non-pivotal Agents Can Communicate . . . . . . . . . . 122.3 Implications and Future Research . . . . . . . . . . . . . . . . . 202.4 Proof of Comment in Footnote 6 . . . . . . . . . . . . . . . . . . 22iv3 Selling to Strategic Consumers:on the Benefits of Valuation Uncertainty . . . . . . . . . . . . . . . . 243.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.2 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.2.1 Consumers? Valuations and Decisions . . . . . . . . . . . 283.2.2 The Seller?s Pricing Decisions . . . . . . . . . . . . . . . 303.3 Model Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.4 The Effect of Consumer Return Policies . . . . . . . . . . . . . . 363.5 Numerical Study . . . . . . . . . . . . . . . . . . . . . . . . . . 383.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.7 Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444 The Multi-Mode Resource-Constrained Cross-Dock Scheduling Prob-lem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.2 Review of Related Literature . . . . . . . . . . . . . . . . . . . . 494.3 Model Development . . . . . . . . . . . . . . . . . . . . . . . . 524.3.1 Stage 1: Container Clustering . . . . . . . . . . . . . . . 534.3.2 Stage 2: Dock-Door Assignment . . . . . . . . . . . . . . 544.3.3 Stage 3: Workflow Scheduling . . . . . . . . . . . . . . 564.3.4 Stage 4: Container Scheduling . . . . . . . . . . . . . . . 624.4 Numerical Study . . . . . . . . . . . . . . . . . . . . . . . . . . 634.4.1 Description of Simulation-Generated Data and Assumptions 634.4.2 Evaluating MRCDSP Stage 2: Optimal Dock-Door As-signment . . . . . . . . . . . . . . . . . . . . . . . . . . 654.4.3 Evaluating MRCDSP Stage 3: Workflow Scheduling . . . 674.4.4 Evaluating MRCDSP Stage 4: Container Scheduling . . . 704.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734.6 Model Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 754.7 Algorithm for Cluster Generation . . . . . . . . . . . . . . . . . . 76Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77vList of TablesTable 3.1 Valuation Transition Probability . . . . . . . . . . . . . . . . . 29Table 3.2 Surplus Comparison: Buying In Period 1 vs. Waiting For Pe-riod 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Table 3.3 The Seller?s Expected Revenue For the Second Period . . . . . 32Table 3.4 Surplus Comparison: Buying In Period 1 vs. Buying In Period2 With Returns Policy - Refund r f . . . . . . . . . . . . . . . 46Table 4.1 Comparison of QAP, cdQAP, and mdQAP . . . . . . . . . . . 66viList of FiguresFigure 3.1 Revenue For The Different Pricing Policies . . . . . . . . . . 40Figure 3.2 Profit When Consumers Are All Myopic Or All Strategic . . . 43Figure 4.1 Flow of Information Between MRCDSP Phases . . . . . . . . 49Figure 4.2 Example of Container Clustering . . . . . . . . . . . . . . . . 54Figure 4.3 Cluster Processing Time as a Function of Allocated Resources 68Figure 4.4 Efficiency Gains - Cluster Makespans : MRCDSP Stage 3 vs.Random-Assignment . . . . . . . . . . . . . . . . . . . . . . 69Figure 4.5 Illustrative Example - MRCDSP Stage 4 for Different Cross-Dock Resource Levels . . . . . . . . . . . . . . . . . . . . . 71Figure 4.6 Percent Improvement of the MRCDSP Stage 4 vs Random As-signment Per Mode . . . . . . . . . . . . . . . . . . . . . . . 73viiAcknowledgmentsThe dissertation presented herein is a by product of an ongoing process of mypersonal growth and evolvement as an academic researcher and as an individual.Throughout this ongoing endeavour, I have learned much about myself and aboutmy ability to partake in research aimed at creating (possibly) useful and (hopefully)interesting knowledge.I want to extend my gratitude to those who provided me with the opportunityto partake in this very rewarding and satisfying journey, and at times shared theexperience with me, helping me pave my way. First and foremost, I wish to thankmy advisors - Daniel Granot, Mahesh Nagarajan - who offered me their time andpatience, and shared with me their vast knowledge and experience. I further thankmy advisors - Frieda Granot, Daniel Granot, and Mahesh Nagarajan - for providingme with extensive funds during my PhD studies, a priceless contribution whichenabled me to devote all of my time to my development as a future academic.I want to thank my co-authors. Specifically, I want to thank Mike Fry for histimeless efforts helping revise Chapter 4 of this dissertation, and for agreeing toserve as a dissertation committee member. Finally I want to thank a number offriends. Benny Mantin, a co-author, mentor, and friend. Hamed Hasheminia, afriend who has shown me that patience and hard work really do payoff in the longrun. And last, but definitely not least, I wish to thank Antoine Saure and GregWerker, who were my second family during my time at UBC.My final yet most important gratitude goes to my loving family.viiiDedicationTo Eitan Gilboa HermelixChapter 1IntroductionThis dissertation presents three essays, each contributing to the field of operationsmanagement by attempting to mitigate a gap identified in the academic literature.In each essay we introduce relevant existing concepts from economics and mathe-matics, adapted to our settings, and derive new results, insights, and methodologies,that enable a better understanding of these settings. We can classify the essays com-prising this dissertation not only by the problem they target, but also by the levelof planning addressed in each. The first essay focuses on strategic issues of sup-ply chain formation, structure, and coordination. The second essay addresses thetactical issue of revenue management when consumers face valuation uncertainty.The third essay focuses on operational issues arising in a cross-dock facility whenplanning a shift level schedule of resources to tasks.In the first essay we study a bargaining problem in a supply chain setting, wheredecentralized decision makers must decide how to cooperate. Specifically, we fo-cus on a single pivotal agent and N non-pivotal agents bargaining over the alloca-tion of profits they generate by cooperation. Our approach to this problem usinga bargaining framework should be contrasted with the existing practice in the op-erations management and economics literature to coordinate decentralized supplychains using a contract type mechanism. The specifics of the contract, however,are often left unaddressed, and it is natural to think of these contract details asagreed upon by the agents through negotiations. We propose an adaptation of theNash bargaining framework to model negotiations. Namely, we present a novel1methodology for construction of the disagreement outcome using readily availabledata, endogenous to the problem, rather than using an exogenously determineddisagreement outcome, which is often the case in many models.We analyze the problem under two distinguishable scenarios which differ inthe ability of the non-pivotal agents to communicate amongst themselves, possiblycoordinating their actions. In the setting where the non-pivotal agents are not al-lowed to communicate among themselves, application of our framework leads to aprescribed supply chain structure and a profit allocation scheme given by a simpleclosed form formula. This allocation scheme constitutes a Nash-Nash equilibriumto the underlying problem, an inter-related system of bi-lateral Nash bargainingproblems between the pivotal agent and each of the non-pivotal agents. In thecomplementary case, where non-pivotal agents can communicate, we prove thatour framework leads to a Nash bargaining solution which coincides with the Shap-ley value of an associated cooperative game.In the second essay we consider a profit maximizing seller who encountersconsumers over two periods. The consumers face valuation uncertainty in the firstperiod, which is resolved in the second period. We show that the seller may benefitfrom encountering strategic, rather than myopic consumers. While this result isnot new, our novel model explains this phenomena using a simple setting of val-uation change, rather than by more complex concepts such as patience level or acomplex mathematical model (and end of horizon conditions within that model) aswas previously done.After establishing the optimal pricing policy, and the possible benefit from en-countering strategic consumers, we extend our model to allow for product returns.We analyze the case where all consumers are strategic, focusing our attention onthe benefits the seller may obtain offering a return option for products sold in thefirst period. We find that the seller could enhance revenues by offering consumersa return option. Moreover, we establish that the seller may benefit from providinga full, rather than a partial refund for the returns.In the third essay we propose a framework for container scheduling and re-source allocation decisions at a cross-dock facility. Our approach minimizes mate-rial flow and optimizes the scheduling of inbound and outbound containers subjectto resource constraints at the cross-dock. While the issues of container scheduling2and resource allocation problems, at cross-dock facilities, have been studied previ-ously in isolation, our work is the first to consider a complete view of cross-dockoperations, providing optimal dock-door-to-container and resource allocations. Wepresent a comprehensive framework that includes container clustering to reduce theproblem size, a dock-door assignment algorithm, and container scheduling modelsthat can be solved to optimality for practically-sized problems. We conclude byshowing, using a comparative numerical study, that our approach outperforms cur-rent practice at a large cross-dock facility. Carrying out our approach on simulateddata reduces the average time required for processing a set of containers by 37%and reduces the weighted-distance material traveled within the cross-dock by 45%.Each of the essays is self contained and contains the relevant assumptions,literature review, and conclusions, which are not repeated in separate sections. Therest of the dissertation is organized so that each chapter includes one essay. Proofsnot included in the body of the essays are included in a technical appendix.3Chapter 2Bargaining For Supply ChainProfit Allocation2.1 IntroductionSupply chains have been a source for research in many fields for the past fewdecades. Specifically, the issue of coordination among decentralized supply chainparticipants has received much attention in the economics, operations management,logistics, and industrial engineering literature. This is largely due to the fact thatdecentralized decision making often leads to inefficiencies with respect to coordi-nated decision making. One well studied example is double-marginalization (Spen-gler (1950)). Many of the studies on coordination take an industrial-organizationapproach (c.f. Bolton and Dewatripont (2005)), modelling interactions betweenagents as a non-cooperative game, where the result is a channel coordinating con-tract, for the setting at stake (e.g., Cachon and Lariviere (2005); Pasternack (1985);Bernstein and Federgruen (2005)). While this non-cooperative approach enablesthe achievement of significant insights in certain scenarios, it has a major drawbackin the form of dependence of the outcome on specific modeling choices. Examplesfor this are: The sequence of events which is not always based on some sound logicand in some cases may even be random (e.g., Compte and Jehiel (2010); Okada(2011)); the action space available for the agents may be limited to a choice ofmodel parameters, and hence lacks the ability to coordinate certain channel struc-4tures (e.g., Cachon and Lariviere (2005)).An alternative approach, which eliminates some of the aforementioned limi-tations is to approach the problem of coordination using cooperative game theoryframeworks. This approach assumes that a given cooperation structure generates acertain profit, and focuses on allocating it to the agents1 (c.f. Peleg and Sudholter(2007)). The underlying premise is that coalitions of agents cooperate in such amanner that they maximize their profits, and all values of an associated character-istic function, mapping coalitions to profit values, need to be accounted for whenallocating the profit. The allocation schemes suggested are characterized by a dif-ferent set of some (possibly) desirable properties. The Shapley value, for exam-ple, is the unique allocation that satisfies, simultaneously, the following attributes:Pareto optimality, symmetry, dummy players are allocated zero profit, and additiv-ity. Further, it may be also thought of as an allocation where each agent receivesprofits that equal the average of all his marginal contributions to all coalitions2.Other cooperative solution concepts prevalently used in the operations manage-ment literature are: the Nucleolus, the Core Set, the von Neumann-MorgensternStable Set, and the Nash-Bargaining Solution (NBS).In a supply chain setting, different agents have some incentive "to cooperate,but also have some conflicting interest with respect to how this cooperation shouldbe carried out" (Muthoo (1999)), bargaining (or negotiating) appears to be a naturalapproach for the determination of the cooperation structure, and the resulting profitallocation. In this study we propose a bargaining framework for supply chain profitallocation using the foundations set-forth in the seminal papers by Nash (Nash(1950);Nash (1953)) regarding a prescription for an allocation resulting from bar-gaining over a profit achievable under cooperation, where no-cooperation leads toinefficiency, in the sense that the profit achievable under cooperation is greater thanthe profit possible under no-cooperation (the latter outcome is often referred to asthe disagreement outcome).Our work joins many recent papers in the operations management literaturethat incorporate bargaining into their methodology. Many of these papers revisit1We emphasize that this is significantly different from studying a revenue sharing type mechanismfor coordination.2For further reading on the Shapley value we refer the readers to Roth (1988)5existing (and well studied) coordination mechanisms (or supply chain structures),and focus on the effect of incorporating bargaining on model parameters (as is thecase for example in Wu et al. (2009), and Feng et al. (2012)). We, however, fol-low Nagarajan and Bassok (2008), Lovejoy (2010), and Aydin and Heese (2012),and provide an holistic approach, using the bargaining framework to carry out theanalysis of the system to achieve, or predict, the cooperation structure of the sup-ply chain that is the result the negotiations process, as well as the associated profitallocation.Nagarajan and Bassok (2008), Lovejoy (2010), and Aydin and Heese (2012),study a two echelon supply chain with a pivotal agent, e.g., a monopolist retailer,and a set of N non-pivotal agents, e.g., suppliers or manufacturers. In Nagara-jan and Bassok (2008), the suppliers provide complementary products, in Lovejoy(2010), they deliver fully substitutable products, and in Aydin and Heese (2012),the suppliers provide partially substitutable products, in the context of an assort-ment problem). Our approach, based on the Nash Bargaining framework, providesa unified approach, and enables the study of all of these systems (as well as a widerange of other systems and settings).Our framework prescribes a profit allocation scheme based on the expectedresult of a simultaneous negotiation process carried out by the agents in the sys-tem, all possessing common and complete information. The inputs required by ourframework are, essentially, the same inputs required for a definition of a cooper-ative game - the set of agents (and all possible coalitions), and a "characteristicfunction" (mapping coalitions to values). In the supply chain context, the possi-ble coalitions are, for example, the cooperation structures achievable by a singlepivotal agent, e.g., retailer, and N non-pivotal agents, e.g., suppliers or manufac-turers. The different profits resulting from these cooperating structures can be usedto define the values of the characteristic function3. We turn to the Nash Bargainingproblem in order to determine the profit allocation scheme to achieve our desiredallocation4.3In this study we assume that this value is provided to us as exogenous data. However, we notethat this may not necessarily be the case, and the profits may need to be calculated based on somegiven demand function. The profit is then calculated assuming a unique decision maker for eachcoalition - equivalent to full cooperation for each coalition.4We mention that even though we analyze and discuss a supply chain structure consisting of6We will assume, as we justify in section 4.3, that bargaining is carried out byall agents that are members of the coalition generating the maximum achievableprofit, and that these agents bargain over this profit. The disagreement outcome,for this bargaining setting, is not necessarily straightforward to identify. Surpris-ingly, despite the impact of the disagreement outcome on the resulting allocation(Binmore et al. (1989)), it is a common assumption in the bargaining literaturethat these outcomes are given exogenously. In order to appropriately account forthe disagreement outcome, our suggested framework uses the information avail-able to construct these independently. Our approach to construct the disagreementoutcome is based on the assumption that in case bargaining with all non-pivotalagents, N, breaks down, the pivotal agent attempts to establish cooperation withthe sub-coalition S1, S1 ? N, yielding her the highest possible payoff. If in turn,bargaining with S1 breaks down, the pivotal agent attempts to achieve cooperationwith a new sub-coalition, S2, S2 ? S1, etc., until reaching such a sub-coalition forwhich the consequences of failure to reach an agreement is clear to all parties.We present our framework under two complementary scenarios. In one, welimit the ability of non-pivotal agents to communicate, as may be the case if weaccount for anti-trust law. We achieve a closed form formula for the resultingallocation scheme. This allocation possesses certain lucrative properties: By con-struction, it is an interior point of the core, and adheres to the axioms introduced byNash (Nash (1950);Nash (1953)) for the NBS; further, it constitutes a Nash-Nashsolution concept to the assortment problem presented in Aydin and Heese (2012).In the complementary setting, the non-pivotal agents are allowed to communicate,and the allocation scheme achieved through our bargaining framework coincideswith the Shapley value of the corresponding cooperative game.2.2 The Bargaining Model and AnalysisWe will first consider a simple example to demonstrate some of the challenges weface in the bargaining problem. Subsequently, we formally introduce and analyzethe general supply chain bargaining problem.two-echelons throughout this paper, our analysis carries through for any multi-echelon system wherethere is at least a single pivotal agent facing a given and finite number of non-pivotal agents72.2.1 Illustrative ExampleConsider the following three person bargaining situation: a pivotal agent, denotedby R, designating a retailer, and two other agents, denoted 1 and 2, designating,respectively, Manufacturer 1 (M1) and Manufacturer 2 (M2). The agents can coop-erate and achieve profits as follows. If all three agents cooperate, they can securea profit of 9 (denoted by v(R,1,2)). If only R and M1 cooperate they achieve aprofit of 7 (denoted v(R,1)), and if only R and M2 cooperate, they can get a profitof 5 (denoted v(R,2)). No other options for cooperation yielding positive profitsare available for the agents5.Given the profits that R, M1, and M2 can achieve from cooperation, we wouldlike to address the question of how the three agents will divide between them theprofit, 9, which they can achieve if all three decide to cooperate. Presumably,they will resort to some sort of bargaining to determine their share of the profits.Accordingly, we will employ the Nash Bargaining (NB) framework to model thebargaining process among the agents, and thus ensure that the profit allocations wederive possess certain desirable properties.To apply the NB framework, we need to identify the set, S, on which the par-ties bargain, which is the profit of 9 if all three decide to cooperate, as well as thedisagreement outcome if the parties fail to reach an agreement. Usually, in the NBframework the disagreement outcome is exogenously given, reflecting outside op-portunities available to the agents. The main challenge that we face is the absenceof an externally given disagreement outcome, and we overcome this challenge byexplicitly accounting for the players? outside option if bargaining breaks down.Apparently, the analysis depends crucially whether the non-pivotal agents are,or are not, able to communicate. Accordingly we will separately consider thesetwo cases.2.2.2 Non-pivotal Agents Cannot CommunicateCommunication and coordination between the non-pivotal agents are not possibleif their relations are governed by anti-trust laws such as the Sherman Antitrust Act5Note that we implicitly assume monotonicity. This assumption is required only for the settingwhere the non-pivotal agents can communicate, where it is discussed explicitly. When comparingthe two setting this assumption is also imposed on the non-communicating setting8of 1890, the Clayton Act of 1914, the Celler-Kefauver Act of 1950, etc.Let us consider first the illustrative example. If bargaining over the profit allo-cation of v(R,1,2) = 9 collapses, R can either bargain with M1 over v(R,1) = 7, orshe can bargain with M2 over v(R,2) = 5, but naturally, she cannot bargain againwith both M1 and M2, since it is assumed that this bargaining has collapsed. Thebargaining is carried out by R, who negotiates with M1 or M2, separately, regardingher share of v(R,1) and v(R,2), if M1 or M2, respectively, is chosen by R as her bar-gaining partner. Now, R can leverage the fact that M1 and M2 cannot communicateand possibly coordinate their actions, to induce M1 and M2 to offer her increas-ingly larger shares of v(R,1) and v(R,2), respectively, just to be chosen by R asher sole bargaining partner. At the limit, this would result with M2 offering R theentire value of v(R,2) = 5 just to be selected by R as her only bargaining partner.Therefore, the inability of the non-pivotal players to communicate implies that M2has relinquished completely his share of v(R,2) = 5 to R, at the stage where R iscarrying out bilateral bargaining with M1 and M2.For each non-pivotal agent Mi, we will refer to R?s outside option with respectto Mi, as the best R and the rest of the non-pivotal players can do at the absence ofMi. Thus, R?s outside option with respect to M1 is v(R,2) and her outside optionwith respect to M2 is v(R,1).Let us turn back now to the bargaining problem between R, M1 and M2, overv(R,1,2). In this problem, R can claim that the bargaining with each non-pivotalagent, Mi, should exclusively be on the marginal profit that can be achieved withthe help of Mi, above R?s outside option with respect to Mi. That is, bargainingwith M1 should be only on (v(R,1,2)? v(R,2)), bargaining with M2 should onlybe on (v(R,1,2)? v(R,1)), and, in view of the outcome in bilateral bargainingstage, R has an exclusive claim over v(R,2). Employing Nash?s symmetry prin-cipal, beyond the disagreement outcome, we conclude that M1?s allocation shouldbe exactly equal to R?s allocation from bargaining over (v(R,1,2)? v(R,2)), andM2?s allocation should be exactly equal to R?s allocation from bargaining over(v(R,1,2)?v(R,1)), and R exclusively claims v(R,2), and we derive the followingallocation of v(R,1,2):9XR =v(R,2)+(v(R,1)? v(R,2))2+(v(R,1,2)? v(R,1))3= 623X1 =(v(R,1)? v(R,2))2+(v(R,1,2)? v(R,1))3= 123X2 =(v(R,1,2)? v(R,1))3=23.(2.1)Let us extend the analysis, and suppose {M1,M2,M3} is a set of three manufactur-ers. R can cooperate with any subset of them yielding profits as follows:v(R,1,2,3)? v(R,1,2)? v(R,1,3)? v(R,2,3)? v(R,1)? v(R,2)? v(R,3).All other coalitions generate zero profits. We would like to use the NB frameworkto determine the allocation of v(R,1,2,3) among all agents. We begin by iden-tifying the outside options that R has when she bargains with each non-pivotalagent, which are as follows: When bargaining with M1, R?s outside option isv(R,2,3); when bargaining with M2, R?s outside option is v(R,1,3); and, whenbargaining with M3, R?s outside option is v(R,1,2). Then, as we have done in thetwo non-pivotal agents example, taking into account R?s outside options and em-ploying Nash?s symmetry axiom we conclude as follows: Over the marginal profit(v(R,1,2,3)?v(R,2,3)), R?s and M1?s shares should be equal; over (v(R,1,2,3)?v(R,1,3)), R?s and M2?s shares should be equal; over (v(R,1,2,3)?v(R,1,2)), R?sand M3?s shares should be equal, and R exclusively claims v(R,2,3). The resultingoutcome isXR =v(R,2,3)+(v(R,1,3)? v(R,2,3))2+(v(R,1,2)? v(R,1,3))3+(v(R,1,2,3)? v(R,1,2))4X1 =(v(R,1,3)? v(R,2,3))2+(v(R,1,2)? v(R,1,3))3+(v(R,1,2,3)? v(R,1,2))4X2 =(v(R,1,2)? v(R,1,3))3+(v(R,1,2,3)? v(R,1,2))4X3 =(v(R,1,2,3)? v(R,1,2))4.(2.2)10The analysis can be easily extended to the general case. Specifically, thevarious coalitions are ordered in decreasing order of the profits they generate,v(R,T ?1 ) ? v(R,T?2 ) ? v(R,T?3 ) ? ..., where it is assumed that T?1 is the set, N,of all manufacturers. Let T ?k denote the coalition with the highest coalitional value,or, equivalently the smallest index, such that for each i ? N, there exists a j, j ? k,such that Mi /? T ?j . Thus, k is the smallest index such that R has an outside option,T , T ? {T ?1 , ...,T?k }, with respect to any non pivotal agent.As in the example previously considered, R bargains with each agent only overthe profit margin above the outside option that R has with respect to this agent. Toderive the allocation vector of v(R,T ?1 ) in the general case, let Q j denote the set ofnon-pivotal agents entitled to a share of the margin v(R,T ?j )? v(R,T?j+1). Then,Q j =???N if j = 1,Q j?1?T ?j for j ? 2, ...,k.(2.3)It follows from the above discussion that if Nash?s symmetry axiom is ap-plied to determine the allocation of the marginal profits, v(R,T ?j )? v(R,T?j+1),j = 1, ...,k? 1, among all entitled non-pivotal agents, Q j, and R, then each agenti ? Q j is allocated:pi j =v(T ?j)? v(T ?j+1)|Q j|+1, j = 1, ...,k?1.Accordingly, we derive a closed form expression for the allocation vector of theprofit, v(R,T ?1 ), referred to as the bargaining solution and denoted XBS:XBSR = v(R,T?k )+?jpi j, and XBSi = ?j|i?Q jpi j, i ? N. (2.4)The bargaining solution XBS, given by (2.4), coincides with the bargaining so-lution derived independently by Aydin and Heese (2012) using a completely dif-ferent approach. In their setting, the pivotal agent carries out bi-lateral bargainingwith each of the non-pivotal agents regarding cooperation and profit allocation. Thebargaining problems, each carried out between the pivotal agent and a single non-11pivotal agent, are modelled as NB problems. These problems are inter-related bythe disagreement outcomes that the pivotal agent utilizes in each of the problems.Specifically, the pivotal agent?s disagreement outcome in the bargaining problemwith each agent i is her allocation in the bargaining problem between her and allother agents except agent i. In that respect, Aydin and Heese?s approach is similarto our outside option approach. Aydin and Heese?s solution, where an inter-relatedsystem of bargaining problems is solved in equilibrium, is referred to in the litera-ture as a Nash-Nash equilibrium.Proposition 1 XBS, given by (2.4), is a Nash-Nash equilibrium to the non-cooperativegame wherein R simultaneously negotiate bilaterally with all the non-pivotal agentsabout the allocation of v(R,T ?1 ).The proof of the proposition follows immediately from the coincidence of XBSwith the profit allocation proposed in Theorem 1 of Aydin and Heese (2012), whichcan be verified by substituting ?k = 1 for all k, in their formula (9).2.2.3 Non-pivotal Agents Can CommunicateNotwithstanding anti-trust laws, communication and coordination between the non-pivotal agents could be possible, for example, if the products they offer are rela-tively complementary.Consider again the illustrative example, where R bargains with M1 and M2 overthe allocation of v(R,1,2). As in the "no-communication" case, if the bargainingover v(R,1,2) collapses, R can still offer either M1 or M2 to bargain with her overthe respective profits the parties can achieve. However, by contrast with the "nocommunication" setting, M1 and M2 are able to communicate in this case and couldpossibly coordinate their actions in order to extract some of the profit R was ableto claim in the "no communication" case. Specifically, R may be unable to inducethe non-pivotal players, M1 and M2, to offer her successively increasing shares ofv(R,1) and v(R,2) in order to be R?s chosen bargaining partner.In fact, in the "communication case", we will assume that in the bilateral bar-gaining stage between R, M1 and M2, R is able to secure onlyv(R,1)2 andv(R,2)2 , inthe bargaining problems over v(R,1) and v(R,2), respectively.12Let us turn now to the bargaining problem over v(R,1,2). Our approach in the"communication case" in this stage is a bit different than in the "no communicationcase" presented above. Specifically, rather than deriving directly the allocation ofv(R,1,2), as it was done in the "no communication case", we will derive insteadthe disagreement outcome vector for the bargaining problem v(R,1,2).Now, as explained above, R is able to secure either v(R,1)2 orv(R,2)2 , if she bar-gains with either M1 or M2, respectively. Thus, we assume that R can securev(R,1)2if bargaining over v(R,1,2) breaks down. Following Nash?s symmetry principle,M1 can claim only a share of v(R,1) which is equal to R?s share of v(R,1) beyondthe profit, v(R,2)2 , that R can secure at the absence of M1. That is, M1 can secure aclaim v(R,1)2 -v(R,2)2 of v(R,1). Since R?s secured profit at the absence of M2 isv(R,1)2 ,M2 cannot claim any share of v(R,1).We conclude that if bargaining over v(R,1,2) breaks down in the "communi-cation case", the parties can claim the following allocations: R gets a payoff of 3 12 ,M1 gets a payoff of 1, and M2 gets zero. We will refer to the vector (3 12 ,1,0) asthe disagreement outcome for the bargaining problem over v(R,1,2). Using thedisagreement outcome (3 12 ,1,0) for the NB problem over v(R,1,2), we obtain thefollowing profit shares for the players:XR =v(R,1,2)? ( v(R,1)2 +v(R,1)?v(R,2)2 )3+v(R,1)2= 5XM1 =v(R,1,2)? ( v(R,1)2 +v(R,1)?v(R,2)2 )3+v(R,1)? v(R,2)2= 212XM2 =v(R,1,2)? ( v(R,1)2 +v(R,1)?v(R,2)2 )3= 112.(2.5)Note that, as expected, R?s share of the profit in the "communication case" islower than her share in the "no communication case", and, by contrast, M1?s andM2?s shares are larger in the "communication case"6. Further, note that this profitallocation coincides with the Shapley value of the cooperative game associatedwith the NB problem.6In fact, this statement remains true for the setting where R faces N non-pivotal agents when weassume the payoffs are such that the characteristic function for the associated cooperative game ismonotonic in the coalition size. The proof of this statement is provided below. Note that it is a directconsequence of comparing R?s payoff for both cases as provided in (2.4) and (2.19).13As in the "no communication case", let us briefly extend the discussion to thethree manufacturers case, wherev(R,1,2,3)? v(R,1,2)? v(R,1,3)? v(R,2,3)? v(R,1)? v(R,2)? v(R,3),and all other coalitions generate zero profits. Let us denote R?s allocation whenbargaining with Mi and M j over v(R, i, j), i 6= j, by ?R(i, j). Note that ?R(i, j)was derived above for the two non-pivotal agents case. Clearly, if bargainingover v(R,1,2,3) breaks down, R will choose to cooperate with the two non-pivotalagents that would lead to a maximization of her disagreement outcome. That is Rwould choose to bargain with the two agents that will offer hermax{?R(1,2),?R(1,3),?R(2,3)}, which in our example is?R(1,2) =v(R,1,2)? ( v(R,1)2 +v(R,1)?v(R,2)2 )3+v(R,1)2.Thus, ?R(1,2) forms R?s disagreement outcome in case bargaining over v(R,1,2,3)breaks down. To calculate the other agents? disagreement outcome we note that R?soutside option with respect to M1 is ?R(2,3), her outside option with respect to M2is ?R(1,3), and her outside option with respect to M3 is ?R(1,2). Thus, as in the twonon-pivotal agents example, when calculating the disagreement outcome of the twonon-pivotal agents if bargaining over v(R,1,2,3) breaks down, each of these agentscan only claim their egalitarian share from their marginal profit contribution aboveR?s corresponding outside option. We conclude therefore that the disagreementoutcome vector d(v(R,1,2,3)) = (dR(v(R,1,2,3)),di(v(R,1,2,3)), i = 1,2,3), cor-responding to R,M1,M2,M3, in the NB problem over v(R,1,2,3), is as follows:dR(v(R,1,2,3)) =?R(1,2)d1(v(R,1,2,3)) =?R(1,2)??R(2,3)d2(v(R,1,2,3)) =?R(1,2)??R(1,3)d3(v(R,1,2,3)) =?R(1,2)??R(1,2)) = 0.(2.6)We later prove the NB solution for v(R,1,2,3) with the disagreement outcome vec-tor d(v(R,1,2,3)) coincides with the Shapley value for the associated cooperativegame.We can now turn to extending our analysis to the case of a set N, of non-pivotal14agents, N = {M1,M2, ....,Mn}. We will assume that the highest profit is achievedby cooperation of the pivotal agent, R, with the entire set of non-pivotal agents, andthat v(R,T ) is monotonic in T . That is v(R,N)? v(R,T )? v(R,S) for S? T ? N.We suggest that the monotonicity assumption is reasonable since the non-pivotalagents are allowed to communicate and possibly coordinate their actions (e.g., ifv(R,T ) < v(R,S) and S ? T then all agents in T can coordinate their actions andachieve v(R,S)). Recall that we refer to (N ?{R},v(R, ?)), with v(R,S), S ? N, asthe cooperative game associated with the NB problem.All agents bargain on the their share of v(R,N). As before, we adopt the NBframework to model the bargaining process over v(R,N). The disagreement out-come, denoted d(v(R,N)), reflects the outside options of the players, stemmingfrom their abilities to form coalitions.We aim to construct a recursive formula for d(v(R,N)). Let NBS(v(R,T ),d(v(R,T )))denote the NBS over v(R,T ) with a disagreement outcome d(v(R,T )). Then, rec-ognizing R?s ability to select the cooperation structure in case bargaining breaksdown, we have that R?s disagreement outcome, dR(v(R,N)), if bargaining overv(R,N) breaks down is given by:dR(v(R,N))? maxS?N, |S|=|N|?1{NBSR(v(R,S),d(v(R,S)))}, (2.7)where NBSR is R?s allocation in the corresponding NB problem.As in the example previously considered, the disagreement outcome for anynon-pivotal agent, u, denoted du(v(R,N)), is defined to be equal to R?s marginalbenefit from the inclusion of u in the cooperation structure, which, as was in thenon-communicating case, can also be thought of as agent?s u egalitarian share ofthe profit generated above R?s disagreement outcome when not cooperating with u.That is,du(v(R,N)) = dR(v(R,N))?NBSR{v(R,N/{u},d(v(R,N/{u}))}. (2.8)A recursive formula for R?s disagreement outcome corresponding to R and any15given set of non-pivotal agents T ? N, |T |> 2, is as follows:dR(v(R,T )) = maxS?T,|S|=|T |?1NBSR{v(R,S),d(v(R,S))}, (2.9)and for any non-pivotal agent u:du(v(R,T )) = dR(v(R,T ))?NBSR{v(R,T/{u}),d(v(R,T/{u}))}. (2.10)As a base case for the recursion we have the case of a NB problem between R andany of the non-pivotal agents. Specifically, when bargaining with any non-pivotalagent u ? N,dR(v(R,{u})) =v(R,{u})2. (2.11)This enables us to recursively solve for dR(v(R,S)) for any coalition of non-pivotalagents S, and consequently, for the disagreement outcome du(v(R,S)) for all u ? S.We define a cooperative game (N ?{R},v) where v is the "characteristic func-tion" as described above to be the cooperative game associated with our Nash Bar-gaining problem, and are able to now state the following theorem.Theorem 1 The NBS over v(R,N) with a disagreement outcome, d(v(R,N)), en-dogenously generated via (2.7)-(2.11), coincides with the Shapley value of the co-operative game (N?{R},v) associated with the Nash Bargaining problem.Before presenting the proof we introduce the following notation. For any set ofnon-pivotal agents T, we will refer to (T ?{R},v) as the cooperative game associ-ated with the coalition {T ?{R}}. Further, we denote by NBSi{v(R,T ),d(v(R, t))}and Shi(T ? {R},v) the allocation to agent i ? {T ? {R}} from the NB prob-lem {v(R,T ),d(v(R,T ))} and from the Shapley value for the cooperative game(T ?{R},v), respectively.The proof is by induction on the number of non-pivotal agents. When R bar-gains with a single agent, the pivotal and non-pivotal agents share the profit equally,both according to the NB solution and the Shapley value. For clarity of exposition,let us also provide the proof for the two non-pivotal agent setting, considered in ourillustrative example, where v(R,1,2)> v(R,1)> v(R,2). As previously shown, thedisagreement outcome vector in this case is d(v(R,1,2)) = ( v(R,1)2 ,v(R,1)?v(R,2)2 ,0).16Now the Nash Bargaining solution, NBS{v(R,1,2),( v(R,1)2 ,v(R,1)?v(R,2)2 ,0)}, mustsatisfy symmetry. That is,NBSR{v(R,1,2),d(v(R,1,2))}?dR(v(R,1,2)) =NBS1{v(R,1,2),d(v(R,1,2))}?d1(v(R,1,2))NBSR{v(R,1,2),d(v(R,1,2))}?dR(v(R,1,2)) =NBS2{v(R,1,2),d(v(R,1,2))}?d2(v(R,1,2)) (2.12)NBS1{v(R,1,2),d(v(R,1,2))}?d1(v(R,1,2)) =NBS2{v(R,1,2),d(v(R,1,2))}?d2(v(R,1,2)).As well as Pareto Optimality:?i?{R,1,2}NBSi{v(R,1,2),d(v(R,1,2))}= v(R,1,2). (2.13)Solving (2.12) and (2.13) yields:NBSR{v(R,1,2),d(v(R,1,2))} =2v(R,1,2)+ v(R,1)+ v(R,2)6NBS1{v(R,1,2),d(v(R,1,2))} =2v(R,1,2)+ v(R,1)?2v(R,2)6(2.14)NBS2{v(R,1,2),d(v(R,1,2))} =2v(R,1,2)+ v(R,2)?2v(R,1)6.Then, it can be easily verified, using the explicit expression for the Shapley value,that Sh({1,2}?{R},v) = NBS{v(R,1,2),( v(R,1)2 ,v(R,1)?v(R,2)2 ,0)}, given by (2.14).We now proceed to state our induction hypothesis. For any bargaining settingwhere a pivotal agent, R, bargains with a set, S, of k?1 communicating non-pivotalagents over v(R,S), the allocation prescribed by our framework, as described byequations (2.7)- (2.11), coincides with Sh(S ? {R},v). We need to prove that,for any bargaining setting where the pivotal agent,R, bargains with a set, T , ofk communicating non-pivotal agents over v(R,T ), the allocation prescribed by ourframework coincides with the Shapley value, Sh(T ?{R},v).17Let T be an arbitrary set of k non-pivotal agents. Then, as given by (2.9):dR(v(R,T )) = maxj?T{NBSR{v(R,T/{ j}),d(v(R,(T/{ j})))}}.By the induction hypothesis, since |T/{ j}|= k?1,dR(v(R,T )) = ShR((T/{ j?})?{R},v)? maxj?T{ShR((T/M j)?{R},v)}, for some j? ? T . (2.15)By (2.10), for any non-pivotal agent, j ? T ,d j(v(R,T )) = dR(v(R,T ))?NBSR{v(R,T/{ j}),d(v(R,T/{ j}))}.By our induction step we haveNBSR{v(R,T/{ j}),d(v(R,T/{ j}))}= ShR((T/{ j})?{R},v)and from (2.15), dR(v(R,T )) = ShR((T/{ j?})?{R},v). We therefore have that forany j ? T :d j(v(R,T )) = dR(v(R,T ))?ShR((T/{ j})?{R},v)= ShR((T/{ j?})?{R},v)?ShR((T/{ j})?{R},v). (2.16)The symmetry of the NBS over v(R,T ) implies that for any two agentsi, j ? {T ?{R}}, i 6= j:NBSi{v(R,T ),d(v(R,T ))}?di(v(R,T ))=NBS j{v(R,T ),d(v(R,T ))}?d j(v(R,T ))).In particular, for R and j ? T ,NBS j{v(R,T ),d(v(R,T ))}?d j(v(R,T )) =NBSR{v(R,T ),d(v(R,T ))}?dR(v(R,T )). (2.17)18From Pareto Optimality of the NBS:|T |?j=1[NBS j{v(R,T ),d(v(R,T ))}]+NBSR{v(R,T ),d(v(R,T ))}= v(R,T ), (2.18)and by (2.16), ?dR(v(R,T ))+ d j(v(R,T )) = ?ShR((T/{ j})?{R},v), ? j ? T .We therefore have:|T |?j=1[NBS j{v(R,T ),d(v(R,T ))}]+NBSR{v(R,T ),d(v(R,T ))}=|T |?j=1[NBSR{v(R,T ),d(v(R,T ))}?ShR((T/{ j})?{R},v)]+NBSR{v(R,T ),d(v(R,T ))},which implies that:(|T |+1) ?NBSR{v(R,T ),d(v(R,T ))}?|T |?j=1ShR((T/{ j})?{R},v)) = v(R,T ),which we can re-write as:NBSR{v(R,T ),d(v(R,T ))}=v(R,T )+|T |?j=1ShR((T/{ j})?{R},v)|T |+1. (2.19)By Hart and Mas-Colell (1989, Section 2) , or Peleg and Sudholter (2007, Sec-tion 8.4)7:1|T |+1v(R,T )+1|T |+1|T |?j=1ShR((T/{ j})?{R},v) = ShR(T ?{R},v). (2.20)Therefore, by (2.19) and (2.20) we conclude that our allocation for the pivotalagent, R, derived via (2.7)-(2.11), coincides with ShR(T ?{R},v)).Next, consider any other agent, j ? T , and recall that the Shapley value satisfies7This formulation is a result of the potential function as defined in Hart and Mas-Colell (1989,Section 2). The allocation resulting from this potential function guarantees efficiency as it calls foran equal allocation of profits beyond marginal contributions.19the balanced contributions property (Myerson, 1980). That is, for any j ? T :ShR(T ?{R},v)?ShR((T/ j)?{R},v) = Sh j(T ?{R},v)?Sh j((T ?{R})/{R},v),which yields - since ? j ? T we know Sh j((T ?{R})/{R},v) = 0 - that:ShR(T ?{R},v)?ShR((T/{ j})?{R},v) = Sh j(T ?{R},v).Notice that by our construction, the allocations to the agents, resulting fromNBS{v(R,T ),d(v(R,T ))}, satisfy:NBS j{v(R,T ),d(v(R,T ))}=NBSR{v(R,T ),d(v(R,T ))}?dR(v(R,T ))+d j(v(R,T )),and recall that ?dR(v(R,T ))+d j(v(R,T )) =?ShR((T/{ j})?{R},v). Therefore:NBS j{v(R,T ),d(v(R,T ))}=NBSR{v(R,T ),d(v(R,T ))}?ShR((T/{ j})?{R},v),but since NBSR{v(R,T ),d(v(R,T ))}= ShR(T ?{R},v), we have that:NBS j{v(R,T ),d(v(R,T ))}= ShR(T ?{R},v)?ShR((T/{ j})?{R},v),which implies that: NBS j{v(R,T ),d(v(R,T ))}= Sh j(T ?{R},v), and the proof iscomplete.2.3 Implications and Future ResearchMotivated by the problem of revenue sharing in a supply chain setting, we proposea novel bargaining framework for the allocation of supply chain profits. We focuson bargaining problems where the disagreement outcome is not determined exoge-nously, and must be inferred, and constructed, based on data endogenous to theproblem. Focusing attention to this issue results in allocations that have desirableproperties in excess of those guaranteed by the NBS, which serves as a foundationfor our framework.In the setting where the non-pivotal agents can not communicate, the resultingallocation is guaranteed, by the manner of its construction, to be an internal point20of the core set. This implies a notion of stability for our solution, as well as a notionof fairness, since proper coalitions are allocated more than what they can achieveon their own. In the setting where the non-pivotal agents can communicate, the re-sulting allocation is guaranteed to also satisfy the balanced contributions property,due to its equality to the Shapley value, which also constitutes a notion of fairnessregarding the allocation.We note that both communication structures exist in practice, and a possibleramification of our analysis is that there are some possible settings, where intro-ducing limitations on the ability of certain agents to communicate, and possiblycoordinate their actions, leads to drastic reduction in the equity of allocation ofprofits in this setting, something which may not necessarily coincide with the orig-inal motivation for placing these limitations.A further implication of the allocations prescribed by our framework, relevantto supply chain coordination, is the ability to gain insight regarding the ability toimplement a mechanism to coordinate a channel via a contract. Specifically, letus assume, as is done in contract theory, that we can translate (or map) a givencontract into resulting profits, as a function of model parameters. In that case, wecan prescribe a profit allocation that would result in cooperation, and consequentlychoose contract parameters that will result in these allocations. This would provideus with a specific implementable contract to coordinate the channel.This work fills gaps in the existing supply chain management literature and bar-gaining literature. The concept of a bargaining problem in which the disagreementoutcome needs to be constructed independently, based on data endogenous to theproblem, as introduced in our framework, provides the ability to relieve the depen-dence on exogenous disagreement outcomes in certain settings. Specifically, in thesupply chain setting, it also enables a unified approach for the analysis of a widevariety of supply chain structures, thus far studied independently or un-addressed.These contributions still have much room for further development. Specifically, weidentify two promising avenues of future research. One is to extend this frameworkinto a setting where there are no pivotal agents - for example, two competing retail-ers in the supply chain setting. This would allow analysis currently un-addressableby our framework. The second, is the incorporation of uncertainty regarding profitsgenerated by the different coalitions, for example when demand is stochastic.212.4 Proof of Comment in Footnote 6We wish to prove that, for a given bargaining problem, where N non-pivotal agentsbargaining with a pivotal agent, denoted R, regarding the allocation of v(r,T ?1 ), thefollowing holds:XBSR (v(R,T?1 ))? ShR(T?1 ?R,v).We assume that the function v is monotone (as assumed for our communicatingsetting). Further we assume the notation is such that v(r,T ?j+1) = v(r,T?1 /{ j}),? j ? 1,2, ...,N.We prove by induction regarding the number of non-pivotal agents.For the base case, where |N| = 2, we can compare equations (2.2) and (2.6)and achieve that:XBSR (v(R,T?1 ))? ShR(T?1 ?R,v).Our induction hypothesis is that this holds for any case where there are |N|= knon-pivotal agents., i.eXBSR (v(R,Tj +1?))? ShR(T ?j+1?R,v) ? j = 1,2, ...,N.We will now turn to prove for the case that |N|= k+1. We begin by noting that:XBSR (v(R,T?1 )) =v(R,T ?1 )? v(R,T?2 )|k|+1+XBSR (v(R,T?2 )) (2.21)therefore:(|k|+1) ?XBSR (v(R,T?1 )) = v(R,T?1 )? v(R,T?2 )+(|k|+1) ?XBSR (v(R,T?2 )) (2.22)which we can re-write as:(|k|+1) ?XBSR (v(R,T?1 )) = v(R,T?1 )+XBSR (v(R,T?2 ))? v(R,T?2 )+ |k| ?XBSR (v(R,T?2 ))= v(R,T ?1 )+XBSR (v(R,T?2 ))? v(R,T?2 )+ |k|(v(R,T ?2 )? v(R,T?3 )|k|+XBSR (v(R,T?3 )))= v(R,T ?1 )+XBSR (v(R,T?2 ))+XBSR (v(R,T?3 ))? v(R,T?3 )+(|k|?1) ?XBSR (v(R,T?3 ))= v(R,T ?1 )+XBSR (v(R,T?2 ))+XBSR (v(R,T?3 ))? v(R,T?3 )+(|k|?1)(v(R,T ?3 )? v(R,T?4 )|k|?1+XBSR (v(R,T?4 ))22And generally we can write this as:(|k|+1)?XBSR (v(R,T?1 ))= v(R,T?1 )+j?i=2XBSR (v(R,T?i )?v(R,T?j )+(|k|+2? j)?XBSR (v(R,T?j )).Specifically, for j = k+1, which is the value we are interested in, the formulais:(|k|+1) ?XBSR (v(R,T?1 )) = v(R,T?1 )+|k|+1?i=2XBSR (v(R,T?i )? v(R,T?k+1)+XBSR (v(R,T?k+1)).Further, noting that XBSR (v(R,T?k+1) = v(R,T?k+1) we achieve that:(|k|+1) ?XBSR (v(R,T?1 )) = v(R,T?1 )+|k|+1?i=2XBSR (v(R,T?i ). (2.23)orXBSR (v(R,T?1 )) =v(R,T ?1 )(|k|+1)+1(|k|+1)|k|+1?i=2XBSR (v(R,T?i ). (2.24)By our induction hypothesis, from (2.20) and from (2.24) we have that:XBSR (v(R,T?1 )) =v(R,T ?1 )(|k|+1)+1(|k|+1)|k|+1?i=2XBSR (v(R,T?i )? (2.25)v(R,T ?1 )(|k|+1)+1(|k|+1)|k|+1?i=2ShR(T?i ?R,v) = ShR(T?1 ?R,v). (2.26)Which completes our proof that XBSR (v(R,T?1 ))? ShR(T?1 ?R,v).23Chapter 3Selling to Strategic Consumers:on the Benefits of ValuationUncertainty3.1 IntroductionConsumers are oftentimes uncertain about their valuation for future consumption ofservices and products. This arises in many instances, such as in tourism and travel,where consumers may develop positive expectations or face scheduling conflicts.Changes in valuation could be internally or externally induced. Considering theprevious example of tourism and travel, the latter change can be stimulated by ex-ternal inputs such as major events (sports, exhibitions, concerts) that coincide withthe travel plans and may be perceived both positively and negatively by differentconsumers.1When making a purchase decision, consumers possess some initial valuationfor this good. Consumers may recognize that their valuations could change over1Examples from other industries are numerous. For instance, season passes that are purchasedahead of the season in a variety of recreational sports. Another example is entertainment events suchas concerts and sport matches. An interesting example emerges from the world of sports memorabiliastimulated by transfers of players from one team to another (consider, for example, the transfer of thehockey player Wayne Gretzky from Edmonton to LA in the early 1980s, or that of the NBA playerJames Lebron from Cleveland to Miami).24time. Consumers who account for those possible future valuation fluctuations be-have strategically, whereas their counterparts, who are unaware of these fluctua-tions, or simply ignore them, can be characterized as myopic. In this chapter weseek to identify the seller?s benefits that may arise from encountering strategic,rather than myopic consumers who face valuation uncertainty. Specifically, we areinterested in addressing the following question: Can the seller be better off whenall consumers behave strategically than when they all behave myopically? Presum-ably, the seller would take advantage of the consumers? changing valuations, yet,exploiting rational expectations, strategic consumers would predict this behaviorby the retailer and adjust their purchasing decisions in the first period accordingly.Thus, strategic consumers face a tradeoff in the first period: purchase immediately,when the price might be lower, or wait for the second period until the valuationuncertainty is resolved. Hence, it is not clear a-priori whether the seller can exploitthe consumers? awareness of their future uncertainty and be better off.Modeling sellers? dynamic pricing decisions in the presence of strategic con-sumers can be traced back to the seminal works by Coase (1972) and Stokey(1981). These were later followed, among others, by works such as Gul et al.(1986) and Besanko and Winston (1990), and more recently by Su (2007), Avivand Pazgal (2008), and Dasu and Tong (2010). In this emerging literature, it isgenerally assumed that the evolution of prices over time is such that the pricingscheme is non-increasing over time. This is an outcome of discounting imposedon consumers? valuations (or surplus) over time. Strategic consumers anticipatethe non-decreasing pricing behavior, and respond accordingly by timing their pur-chases so that they maximize, separately, their consumer?s surplus. The result-ing equilibrium is such that the presence of strategic consumers hurts the seller?srevenue?strategic consumers are willing to wait as they consider buying the goodnow versus later. Hence, they introduce inter-temporal substitution which exposesthe seller to inter-temporal competition with herself, ultimately forcing the sellerto reduce its prices, thereby, reducing the profit.The operations management literature has seen a recent surge in studies ad-dressing revenue management in the presence of strategic consumers. Some ofthe related issues addressed include dynamic pricing decisions (e.g., the specialissue of the European Journal of Operational Research on revenue management25and dynamic pricing (Levin and McGill (2009)), as well as capacity and inventorydecisions, such as rationing, display of inventory (is all inventory displayed or justone unit at a time), and replenishment (e.g., Liu and Van-Ryzin (2008); Yin et al.(2009); Cachon and Swinney (2009)). The recent focus of this literature is on mit-igating the negative effect on revenue and profit associated with the presence ofstrategic consumers. For recent reviews see Shen and Su (2007) and Aviv et al.(2009). Though valuation uncertainty has been mentioned as an issue of impor-tance in a number of papers (e.g. Su (2007); Swinney (2011)), it has received littleattention in the literature.Our interest is in a setting where a seller offers a good for sale during anadvanced-selling period, and the consumers, who arrive at this time, face valua-tion uncertainty about their future valuation at time of consumption, which occursduring the selling period. Existing work is generally concerned with the conditionsunder which sellers should offer advance sales of a good. For example, Shuganand Xie (2001) show that advance selling can be used as a tool to mitigate theseller?s inability to price discriminate consumers, if consumers face uncertainty re-garding their future valuations; Nocke et al. (2010) define conditions upon whicha discounted advanced selling period price serves as a price discrimination device;Fay and Xie (2010) compare and contrast advance selling and probabilistic selling.They provide conditions on heterogeneity of consumer?s valuation for which itmay be beneficial for the seller to deploy each approach in order to mitigate uncer-tainty in demand; and Chu and Zhang (2011) investigate the relationship betweeninformation sharing and a pricing decision when advance-selling is offered. Thesetting is such that before selling commences, the seller provides some informationregarding the properties of the product, and announces a pricing scheme for pre-order units and regular sales period units of the product. Their main conclusion isregarding the optimal information sharing strategy, which depends on the expectedprofit margin and the standard deviation of consumer valuation.In this chapter, we study, in a stylized fashion, a model that emphasizes theeffects of valuation uncertainty and the consequences it may bear on dynamic pric-ing decisions in the presence of strategic consumers, who time their purchase tomaximize their own utility. We show that, contrary to the mainstream literature onstrategic consumers, due to consumers? valuation uncertainty, the optimal pricing26scheme is such that it is not necessarily decreasing over time. This result has alsobeen derived, for different reasons, by Su (2007) and Levin et al. (2010). Simi-lar to Xie and Shugan (2001), we consider the conditions under which prices mayincrease over time, when the seller offers the good in an advance selling period.We also find that the presence of strategic consumers with uncertain valuations en-ables the seller to extract additional surplus from the consumers when comparedto the case where consumers behave myopically. This finding is important. Asmentioned before, the literature is in agreement on the perils posed to sellers dueto the presence of strategic consumers. By contrast, we reveal that the presenceof strategic consumers may, in fact, be beneficial for sellers if the consumers arefaced with valuation uncertainty.We proceed to investigate how our result could be further exploited by the sell-ers when they deploy a return policy. Return policy is a common practice used tomitigate the effects of consumers? valuation uncertainty, and induce early purchas-ing. Indeed, we find that offering consumers the option of returning the productcan, in our setting, enhance sellers? revenues. Moreover, the sellers may benefitfrom offering a full, rather than a partial refund to consumers upon return of theproduct.The rest of this chapter is organized as follows: In Section 3.2 we present ourmodel, which is analyzed and discussed in Section 3.3. Consumer return policiesare considered in Section 3.4. We present a numerical study in Section 3.5 andconcluding remarks in Section 3.6. Throughout this chapter we assume the costsfor the seller are normalized to zero, and therefore we use the terms profits andrevenues interchangeably.3.2 ModelWe study a stylized two-period, dynamic pricing model, in which a profit max-imizing seller, who is endowed with Q units of a product, encounters strategicconsumers. At the beginning of the first period, to which we refer as the advance-selling period, the seller announces the first period price, p1, and N1 consumersshow up in the first period independently of the announced price (N1?Poisson(?1)).The consumers who arrive in this advance-selling period face uncertainty regard-27ing their valuation for the product. They possess an initial valuation, but, beingstrategic consumers, they are aware this valuation may change as described belowin Section 3.2.1. We assume that a proportion ?1 of the consumers that show up inthe advance-selling period have an initial valuation of VL, whereas the remainingfraction, 1? ?1, of the consumers initially value the product at VH .The consumers that arrive during the advance-selling period decide whether tobuy the product at the posted advance-selling price, p1, or postpone their purchas-ing decision until the second period. We refer to the second period as the sellingperiod. When making this wait-or-buy decision in the advance-selling period, eachconsumer accounts for three important factors: (i) The fact that in the selling pe-riod there may be a different selling price, p2; (ii) the possibility of a stock-out;and (iii) the possibility of a different personal valuation for the product.At the beginning of the selling period the valuation uncertainty is resolvedand the seller announces the second period price, p2. All consumers that arrivedin the advance-selling period who have decided to wait, return to the store, and,at the same time, another cohort of N2 consumers arrive, independently of theannounced second period price (N2 ? Poisson(?2)). Of the new consumers thatarrive, a fraction of ?2 value the product at VL, and the remaining fraction, 1? ?2,value the product at VH . Sales are carried out, and the season ends.3.2.1 Consumers? Valuations and DecisionsThe consumers that arrive in the advance-selling period face valuation uncertainty.We model this uncertainty by assuming that the consumers have an initial valuationVL or VH , and allow this valuation to change in a probabilistic fashion. Specifi-cally, consumers with initial valuation VL will end up either with valuation VL withprobability ? or with valuation VH with probability (1??), whereas consumerswith initial valuation VH will end up either with valuation VL with probability ? ,or with valuation VH with probability (1? ? ). This is summarized in Table 3.1.The change in valuation occurs simultaneously, following the end of the advance-selling period, for all consumers that arrive in the advance-selling period.Since each consumer knows his own initial valuation for the product and theprobability of change of this valuation, he can make a purchasing decision so that28Table 3.1: Valuation Transition ProbabilityInitial ValuationFinal ValuationVL VHVL ? 1??VH ? 1??his own expected surplus is maximized. Specifically, consumers who show up inthe advance-selling period compare their expected surplus from buying during theadvance-selling period with the expected surplus from postponing the purchasingdecision to the selling period. Essentially, the consumer calculates the expectedsurplus of buying the product in the first period, accounting for the possibility hisvaluation will change. He then compares this value with the expected surplus hemay achieve if he waits for the second period. This future surplus accounts forthree elements: the price that the consumer expects to encounter during the sell-ing period, his future valuation of the product, and product availability, i.e. theprobability he will be able to obtain a unit of the product in the selling period. Wedenote by p?2, the rational expectations (RE) price estimate that all the consumersdeduce that the seller will announce in the selling period2. This accounts for theseller?s goal of maximizing overall revenues when setting prices for the two peri-ods. We also denote by H(?), the RE availability probability of the product, thatis, the probability that a consumer who wants to buy a unit in the second periodwill not face a stock-out. Note that H(?) may depend on the initial valuations, theprices, the consumer arrivals (i.e., market sizes) in the two periods, the initial in-ventory, as well as the valuation fluctuation probabilities. Using these notation, wesummarize in Table 3.2 the surplus comparison that a consumer would carry outin the advance-selling period. This comparison accounts for the three types of riskdescribed above. Note that if a consumer postpones his purchasing decision to theselling period, at which the second period price, p2, is announced, the decision theconsumer faces becomes trivial?purchase the product if the immediate surplus isnon-negative (that is, if the valuation is equal to, or exceeds, p2).Note that RE enables us to conclude that all consumers of the same type should2By assuming RE we refer to the following implicit assumption: the consumers assume that giventhe observed advance selling price, the retailer will price optimally in the selling period.29Table 3.2: Surplus Comparison: Buying In Period 1 vs. Waiting For Period 2Initial Valuation Surplus From Buying In Period 1: Surplus From Buying In Period 2:VL ?p1 +?VL +(1??)VH (?p?2 +?VL +(1??)VH)H (?)VH ?p1 +?VL +(1?? )VH (?p?2 +?VL +(1?? )VH)H (?)Note that the consumer will purchase in the second period only if the realized surplus is non-negative.behave in the same manner, i.e., they either all buy immediately or all wait for thesecond period. This simplifies the analysis that the seller needs to carry out.3.2.2 The Seller?s Pricing DecisionsWe now turn our attention to the pricing decisions made by the revenue maximizingseller. Recall that a consumer that arrives in the advance-selling period compareshis expected utility from purchasing the product immediately with the expectedutility from deferring his purchasing decision to the second period. The seller?spricing decision in the first period, p1, induces one of three different possible con-sumer behaviors. If the first period price is sufficiently high, then all consumerswho arrive in the advance-selling period refrain from purchasing the product inthat period. If the price is sufficiently low, then all the consumers who are presentin the first period purchase the product. Finally, if the price is within some in-termediate range, then only some of the consumers who arrive in the first periodpurchase the product.In order to determine the price ranges that determine the aforementioned high,low, and intermediate prices, we note the following. There is a unique thresholdprice, denoted by p?1, such that if p1 ? p?1 all consumers present in the first periodbuy the product immediately. Further, there is a unique threshold price, ??p1, suchthat if p1 > ??p1, all consumers in the advance-selling period defer their purchasingdecision to the second period. Intermediate pricing, p1, p?1 < p1 ? ??p1, inducesmixed behavior where some consumers buy in the first period whereas the otherswait for the selling period.3It can be shown that a choice of an intermediate price may induce only con-3Note that inducing postponement of purchase behavior by all consumers can be easily done bysetting p1 > VH . Similarly, inducing purchasing behavior such that all consumers buy in the firstperiod, can be achieved by setting p1 < VL.30sumers with initial valuation VL (resp. VH) to purchase in the first period, if thevaluation fluctuation probabilities are such that ? > ? (resp. ? < ?). As thepricing decision, p1, induces a unique consumer behavior in the advance-sellingperiod, we can exploit this segmentation behavior to determine the remaining in-ventory for the selling period. Consequently, we can determine the optimal pricingdecisions made by the seller in both the advance-selling and selling period, as weshow below.The seller?s pricing decision is such that she maximizes her total revenue fromthe sale of the Q available units. We also assume that a stock-out, if occurs, isexperienced only in the selling period. That is, there are sufficient units to satisfydemand in the first period. The seller, therefore, solves the following optimizationproblem:max(p1,p2(p1,n1))E {p1n1 + p2(p1,n1)n2}Subject ton1 +n2 ? Q (3.1)p1, p2(p1,n1)? 0,where n1 and n2 are the actual sales quantities in each period. These quantitiesare functions of the pricing decisions as described above, as well as of the actualrealizations of the consumer arrivals.3.3 Model AnalysisWe use backward induction to solve for the pricing decisions that the seller makes.We state the following lemma about possible prices in the second period (all proofsare provided in the appendix).Lemma 1 The price set by the seller in the selling period, p2, is either VL or VH .The intuition that drives this conclusion is as follows. After valuation uncer-tainty is resolved the consumers are pooled into two distinct valuation groups -those with valuation VH and those with valuation VL. The seller can choose to set alow price that attracts all consumers, or alternatively she can set a high price such31that only high valuation consumers purchase the product in the second period. Ifthe seller decides to sell only to the high valuation group, she extracts all surplusfrom these consumers by selling at a price VH . In this case, the seller may end upwith some unsold units. Alternatively, the seller can target all consumers present inthe selling period by announcing a selling price of VL. By pricing at VL, the sellerextracts all surplus from the low valuation consumers who are able to obtain a unitof product?note that stock-outs may occur? and the high valuation consumerswho are able to obtain a unit of product are left with some positive surplus. Thesehigh valuation consumers retain a surplus of (VH?VL). Any other choice of pricingin the second period is inferior to those suggested above. Pricing at a price differ-ent from either VL or VH in the second period leaves the consumers with surplusthat the seller could have extracted without effecting the consumers? purchasingdecision.We now use Lemma 1 to analyze the seller?s decision in the selling period. Theseller needs to compare her expected revenues from setting p2 = VL or p2 = VH .We denote the seller?s expected revenue in the second period by pi2. Then, we have:pi2 = maxp2{p2 ?min(Q?n1,E[Demand2(p2)])}. (3.2)The expected demand in the selling period, denoted E[Demand2(p2)], can be de-duced using Lemma 1. Consider Table 3.3 below wherein we develop the expres-sions for pi2 for each of the possible combinations of the first period pricing de-cision (and the corresponding segmentation policy) and the second period pricingdecision (where p2 ? {VL,VH}).Table 3.3: The Seller?s Expected Revenue For the Second PeriodAdvance-SellingPriceAdvance-SellingSegmentation#Expected Revenue in Selling Periodp2 =VL p2 =VHp1 > ??p1 No One VLE[min(Q,?1 +?2)] VHE[min(Q,?1(1??)?1 +(1? ?1)(1?? )?1 +(1? ?2)?2)]p?1 < p1 ? ??p1and ? > ?Those with initialvaluation VLVLE[min(Q? ?1?1,(1? ?1)?1 +?2)] VHE[min(Q? ?1?1,(1? ?1)(1?? )?1 +(1? ?2)?2)]p?1 < p1 ? ??p1and ? < ?Those with initialvaluation VHVLE[min(Q? (1? ?1)?1,?1?1 +?2)] VHE[min(Q? (1? ?1)?1,?1(1??)?1 +(1? ?2)?2)]p1 ? p?1 All VLE[min(Q??1,?2)] VHE[min(Q??1,(1? ?2)?2)]#This column characterizes the consumers who buy in advance-selling period32Note that Table 3.3 enables the computation of all expected revenues, and fromthis the seller, and consumers, can conclude the optimal pricing policy the sellerdeploys when maximizing her expected revenues.Since all parameters are common knowledge, both the seller and all (strategic)consumers can infer the second period price for each possible scenario. The sub-sequent analysis that needs to be carried out is that of the first period pricing. Wedenote the maximum expected revenue in the selling period by pi?2 , and the decisionthe seller makes in the first period is then:p?1 = argmaxp1E {p1n1 +pi?2} . (3.3)We note that n1 is a function of both p1 and N1. We can replace (3.3) witha comparison of values based on the parameters of the model. Evaluating H(?)explicitly can be quite difficult (as discussed in Yin et al., 2009). However, themain insight stemming from this model does not require an explicit solution forH(?). The value of H(?) is derived numerically in Section 3.5 where we present anumerical study of the model.We proceed with the investigation of the effect of valuation uncertainty on pric-ing decisions. While it is not very surprising, the introduction of a possible rise inconsumer valuation (from VL to VH) brings about the possibility of price increasesbetween the advance-selling period and the selling period. Indeed, this result hasalready been demonstrated under certain properties such as ?degrees of patience?(i.e., how patient consumers are with respect to making the decision regarding theirpurchase) as in Su (2007), or what may be referred to as end of planning horizoneffects as in Levin et al. (2010). In contrast, our conclusion stems from a ratherintuitive and objective notion of valuation uncertainty. We first state this result.Proposition 2 For each possible segmentation policy induced by the optimal advance-selling period pricing decision, p?1, there exists a set of parameters under whichp2 > p?1.This result stems from valuation uncertainty, and is driven by the fact that thereis a probability that consumers may experience a product valuation increase be-tween the first and second periods. Further, this result reveals that some consumers,33arriving in the advance-selling period, are willing to accept higher prices for theproduct in the selling period after resolving uncertainty regarding their valuationfor the product, rather than pay a lower price when still facing some uncertainty.While this result may be somewhat intuitive, and may be regarded to as a notion ofvalue of information, it is surprising that the same type of analysis may yield, underdifferent combination of valuation fluctuation probabilities, a result that is exactlythe opposite. This means that some consumers may be willing to risk facing strictlynegative surplus in order to obtain a unit of product. This result is presented in thefollowing proposition:Proposition 3 Assume the seller commits to p2 = VL, then there exists a set ofparameter values such that a strategic consumer who arrives in the advance-sellingperiod, with an initial valuation VL, chooses to buy in the advance-selling periodat a price p?1 > VL.This result stems from the trade-off between expected positive utility, and theprobability of obtaining the product, H(?). However, it is still somewhat counterintuitive that a strategic consumer forgoes a future surplus, which is guaranteed tobe non-negative, for an immediate negative surplus and a future surplus that maynot be positive.We next turn our attention to the related issue of the effects of the presence ofstrategic consumers on the seller?s revenue. Before proceeding, we first define areference point to our analysis ? the case where consumers are myopic rather thanstrategic. These myopic consumers are short sighted and either ignore or are notaware that their valuation may change from the first to the second period. Whenfacing a purchase decision, they only consider their current valuation and the cur-rent posted price. That is, myopic consumers do not optimally time their purchase,like the strategic consumers. When faced with myopic consumers, any first periodpricing decision, p1, set by the seller that induces consumers with valuation VL tobuy, will induce consumers with valuation VH to buy as well. Therefore, the sellercannot segment the myopic consumers in the first period to the same degree she isable to when the consumers are strategic. This is an important insight that leads tothe following theorem.34Theorem 2 There exists a set of parameters under which the seller is better offfacing strategic, rather than myopic, consumers.We illustrate this with an example. Assume that the seller faces strategic con-sumers and that the parameters are such that the optimal decisions the seller shouldmake are such that consumers with initial valuation of VL buy the product in theadvance-selling period, while consumers with initial valuation of VH defer theirpurchasing decision to the second period. By contrast, assume that the sellerfaces myopic consumers. In the advance-selling period, this segmentation (whereonly low valuation consumers purchase the product in the first period) cannot beachieved since myopic consumers with initial high valuation always buy the goodif low valuation consumers buy the good as well. Hence, several segmentationpolicies are excluded when a seller faces myopic, rather than strategic consumers.Further, in the presence of strategic consumers, there are scenarios in which theseller?s pricing decision for the advance-selling period may be higher than for thecase of myopic consumers. This stems from the fact that myopic consumers do notaccount for future valuation when making their purchasing decision in the advance-selling period. Selling to myopic consumers with initial valuation VL implies anadvance-selling period price of p1 = VL. However, if the same consumers wereto be strategic and account for their future valuation, the selling price would behigher (assuming a positive probability of valuation increase). To conclude, theseexamples demonstrate that some segmentation possibilities available when facingstrategic consumers are not available when facing myopic consumers, and limit theability of the seller to benefit from these policies.The main conclusion from Theorem 1 is that facing strategic consumers maygive rise to new possibilities when segmenting a market of consumers with un-certain valuation which would be beneficial to the seller.4 Indeed, contrary tocurrent main stream operations and revenue management literature, the presenceof strategic consumers with uncertain valuation could be beneficial to the seller ascompared to the situation where she faces myopic consumers.4Specifically, the seller can attempt to raise awareness to future valuation fluctuations. For ex-ample, a targeted marketing campaign may induce certain consumers to behave in a strategic ratherthan myopic manner, a positive and beneficial behavior for the seller in some cases.35The next natural step in our analysis is to examine the common practices usedto mitigate the negative effects that emerge due to the presence of strategic con-sumers. This is important as we now focus on enhancing the possible positiveeffects strategic consumers offer. The literature consider two well studied prac-tices: Price guarantees and return policies. Price guarantee is a mechanism usedby sellers to impact the decision undertaken by consumers by providing the con-sumers with a promise for compensation in case of a future price decrease. For anoverview of price guarantees we refer the reader to Aviv et al. (2010), and Nalca etal. (2010). The second mechanism?a returns policy?allows consumers to returna product for some refund (see Su, 2009 for a review). A returns policy focuses onmitigating valuation uncertainty. It attempts to induce purchasing when valuationuncertainty exists. Since returns policies are related to valuation uncertainty, ratherthan the prospect of creating excess surplus in case prices decline, we analyze inthe next section its incorporation into our framework.3.4 The Effect of Consumer Return PoliciesAs stated in Su (2009), revenue management in the presence of strategic consumersis closely related to the topic of consumer return policies. Further, valuation uncer-tainty is one of the key drivers of the analysis presented in Su (2009). In this sectionwe analyze how incorporating return policies in our model, effects the seller?s opti-mal pricing decisions. Our analysis differs from the one in Su (2009) in three mainaspects: (i) we examine a two period model, and not a single period model, as inSu (2009); (ii) we allow for units return to be resold as unused units (this is rele-vant, for example, in the case of tickets for a sporting events) rather than sell themas used units; and (iii) we restrict our analysis to a choice between two discretevaluations (namely VL and VH) rather than a continuum of valuations.Our analysis in this section is based on the model we presented in section 3.3with the following adjustments: When announcing the advance-selling price, p1,the seller also announces the refund value, r, that she will reimburse consumers thatchoose to return the product. The return of products is made prior to the initiationof the selling period, and before the seller announces the selling period price, p2.While it is evident that the possibility to return the product may put the seller in36a compromising position (e.g., having excess inventory by the end of the season),it may also be viewed as a mitigating mechanism for consumers? valuation uncer-tainty by providing the consumers with some insurance in the case that the realizedvaluation is not as high as they anticipate, or in the case the surplus generated isnegative. Further, the ability to offer returned products for resale, enables the sellerto explore possibilities that are not available in the case returns are not allowed.This means that a finer segmentation policy, compared to the ones analyzed in ourmodel, may be available for the seller to exploit. Our conclusion, later formallystated as part of Proposition 4, is that there exist a set of parameter values such thatthe seller benefits from providing consumers with the ability to return the productfor some refund r > 0.The intuition behind this result is as follows. A returns policy allows the sellerto extract some surplus from high-valuation consumers that arrive in the sellingperiod, on account of consumers that bought the product in the first period, forsome price p1 >VL, and later realized their valuation for the product is actually VL,and therefore chose to return the product for a refund. The proposition reveals thatthere are scenarios that enable the seller to enhance the positive effects of facingstrategic consumers by offering the ability to return products for a refund.We turn to analyze the extent to which the seller should offer the refund inthe case of returns. Both Xie and Gestner (2007) and Su (2009) find that thereexist conditions where offering the ability to return products for a partial refundis profitable for the seller. While Xie and Gestner (2007) only analyze partialrefunds, Corollary 1 of Su (2009) states that partial refunds are always superior tofull refunds. In our setting, similar to Xie and Gestner, the seller can resell returnedunits of product and create a positive surplus. Due to this possibility we are able tostate the following.Proposition 4 There exist a set of parameter values such that the seller benefitsfrom providing consumers with the ability to return the product for a refund. Fur-ther, there is a subset of these parameter values such that the seller is better offwhen providing consumers with a full, rather than partial refund upon the returnof the product.The result in Proposition 4 stems from the trade-off between the price the seller37is able to charge in the advance-selling period, and the extra surplus that she mayachieve in the selling period. This additional surplus is based on the pricing de-cision that accounts for reselling of the returned units and the refund paid to con-sumers returning the product. As full refunds become optimal according to Propo-sition 4, one may be tempted to consider more than full refunds. However, we electto ignore such refunds, as they may induce speculative behavior by consumers, anissue that is beyond the scope of our work.The main conclusion of our analysis regarding returns policy in the presenceof strategic consumers with uncertain valuation for the product is that this practicemay benefit the seller, as it acts as an enhancer of the beneficial effects that strategicconsumers may impose. Further, providing consumers with a full, as opposed topartial refund in case of returns may be beneficial to the seller.3.5 Numerical StudyAs mentioned above, the seller?s pricing decisions and the consumers? purchasingdecisions are inter-related. This interdependency is of particular interest strategicconsumer are present. A key element in this interdependency is the probability thata consumer who defers a purchasing decision to the future is able to obtain a unitof product in the future if he does choose to purchase. As extensively discussedin Yin et al. (2009), finding this probability, H(?), is a tedious and complex task.Moreover, in our setting, this task encounters further complexities due to valuationuncertainty?an issue not addressed in Yin et al. (2009). Further, noting that allconsumers of the same type should make the same decision, results in four possibleconsumer surplus levels that need to be analyzed. Thus, while it is essential to findH(?) in order to achieve equilibria decisions, these complicating circumstancesprevent us from presenting an explicit formulation of H(?). Therefore, we resort toa numerical analysis to illustrate our insights.We were able to avoid the aforementioned difficulties by using the followingapproach. We use the thresholds on pricing decisions described in Table 3.3, andthe purchasing decisions that are induced, which provides us with bounds on therevenues achievable under each possible policy. We then check which of the result-ing prices leads to an equilibrium outcome by numerically comparing all possible38cases of consumer behavior. For each set of parameters, we calculate the maximalprofits for each segmentation policy. The first period pricing decisions for eachpolicy are the maximal prices that induce this policy, and we then verify that theresulting optimal policy for the seller (i.e., the one resulting in the highest revenue)is an equilibrium, i.e., no consumer class is better off by changing its decision. Inthis case we used the resulting expected number of consumers making a purchasefor the evaluation of H(?) and compared all possible cases for each policy to ensurethis is indeed an equilibrium.To demonstrate that no single policy universally dominates, in Figure 3.1 wedepict the revenues generated under each of the segmentation policies as a functionof the initial inventory. Note that for each value we verified that this is indeed anequilibrium.39DHBHCHAHAL (Dashed)DL (Dashed)CL (Dotted)BL (Dotted)I II IVIII V20 40 60 80 100 120Q20406080ProfitFigure 3.1: Revenue Generated For Each of the Pricing Policies as a Functionof Initial Inventory; VL = 1, VH = 2, ? = 0.9, ? = 0.95, E(N1) = 40,E(N2) = 50, ?1 = 0.1, ?2 = 0.75. To distinguish between the pricing policies,a two-letter notation is employed, the first represents the first period purchasing seg-mentation: A for All, B for consumers with initial valuation VL, C for consumers withinitial valuation VH , and D for None; the second letter stands for the price in the secondperiod: L for VL and H for VH .40Figure 3.1 depicts several segments based on the initial inventory, Q. In Seg-ment I, where the initial inventory is low, the optimal policy is to price the productso that no consumers buy the product in the first period, and then price the productat VH , clearing all inventory. The intuition behind this policy is that due to thelow levels of inventory the seller can generate a revenue of VH ?Q, as enough con-sumers, i.e. at least Q, will be willing purchase the product in the selling periodat p2 = VH . In Segment II - the pricing decision is such that only consumers withinitially low valuation for the product purchase it immediately. The posted price inthe advance-selling period is equal to the expected valuation of the low valuationconsumers. In the selling period the product is sold at a price p2 =VH . The optimalpolicy in this segment is such that it trades-off guaranteed advance-selling revenueswith the possibility of a higher per-product revenue in the selling period but alsothe risk of unmatched supply at the selling period price. The optimal pricing pol-icy suggested in segment III is such that it aims to induced advance-selling of theproduct to consumers with initially high valuation for the product. For the analyzedset of parameters this suggested policy is not an equilibrium as it is dominated bythe strategy AH, in which ALL consumers arriving in the first period purchase theproduct, and the second period price is p2 = VH . AH, is also the equilibrium opti-mal policy in segment IV. In segment V the optimal policy is such that it inducesthe purchase of the product by all consumers in the advance-selling period. Dueto the abundance of inventory remaining in the selling period, the optimal pricingpolicy is a market clearing one, where VL is the selling period price.Recall that we assume the seller?s costs are normalized to zero, and thereforein our analysis we treat revenue maximization and profit maximization as one. Weclaim that our numeric analysis regarding revenue maximization can help makeoptimal capacity decisions that would maximize profits. This can be achieved byone of two possible courses of action. The first is to incorporate the costs intothe expressions being plotted, i.e. plot profits rather than revenues, and select theoptimal course of action, ensuring it constitutes an equilibrium purchasing decisionfor the consumers. Alternatively, we can plot the cost curve together with therevenue curves. The optimal decisions would be inventory levels for which thederivatives of both curves is equal (as we recall from basic microeconomics). Notethat there may be numerous optima, and the difference between them would be the41resulting optimal pricing policy and initial inventory levels.When costs are normalized to zero, the optimal pricing policy and the corre-sponding purchasing behavior of consumers is subject to model parameters. How-ever, for certain inventory levels the optimal pricing policy is independent of modelparameters. Specifically, for very low initial inventory it is always optimal to pricesuch that all consumers defer their purchase, and in the second period the priceis VH . Above a certain level of inventory, it is optimal to segment the market sothat at least part, if not all of the first period consumers purchase the product inthe first period, and the optimal second period price is p2 = VH . Finally, there isalways a high enough inventory level such that the second period pricing policy isp2 = VL. This behavior is consistent with intuition and with the example depictedin Figure 3.1.Next, we compare the profits derived in two contrasting cases. In one, the sellerfaces only strategic consumers. In the other, she faces only myopic consumers. InFigure 3.2 we depict the profits associated with optimal pricing policy for each ofthe two cases, for a given set of parameters (valuations, arrival rates, and fluctuationprobabilities). It follows from Figure 3.2 that with low inventory levels (Q ? Q?)the seller is better off facing myopic, rather than strategic consumers. She is ableto capture all consumer surplus from high valuation consumers in both periods,which she is not able to do when facing strategic consumers, as the optimal p1is strictly less than vH . For higher initial inventory (Q > Q?) the seller is betteroff selling to strategic, rather than myopic consumers. The intuition behind thisresult is as follows. When facing strategic consumers, the seller is able to extract,upfront and from all consumers, the surplus resulting from the possibility of futurehigh valuation. Further, the seller is able to sell off all inventory in the secondperiod. This is in contrast with the case the seller faces myopic consumers, whereall consumer surplus for high valuation consumers is extracted, but some inventoryremains unsold. This example also proves Theorem 1.3.6 ConclusionsWe have shown that when a seller faces consumers who have uncertainty regardingtheir final product valuation, she may choose to increase the price of the product42Q*PMyopicPStrategic40 45 50 55Q68707274767880ProfitFigure 3.2: Profit When All Consumers Are Myopic and When All Con-sumers Are Strategic; VL = 1, VH = 2, ? = 0.05, ? = 0.1, E(N1) = 40,E(N2) = 5, ?1 = 0.75, ?2 = 0.75.over time. Further, we have also shown that she may be better off facing strategic,rather than myopic consumers, contrary to the main stream belief in the literaturethat strategic consumers have an adverse effect on revenues.Our main insights provide a new perspective on the influence of strategic con-sumers in revenue management. It may provide some justification to revisit wellknown results and incorporate the effect of valuation uncertainty on revenue man-agement decisions in the presence of strategic consumers. Further, our study mo-tivates further research into the benefits of targeting consumers. More specifically,the seller may benefit from targeting certain consumers, turning their attention tothe possibility of valuation uncertainty, and, as a result, induce more strategic be-havior.This paper can be used as a basis for future research in the area of strategicconsumers. First, finding bounds on model parameters to satisfy the main resultscould provide useful when applying dynamic pricing when facing strategic con-sumers. Next, this model assumes a fixed capacity of stock. Future research can43incorporate replenishment possibilities between the two periods or incorporationof an initial stocking decision to the model.3.7 ProofsIn this section we provide proofs not provided as part of the body of the essay.Proof of Lemma 1.We show that any feasible value of p2 is dominated either by p2 =VH or by p2 =VL.Note that if p2 >VH , no consumers buy the product; therefore, p2 =VH dominatesp2 > VH . If p2 ? VL, all consumers in the market in the second period attempt tobuy a unit of product. However, setting p2 =VL trivially generates more profit thansetting p2 < VL. For the remaining interval of VL < p2 < VH , notice that any pricehis range does not result in purchase of the product by low valuation consumers.Therefore, if the seller seeks to attract low valuation consumers she must pricethe product at p2 = VL. If the seller is not interested in attracting low valuationconsumers, she will simply set p2 =VH . Hence, p2 =VL,VH .Proof of Proposition 1.Considering Table 3.3, it is evident that there exists a set of parameters such thatfor any given p1 there is a distinguishable advance-selling purchasing behavior bythe consumers that arrive in the first period, and further, there exist a set of modelparameters such that the seller?s optimal second period pricing decision is to setp2 = VH . To prove our proposition, we show that there exist a set of parameterssuch that the first period price is lower than VH and that this first period price stillresults in the correct purchasing behavior by the consumers.Since we are looking for model parameters such that p2 =VH , we can assumethat the consumers arriving in the first period face an expected surplus of zero in thesecond period. In order to induce the required consumer behavior, the seller needsthe consumers in the first period to yield a positive surplus so that they purchasethe product in the first period. We consider the three price levels and the (four)resulting purchasing segmentation policies presented in Table 3.3 separately.Pricing scheme p1? p?1, which results in a advance-selling purchasing decisionby all consumers arriving in first period. In order for this to hold, consumers withinitial valuation VL need to obtain a positive surplus relative to the pricing scheme:44?p1+VL+(1??)(VH?VL)? 0??VL+(1??)VH ? p1. Consumers with initialvaluation VH also need to obtain a positive surplus: ?p1 +VH +? (VH?VL)? 0??VL +(1?? )VH ? p1. For p1 = Minimum {?VL +(1?? )VH , ?VL +(1??)VH}both the required constraints hold. Clearly there is a set of parameters for whichthe seller can set p1 as above and p2 =VH > p1.Pricing scheme p?1 < p1 ? ??p1. We split this case into two distinct cases ofpurchasing behavior of consumers that arrive in the first period: 1. For ? > ? ,those with initial valuation VL purchase the product in the first period. 2. For? < ? , those with initial valuation VH purchase the product in the first period.For case 1: The seller will set p1 so that a consumer?s with an initial valuationVL buy in the first period and consumers of initial valuation VH do not buy. Thisis achieved by when consumers with initial valuation VL have a positive surplusin the first period whereas consumers with initial valuation VH obtain a strictlynegative surplus. A price p1 that achieves this needs to satisfy ?VL +(1?? )VH ?p1 ? ?VL +(1??)VH . It is easy to concoct a set of parameters that satisfies thiscondition along with the condition that the optimal second period price is p2 =VHas in Table 3.3, resulting in the desired result of p2 =VH > p1.For case 2: The setting is similar to case 1, but in this case the seller sets p1so that period 1 consumers with initial valuation VH buy and consumers of initialvaluation VL defer their purchasing decision, and the proof is similar to case 1,exchanging ? and ? .Pricing scheme p1 > ??p1 induces a first period purchasing behavior such thatall consumers defer their purchase to the second period. In order to achieve thiswe need all first period consumers to obtain a negative surplus, w.r.t. p1. This isachieved, in a manner similar to above, by setting p1 that satisfies p1?max{?VL+(1??)VH ;?VL+(1?? )VH}. Choosing p1 in the range: [max{?VL+(1??)VH ;?VL+(1?? )VH},VH) results in the required consumer behavior as well as p2 =VH > p1.Proof of Proposition 2A low valuation consumer purchases in the first period only if: ?p1 +?VL +(1??)VH ? (1??)(VH ?VL)H(?). This can be rewritten as?p1+VH ?? (VH ?VL)+(1??)(VH ?VL)H(?). Since H(?) < 1, we know that (VH ?VL) ? ? (VH ?VL)+(1??)(VH ?VL)H(?). This, in turn, means that there exists p1 > VL that maysatisfy: ?p1 +VH ? ? (VH ?VL)+(1??)(VH ?VL)H(?).45Proof of Theorem 1The existence of this result follows from the example provided in Section 3.5 (seeFigure 3.2).Proof of Proposition 4If the seller offers a refund, r, then the consumers? comparison of expected surplusin the first period must now account for this refund. The resulting comparisonsare presented in Table 3.4. Note that we implicitly assume that the refund is onlyavailable to consumers who buy in the product first period, and whose final surplusfrom purchasing in the first period is negative, i.e. only consumers with a lowvaluation, VL, for the product in the selling period, if any, return the product for arefund.Table 3.4: Surplus Comparison: Buying In Period 1 vs. Buying In Period 2With Returns Policy - Refund r fInitial Valuation Surplus From Buying In Period 1 Surplus From Buying In Period 2VL ?p1 +? (VL + r f )+(1??)VH (?p?2 +?VL +(1??)VH)H (?)VH ?p1 +? (VL + r f )+(1?? )VH (?p?2 +?VL +(1?? )VH)H (?)Note that the consumer will decide to purchase in the second period only if the realized surplus is non-negative.While the seller?s comparison for the selling period surplus now needs to ac-count for the returned units when making the pricing decision, it is also apparentthat the seller can charge a higher price in the advance-selling period comparedto the case of no returns. Specifically, assuming the parameters are such that inthe advance-selling period, only low valuation consumers buy the product, p1 in-creases by ?r f , when compared to the case of no return for refund. We denote bySr the amount of units returned by consumers (and notice this is easily calculatedbased on the pooling prices). Therefore, the revenues from the return policy, whenthe pricing policy is such that p2 =VH , is: ?r f (n1?Sr)+(VH? r f )n?2, where n?2 isthe resulting number of units sold. In this case, the revenues may be an increasingfunction of r f , which implies that a refund policy benefits the seller, and further afull refund policy is better than partial refund policy.46Chapter 4The Multi-ModeResource-ConstrainedCross-Dock Scheduling Problem4.1 IntroductionCross-docks are facilities in which inbound materials are rapidly consolidated, dis-tributed, and transferred to outbound vehicles. Cross-docks reduce transportationcosts by allowing for higher capacity utilization for inbound and outbound vehi-cles. Cross-docks also promote just-in-time (JIT) production methods by sendingmaterial to final destinations in small batches in the correct sequence to reduce in-ventory costs. A recent study by the Saddle Creek Corporation (2011) reported asignificant increase in the number of firms that utilize cross-docks as part of theirsupply chain. The same report noted that firms that had recently implemented theuse of cross-docks within their supply chain reported a 14.3% reduction in annualtransportation costs. The research presented in this chapter is motivated by ourwork with a software firm that develops container packing software and with oneof its clients, a large Canadian retailer, that uses cross-docking as its main meansof transferring goods between suppliers and its retail locations.There are two main operational decisions that drive the majority of operational47costs at a cross-dock: (1) assigning containers to dock-doors; and (2) schedul-ing containers at the cross-dock (accounting for resource requirements and con-straints). Both inbound and outbound containers at a cross-dock must be assignedto a specific dock-door for the processing of freight. Improper assignments ofcontainers to doors can result in excessive travel costs within the cross-dock. Thearrival times of containers must also be carefully managed to allow for efficient useof limited resources such as labor and machines. Previous research has limited itsfocus to either the assignment or the scheduling problem. Our work considers bothproblems simultaneously, and, to the best of our knowledge, is the first to providea solution approach, allowing solutions results for real-world problems.Our solution approach to this problem is a methodological framework whichwe refer to as the Multi-Mode Resource-Constrained Cross-Dock Scheduling Prob-lem (MRCDSP) method. The MRCDSP can be broken down into four stages: (1)container clustering; (2) dock-door assignment; (3) workflow scheduling; and (4)container scheduling. Each of these four stages of the MRCDSP are described indetails in Section 4.3. The flow of information and the relationship between thedifferent stages of the MRCDSP are depicted in Figure 4.1. The container clus-tering stage uses the material flow between containers data as input and providesdisjoint sets of containers as output. The resulting clusters are then used as input tothe dock-door assignment phase which provides a container to dock-door alloca-tion as output. These results then serve as inputs to the workflow scheduling stage,along with the detailed material flow data. The outputs of the workflow schedulingstage are a variety of potential modes of execution (as explained in Section 4.3.4)and associated processing times, which serve, along with the layouts achieved inthe dock-door assignment stage, as inputs to the container scheduling stage. Thefinal result is a detailed allocation schedule of resources to containers that mini-mizes the makespan required to process all container clusters, while minimizingthe weighted-distance that material travels by optimizing the allocation of contain-ers to dock-doors.The MRCDSP is the first attempt to consider all of these aspects of cross-dock operations hierarchically, taking into account available resources at the cross-dock. Further, it is the first work to provide a holistic approach for these cross-dock operating decisions. Using this framework achieves an optimal container to48Figure 4.1: Flow of Information Between MRCDSP Phasesdock-door allocation, and a makespan minimizing schedule of containers to thecross-dock. A comparative numeric study based on test case data from a retailpartner shows that our approach reduces, on average, the makespan by 37% andthe weighted-distance material travels metric by 45% in comparison to methodscommonly used in practice.The remainder of the chapter is organized as follows. In Section 4.2 we providean overview of the literature relevant to our work. In Section 4.3 we describe ourmodeling approach in detail. We present results from a numeric study in Section4.4, and we conclude with a brief summary in Section Review of Related LiteratureBoysen and Fliedner (2010), Vogt (2010), and Van Belle et al. (2012) provide re-cent surveys of the cross-docking literature. Our work targets a gap in the literature49mentioned by each of these survey papers: the need to simultaneously address theissues of material flow and container scheduling at cross-docks. As our researchis related to both the material flow and scheduling decisions, we briefly discussrelevant papers from the cross-docking literature. Specifically we focus on papersregarding material flow and handling performance at cross-docks, and those target-ing operational issues related to the scheduling of containers to be processed at thecross-dock.Early papers related to cross-dock management include the seminal papers byTsui and Chang (1990, 1992) who formulate the problem of assigning containersto dock-doors as a quadratic assignment problem (QAP) and suggest a branch-and-bound approach for solving this problem. Gue (1999) relaxes the assumption thatat an I shaped cross-dock all inbound containers are assigned along one side of thecross-dock, opposite to the outbound containers. By relaxing this assumption, Gueachieves a significant reduction of the weighted-distance material traveled withinthe cross-dock, in comparison with previous models. Miao et al. (2009) extendGue?s work by relaxing the assumption that dock-doors are fixed for specified des-tinations; the authors also account for a notion of scheduling, as we describe below.In the aforementioned papers, only very small instances of the QAP are solvedto optimality. This is due to the computational complexity of the problem. There-fore, many later papers offer heuristic solution approaches. Bartholdi and Gue(2000) use a simulated annealing heuristic to investigate the effects that incorpo-rating congestion and labor costs within the door assignment problem has on dock-door allocation, arguing that considering the complete cost structure might leadto a reduction in total cost. Bozer and Carlo (2008) present a simulated anneal-ing heuristic to solve the QAP in a cross-dock setting, assuming that the numberof containers is exactly equal to the number of dock-doors. Rosales et al. (2009)study the allocation of dock-doors to containers while balancing work load amongthe dock-doors. They focus on minimizing the total cost, accounting for mate-rial flow and workforce resources, under the assumption that a single person isassigned to each cross-dock door with the possibility of overtime and that eachoutbound shipment location is both fixed and exogenous.In our study, we use a computationally efficient formulation of the QAP, cou-pled with a reduction in problem size (achieved via clustering of containers), to ob-50tain an optimal solution. The idea of container clustering in cross-dock operationsis not new; it has been noted in both Li et al. (2008) and Shakeri (2011), where thefocus is on finding a feasible schedule of containers subject to resource constraints.Rosales et al. (2009) use a similar problem size reduction technique where they di-vide their inbound containers sets into smaller subsets when the problem size is toolarge. In our work, we reduce the problem size by assigning containers to disjointclusters that do not share material flows, thereby enabling an optimal solution tothe resulting QAPs.Another stream of research examines scheduling issues in the context of cross-docks. Specifically, many papers focus on the scheduling of containers for pro-cessing, subject to resource constraints, with the objective of optimizing somemeasure of interest. The problem of scheduling containers and tasks in a resource-constrained environment is NP-hard, as was shown by Li et al. (2004), Boysenet al. (2010), and others. Due to its complexity, most papers in this area rely onheuristic solution approaches, c.f. Boysen and Fliedner (2010).Chen and Lee (2009) analyze task scheduling in a cross-docking environment.They assume that the cross-dock is set up so that all inbound containers are on oneside and outbound containers are on the other side. The authors further assumethat only one task can be performed on each side of the cross-dock per time period,taking into account precedence requirements. They show that even at this levelof abstraction, the problem is NP-hard, which demonstrates the complexity of thereal-world problem being analyzed. Wang and Regan (2008) analyze a variety ofscenarios, cross-dock layouts, and performance measures, by simulating rules-of-thumb regarding the scheduling of containers to dock-doors. They conclude thatthe currently-accepted practice of first-come-first-served policy, or even a simplelook-ahead policy, might perform poorly when trying to minimize makespan, com-pared to other policies that account for processing time a priori.Choi et al. (2006) develop a genetic algorithm to solve a non-linear programwith the objective of balancing the workload at the cross-dock. Their model limitsinbound container assignment to a single dock-door and they assume freight sortingtime is negligible. Zhang et al. (2010b) minimize three objectives simultaneously;the total handling time of inbound freight, the total weighted distance material trav-els, and the completion time of processing all outbound containers. They formulate51the problem as a multi-objective mixed-integer linear program with a predefinednumber of outbound and inbound dock-doors and an implicit assumption of abun-dant labor and machine resources. They solve the problem for an instance of nineinbound containers. The authors conclude that minimizing the total handling timeof inbound freight or the completion time of processing all outbound containersdoes not provide a good solution with respect to the dock door assignment; in-stead, first solving the QAP and then optimizing the schedule provides superiorperformance. This is the same format suggested by our MRCDSP, and as such wesee similar improvements in performance. However, we are able to solve muchlarger instances of the problem.Lee et al. (2009) focus on minimizing the time required to process a given setof containers. They assume unlimited space and resources at the cross-dock andformulate the problem as a mixed-integer linear program in which the processingtime accounts for the weighted distance that material travels. They are not ableto solve the model to optimality for practical cases due to the complexity of themodel. Miao et al. (2009) account for both container scheduling and dock-doorallocation simultaneously. However, they assume that the arrival and departuredates are fixed and the issue of scheduling is treated as a constraint rather than asan objective. The authors conclude that there is a need to extend their study tothe case where scheduling is addressed as an optimization study rather than as aninput. Our MRCDSP extends their work. We note that all of the aforementionedpapers resort to heuristic-solution methods, whereas our approach provides optimalsolutions for most stages of the MRCDSP, and bounds on solution quality whenoptimal solutions are not achieved.4.3 Model DevelopmentThe MRCDSP framework provides a makespan-minimizing resource allocationscheme for shift level operations at a cross-dock. This scheme is constructed sub-ject to a container to dock-door assignment that minimizes the weighted distance ofmaterial flows. To achieve this goal, our framework utilizes a hierarchical approachcomposed of four stages. The foundation of our approach is the reduction of thesize of the problem through a data-driven clustering process by which containers52are grouped into independent and disjoint sets. We define this container cluster-ing step as Stage 1 of our MRCDSP. For each container cluster, we solve for thedock-door allocation that minimizes the weighted-distance material travels withinthe cross-dock in Stage 2. We then solve for the makespan-minimizing work-flow schedule for each cluster at several predetermined resource levels in Stage3. Each of these solutions, which maps resource levels to makespans, serves asa possible mode ? i.e. a combination of resources with a consequent makespan? for processing this cluster in Stage 4 of the MRCDSP. In Stage 4 we find themakespan-minimizing schedule of clusters to the cross-dock subject to the con-tainer to dock-door allocations and the total available resource levels at the cross-dock. In summary, the stages of the MRCDSP are:Stage 1: Container ClusteringStage 2: Dock-Door AssignmentStage 3: Workflow SchedulingStage 4: Container Scheduling4.3.1 Stage 1: Container ClusteringIn Stage 1 of the MRCDSP, we cluster the containers into disjoint sets based onthe flow of materials between containers. The identification of the disjoint sub-sets of containers utilizes a transshipment matrix as input, producing independentclusters which do not share material flow between clusters. The transshipment ma-trix describes the flow of material between containers, where the element in rowi and column j is the weight of material that travels from inbound container i tooutbound container j. This matrix is known since we assume that we know theloading plan for all inbound and outbound containers, and we know the origin ofany item on all outbound containers. Each resulting cluster is a minimal cardinalityset of inbound and outbound containers. Figure 4.2 demonstrates a potential clus-tering of containers. Figure 4.2a shows a set of inbound and outbound containers,where connecting arcs between the containers represent material flows. From thisset of containers, we can create the disjoint set of clusters that do not share material53Figure 4.2: Example of Container Clusteringflows between clusters, as shown in Figure 4.2b. Clustering is accomplished usinga simple algorithm such as the one shown in Section 4.7. Through clustering wecreate multiple smaller problems that can then be addressed in the following stagesof the MRCDSP.4.3.2 Stage 2: Dock-Door AssignmentAfter clustering the containers into disjoint clusters, the MRCDSP proceeds toassign the containers within each cluster, C? , to dock-doors. This assignment mini-mizes the weighted rectilinear-distance traveled by material within the cross-dock;this metric is often used in the literature as the main performance measure for cross-dock efficiency e.g. Tsui and Chang (1990, 1992), Gue (1999), and Bartholdi andGue (2000). The MRCDSP uses a linearized version of the QAP, as first proposedby Zhang et al. (2010a). The linearized model and the smaller problem instancesresulting from Stage 1 of the MRCDSP allow us to find an optimal layout solu-tion per cluster within reasonable time using standard optimization methods andsolvers.Model 1 presents the linearized version of the QAP that is used to assign con-54tainers to the dock-doors. This formulation is adopted from the IPQAPR-IV modelin Zhang et al. (2010a). The decision variables used in Model 1 are describedbelow; notation definitions are provided in Section 4.6.xi j =???1 if container i is assigned to dock-door j0 otherwise.yi jkl =???1 if container i is assigned to dock-door j and container k to dock-door l0 otherwise.Model 1:min ?1?i<k<|C? |,(i,k)/?F0?1? j 6=l?|D|?ik? jlyi jkl (1.1)s.t.?|D|l=1,l 6= j yi jkl = xi j for all i,k ?C? , j ? D, i < k,(i,k) /? F0 (1.2)?|D|l=1,l 6= j yi jkl = xkl for all i,k ?C? , l ? D, i < k,(i,k) /? F0 (1.3)yi jkl ? {0,1} i,k ?C? , j, l ? D, i < k, j 6= l(i,k) /? F0 (1.4)xi j ? {0,1} for all i ?C? , j ? D, for xi j ? X where (1.5)X={x|?|D|j=1 xi j = 1 ?i ?C? ,?|C? |i=1 xi j = 1 ? j ? D}and F0 ={(i,k) ?C? ?C? |?ik = 0}.The efficiency of Model 1 depends on the size of F0, the set of all containers notconnected through material flow. Generally, the larger the size of F0 relative to|C? |, the cardinality of the container set of a cluster, the faster Model 1 is solvedto optimality. Furthermore, we solve this QAP for each cluster as if it is the onlycluster to be allocated to the cross-dock, hence formulation (1.1)-(1.5) is equiva-lent to assigning the cluster of containers to a cross-dock with |C? | dock-doors oneach side. This does not change the formulation above, however it does reduce theproblem size as |D| need not be the entire set of doors, but rather a restricted por-tion of this cross-dock. Objective function (1.1) minimizes the weighted distanceof the flow of materials from the inbound to the outbound containers within a clus-ter. Constraints (1.2) and (1.3) require that each dock-door is allocated to a singlecontainer, and that each container is allocated to a single dock-door, respectively.Constraints (1.4) and (1.5) ensure that the variables are binary. Model 1 computesthe optimal allocation of containers to the dock-doors within a cross-dock. Theseallocations become constraints in Stage 4 of the MRCDSP - the container schedul-55ing phase - ensuring that we maintain optimal assignments.4.3.3 Stage 3: Workflow SchedulingThe purpose of this stage is to create the processing time data for multiple exe-cution modes required by Stage 4 of the MRCDSP ? the container schedulingstage. Contrary to previous research related to scheduling at cross-docks, whichtypically assume that the processing time for all containers is constant regardlessof the actual resource allocations (c.f. Boysen and Fliedner (2010), Bartholdi andHackman (2008), and Bartholdi and Gue (2000)), this stage of the MRCDSP findsthe makespan-minimizing schedule of the processing of tasks for each cluster sub-ject to resource availability and precedence constraints. In order to provide a moreappropriate estimate of processing times, the MRCDSP calculates the processingtimes for container clusters subject to resource availability as described in Model2.Model 2 is an instance of the Multi-mode Resource Constrained Project Schedul-ing Problem (MRCPSP), c.f. De Reyck and Herroelen (1999), adapted to ourcross-dock setting. In our model, each task (unloading, sorting and loading) can becarried out by a single resource type (either labor or machine) which is predeter-mined based on the nature of the freight associated with this task (e.g. dimensions,weight, packaging, whether the freight is palletized, etc.). In our setting, we allowfor the task processing types: (1) regular processing, available to both resourcetypes; and (2) ?crash? processing, available only for tasks associated with labor re-sources. ?Crash? processing requires two laborers to execute the task, rather thanone. The complete workflow scheduling model is given below in Model 2. The de-cision variables used in Model 2 are detailed below. Additional notation is definedin Section 4.6.wnt =???1 if job n starts at time t;0 otherwise.znt = number of resource units required for job n at time t;qn =???1 if two workers are assigned to job n where n is ?crash? processed;0 otherwise.? = makespan.56Model 2:min ? (2.1)? ? ?t (t +?n) ?wnt ??nqn for all n ? N (2.2)?t wnt = 1 for all n ? N (2.3)?t (t +?n) ?wnt ??nqn ? ?t wn?t ? t for all (n,n?)where n is a prerequisite of n? (2.4)?n?Ng znt ? ?g for all t ? T, g ? G (2.5)znt ? ?tt ?=t??n+1 wnt ??qn for all n ? N, t ? T (2.6)znt ? 2?tt ?=t??n+?n+1 wnt ?+qn?1 for all n ? N, t ? T (2.7)?n?{Nc?Ng} znt ?Ucg for all t t ? T, g ? G, c ?C (2.8)wnt ? {0,1} for all n ? N, t (2.9)qn ? {0,1} for all n ? N (2.10)znt ? Z for all n ? N, t (2.11)The objective function, (2.1), minimizes the makespan which is defined in (2.2).Constraint (2.3) ensures that each task is assigned to be executed exactly once.Constraint (2.4) ensures that the precedence relationships are satisfied. Constraint(2.5) requires that sufficient resources are available for execution of all tasks be-ing processed at each time unit t (i.e. the resource constraint). Constraints (2.6)and (2.7) define the processing time associated with each task, depending on itsprocessing method (i.e. ?crash? or regular processing). Constraint (2.8) enforcesa maximum number of resources that can be simultaneously assigned to work ontasks in the same container (due to space limitations, safety requirements, etc.).Constraints (2.9) and (2.10) restrict variables wnt and qn to be binary; constraint(2.11) allows znt to be any non-negative integer.We note that Model 2 is NP-hard, as shown by, among others, Blazewicz et al.(1986). Because multiple instances of this model need to be solved for each cluster,each serving as input for Stage 4 of the MRCDSP, we present a heuristic algorithmto obtain a solution to Model 2. The objective for Stage 3, and more specifically forthe employment of our heuristic, is to generate reasonable and relevant processingtimes, which are used as the processing times associated with the different resourcelevels denoted as modes in Stage 4. We note that if exogenous processing times forclusters given a set of resources are available they may be used as input to Stage 457of the MRCDSP, eliminating the need for Stage 3.Our heuristic, as with the model formulation above, assumes the availabilityof the following information from the loading plans of the inbound and outboundcontainers: (1) The set of tasks that need to be processed; (2) processing times foreach task; and (3) the precedence relationships between tasks; (4) the total availableresource levels per shift.Because we assume that the freight locations within the container, dimensionsand weight specifications are known, then the resource requirements for each taskcan be determined. Once resource requirements are determined, processing timesare calculated based on the type of resource associated with each task. We assumethat only tasks that are processed by resource type labor may be ?crashed? to reducethe time needed for material handling.Precedence relationships between tasks are provided by detailed container pack-ing plans. We assume that once unloading of freight has started for a particularcontainer, it must be completed before sorting of its freight can begin. For sorting,tasks are divided into three groups corresponding to their location in the outboundcontainer: Front, middle, and back. This grouping allows us to add a dummytask which serves as a unique predecessor of numerous sorting and loading tasks.1The division into three groups for sorting tasks stems from safety issues regardingcontainer packing to ensure proper weight distribution; however, in general anynumber of groups may be used in our algorithm.In describing our heuristic, we use the following notation for container typesbased on the container contents. Type-1 containers hold freight that require bothmachine and labor resources; Type-2 containers require only laborers; and Type-3containers can be processed entirely by machine resources. For each container,each task is associated with a pre-defined processing time determined by the re-source associated with processing. The total processing time for all tasks on a1For example, consider a single outbound container, and two inbound containers. Once all freightthat is intended to be loaded into the front of the outbound container has been unloaded from theinbound containers, a dummy task will be marked as completed, and hence the sorting of this freightcan begin. Once all sorting of this freight has been completed, a dummy task will be marked ascompleted, and loading of the freight can begin. For the freight bound for the back of the outboundcontainer, the dummy task will need to account for the completion of loading the middle of theoutbound container, before it can be marked as completed, noting that for loading of the middleportion the front portion must first complete loading.58container depends on the allocation of resources to that container.We propose the following heuristic algorithm to compute the processing makespan.Assign the maximum available resources to the set of inbound Type-1 containers.This resource allocation must account for the predefined upper limit on the level ofresources that can work simultaneously on a single container (see constraint (3.8)).After allocating resources to Type-1 containers, allocate any labor resources stillavailable to inbound Type-2 containers, and any machine resources still availableto inbound Type-3 containers. This allocation process continues until the resourcesor set of relevant jobs are exhausted. At each time period, t, the level of unassignedresources and remaining jobs on hand is updated.Upon completion of all unloading tasks, we turn to the sorting tasks. The pro-cess of allocating resources to tasks is such that all available resources are assignedsorting tasks associated with freight that is to be loaded onto the front one-third ofthe container. Upon completion of sorting for the front group, resources are allo-cated to the freight associated with the middle one-third of the container, and thento the back one-third. Finally, all resources are assigned to loading tasks until allcontainers have been loaded.This algorithm is described by the following pseudocode. Additional notationis defined in Section 4.6.59Algorithm 2 : Computing Minimal Makespan.Inputs: resource availability levels; tasks yet to be processed; predecessor relationshipmatrix; processing times for each task.Step 0. Initialize: Set time t = 1, and define the following lists:RA(t) ? Resources Available at time t - initially all resources allocated to the cluster;JR(t) ? Jobs Remaining at time t - initially all tasks in the cluster;JIP(t)? Jobs in Progress at time t;PRM ? Predecessor Relationship Matrix;Step 1. Resource Allocation: While (JR(t) 6= /O and JIP(t) 6= /O)Step 1.a. Unloading jobs in JR(t) associated with Type?1 containers:If Ucg < RA(t): assign maximum levels of machines and labor subject to Ucg, PRM;Else : assign resources proportionately to job types on containers, s.t. RA(t) and PRM;Update JR(t), JIP(t), and RA(t), based on resource allocation and processing times.Step 1.b. Unloading jobs in JR(t) associated with Type?2 and Type?3 containers:Assign maximum levels of resources s.t. Ucg, RA(t), and PRM.Update JR(t), JIP(t), and RA(t), based on resource allocation and processing times.Step 1.c. Sorting jobs in JR(t):Assign maximum levels of resources s.t. RA(t) and PRM.Update JR(t), JIP(t), and RA(t) based on resource allocation and processing times.Step 1.d. Loading jobs in JR(t):Assign maximum levels of machines and labor s.t. RA(t) and PRM.Update JR(t), JIP(t), and RA(t) based on resource allocation and processing times.Step 2. Time update:t = t +1.Go to Step 1 with updated lists.Step 3. End While.Output: (t?1), the makespan for a cluster, given a set of resources.60Algorithm 2 can be used to solve realistically-sized problems within seconds.We have solved instances of simulated data consisting of over a hundred containerswithin seconds. Furthermore, we are able to bound the gap between the optimalsolution and the solution generated by this algorithm. This bound tends towardzero as the number of tasks increases.To construct our bound, we recall the following assumptions: once resourcesare allocated to unloading a container they remain assigned until the unloadingprocess of that container has been completed; only tasks carried out by labor canbe crashed; all precedence relationships are known; and each unit of freight passesthrough a path of unloading, sorting, and loading. We recall the notation, ?g,g = {Labor,Machine}, is the number of resources of each type, available to us. Wealso know the number of tasks per container c, denoted Nc, and the total numberof tasks to be undertaken using labor and machine resources, denoted NLabor andNMachine.We assume that tasks carried out by labor in regular mode require k ? t timeunits, where k > 1, and when carried out in ?crash? processing, tasks require t timeunits to complete.The worst-case solution for Algorithm 2 occurs when a single available la-borer is assigned to unload the very last fully-loaded, Type-2 container, denotedc?, which contains jobs that need to be loaded in the front segment of all outboundcontainers. An upper bound on the optimality gap is the difference between thetime required to unload and sort the task in this Type-2 container, and the timeneeded to sort all other tasks after which the resources are idle. The bound on theoptimality gap is therefore,Max{[2 ? k ? |Nc? | ? t?max{(NLabor?NLabor?Nc??Labor2 ?1), NMachine?Machine}? t],0}.The first term in the expression, 2 ?k ? |Nc? | ? t, is the amount of time required forunloading and sorting of all freight on container Nc? . The term(NLabor?NLabor?Nc??Labor2 ?1)?t is the minimal amount of time required by labor resources for processing (sortingand loading) all freight not on container Nc? after unloading of this container hascommenced. Finally, the term NMachine?Machine ? t is the amount of time required by machineresources to complete processing of freight. For the case in which the number61of tasks is much larger than the available set of resources, i.e. Ng  ?g for g ={Labor, Machine}, then our bound tends toward zero. Recall that each unit offreight is associated with three tasks (unloading, sorting and loading), and thereforeNg will often be significantly larger than ?g in practice, unless we are dealing withan instance containing very few containers in the cluster, or one where there arevery few units of freight on each container.4.3.4 Stage 4: Container SchedulingThe final stage of the MRCDSP creates a makespan-minimizing schedule of con-tainer clusters in the cross-dock subject to resource constraints. Stage 4 uses theresults from Stages 2 and 3 as inputs to find an optimal makespan-minimizingschedule of containers to the cross-dock. The final schedule allocates resources ?labor, machines, and dock-doors ? to particular container clusters over the plan-ning horizon. The decision variables for Stage 4 are as follows.k?mdt =???1 if cluster ? ? ? starts in mode m ?M at door d ? D in time t ? T ;0 otherwise;?= makespan.Model 3:min ? (3.1)? ? ?m?d ?t(t + s?m)? k?mdt for all ? ? ? (3.2)?m?????+1d=1 ?t k?mdt = 1 for all ? ? ? (3.3)?? ?m ??mg?d ?tt ?=t?s?m+1 k?mdt ? ? ?g for all t,g (3.4)?? ?m?dd?=d???+1?tt ?=t?s?m+1 k?md?t ? ? 1 for all t,d ? D (3.5)k?mdt ? {0,1} for all ? ? ?,m ?M,d ? D, t (3.6)The objective function (3.1) minimizes the makespan of processing all containerclusters. The makespan defined by (3.2) evaluates the total time required to com-plete processing of all container clusters. Constraint (3.3) ensures that every clusteris processed exactly once. Constraint (3.4) guarantees that sufficient resources areavailable to the container clusters being processed at a given time. Constraint (3.5)ensures that sufficient contiguous doors are assigned to container clusters, so thatthe layout achieved in Stage 2 is implemented. Constraint (3.6) requires all deci-sion variables to be binary.62Similar to Model 2, Blazewicz et al. (1986) have shown that this binary-optimization model is NP-hard. However, we are able to solve realistically-sizedproblems encountered in practice due to reduction in problem size achieved throughcontainer clustering. Further, we use two common cutting-plane methods to fur-ther reduce the problem size. The first type of cutting plane is generated by solvingthe model using a weak resource constraint, i.e. large ?g values, which producesa lower bound on the makespan. This type of bound is particulary useful whenconvergence to optimality is slow, i.e. the integer solution is easily found, but theconvergence process is slow. The second type of cutting plane is generated bysolving the problem in an iterative fashion, starting with a small subset of con-tainer clusters and subsequently adding an additional container cluster until theentire set of container clusters have been scheduled. This type of cutting plane isparticularly useful for reducing computer memory requirements. The general ideais to first solve smaller problems, and slowly increase the size of the problem beingsolved by gradually adding clusters to be scheduled. For each new larger problembeing solved we use the result of the previously solved problems as lower boundconstraints and reduce the required search space.4.4 Numerical StudyIn order to evaluate the performance of our MRCDSP formulation, we applied ourfull MRCDSP to a set of simulated data. We first describe the assumptions usedin our numerical example as well as the data generating process for our simulateddata. We next evaluate Stages 2 and 3 of our MRCDSP method using these sim-ulated data. Finally, we compare the results of our container cluster schedulingstage (Stage 4) with a schedule generated using a random assignment rule, whichis commonly employed in practice. All of our numerical results were generatedand analyzed using an Intel 3GHz Quad Core PC with 16 GB of RAM. We useGAMS with Gurobi solver and MATLAB to implement our MRCDSP method.4.4.1 Description of Simulation-Generated Data and AssumptionsDue to confidentiality concerns, we are not able to present results of our MRCDSPmethod using exact data from the implementation of the method with our industrial63partner. However, our simulated dataset was generated through extensive consul-tation with our industrial partner and its largest customer to closely imitate realworld data. The simulated data are based on approximations of our observations atvarious cross-dock facilities associated with our industry partner. Using simulateddatasets also allows us to create a much larger set of instances for our numerical re-sults: we simulate 1,000 datasets consisting of 100 containers each - a reasonableamount of containers to be processed within a 10 hour shift.We use the following assumptions when generating our simulated data.1. Cross-dock Layout: We assume an I-shaped cross-dock facility, with evenlyspaced doors on each side of the dock (where the distance between any twoadjacent doors - both to the sides and exactly across the dock - is normalizedto 1 unit of distance in our numerical results).2. Container to Dock-Door Assignment: We assume that any container maybe assigned to any dock-door when allocating containers; however, once al-located, dock-doors remain associated with a container until all tasks withinthe container?s cluster have been processed.3. Resources: We assume that resource levels are known for all sets of re-sources: dock-doors, labor and machines.4. Processing Times of Tasks: We assume that all tasks (unload, sort, and load)processed by the same type of resource require equal time. Extensive discus-sion with foremen and shift managers at several cross-dock facilities verifiedthat this assumption is reasonable. For illustrative purposes, we assume thateach time unit, t, is 5 minutes.5. Containers: Each inbound container has up to 30 units of freight (i.e. pal-lets) that require processing. Each outbound container has up to 40 unitsof freight that require processing. (Container sizes typically differ becauseinbound containers often arrive from sea vessels and outbound containersare transported by truck). Each inbound container has material destined forbetween two and ten outbound containers, and this value follows a uniformdistribution. This results, in Stage 1, in container clusters of five to fifteen64containers per cluster. We assume that units of freight are sorted into threedesignated segments ? front, middle, and back ? on outbound containers.For the simulated data, assume that Type-1 containers, requiring both laborand machine resources, have an equal amount of tasks requiring labor andmachine resources. Further, we assume, for constraint (2.8), that the max-imum number of resources allowed to simultaneously process loading andunloading tasks on a specific container is: two laborers and two machines forType-1 containers; three laborers for Type-2; and three machines for Type-3containers.4.4.2 Evaluating MRCDSP Stage 2: Optimal Dock-Door AssignmentTo assess the efficiency of Stage 2 of our approach in being able to intermix in-bound and outbound dock-doors, we compare the following scenarios: in Scenario1 we solve Model 1, as defined in Equations (1.1) to (1.5), where any containercan be allocated to any of the dock-doors; in Scenario 2, we solve Model 1 withthe additional constraint, frequently used in practice, that inbound containers areassigned to doors along one side of the cross-dock and outbound containers areassigned to the opposite side. Unsurprisingly, the less constrained model solution(Scenario 1) outperforms the solution in Scenario 2 in terms of the weighted dis-tance of material flow objective.We analyze an I-shaped cross-dock with 20 dock-doors on each side (i.e. atotal 40 dock-doors). Our cluster sizes range from five to fifteen containers, and werandomly select twenty-five clusters for each cluster size, from our clustered data.These cluster sizes represent actual cluster sizes based on data from our industrialpartner. We solve the linearized version of the QAP for each of these clusters usingthree different approaches. (1) Using Stage 2 of the MRCDSP, which we refer tohere simply as QAP. (2) Using Stage 2 of the MRCDSP with an additional across-the-dock constraint, limiting inbound containers to one side of the cross-dock andthe outbound containers to the other side, which we refer to as cross-dock QAP(cdQAP).(3) Using Stage 2 of the MRCDSP while limiting the number of doorsto precisely the number of containers in the cluster by allocating a segment of thecross-dock of size |C? |2 to the cluster (if |C? | is odd we add one dummy trailer); we65Table 4.1: Comparison of QAP, cdQAP, and mdQAPrefer to this third approach as the minimal door QAP (mdQAP). The results arereported in Table 4.1.From Table 4.1, we see that the QAP outperforms the cdQAP by approximatly45% on average. This implies that the current practice in which all inbound con-tainers are located on one side of the cross-dock and all outbound containers on theopposite side increases material flows substantially compared to the QAP, whichallows containers to be allocated to either side of the cross-dock. Furthermore, wesee that the mdQAP achieves a weighted distance material flow value that is onaverage only 0.86% worse than the QAP. This implies that it is sufficient to allowa cluster to be allocated to the cross-dock in a fashion that it is only allocated acontiguous number of doors (facing each-other), rather than allowing for all pos-sible optimal allocations of containers to dock-doors. This allows us to achieve aclose-to-optimal allocation, which utilizes contiguous dock-doors, which is impor-tant, as dock-doors may be a bottleneck resource, and in that case we would liketo refrain from leaving these dock-doors idle.2 Recall that we solved the QAP inStage 2 of the MRCDSP for a number of dock-doors equal twice the number ofcontainers in the cluster. Our results here suggest that we can reduce the problem2It is easy to see that in any optimal allocation of containers to dock-doors, there may be amaximum of 33% unused dock-doors.66size, using a number of dock-doors equal to the number of containers in the clus-ter, and solve the mdQAP without significantly increasing the weighted-distancematerial travels.4.4.3 Evaluating MRCDSP Stage 3: Workflow SchedulingIn this section, we analyze the efficiency of our heuristic approach for solving themakespan-minimizing work schedule within clusters in Stage 3 of our MRCDSP.We analyze the efficiency of Stage 3 by comparing our solution to an alternativeapproach commonly used in practice in which tasks are randomly assigned to re-sources.The random assignment benchmark we use is as follows. At each time unit,all available tasks, regardless of their container of origin, but accounting for pre-decessor relationships, have an equal probability of being assigned a resource forprocessing. In our implementation of a random allocation, we account, as in theMRCDSP, for the predefined upper limit on the level of resources that can worksimultaneously on a single container. We note that the benchmark used here isa rather optimistic measure compared with another commonly used policy whereassignments are made on first-come-first-served basis. The random assignmentmethod inherently assumes that containers are clustered, which may not be thecase in reality, where a container may be unloaded yet its freight cannot be loadedonto an outbound container because their predecessors have yet to be allocated tothe cross-dock. In order to compare our heuristic to the benchmark we need to:select different resource levels (i.e. modes); compute the makespan for both ourheuristic and the random approach; use these results to solve Model 3. The choiceof modes used for each cluster analyzed is as follows. We begin by searching forthe resource level required to minimize the makespan of the cluster without waste(i.e. the minimum level of resources that allows for a makespan equal to the non-capacitated resource level). Subsequently, the resources are reduced to a minimumsuch that the cluster will be completed within a reasonable time window (e.g. halfthe length of a shift). The remaining modes that we use for calculation are chosenat fixed intervals between these two points.The minimum level of resources that sets a makespan equal to the non-capacitated67case is, in general, not easy to establish. Due to the low computational require-ments of our heuristic, we are able to gain insight into the relationship betweenresource levels and processing times by carrying out an extensive analysis for eachof the clusters. For example, in Figure 4.3, we present a single cluster with 9 in-bound and 6 outbound containers (containing 160 units of freight that are to beprocessed). This cluster is analyzed 1,600 times, with varying levels of resources,to determine the processing time required for each resource level. The result is aproduction-function type relationship such as is shown in Figure 4.3. This rela-tionship illustrates, as expected, that as additional resources become available, theprocessing time decreases. However, Figure 4.3 also suggests that there is a limitto this improvement. This limit is due to the precedence relationships among dif-ferent tasks which constrains the number of tasks that are available for processingper time period, as well as to the constraint on the number of resources that cansimultaneously process tasks on the same container.Figure 4.3: Cluster Processing Time as a Function of Allocated Resources68Figure 4.4 displays the average efficiency gain (percentage) of the MRCDSPStage 3 over the random assignment approach. It is generated by comparing themakespans resulting from the two approaches for 1,000 clusters, randomly chosenfrom the simulated dataset. For each of these clusters we compute the makespanrequired both under the MRCDSP Stage 3 and the random assignment for ten re-source levels. The 100% resource level is, for a specific cluster, the minimumnumber of resources that achieves the minimal makespan (i.e. the non-capacitatedresource case). The other resource levels (i.e. modes) are percentages with respectto this 100% level. The solid line in Figure 4.4 represents the average efficiencygap, which increases as the resource percentage level increases. The dashed linesrepresent a 95% confidence interval for the efficiency gain. Our results indicatethat the MRCDSP achieves an average efficiency gain of 29% for the makespan oftasks within a cluster when compared to the benchmark commonly used in practiceof random assignment.Figure 4.4: Efficiency Gains - Cluster Makespans : MRCDSP Stage 3 vs.Random-Assignment694.4.4 Evaluating MRCDSP Stage 4: Container SchedulingFigure 4.5 displays three makespan-minimizing schedules for one illustrative ex-ample of our simulated data containing 13 clusters of containers. Figures 4.5a,4.5b, and 4.5c correspond to different level of resources available at the cross-dockfor the duration of the shift. In this example we analyze four potential resource lev-els (i.e. modes of execution) per cluster. The processing times per mode (resourcelevel) are calculated using the heuristic algorithm presented in Section ??. Mode 1is defined as the minimum set of resources required to complete the processing ofa cluster within half a shift and mode 4 corresponds to the 100% resource level, asdescribed above. Modes 2 and 3 are set respective to modes 1 and 4 at one-third andtwo-thirds of the gap between these upper and lower resource levels. Figure 4.5apresents the solution assuming 180 laborers and 90 machines are available duringthe shift. Figure 4.5b presents the result assuming 90 laborers and 45 machines areavailable. Figure 4.5c presents the result for 60 laborers and 20 machines. Eachfigure presents a schedule of clusters (denoted c1,c2,c3, ...) to the dock-doors, andthe mode of processing for the cluster (denoted m1,m2,m3, or m4) followed by theassociated processing time for the cluster in this mode.Figure 4.5a shows that all containers are processed in mode 4 which utilizes100% of the resources for each of the clusters. This is not surprising because laborand machine resource constraints are relatively weak in this scenario of abundantresources. In Figure 4.5b, resources become a binding constraint, hence somecontainer-clusters are executed in modes other than mode 4. Figure 4.5c displaysthe extreme case of very low resource levels, hence clusters in this setting requiresubstantially longer times to be completed. Comparisons of potential solutions,as shown in Figure 4.5, enable managers to reveal the bottlenecks in the system,whether dock-doors, labor, or machinery, and respond accordingly to adjust thebottleneck, by scheduling appropriate labor and machine levels.After presenting an illustrative example for a specific data set, we turn to eval-uating the expected improvements that may occur by implementing Stage 4 of theMRCDSP. We compare the makespan required using the MRCDSP Stage 4 withthat generated by a random assignment of resources to container clusters, and re-port the average difference between the two solutions.70Figure 4.5: Illustrative Example - MRCDSP Stage 4 for Different Cross-Dock Resource LevelsThe random assignment is such that a non-processed cluster of containers israndomly chosen, and all available resources are allocated to it, processing thecluster in the mode resulting in the quickest processing time subject to the levelof available resources. Resources are allocated iteratively, to randomly selectedclusters of containers, until cross-dock resources are exhausted. Once resourcescomplete the processing of a cluster, they are released back to be used for the re-maining clusters. This procedure is repeated until all such clusters have completedprocessing.For purposes of comparison, we use the simulated container data set. Initially,71layouts are found, using the linearized QAP formulation which identifies the num-ber of doors required by each of the clusters. Next we apply Stage 3 of the MR-CDSP to generate four modes of processing for each container cluster (in the samemanner carried out in the example above). Finally, we solve for the minimummakespan of the clusters of containers subject to a number of different levels ofresources available at the cross-dock using both MRCDSP Stage 4 and the randomapproach. This was carried out for each of our 1,000 simulated data sets, solvingthe problem using 121 combinations of resource and door levels for each data set(11 levels of available resources at the cross-dock levels and 11 levels of availabledoors). For each data set the corresponding minimum number of doors is equal tothe largest number of doors required by all clusters within this set. Similarly, themaximum number of doors is equal to the sum of the number of doors requiredby all clusters in the data set. We then divide the range between these two valuesequally to provide us with 11 levels of available dock-doors. We relate 11 lev-els of resources in a similar manner, defining the 100% level for resources as theone associated with the sum of resources required to process, simultaneously, allcontainer clusters at a resource level (mode) that provides the shortest makespan.Similarly, the minimal resource level is such that it enables the processing of anycontainer cluster.Our results indicate that the MRCDSP Stage 4 provides a makespan that is, onaverage, 11% shorter than that provided using a random allocation of resources.The most significant impact, over 20% average improvement in makespans, isachieved for moderate-sized cross-docks and moderate resource levels. The com-parison, displayed in Figure 4.6, shows that scenarios in which the cross-dock isnot resource constrained with respect to either dock-doors or labor and machin-ery resources, the random assignment heuristic performs as well as the optimalsolution. This is also true for settings where the cross-dock is extremely resourceconstrained. If the system is extremely constrained, the container clusters must beprocessed in a sequential manner and available processing modes are limited.72Figure 4.6: Percent Improvement of the MRCDSP Stage 4 vs Random As-signment Per Mode4.5 ConclusionsIn this research we present a novel approach, the MRCDSP, to address manage-rial decisions regarding cross-dock operations. Specifically, our approach resultsin an optimal makespan-minimizing schedule of containers to doors at a cross-dock subject to resource availabilities. Simultaneously, our approach minimizesthe weighted distance that material must travel in the cross-dock and allows forresource-allocation dependent freight processing times.We exploit the availability of predefined container loading plans to decomposethe overall problem into smaller problem instances by clustering containers intodisjoint sets which are not connected by the flow of materials between clusters. Foreach identified container cluster, we then solve for an optimal container to dock-door allocation which minimizes the weighted distance that material travels withinthe cluster. By reducing the overall size of this combinatorially hard problem, weare able to solve the smaller instances to optimality. We then heuristically estimatethe processing time required for each container cluster, based on the amount ofresources allocated to the cluster. We show that our heuristic provides reasonable73estimates of the optimal required processing time for each cluster. Next, we de-velop a container-sequencing schedule that assigns resources to container clustersin order to minimize the required makespan. Again, through our use of clusteringto reduce the problem size, we are able to obtain optimal solutions.We evaluate the benefits achievable from the MRCDSP by comparing it to com-mon cross-dock management practices used in industry. Using a simulated data setbased on our industry partner?s actual cross-dock facility operations, we show thatour MRCDSP method outperforms current practice resulting in an average reduc-tion in makespan of 37% and an average reduction in the weighted distance mate-rial travels of 45%. Once implemented, the MRCDSP method provides managerswith an ability to conduct sensitivity analysis regarding the effects of resource lev-els at the cross-dock on the overall schedule; this can help managers understandthe impact of resource level assignments on overall cross-dock operations. OurMRCDSP method can be implemented using software such as MS-Excel, Matlab,and dedicated optimization software such as Gurobi or CPLEX.We close by noting a future research possibility. During our visits to cross-dock facilities, as part of this project, we observed that some of these facilitiesoffer a warehousing and storage service to complement their cross-dock services.Further investigation suggests that this practice is not uncommon; a recent studyby the Saddle Creek Corporation (2011) reports that over 20% of firms that usecross-docks store their freight at the cross-dock facility for more that two days.Therefore, we find some motivation in future exploration of the incorporation ofwarehousing and storage at a cross-dock into the MRCDSP framework.744.6 Model NotationNotation IndexC set of all containers c, i,kD set of doors d, j, l? set of clusters ?C? set of all containers in a cluster ? ? ?N set of all tasks/jobs to be processed (unloading, sorting, loading) nNc set of jobs belonging to container c ?C where Nc ? N and ?cNc = NG set of all resource types (clamp, forklift, worker/labor) gNg set of jobs handled by resource type g where g ? G Ng ? N and ?gNg = NM set of possible modes in which a cluster may be processed mT set of discrete time slots, t = 1, ...,T tF0 set of all unconnected containers in a clusterA set of all inbound containers, A ?CB set of outbound containers , B ?CA(?) set of inbound containers in cluster ? ? ?, A(?)?AB(?) set of outbound containers in cluster ? ? ?, B(?)?B?ik amount of material to be transferred from container i to container k, (i,k ?C)W matrix of ?ik values? jl rectilinear distance from door j to door l, ( j, l ? D)??mg number of type g ? G resource units used by cluster ? ? ? in mode m ?Ms?m processing time of cluster ? ? ? in mode m ?M (in units of t ? T )?? number of doors needed for cluster ?? number of doors available at the cross-dock =|D|?n time required to complete job n ? N (based on Stage 2 dock-door assignment)?n time saved using extra resource of type worker to complete job n ? N (=0 for otherresource types)?g available units of resource g ? GUcg limit on number of resources g ? G simultaneously utilized at c ?C754.7 Algorithm for Cluster GenerationINPUTS: W , A and B.Step 0. Initialize: Set cluster counter ?=0.Define the set Q as an interim set aiding in the construction of the clusters;Step 1. Cluster initialization:If A 6= /O? = ?+1;B(?)= Bmin (where Bmin is the element of B with the lowest index yet to bechosen);Q = /O;Go to step 2.Else, End. At this stage the algorithm returns all clusters.Step 2. Cluster Construction:If Q 6= B(?)Q = B(?);A(?)=A(?)?{All inbound containers ?A connected to B(?)}, wi j > 0;B(?)=B(?)?{All outbound containers ?B connected to A(?)}, wi j > 0;B={B/B(?)};A ={A /A(?)};Go to Step 2.Else, Go to Step 1.OUTPUTS: A(?),B(?), disjoint clusters of containers ?? ? ?.76BibliographyY. Aviv and A. Pazgal. Optimal pricing of seasonal products in the presence offorward-looking consumers. Manufacturing & Service OperationsManagement, 10(3):339?359, 2008.Y. Aviv, C. S. Tang, and R. Yin. Mitigating the adverse impact of strategic waitingin dynamic pricing settings: A study of two sales mechanisms. In C. S. Tang,S. Netessine, F. S. Hillier, and C. C. Price, editors, Consumer-Driven Demandand Operations Management Models, volume 131 of International Series inOperations Research & Management Science, pages 353?370. Springer US,2009. ISBN 978-0-387-98026-3.Y. Aviv, Y. Levin, and M. Nediak. Can price matching mitigate strategicconsumer behavior? Working Paper, 2010.G. Aydin and H. S. Heese. Bargaining for an assortment. Working Paper, KelleySchool of Business, University of Indiana, 2012.J. J. Bartholdi and K. R. Gue. The best shape for a crossdock. TransportationScience, 38(2):235?244, 2004.J. J. Bartholdi and S. T. Hackman. Warehouse & distribution science. GeorgiaInstitute of Technology. Available online at:http://www.tli.gatech.edu/whscience/book/wh-sci.pdf, 2008.J. J. Bartholdi III and K. R. Gue. Reducing labor costs in an ltl crossdockingterminal. Operations Research, 48(6):823?832, Nov. 2000.F. Bernstein and A. Federgruen. Decentralized supply chains with competingretailers under demand uncertainty. Management Science, 51(1):18?29, 2005.D. Besanko and W. L. Winston. Optimal price skimming by a monopolist facingrational consumers. Management Science, 36(5):555?567, 1990.77K. Binmore, A. Shaked, and J. Sutton. An outside option experiment. TheQuarterly Journal of Economics, 104(4):753?770, 1989.J. Blazewicz, W. Cellary, R. Slowinski, and J. Weglarz. Scheduling UnderResource Constraints-Deterministic Models. Blazer, Basel., 1986.P. Bolton and M. Dewatripont. Contract Theory. MIT, Cambridge, Mass., USA,2005. ISBN 0262025760.N. Boysen and M. Fliedner. Cross dock scheduling: Classification, literaturereview and research agenda. Omega, 38(6):413 ? 422, 2010.N. Boysen, M. Fliedner, and A. Scholl. Scheduling inbound and outbound trucksat cross docking terminals. OR Spectrum, 32:135?161, 2010.Y. Bozer and H. Carlo. Optimizing inbound and outbound door assignments inless-than-truckload crossdocks. IIE Transactions, 40(11):1007?1018, 2008.G. P. Cachon and M. A. Lariviere. Supply chain coordination withrevenue-sharing contracts: Strengths and limitations. Management Science, 51(1):30?44, 2005.G. P. Cachon and R. Swinney. Purchasing, pricing, and quick response in thepresence of strategic consumers. Management Science, 55(3):497?511, 2009.F. Chen and C.-Y. Lee. Minimizing the makespan in a two-machine cross-dockingflow shop problem. European Journal of Operational Research, 193(1):59 ?72, 2009.E. Choi, J. Lee, and C. Ko. A study on the dock door assignment problems incross-docking terminal. In Proceedings of the 7th Asia Pacific IndustrialEngineering and Management Systems Conference, pages 198?204, 2006.L. Y. Chu and H. Zhang. Optimal preorder strategy with endogenous informationcontrol. Management Science, 57(6):1055?1077, 2011.R. H. Coase. Durability and monopoly. Journal of Law and Economics, 15(1):143?149, 1972.O. Compte and P. Jehiel. The coalitional nash bargaining solution. Econometrica,78(5):1593?1623, 2010.S. C. Corporation. 2011 cross-docking trends report.http://www.distributiongroup.com/articles/070111DCMwe.pdf, 2011.78S. Dasu and C. Tong. Dynamic pricing when consumers are strategic: Analysis ofposted and contingent pricing schemes. European Journal of OperationalResearch, 204(3):662 ? 671, 2010. ISSN 0377-2217.S. Fay and J. Xie. The economics of buyer uncertainty: Advance selling vs.probabilistic selling. Marketing Science, 29(6):1040?1057,November/December 2010.Q. Feng, G. Lai, and L. X. Lu. Dynamic bargaining in a supply chain withasymmetric demand information. Working Paper, 2012.K. R. Gue. The effects of trailer scheduling on the layout of freight terminals.Transportation Science, 33(4):419?428, 1999.F. Gul, H. Sonnenschein, and R. Wilson. Foundations of dynamic monopoly andthe coase conjecture. Journal of Economic Theory, 39(1):155?190, 1986.S. Hart and A. Mas-Colell. Potential, value, and consistency. Econometrica, 57(3):589?614, 1989.Y. Levin, J. McGill, and M. Nediak. Optimal dynamic pricing of perishable itemsby a monopolist facing strategic consumers. Production and OperationsManagement, 19(1):40?60, 2010.Y. Li, A. Lim, and B. Rodrigues. Crossdocking - jit scheduling with timewindows. Journal of Operational Research Society, 55:1342?1351, 2004.Z. Li, W. He, C. H. Sim, and C. C. Chen. A solution for cross-docking operationsplanning, scheduling and coordination. In Service Operations and Logistics,and Informatics, 2008. IEEE/SOLI 2008. IEEE International Conference on,volume 2, pages 2957 ?2962, oct. 2008. doi:10.1109/SOLI.2008.4683041.Q. Liu and G. J. van Ryzin. Strategic capacity rationing to induce early purchases.Management Science, 54(6):1115?1131, 2008. doi:10.1287/mnsc.1070.0832.URL http://mansci.journal.informs.org/content/54/6/1115.abstract.W. S. Lovejoy. Bargaining chains. Management Science, 56(12):2282?2301,2010.Z. Miao, A. Lim, and H. Ma. Truck dock assignment problem with operationaltime constraint within crossdocks. European Journal of Operational Research,192(1):105 ? 115, 2009.A. Muthoo. Bargaining Theory with Applications. Cambridge University Press,Cambridge, UK, 1999. ISBN 0521576474.79R. B. Myerson. Conference structures and fair allocation rules. InternationalJournal of Game Theory, 9:169?182, 1980.M. Nagarajan and Y. Bassok. A bargaining framework in supply chains: Theassembly problem. Management Science, 54(8):1482?1496, 2008.A. Nalca, T. Boyaci, and S. Ray. Competitive price-matching guarantees underdemand uncertainty and consumer heterogeneity: Effects of product availabilityand its verification. Working Paper, 2010.J. F. Nash. The bargaining problem. Econometrica, 18(3):155?162, 1950.J. F. Nash. Two-person cooperative games. Econometrica, 21(1):128?140, 1953.V. Nocke, M. Peitz, and F. Rosar. Advance-purchase discounts as a pricediscrimination device. Journal of Economic Theory, 146(1):141?162, 2011.A. Okada. Coalitional bargaining games with random proposers: Theory andapplication. Games and Economic Behavior, 73(1):227?235, 2011.B. A. Pasternack. Optimal pricing and return policies for perishable commodities.Marketing Science, 4(2):166?176, 1985.B. Peleg and P. Sudholter. Introduction to the Theory of Cooperative Games.Springer, Berlin, 2007.C. R. Rosales, M. J. Fry, and R. Radhakrishnan. Transfreight reduces costs andbalances workload at georgetown crossdock. Interfaces, 39(4):316?328,July/August 2009.A. E. Roth, editor. The Shapley Value: Essays in Honor of Lloyd S. Shapley.Cambridge University Press, 1988.M. Shakeri. Truck scheduling problem in logistics of cross-docking.http://pdcc.ntu.edu.sg/gsfiles/mojtaba-shakeri/TR-NTU-SCE-1110.pdf, 2011.Z.-J. M. Shen and X. Su. Customer behavior modeling in revenue managementand auctions: A review and new research opportunities. Production andOperations Management, 16(6):713?728, 2007.J. J. Spengler. Vertical integration and antitrust policy. Journal of PoliticalEconomy, 58(4):347?352, 1950.N. L. Stokey. Rational expectations and durable goods pricing. Bell Journal ofEconomics, 12(1):112?128, 1981.80X. Su. Intertemporal pricing with strategic customer behavior. ManagementScience, 53(5):726?741, 2007.X. Su. Consumer returns policies and supply chain performance. Manufacturing& Service Operations Management, 11(4):595?612, 2009.R. Swinney. Selling to strategic consumers when product value is uncertain: Thevalue of matching supply and demand. Management Science, 57(10):1737?1751, 2011.L. Tsui and C. Chang. An optimal solution to a dock door assignment problem.Computers & Industrial Engineering, 23:283?286, 1992.L. Y. Tsui and C. Chang. A microcomputer based decision support tool forassigning dock doors in freight yards. Computers & Industrial Engineering, 19:309?312, 1990.J. Van Belle, P. Valckenaers, and D. Cattrysse. Cross-docking: State of the art.Omega, 40(6):827 ? 846, 2012.J. J. Vogt. The successful cross-dock based supply chain. Journal of BusinessLogistics, 31(1):99?119, 2010. ISSN 2158-1592.J. Wang and A. Regan. Real-time trailer scheduling for cross-dock operations.Transportation Journal, 47(2):5?20, 2008.D. Wu, O. Baron, and O. Berman. Bargaining in competing supply chains withuncertainty. European Journal of Operational Research, 197(2):548?556, 2009.J. Xie and E. Gerstner. Service escape: Profiting from customer cancellations.Marketing Science, 26(1):18?30, 2007.J. Xie and S. M. Shugan. Electronic tickets, smart cards, and online prepayments:When and how to advance sell. Marketing Science, 20(3):219?243, 2001.R. Yin, Y. Aviv, A. Pazgal, and C. S. Tang. Optimal markdown pricing:Implications of inventory display formats in the presence of strategiccustomers. Management Science, 55(8):1391?1408, 2009.H. Zhang, C. Beltran-Royo, and M. Constantino. Effective formulation reductionsfor the quadratic assignment problem. Computers & Operations Research, 37(11):2007 ? 2016, 2010a.81T. Zhang, G. Saharidis, S. Theofanis, and M. Boile. Scheduling of inbound andoutbound trucks at cross-docks - modeling and analysis. TransportationResearch Record: Journal of the Transportation Research Board, 2162:2007 ?2016, 2010b.82


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items