A multistage production system consists of a number of production stages that are interrelated, that is the output from one stage forms input to the next stage. There are constraints associated with each stage as well as constraints imposed by the overall system. Besides, there are multiple objectives that need to be satisfied, and in numerous cases, these objectives conflict with each other. What is required is an efficient technique to allocate and schedule resources so as to provide a balance between the conflicting objectives within the system constraints. This study is concerned with the problem of scheduling multistage production systems in food processing industry. The system and products have complex structure and relationships. This makes the system difficult to be solved analytically. Therefore, the problem is solved by developing a heuristic algorithm that considers most of the constraints. The output generated by the algorithm includes a production schedule which specifies the starting and completion times of the products in each stage and the machines where the products are to be processed. In addition, a summary of system performances including throughput times, resources' utilizations, and tardy products is reported. / Graduation date: 1992

In maritime transportation, liner shipping accounts for over 60\% of the value of goods shipped. However, very limited literature is available on the study of various problems in liner shipping. In this thesis we focus on problems related to this industry. Given a set of cargo to be transported, a set of ports and a set of ships, a common problem faced by carriers in liner shipping is the design of their service network. We develop an integrated model to design service network for the ships and to route the available cargo, simultaneously. The proposed model incorporates many relevant constraints, such as the weekly frequency constraint on the operated routes, and emerging trends, such as obtaining benefits from transshipping cargo on two or more service routes, that appear in practice but have not been considered previously in literature. Also, we design exact and heuristic algorithms to solve the integer program efficiently. The proposed algorithms integrate the ship scheduling problem, a tactical planning level decision, and the cargo routing problem, an operational planning level decision, and provide good overall solution strategy. Computational experiments indicate that larger problem instances, as compared to the literature, can be solved using these algorithms in acceptable computational time. Alliance formation is very common among global liner carriers however a quantitative study of liner alliances is missing from literature. We provide a mathematical framework for the quantitative study of these alliances. For the formation of a sustainable alliance, carriers need to agree on an overall service network and resolve issues concerning distribution of benefits and costs among the members of the alliance. We develop mechanisms to design a collaborative service network and to manage the interaction among the carriers through the allocation of profits in a fair way. The mechanism utilizes inverse optimization techniques to obtain resource exchange costs in the network. These costs provide side payments to the members, on top of the revenue generated by them in the collaborative solution, to motivate them to act in the best interest of the alliance while satisfying their own self interests.

A load plan specifies how freight is routed through a linehaul terminal network operated by a less-than-truckload (LTL) carrier. Determining the design of the load plan is critical to effective operations of such carriers. This dissertation makes contributions in modeling and algorithm design for three problems in LTL load plan design: (1) Refined execution cost estimation. Existing load plan design models use approximations that ignore important facts such as the nonlinearity of transportation costs with respect to the number of trailers, and empty travel beyond what is required for trailer balance that results from driver rules. We develop models that more accurately capture key operations of LTL carriers and produce accurate operational execution costs estimates; (2) Dynamic load planning. Load plans are traditionally revised infrequently by LTL carriers due to the difficulty of solving the associated optimization problem. Technological advances have now enabled carriers to consider daily load plan updates. We develop technologies that efficiently and effectively adjust a nominal load plan for a given day based on the actual freight to be served by the carrier. We present an integer programming based local search procedure, and a greedy randomized adaptive search heuristic; and (3) Stochastic load plan design. Load plan design models commonly represent origin-destination freight volumes using average demands, which do not describe freight volume fluctuations. We investigate load plan design models that explicitly utilize information on freight volume uncertainty and design load plans that most cost-effectively deal with varying freight volumes and lead to the lowest expected cost. We present a Sample Average Approximation approach and a variant of the method for solving the stochastic integer programming formulations.

Not available / text

We consider the problem of optimization and decision-making in various settings involving complex systems. In particular, we consider specific problems in decentralized finance which we address employing insights from mathematical finance, in course-mode selection that we solve by applying mixed-integer programming, and in social networks that we approach using tools from graphical game theory.In the first part of the thesis, we model and analyze fixed spread liquidation lending in DeFi as implemented by popular pooled lending protocols such as AAVE, JustLend, and Compound. Empirically, we observe that over 70% of liquidations occur in the absence of any downward price jumps. Then, assuming the borrowers monitor their loans with exponentially distributed horizons, we compute the expected liquidation cost incurred by the borrowers in closed form as a function of the monitoring frequency. We compare this cost against liquidation data obtained from AAVE protocol V2, and observe a match with our model assuming the borrowers monitor their loans five to six times more often than they interact with the pool. Such borrowers must balance the financing cost against the likelihood of liquidation. We compute the optimal health factor in this situation assuming a financing rate for the collateral. Empirically, we observe that borrowers are often more conservative compared to model predictions, though on average, model predictions match with empirical observations. In the second part of the thesis, we consider the problem of hybrid scheduling that was faced by Columbia Business School during the Covid-19 pandemic and describe the system that we implemented to address it. The system allows some students to attend in-person classes with social distancing, while their peers attend online, and schedules vary by day. We consider two variations of this problem: one where students have unique, individualized class enrollments, and one where they are grouped in teams that are enrolled in identical classes. We formulate both problems as mixed-integer programs. In the first setting, students who are scheduled to attend all classes in person on a given day may, at times, be required to attend a particular class on that day online due to social distancing constraints. We count these instances as “excess.” We minimize excess and related objectives, and analyze and solve the relaxed linear program. In the second setting, we schedule the teams so that each team’s in-person attendance is balanced over days of week and spread out over the entire term. Our objective is to maximize interaction between different teams. Our program was used to schedule over 2,500 students in student-level scheduling and about 790 students in team-level scheduling from the Fall 2020 through Summer 2021 terms at Columbia Business School. In the third part of the thesis, we consider a social network, where individuals choose actions which optimize utility which is a function of their neighbors’ actions. We assume that a central authority aiming to maximize social welfare at equilibrium can intervene by paying some cost to shift individual incentives, and that the cost is upper bounded by a budget. The intervention that maximizes the social welfare can be computed using the spectral decomposition of the adjacency matrix of the graph, yet this is infeasible in practice if the adjacency matrix is unknown. We study the question of designing intervention strategies for graphs where the adjacency matrix is unknown and is drawn from some distribution. For several commonly studied random graph models, we show that the competitive ratio of in intervention proportional to the first eigenvector of the expected adjacency matrix, approaches 1 in probability as the graph size increases. We also provide several efficient sampling-based approaches for approximately recovering the first eigenvector when we do not know the distribution. On the whole, our analysis compares three categories of interventions: those which use no data about the network, those which use some data (such as distributional knowledge or queries to the graph), and those which are fully optimal. We evaluate these intervention strategies on synthetic and real-world network data, and our results suggest that analysis of random graph models can be useful for determining when certain heuristics may perform well in practice.