Browsing by Author "Song, Jing-Sheng"
- Results Per Page
- Sort Options
Item Open Access Analysis and Comparison of Queues with Different Levels of Delay Information.(2007) Guo, PengfeiInformation about delays can enhance service quality in many industries. Delay information can take many forms, with different degrees of precision. Different levels of information have different effects on customers and so on the overall system. The goal of this research is to explore these effects. We first consider a queue with balking under three levels of delay information: No information, partial information (the system occupancy) and full information (the exact waiting time). We assume Poisson arrivals, independent, exponential service times, and a single server. Customers decide whether to stay or balk based on their expected waiting costs, conditional on the information provided. By comparing the three systems, we identify some important cases where more accurate delay information improves performance. In other cases, however, information can actually hurt the provider or the customers. We then investigate the impacts on the system of different cost functions and weight distributions. Specifically, we compare systems where these parameters are related by various stochastic orders, under different information scenarios. We also explore the relationship between customer characteristics and the value of information. The results here are mostly negative. We find that the value of information need not be greater for less patient or more risk-averse customers. After that, we extend our analysis to systems with phase-type service times. Our analytical and numerical results indicate that the previous conclusions about systems with exponential service times still hold for phase-type service times. We also show that service-time variability degrades the system’s performance. At last, we consider two richer models of information: In the first model, an arriving customer learns an interval in which the system occupancy falls. In the second model, each customer’s service time is the sum of a geometric number of i.i.d. exponential phases, and an arriving customer learns the total number of phases remaining in the system. For each information model, we compare two systems, identical except that one has more precise information. We study the effects of information on performance as seen by the service provider and the customers.Item Open Access Data-driven Decision Making with Dynamic Learning under Uncertainty: Theory and Applications(2022) Li, YuexingDigital transformation is changing the landscape of business and sparking waves of innovation, calling for advanced big data analytics and artificial intelligence techniques. To survive from intensified and rapidly changing market conditions in the big data era, it is crucial for companies to hone up their competitive advantages by wielding the great power of data. This thesis provides data-driven solutions to facilitate informed decision making under various forms of uncertainties, making contributions to both theory and applications.
Chapter 1 presents a study motivated by a real-life data set from a leading Chinese supermarket chain. The grocery retailer sells a perishable product, making joint pricing and inventory ordering decisions over a finite time horizon with lost sales. However, she does not have perfect information on (1) the demand-price relationship, (2) the demand noise distribution, (3) the inventory perishability rate, and (4) how the demand-price relationship changes over time. Moreover, the demand noise distribution is nonparametric for some products but parametric for others. To help the retailer tackle these challenges, we design two versions of data-driven pricing and ordering (DDPO) policies, for the settings of nonparametric and parametric noise distributions, respectively. Measuring performance by regret, i.e., the profit loss relative to a clairvoyant policy with perfect information, we show that both versions of our DDPO policies achieve the best possible rates of regret in their respective settings. Through a case study on the real-life data, we also demonstrate that both of our policies significantly outperform the historical decisions of the supermarket, establishing the practical value of our approach. In the end, we extend our model and policy to account for age-dependent product perishability and demand censoring.
Chapter 2 discusses a work inspired by a real-life smart meter data set from a major U.S. electric utility company. The company serves retail electricity customers over a finite time horizon. Besides granular data of customers' consumptions, the company has access to high-dimensional features on customer characteristics and exogenous factors. What is unique in this context is that these features exhibit three types of heterogeneity---over time, customers, or both. They induce an underlying cluster structure and influence consumptions differently in each cluster. The company knows neither the underlying cluster structure nor the corresponding consumption models. To tackle this challenge, we design a novel data-driven policy of joint spectral clustering and feature-based dynamic pricing that efficiently learns the underlying cluster structure and the consumption behavior in each cluster, and maximizes profits on the fly. Measuring performance by average regret, i.e., the profit loss relative to a clairvoyant policy with perfect information per customer per period, we derive distinct theoretical performance guarantees by showing that our policy achieves the best possible rate of regret. Our case study based on the real-life smart meter data indicates that our policy significantly increases the company profits by 146\% over a three-month period relative to the company policy. Our policy performance is also robust to various forms of model misspecification. Finally, we extend our model and method to allow for temporal shifts in feature means, general cost functions, and potential effect of strategic customer behavior on consumptions.
Chapter 3 investigates an image cropping problem faced by a large Chinese digital platform. The platform aims to crop and display a large number of images to maximize customer conversions in an automated fashion, but it does not know how cropped images influence conversions, referred to as the reward function. What the platform knows is that good cropping should capture salient objects and texts, collectively referred to as salient features, as much as possible. Due to the high dimensionality of digital images and the unknown reward function, finding the optimal cropping for a given image is a highly unstructured learning problem. To overcome this challenge, we leverage the more advanced deep learning techniques to design a neural network policy with two types of neural networks, one for detecting salient features and the other for learning the reward function. We then show that our policy achieves the best possible theoretical performance guarantee by deriving matching upper and lower bounds on regret. To the best of our knowledge, these results are the first of their kind in deep learning applications in revenue management. Through case studies on the real-life data set and a field experiment, we demonstrate that our policy achieves statistically significant improvement on conversions over the platform's incumbent policy, translating into an annual revenue increase of 2.85 million U.S. dollars. Moreover, our neural network policy significantly outperforms the traditional machine learning methods and exhibits good performance even if the reward function is misspecified.
Item Open Access Design and Performance Prediction for Supply Chain Systems with Graphical Structures(2022) Chen, ShuyuThis dissertation studies the optimal design and performance evaluation of large-scale supply chain systems with graphical structures such as assemble-to-order (ATO) systems and e-commerce fulfillment networks. It consists of three essays.
The first essay studies the design of effective operational policies in the assemble-to-order (ATO) systems. We consider continuous-review ATO systems with general bills of materials (BOM) and general leadtimes. First, we characterize the asymptotically optimal policy for the M-system. The policy consists of a periodic review priority (PRP) allocation rule and a coordinated base-stock (CBS) replenishment policy. We then construct heuristic policies using insights from the asymptotically optimal policy. In particular, we adopt the PRP allocation rule and develop a decomposition approach for inventory replenishment. This approach decomposes a general system into a set of assembly subsystems and constructs a linear program to compute the optimal policy parameters. However, both the CBS and the assembly decomposition approach are limited to simple systems. We then consider a second approach, which decomposes a system into a set of distribution subsystems and each subsystem has a straightforward optimal solution, which is similar to the newsvendor problem. Finally, in a numeral test, we find that the assembly decomposition is very effective but computationally expensive and thus only good for small-scale systems; the distribution decomposition performs as effective as the optimal independent base-stock (IBS) policy, but is highly scalable than finding the optimal IBS policy for large-scale systems.
The second essay focuses on optimizing the operational decision at one layer of the supply chain network when some operational decisions at another layer are unknown to the decision-maker. More specifically, we consider the transportation network design problem for the e-commerce marketplace. A salient feature in this problem is decentralized decision-making. While the middle-mile manager decides the network configuration on a weekly or bi-weekly basis, the real-time flows of millions of packages on any given network configuration (which we call the flow response) are controlled by a fulfillment policy employed by a different decision entity. Thus, we face a fixed-cost network design problem with unknown flow response. To meet this challenge, we first develop a predictive model for the unknown response leveraging observed shipment data and machine learning techniques. Apart from the most natural network-level predictive model, we find that the more parsimonious destination-level and arc-level predictive models are more effective. We then embed the predictive model to the original network design problem and characterize this transformed problem as a c-supermodular minimization problem. We develop a linear-time algorithm with an approximation guarantee that depends on c. We demonstrate that this algorithm is scalable and effective in a numerical study.
The third essay investigates how to use the Graph Neural Network (GNN) model to predict the operational performances of supply chain networks. GNN is a newly developed machine learning tool to leverage the graphical structure information. It has demonstrated good prediction accuracy in various contexts, including social, bioinformatics and citation networks. Surprisingly, GNNs have not received much attention in supply chain systems despite the fact that many systems exhibit a graphical structure, such as assemble-to-order systems and process flexibility networks. To the best of our knowledge, we are the first to explore the application of GNN to supply chain problems. As operational performances of the entire network can often be decomposed into node-level or edge-level performances, we study both node-level and edge-level predictions. We find that while the existing GNN model can generate reasonable node-level predictions, special tailoring is needed for edge-level predictions of supply chain networks. A key contribution of our research is to develop a novel graph transformation approach, which allows an edge to learn from its neighborhood edges. Tested on different synthetic datasets from two different supply chain systems, we implement the GNN model with our proposed graph transformation and several benchmark methods, including an existing GNN model and the traditional machine learning methods, such as the convolutional neural network and random forest. The results indicate that our approach significantly outperforms the benchmarks in edge-level prediction. We also observe the importance of utilizing the graphical structure and edge directions. Our comparison reveals that it is beneficial to start with node-level or edge-level predictions and then aggregate them together for the graph-level prediction, instead of the direct graph-level prediction commonly used in other applications.
Item Open Access Effective Heuristics for Dynamic Pricing and Scheduling Problems with High Dimensionality(2019) Wu, ChengyuHigh-dimensional state spaces and/or decision spaces sometimes arise when sequential operational decisions need to be made dynamically in reflection of complex system information. To tackle the "curse of dimensionality," effective heuristics are needed that achieve both computational efficiency and satisfactory performance (e.g. high revenue or low cost).
This dissertation studies two such problems with three essays. The first two essays consider a dynamic pricing problem faced by a seller of a limited amount of inventory over a short time horizon. She faces an unknown demand which she must learn about during the selling season from observing customer purchase decisions. This problem can be formulated as a Bayesian dynamic program, with a high-dimensional state space representing the prior belief about the unknown demand. In the first essay, we develop insights, solution bounds, and heuristics for the problem. It is demonstrated that our derivative-based heuristics provide good revenue performance compared with two well-known algorithms in the literature. In the second essay, we apply open-loop policies to this dynamic pricing problem and reveal counter-intuitive observations. In particular, incorporating more information into a policy may actually hurt its revenue performance. This can be explained by the incomplete learning effect under limited inventory.
The third essay studies the hospital's problem to dynamically schedule elective surgeries in advance. Since after surgeries patients stay for a random number of days in an ICU with limited bed capacity, the schedule takes into account current and future ICU congestion and dynamically adjusts itself accordingly. This problem is formulated as a dynamic program where both the state space and the decision space are infinite-dimensional. We devise two schemes to relax the problem as an allocation scheduling problem and use the solution to the relaxed problems to construct heuristic solutions to the original problem. Numerical experiment confirms that our heuristics outperform benchmarks.