Title: Efficient Two-Sample Bernoulli Confidence Intervals and Submodular Dispatching

Date: January 24th, 2024

Time: 11am - 1pm ET

Location: Groseclose 226A (Georgia Freight Bureau Conference Room) or https://gatech.zoom.us/j/92394559498

Location: Ignacio Ismael Erazo Neira

Committee

Dr. Alejandro Toriello, Industrial and Systems Engineering, Georgia Institute of Technology (co-advisor)

Dr. David Goldsman, Industrial and Systems Engineering, Georgia Institute of Technology (co-advisor)

Dr. Jan Ehmke, Department of Business Decisions and Analytics, University of Vienna

Dr. Yajun Mei, Industrial and Systems Engineering, Georgia Institute of Technology

Dr. Mohit Singh, Industrial and Systems Engineering, Georgia Institute of Technology

Abstract

This thesis focuses on two different problems: the computation of confidence intervals of the difference between the success parameter of two Bernoulli populations, and how to optimize the trade-off between batching orders and dispatching, when waiting helps to increase economies of scale, but produces idleness. The former problem is motivated by applications in healthcare and manufacturing, among others; whereas the latter is motivated by applications in e-commerce, machine scheduling, and others.

In Chapter 2, we study the two-sample Bernoulli confidence interval problem, for which we propose computationally efficient methods that: i) minimize the number of observations taken to construct the confidence interval; and ii) minimize the total cost incurred over the sampling procedure. We extensively test our algorithms and study their successful performance versus commonly used benchmarks. Furthermore, we present a case study comparing the efficacy and costs of generic vs. brand-name drugs; we establish the effectiveness of our methods for real-world applications.

In Chapter 3, motivated by applications in e-commerce logistics where orders or items arrive at different times and must be dispatched or processed in batches, we propose the subadditive dispatching problem (SAD), a strongly NP-hard problem defined by a set of orders with release times and a non-decreasing subadditive dispatch time function. A single uncapacitated vehicle must dispatch orders in batches to minimize the makespan, the time at which all orders have been dispatched. We propose a mixed-integer linear formulation for SAD; based on the linear relaxation's optimal solution, we construct a two-dispatch solution with a 3/2 approximation ratio, and a solution with at most three dispatches that has a 4/3 approximation ratio under an additional assumption. The guarantees hold for fractionally subadditive functions and are respectively the best possible for solutions using at most two or three dispatches. Moreover, we analyze FIFO solutions, discuss cases when they are optimal, and provide a dynamic program to obtain them. Finally, we computationally test our methods on applications inspired by same-day delivery and routing on restricted topologies.

In Chapter 4 we build upon Chapter 3 and propose the Multi-Vehicle Submodular Dispatching problem (MSMD); this problem considers a fleet with multiple vehicles, each vehicle with a submodular dispatch time function. This chapter focuses mainly on the case where the fleet is homogeneous, and we propose four different mixed-integer programming formulations to solve this problem. We analyze the complexity of solving each formulation's linear relaxation, study the quality of the corresponding bounds, and leverage column generation to create heuristics. Moreover, we analyze solutions where all batches are intervals of consecutive orders and identify two classes of functions for which such a solution is optimal. Finally, we computationally test our methods on applications in same-day delivery and machine scheduling with family setups.