INFORMS 2021 Program Book

INFORMS Anaheim 2021

MC46

2 - Overhaul Planning and Exchange Scheduling for Maintenance Services with Rotable Inventory Ameen Alshikh, University of Miami, Coral Gables, FL, United States, Murat Erkoc We study joint optimization of scheduling and rotable inventory management in overhaul operations with a primary focus on the MRO aviation industry. In this setting, an incoming equipment set that requires overhaul is exchanged with a ready-to-go set from the MRO service provider’s inventory. When the overhauling for the former set is completed, it is placed in the service provider’s inventory for a future exchange. The service provider’s available capacity and exchange inventory may necessitate that early arrivals of MRO orders with respect to their requested dates. We propose a mixed integer programming model that minimizes total earliness and inventory costs for the service provider. 3 - A Novel Problem of Scheduling Resource Constrained Preventive Maintenance and Production Simultaneously for the Unrelated Parallel Machine Environment Michael Geurtsen, Eindhoven University of Technology, Eindhoven, Netherlands, Jelle Adan This study proposes a new mathematical formulation and a Memetic Algorithm for a novel integrated maintenance and production scheduling problem. The novelty lies in the combination of two constraints, i.e. (1) a single maintenance activity can only be scheduled in one of its set of available time windows, and (2) a maintenance activity demands additional scarce resources. A case study is performed with real-world production data from a semiconductor manufacturer, where production and maintenance are currently scheduled separately. It is shown that scheduling production and maintenance activities simultaneously enables significant improvements. 4 - Marginal Cost Pricing in Flow Shop Scheduling In this research we use simulation to examine the performance of several priority scheduling rules in both total utility (value) created and make span for a flow shop where customer balking is allowed in response to shop congestion. In addition to developing two new priority scheduling rules based on marginal cost pricing, we also imbed a random choice utility model into the simulation model to more accurately mirror the customer’s decision to use the flow shop or an alternative. We find that the optimal priority scheduling rule depends on the perspective of the decision maker. MC46 CC Room 213D In Person: Discrete Optimization/Online Optimization Contributed Session Chair: James Patrick Bailey, Texas A&M University, College Station, TX, 77840, United States 1 - A Polyhedral Approach to Some Max-min Problems Thomas Lidbetter, Assistant Professor, Rutgers Business School, Newark, NJ, United States, Lisa Hellerstein We consider a max-min variation of the classical problem of maximizing a linear function over the base of a polymatroid. In our problem we assume that the vector of coefficients of the linear function is some unknown vertex of a simplex, and we maximize the linear function in the worst case. Equivalently, we formulate the problem as a zero-sum game. We show how to efficiently obtain optimal strategies for both players and an expression for the value of the game. Furthermore, we give a characterization of the set of optimal strategies for the minimizing player. We consider four versions of the game and discuss the implications of our results for problems in search, sequential testing and queueing. 2 - Strategic Defense of Feedback-controlled Parallel Servers Against Reliability and Security Failures Qian Xie, New York University, Brooklyn, NY, United States, Zhengyuan Zhou, Li Jin In this research, we analyze the reliability/security risk of feedback-controlled queuing systems and propose advice for strategic defense. We consider a system of parallel servers and queues with dynamic routing subject to reliability and/or security failures. For the reliability setting, we formulate it as a Markov decision process. We prove that the system operator’s optimal protecting policy is threshold-based and use dynamic programming to compute it. For the security setting, we formulate it as an attacker-defender game. We characterize the equilibria regimes and apply Shapley’s algorithm to compute the equilibria. We also present examples to illustrate our proposed models and methods. Stanislaus Solomon, Assistant Professor of Supply Chain Management, Southern Illinois University Edwardsville, Edwardsville, IL, United States, Kevin D. Sweeney, William A. Ellegood, Mitchell Millstein

3 - Robust Machine Learned Predictions for Online Allocation Thomas Lavastida, Carnegie Mellon University, Pittsburgh, PA, United States, Benjamin Moseley, R. Ravi, Chenyang Xu This talk considers a beyond-worst-case analysis model that integrates machine learned predictions into algorithm design. We give an end-to-end framework for incorporating predictions into online allocation problems including Adwords, matching, flow allocation, and scheduling. Our algorithms give near optimal performance with good predictions. Moreover, they are robust to prediction error and the quality degrades gracefully in terms of the error. Empirical results demonstrating the quality of the algorithms as well as the learnability of the predictions validate our theoretical findings. 4 - 1/T Regret and Convergence for Multiagent Optimization James Patrick Bailey, Texas A&M University, College Station, TX, United States In a repeated multiagent game, the standard implementation of gradient descent results in agents’ strategies that diverge from Nash equilibria and where regret grows overtime. In this paper, we provide a different implementation of gradient descent and show that an agent can obtain finite regret via arbitrarily fixed step- size regardless of the actions of all other agents. This is the first known algorithm to guarantee finite regret in general network games. Further, in the adversarial setting, we show that if all agents use this different implementation then strategies cycle around the set of Nash equilibria and the time-average of the strategies converge to Nash at rate 1/T. Keynote: Multiagent Reasoning for Social Impact: Results from Deployments for Public Health and Conservation Keynote Session 1 - Multiagent Reasoning for Social Impact: Results from Deployments for Public Health and Conservation Milind Tambe, Harvard University & Google Research, Cambridge, Massachusetts, United States With the maturing of AI and multiagent systems research, we have a tremendous opportunity to direct these advances towards addressing complex societal problems. I focus on the problems of public health and conservation, and address one key cross-cutting challenge: how to effectively deploy our limited intervention resources in these problem domains. I will present results from work around the globe in using AI for HIV prevention, Maternal and Child care interventions, TB prevention and COVID modeling, as well as for wildlife conservation. Achieving social impact in these domains often requires methodological advances. To that end, I will highlight key research advances in multiagent reasoning and learning, in particular in, computational game theory, restless bandits and influence maximization in social networks.In pushing this research agenda, our ultimate goal is to facilitate local communities and non- profits to directly benefit from advances in AI tools and techniques. Monday Keynote 02 CC Ballroom B /Virtual Theater 2 Keynote: Stochastic First Order Oracles and Where to Find Them Keynote Session 1 - Stochastic First Order Oracles and Where to Find Them Katya Scheinberg, Cornell University, Ithaca, NY, 14853, United States Continuous optimization is a mature field, which has recently undergone major expansion and change. One of the key new directions is the development of methods that do not require exact information about the objective function. Nevertheless majority of these methods, from stochastic gradient descent to “zero- th order” methods use some kind of approximate first order information. We will overview different methods of obtaining this information, including simple stochastic gradient via sampling, robust gradient estimation in adversarial settings, traditional and randomized finite difference methods and more. We will discuss what key properties of these inexact, stochastic first order oracles are useful for convergence analysis of optimization methods that use them. Monday, 1:30PM-2:30PM Monday Keynote 01 CC Ballroom A /Virtual Theater 1

72