Scheduling preventive maintenance for modular designed components: A dynamic approach

One of the benefits of modular design is ease-of-service. While modular design helps simplify field maintenance, extensive depot maintenance and spare modules are required to support the field maintenance. This study develops a dynamic approach for scheduling preventive maintenance at a depot with the limited availability of spare modules and other constraints. A backward allocation algorithm is proposed and applied to scheduling the preventive maintenance of an engine module installed in T-59 advanced jet trainers in the Republic of Korea Air Force. The algorithm developed by this study can be used to solve similar problems for various systems such as aerospace vehicles, heavy machinery, and medical equipment. The contribution of this study includes the uniqueness of the algorithm, the flexibility to deal with variables changing over time, and the ability to incorporate additional variables to handle complex situations.     

Time-indexed formulations for scheduling chains on a single machine: An application to airborne radars

Airborne radars are widely used to perform a large variety of tasks in an aircraft (searching, tracking, identifying targets, etc.) Such tasks play a crucial role for the aircraft and they are repeated in a “more or less” cyclic fashion. This defines a scheduling problem that impacts a lot on the quality of the radar output and on the overall safety of the aircraft.     

A stochastic programming approach to cash management in banking

The treasurer of a bank is responsible for the cash management of several banking activities. In this work, we focus on two of them: cash management in automatic teller machines (ATMs), and in the compensation of credit card transactions. In both cases a decision must be taken according to a future customers demand, which is uncertain. From historical data we can obtain a discrete probability distribution of this demand, which allows the application of stochastic programming techniques. We present stochastic programming models for each problem. Two short-term and one mid-term models are presented for ATMs. The short-term model with fixed costs results in an integer problem which is solved by a fast (i.e. linear running time) algorithm. The short-term model with fixed and staircase costs is solved through its MILP equivalent deterministic formulation. The mid-term model with fixed and staircase costs gives rise to a multi-stage stochastic problem, which is also solved by its MILP deterministic equivalent. The model for compensation of credit card transactions results in a closed form solution. The optimal solutions of those models are the best decisions to be taken by the bank, and provide the basis for a decision support system.     

Optimizing revenue in CDMA networks under demand uncertainty

Mathematical programming models for telecommunications network design are prevalent in the literature, but little research has been reported on stochastic models for cellular networks. We present a stochastic revenue optimization model for CDMA networks inspired by bid pricing models from the airline industry. We describe the optimality conditions for the model and develop a supergradient algorithm to solve it. We provide computational results that show the effects of the distribution and variance of demand. Finally, we discuss areas of future research, including a method to optimize the locations of the towers.     

Resource allocation in dynamic PERT networks with finite capacity

This article models the resource allocation problem in dynamic PERT networks with finite capacity of concurrent projects (COnstant Number of Projects In Process (CONPIP)), where activity durations are independent random variables with exponential distributions, and the new projects are generated according to a Poisson process. The system is represented as a queuing network with finite concurrent projects, where each activity of a project is performed at a devoted service station with one server located in a node of the network. For modeling dynamic PERT networks with CONPIP, we first convert the network of queues into a stochastic network. Then, by constructing a proper finite-state continuous-time Markov model, a system of differential equations is created to solve and find the completion time distribution for any particular project. Finally, we propose a multi-objective model with three conflict objectives to optimally control the resources allocated to the servers, and apply the goal attainment method to solve a discrete-time approximation of the original multi-objective problem.     

Connectivity-and-hop-constrained design of electricity distribution networks

This paper addresses the problem of designing the configuration of an interconnected electricity distribution network, so as to maximize the minimum power margin over the feeders. In addition to the limitation of feeder power capacity, the distance (as hop count) between any customer and its allocated feeder is also limited for preventing power losses and voltage drops. Feasibility conditions are studied and a complexity analysis is performed before introducing a heuristic algorithm and two integer linear programming formulations for addressing the problem. A cutting-plane algorithm relying on the generation of two classes of cuts for enforcing connectivity and distance requirements respectively is proposed for solving the second integer linear programming formulation. All the approaches are then compared on a set of 190 instances before discussing their performances.     

Stochastic programming based capacity planning for semiconductor wafer fab with uncertain demand and capacity

Capacity planning is a challenging problem in semiconductor manufacturing industry due to high uncertainties both in market and manufacturing systems, short product life cycle, and expensive capital invest. To tackle this problem, this paper proposes a scenario-based stochastic programming model which considers demand and capacity uncertainties via scenarios, where the overall equipment efficiency is employed to describe the uncertain capacity for the first time. Based on the decentralized structure of tool procurement, production, stockout, and inventory decision-making processes, recourse approximation strategies are presented with varying degree of information share. The computational experiments show that the resulting tool set is robust enough to cope with the changes in capacity with the expected profits being maximized for different scenarios, and the scheme can generate pretty good solutions in reasonable computational time.     

The multi-terminal maximum-flow network-interdiction problem

This paper defines and studies the multi-terminal maximum-flow network-interdiction problem (MTNIP) in which a network user attempts to maximize flow in a network among K ? 3 pre-specified node groups while an interdictor uses limited resources to interdict network arcs to minimize this maximum flow. The paper proposes an exact (MTNIP-E) and an approximating model (MPNIM) to solve this NP-hard problem and presents computational results to compare the models. MTNIP-E is obtained by first formulating MTNIP as bi-level min-max program and then converting it into a mixed integer program where the flow is explicitly minimized. MPNIM is binary-integer program that does not minimize the flow directly. It partitions the node set into disjoint subsets such that each node group is in a different subset and minimizes the sum of the arc capacities crossing between different subsets. Computational results show that MPNIM can solve all instances in a few seconds while MTNIP-E cannot solve about one third of the problems in 24 hour. The optimal objective function values of both models are equal to each other for some problems while they differ from each other as much as 46.2% in the worst case. However, when the post-interdiction flow capacity incurred by the solution of MPNIM is computed and compared to the objective value of MTNIP-E, the largest difference is only 7.90% implying that MPNIM may be a very good approximation to MTNIP-E.     

Joint-optimization of inventory policies on a multi-product multi-echelon pharmaceutical system with batching and ordering constraints

This paper presents a methodology to find near-optimal joint inventory control policies for the real case of a one-warehouse, n-retailer distribution system of infusion solutions at a University Medical Center in France. We consider stochastic demand, batching and order-up-to level policies as well as aspects particular to the healthcare setting such as emergency deliveries, required service level rates and a new constraint on the ordering policy that fits best the hospital’s interests instead of abstract ordering costs. The system is modeled as a Markov chain with an objective to minimize the stock-on-hand value for the overall system. We provide the analytical structure of the model to show that the optimal reorder point of the policy at both echelons is easily derived from a simple probability calculation. We also show that the optimal policy at the care units is to set the order-up-to level one unit higher than the reorder point. We further demonstrate that optimizing the care units in isolation is optimal for the joint multi-echelon, n-retailer problem. A heuristic algorithm is presented to find the near-optimal order-up-to level of the policy of each product at the central pharmacy; all other policy parameters are guaranteed optimal via the structure provided by the model. Comparison of our methodology versus that currently in place at the hospital showed a reduction of approximately 45% in the stock-on-hand value while still respecting the service level requirements.     

A linear model for surface mining haul truck allocation incorporating shovel idle probabilities

We present models of trucks and shovels in oil sand surface mines. The models are formulated to minimize the number of trucks for a given set of shovels, subject to throughput and ore grade constraints. We quantify and validate the nonlinear relation between a shovel’s idle probability (which determines the shovel’s productivity) and the number of trucks assigned to the shovel via a simple approximation, based on the theory of finite source queues. We use linearization to incorporate this expression into linear integer programs. We assume in our integer programs that each shovel is assigned a single truck size but we outline how one could account for multiple truck sizes per shovel in an approximate fashion. The linearization of shovel idle probabilities allows us to formulate more accurate truck allocation models that are easily solvable for realistic-sized problems.     

Sensitivity of optimal prices to system parameters in a steady-state service facility

We consider the problem of maximizing the long-run average reward in a service facility with dynamic pricing. We investigate sensitivity of optimal pricing policies to the parameters of the service facility which is modelled as an M/M/s/K$M/M/s/K$ queueing system. Arrival process to the facility is Poisson with arrival rate a decreasing function of the price currently being charged by the facility. We prove structural results on the optimal pricing policies when the parameters in the facility change. Namely, we show that optimal prices decrease when the capacity of the facility or the number of servers in the facility increase. Under a reasonable assumption, we also show that optimal prices increase as the overall demand for the service provided by the facility increases or when the service rate of the facility decreases. We illustrate how these structural results simplify the required computational effort while finding the optimal policy.     

Multi-period traffic routing in satellite networks

We introduce a traffic routing problem over an extended planning horizon that appears in geosynchronous satellite networks. Unlike terrestrial (e.g., fiber optic) networks, routing on a satellite network is not transparent to the customers. As a result, a route change is associated with significant monetary penalties that are usually in the form of discounts (up to 40%) offered by the satellite provider to the customer that is affected. The notion of these rerouting penalties requires the network planners to explicitly consider these penalties in their routing decisions over multiple time periods and introduces novel challenges that have not been considered previously in the literature. We develop a branch-and-price-and-cut procedure to solve this problem and describe an algorithm for the associated pricing problem. Our computational work demonstrates that the use of a multi-period optimization procedure as opposed to a myopic period-by-period approach can result in cost reductions up to 13% depending on problem characteristics and network size considered. These cost reductions correspond to potential savings of several hundred million dollars for large satellite providers.     

Developing work schedules for an inter-city transit system with multiple driver types and fleet types

In developing work schedules, the job assignment flexibility exploits the variety of available skills, thus enabling the assignment of workers to perform different jobs. In this study, we investigate the problem of finding the mix of primary and secondary jobs in short term work schedules to meet, at minimum cost, the daily service requirements of an inter-city bus transit firm in Andra Pradesh India operating multiple fleet types. We formulate the problem as a set covering model with resource allocation constraints. We develop a branch-and-price procedure to solve the model. Computational results are provided.     

Optimal maintenance service contract negotiation with aging equipment

In recent years, there has been a growing trend to out-source service operations in which the equipment maintenance is carried out by an external agent rather than in-house. Often, the agent (service provider) offers more than one option and the owners of equipment (customers) are faced to the problem of selecting the optimal option, under the terms of a contract. In the current work, we develop a model and report results to determine the agent’s optimal strategy for a given type of contract. The model derives in a non-cooperative game formulation in which the decisions are taken by maximizing expected profits. This work extends previous models by considering the realistic case of equipments having an increasing failure intensity due to imperfect maintenance, instead of the standard assumption that considers failure times are exponentially distributed (constant failure intensity). We develop a model using a linear function of time to characterize the failure intensity. The main goal, for the agent, is to determine the pricing structure in the contract and the number of customers to service. On the other hand, for the clients, the main goal is to define the period between planned actions for preventive maintenance and the time to replace equipments. In order to give a complete characterization of the results, we also carry out a sensitivity analysis over some of the factors that would influence over the failure intensity.     

Solving knapsack problems with S-curve return functions

We consider the allocation of a limited budget to a set of activities or investments in order to maximize return from investment. In a number of practical contexts (e.g., advertising), the return from investment in an activity is effectively modeled using an S-curve, where increasing returns to scale exist at small investment levels, and decreasing returns to scale occur at high investment levels. We demonstrate that the resulting knapsack problem with S-curve return functions is NP-hard, provide a pseudo-polynomial time algorithm for the integer variable version of the problem, and develop efficient solution methods for special cases of the problem. We also discuss a fully-polynomial-time approximation algorithm for the integer variable version of the problem.     

Hop constrained Steiner trees with multiple root nodes

We consider a network design problem that generalizes the hop and diameter constrained Steiner tree problem as follows: Given an edge-weighted undirected graph with two disjoint subsets representing roots and terminals, find a minimum-weight subtree that spans all the roots and terminals so that the number of hops between each relevant node and an arbitrary root does not exceed a given hop limit H. The set of relevant nodes may be equal to the set of terminals, or to the union of terminals and root nodes. This article proposes integer linear programming models utilizing one layered graph for each root node. Different possibilities to relate solutions on each of the layered graphs as well as additional strengthening inequalities are then discussed. Furthermore, theoretical comparisons between these models and to previously proposed flow- and path-based formulations are given. To solve the problem to optimality, we implement branch-and-cut algorithms for the layered graph formulations. Our computational study shows their clear advantages over previously existing approaches.     

Operational aircraft maintenance routing problem with remaining time consideration

The aircraft maintenance routing problem is one of the most studied problems in the airline industry. Most of the studies focus on finding a unique rotation that will be repeated by each aircraft in the fleet with a certain lag. In practice, using a single rotation for the entire fleet is not applicable due to stochasticity and operational considerations in the airline industry. In this study, our aim is to develop a fast responsive methodology which provides maintenance feasible routes for each aircraft in the fleet over a weekly planning horizon with the objective of maximizing utilization of the total remaining flying time of fleet. For this purpose, we formulate an integer linear programming (ILP) model by modifying the connection network representation. The proposed model is solved by using branch-and-bound under different priority settings for variables to branch on. A heuristic method based on compressed annealing is applied to the same problem and a comparison of exact and heuristic methods are provided. The model and the heuristic method are extended to incorporate maintenance capacity constraints. Additionally, a rolling horizon based procedure is proposed to update the existing routes when some of the maintenance decisions are already fixed.     

Flexible supply policy with options and capacity constraints

This paper considers a class of multi-period flexible supply policies with options and capacity constraints. The main results are to characterize the optimal ordering and purchasing options policy and the minimum expected cost in a period and thereafter under the assumptions about the options and ordering quantities.     

On stochastic auctions in risk-averse electricity markets with uncertain supply

This paper studies risk in a stochastic auction which facilitates the integration of renewable generation in electricity markets. We model market participants who are risk averse and reflect their risk aversion through coherent risk measures. We uncover a closed form characterization of a risk-averse generator’s optimal pre-commitment behaviour for a given real-time policy, both with and without risk trading.     

Optimal policy for a dynamic,non-stationary,stochastic inventory problem with capacity commitment

This paper studies a single-product, dynamic, non-stationary, stochastic inventory problem with capacity commitment, in which a buyer purchases a fixed capacity from a supplier at the beginning of a planning horizon and the buyer’s total cumulative order quantity over the planning horizon is constrained with the capacity. The objective of the buyer is to choose the capacity at the beginning of the planning horizon and the order quantity in each period to minimize the expected total cost over the planning horizon. We characterize the structure of the minimum sum of the expected ordering, storage and shortage costs in a period and thereafter and the optimal ordering policy for a given capacity. Based on the structure, we identify conditions under which a myopic ordering policy is optimal and derive an equation for the optimal capacity commitment. We then use the optimal capacity and the myopic ordering policy to evaluate the effect of the various parameters on the minimum expected total cost over the planning horizon.