Scheduling Truck Arrivals at an Air Cargo Terminal

We consider the scheduling of truck arrivals at an air cargo terminal. By coordinating arrivals of cargo delivery trucks with outbound flight departure schedules, some of the shipments can be transferred directly to the departing flights, while others will be stored at the terminal's storage facility and incur extra handling and storage costs. The objective is to obtain a feasible schedule so as to minimize the total cost of operations. We formulate the problem as a time‐indexed integer program and show that, even with limited number of unloading docks at the terminal, the problem is non‐trivial (NP‐hard in the strong sense). Our solution method includes an exact solution procedure to determine an optimal unloading sequence for the shipments carried by each truck, together with a Lagrangian relaxation‐based heuristic for assigning trucks to truck docks and determining truck arrival times. We conducted computational experiments to test the performance of our solution method. Computational results show that our method can generate near‐optimal solutions efficiently. Our simulation results indicate that the scheduling approach proposed in this paper has the potential to generate significant cost savings over a first‐come, first‐served approach currently used at the air cargo terminal that we observed.     

Appointment Overbooking in Health Care Clinics to Improve Patient Service and Clinic Performance

The problem of no‐shows (patients who do not arrive for scheduled appointments) is particularly significant for health care clinics, with reported no‐show rates varying widely from 3% to 80%. No‐shows reduce revenues and provider productivity, increase costs, and limit patient access by reducing effective clinic capacity. In this article, we construct a flexible appointment scheduling model to mitigate the detrimental effects of patient no‐shows, and develop a fast and effective solution procedure that constructs near‐optimal overbooked appointment schedules that balance the benefits of serving additional patients with the potential costs of patient waiting and clinic overtime. Computational results demonstrate the efficacy of our model and solution procedure, and connect our work to prior research in health care appointment scheduling.     

Shift scheduling for tank trucks

In this paper we deal with shift scheduling of tank trucks for a small oil company. Given are a set of tank trucks with different characteristics and a set of drivers with different skills. The objective is to assign a feasible driver to every shift of the tank trucks such that legal and safety restrictions are satisfied, the total working times of the drivers are within desired intervals, requested vacation of the drivers is respected and the trucks are assigned to more favored drivers. We propose a two-phase solution algorithm which is based on a mixed integer linear programming formulation and an improvement procedure. Computational results are reported showing that the algorithm is able to generate feasible schedules in a small amount of time.     

Appointment Scheduling with No‐Shows and Overbooking

We study an overbooking model for scheduling arrivals at a medical facility under no‐show behavior, with patients having different no‐show probabilities and different weights. The scheduler has to assign the patients to time slots in such a way that she minimizes the expected weighted sum of the patients' waiting times and the doctor's idle time and overtime. We first consider the static problem, where the set of patients to be scheduled and their characteristics are known in advance. We partially characterize the optimal schedule and introduce a new sequencing rule that schedules patients according to a single index that is a function of their characteristics. Then we apply our theoretical results and conclusions from numerical experiments to sequential scheduling procedures. We propose a heuristic solution to the sequential scheduling problem, where requests for appointments come in gradually over time and the scheduler has to assign each patient to one of the remaining slots that are available in the schedule for a given day. We find that the no‐show rate and patients' heterogeneity have a significant impact on the optimal schedule and should be taken under consideration.     

A Maximum Entropy Joint Demand Estimation and Capacity Control Policy

We propose a tractable, data‐driven demand estimation procedure based on the use of maximum entropy (ME) distributions, and apply it to a stochastic capacity control problem motivated from airline revenue management. Specifically, we study the two fare class “Littlewood” problem in a setting where the firm has access to only potentially censored sales observations; this is also known as the repeated newsvendor problem. We propose a heuristic that iteratively fits an ME distribution to all observed sales data, and in each iteration selects a protection level based on the estimated distribution. When the underlying demand distribution is discrete, we show that the sequence of protection levels converges to the optimal one almost surely, and that the ME demand forecast converges to the true demand distribution for all values below the optimal protection level. That is, the proposed heuristic avoids the “spiral down” effect, making it attractive for problems of joint forecasting and revenue optimization problems in the presence of censored observations.     

A Universal Appointment Rule in the Presence of No‐Shows and Walk‐Ins

This study introduces a universal “Dome” appointment rule that can be parameterized through a planning constant for different clinics characterized by the environmental factors—no‐shows, walk‐ins, number of appointments per session, variability of service times, and cost of doctor's time to patients’ time. Simulation and nonlinear regression are used to derive an equation to predict the planning constant as a function of the environmental factors. We also introduce an adjustment procedure for appointment systems to explicitly minimize the disruptive effects of no‐shows and walk‐ins. The procedure adjusts the mean and standard deviation of service times based on the expected probabilities of no‐shows and walk‐ins for a given target number of patients to be served, and it is thus relevant for any appointment rule that uses the mean and standard deviation of service times to construct an appointment schedule. The results show that our Dome rule with the adjustment procedure performs better than the traditional rules in the literature, with a lower total system cost calculated as a weighted sum of patients’ waiting time, doctor's idle time, and doctor's overtime. An open‐source decision‐support tool is also provided so that healthcare managers can easily develop appointment schedules for their clinical environment.     

Throughput Optimization in Constant Travel‐Time Dual Gripper Robotic Cells with Parallel Machines

Constant travel‐time robotic cells with a single gripper robot and with one or more machines at each processing stage have been studied in the literature. By contrast, cells with a dual gripper robot, although more productive, have so far received scant attention, perhaps due to their inherent complexity. We consider the problem of scheduling operations in dual gripper robotic cells that produce identical parts. The objective is to find a cyclic sequence of robot moves that minimizes the long‐run average time to produce a part or, equivalently, maximizes the throughput. We provide a structural analysis of cells with one or more machines per processing stage to obtain first a lower bound on the throughput and, subsequently, an optimal solution under conditions that are common in practice. We illustrate our analysis on two cells implemented at a semiconductor equipment manufacturer and offer managerial insights for assessing the potential productivity gains from the use of dual gripper robots.     

A New Dynamic Programming Decomposition Method for the Network Revenue Management Problem with Customer Choice Behavior

In this paper, we propose a new dynamic programming decomposition method for the network revenue management problem with customer choice behavior. The fundamental idea behind our dynamic programming decomposition method is to allocate the revenue associated with an itinerary among the different flight legs and to solve a single‐leg revenue management problem for each flight leg in the airline network. The novel aspect of our approach is that it chooses the revenue allocations by solving an auxiliary optimization problem that takes the probabilistic nature of the customer choices into consideration. We compare our approach with two standard benchmark methods. The first benchmark method uses a deterministic linear programming formulation. The second benchmark method is a dynamic programming decomposition idea that is similar to our approach, but it chooses the revenue allocations in an ad hoc manner. We establish that our approach provides an upper bound on the optimal total expected revenue, and this upper bound is tighter than the ones obtained by the two benchmark methods. Computational experiments indicate that our approach provides significant improvements over the performances of the benchmark methods.     

Dynamic Policies for Optimal LEO Satellite Launches

Low‐earth orbit satellite (LEO) systems continue to provide mobile communication services. The issue of cost containment in system maintenance is a critical factor for continued operation. Satellite finite life‐times follow a stochastic process, and since satellite replenishment cost is the most significant on‐going cost of operation, finding optimal launch policies is of paramount importance. This paper formulates the satellite launch problem as a Markovian decision model that can be solved using dynamic programming. The policy space of the system is enormous and traditional action space dominance rules do not apply. In order to solve the dynamic program for realistic problem sizes, a novel procedure for limiting the state space considered in the dynamic program is developed. The viability of the proposed solution procedure is demonstrated in example problems using realistic system data. The policies derived by the proposed solution procedure are superior to those currently considered by LEO system operators, and result in substantial annual cost savings.     

Flexible Servers in Understaffed Tandem Lines

We study the dynamic assignment of cross‐trained servers to stations in understaffed lines with finite buffers. Our objective is to maximize the production rate. We identify optimal server assignment policies for systems with three stations, two servers, different flexibility structures, and either deterministic service times and arbitrary buffers or exponential service times and small buffers. We use these policies to develop server assignment heuristics for Markovian systems with larger buffer sizes that appear to yield near‐optimal throughput. In the deterministic setting, we prove that the best possible production rate with full server flexibility and infinite buffers can be attained with partial flexibility and zero buffers, and we identify the critical skills required to achieve this goal. We then present numerical results showing that these critical skills, employed with an effective server assignment policy, also yield near‐optimal throughput in the Markovian setting, even for small buffer sizes. Thus, our results suggest that partial flexibility is sufficient for near‐optimal performance, and that flexibility structures that are effective for deterministic and infinite‐buffered systems are also likely to perform well for finite‐buffered stochastic systems.     

Time‐Staged Overtime Staffing for Services with Updated Forecasts and Availabilities

This article develops a framework for staffing in a service environment when multiple opportunities exist for prescheduling overtime prior to the start of a shift. Demand forecasts improve as the shift approaches, while the availability of workers to be scheduled for overtime decreases. First, a single‐shift model is developed and used in computational studies to evaluate the benefits of time‐staged overtime staffing, which include slightly lower costs and significant reductions in unscheduled overtime and outside agents. A multishift model is then developed to consider constraints on consecutive hours worked and minimum rest intervals between shifts. A multishift computational study shows how the benefits of time‐staged overtime staffing depend on problem characteristics when interactions between shifts are considered. The article discusses how single‐shift and multishift models relate to each other and alternative ways the models may be used in practice, including decentralized open shift management and centralized overtime scheduling.     

PRODUCTION SCHEDULING OF CONTINUOUS FLOW LINES: MULTIPLE PRODUCTS WITH SETUP TIMES AND COSTS

The problem of production planning and setup scheduling of multiple products on a single facility is studied in this paper. The facility can only produce one product at a time. A setup is required when the production switches from one type of product to another. Both setup times and setup costs are considered. The objective is to determine the setup schedule and production rate for each product that minimize the average total costs, which include the inventory, backlog, and setup costs. Under the assumption of a constant production rate, we obtain the optimal cyclic rotation schedule for the multiple products system. Besides the decision variables studied in the classical economic lot scheduling problem (ELSP), the production rate is also a decision variable in our model. We prove that our solutions improve the results of the classical ELSP.     

Facility Location: A Robust Optimization Approach

In this research, we apply robust optimization (RO) to the problem of locating facilities in a network facing uncertain demand over multiple periods. We consider a multi‐period fixed‐charge network location problem for which we find (1) the number of facilities, their location and capacities, (2) the production in each period, and (3) allocation of demand to facilities. Using the RO approach we formulate the problem to include alternate levels of uncertainty over the periods. We consider two models of demand uncertainty: demand within a bounded and symmetric multi‐dimensional box, and demand within a multi‐dimensional ellipsoid. We evaluate the potential benefits of applying the RO approach in our setting using an extensive numerical study. We show that the alternate models of uncertainty lead to very different solution network topologies, with the model with box uncertainty set opening fewer, larger facilities. Through sample path testing, we show that both the box and ellipsoidal uncertainty cases can provide small but significant improvements over the solution to the problem when demand is deterministic and set at its nominal value. For changes in several environmental parameters, we explore the effects on the solution performance.     

From Linear to Semidefinite Programming: An Algorithm to Obtain Semidefinite Relaxations for Bivalent Quadratic Problems

In this paper, we present a simple algorithm to obtain mechanically SDP relaxations for any quadratic or linear program with bivalent variables, starting from an existing linear relaxation of the considered combinatorial problem. A significant advantage of our approach is that we obtain an improvement on the linear relaxation we start from. Moreover, we can take into account all the existing theoretical and practical experience accumulated in the linear approach. After presenting the rules to treat each type of constraint, we describe our algorithm, and then apply it to obtain semidefinite relaxations for three classical combinatorial problems: the K-CLUSTER problem, the Quadratic Assignment Problem, and the Constrained-Memory Allocation Problem. We show that we obtain better SDP relaxations than the previous ones, and we report computational experiments for the three problems.     

Integrated Procurement Planning in Multi‐division Firms

For large multi‐division firms, coordinating procurement policies across multiple divisions to leverage volume discounts from suppliers based on firm‐wide purchasing power can yield millions of dollars of savings in procurement costs. Coordinated procurement entails deciding which suppliers to use to meet each division's purchasing needs and sourcing preferences so as to minimize overall purchasing, logistics, and operational costs. Motivated by this tactical procurement planning problem facing a large industrial products manufacturer, we propose an integrated optimization model that simultaneously considers both firm‐wide volume discounts and divisional ordering and inventory costs. To effectively solve this large‐scale integer program, we develop and apply a tailored solution approach that exploits the problem structure to generate tight bounds. We identify several classes of valid inequalities to strengthen the linear programming relaxation, establish polyhedral properties of these inequalities, and develop both a cutting‐plane method and a sequential rounding heuristic procedure. Extensive computational tests for realistic problems demonstrate that our integrated sourcing model and solution method are effective and can provide significant economic benefits. The integrated approach yields average savings of 7.5% in total procurement costs compared to autonomous divisional policies, and our algorithm generates near‐optimal solutions (within 0.75% of optimality) within reasonable computational time.     

Coordination of Supply Chains with Risk‐Averse Agents

The extant supply chain management literature has not addressed the issue of coordination in supply chains involving risk‐averse agents. We take up this issue and begin with defining a coordinating contract as one that results in a Pareto‐optimal solution acceptable to each agent. Our definition generalizes the standard one in the risk‐neutral case. We then develop coordinating contracts in three specific cases: (i) the supplier is risk neutral and the retailer maximizes his expected profit subject to a downside risk constraint; (ii) the supplier and the retailer each maximizes his own mean‐variance trade‐off; and (iii) the supplier and the retailer each maximizes his own expected utility. Moreover, in case (iii), we show that our contract yields the Nash Bargaining solution. In each case, we show how we can find the set of Pareto‐optimal solutions, and then design a contract to achieve the solutions. We also exhibit a case in which we obtain Pareto‐optimal sharing rules explicitly, and outline a procedure to obtain Pareto‐optimal solutions.     

Staff rostering in call centers providing employee transportation

We address the staff rostering problem in call centers with the goal of balancing operational cost, agent satisfaction and customer service objectives. In metropolitan cities such as Istanbul and Mumbai, call centers provide the transportation of their staff so that shuttle costs constitute a significant part of the operational costs. We develop a mixed integer programming model that incorporates the shuttle requirements at the beginning and end of the shifts into the agent-shift assignment decisions, while considering the skill sets of the agents, and other constraints due to workforce regulations and agent preferences. We analyze model solutions for a banking call center under various management priorities to understand the interactions among the conflicting objectives. We show that considering transportation costs as well as agent preferences in agent-shift assignments provides significant benefits in terms of both cost savings and employee satisfaction.     

Penalizing passenger’s transfer time in computing airlines revenue

Airline strategic alliances result in a form of cooperation where firms can access the resources of others network members in order to create added value for their passengers. The shortcoming of this process is that each member of the network makes individual revenue management decisions to maximize its own income, resulting in a sub-optimal income for the network members.To deal with this problem, this paper suggests a resource allocation based on a transfer pricing mechanism, to cooperatively divide the revenue of a passenger between network members. The method penalizes the total time that a passenger takes for reaching the final destination. The model takes into consideration that the profit is independent of the number of available seats (with a maximum determined for each airline). The method computes the optimal transfer pricing and, at the same time, optimizes the quantity of seats (the booking limits). The solution results in a strong Nash equilibrium, which incorporate both the transfer prices and booking limits. We describe the transfer pricing process using an ergodic, finite and continuous-time Markov game model for multiple players. The revenue of each airline in the supply chain will depend on the number of flight transfers and the transit time of the passenger at the airports: the longer the time to the final destination, the lower the price. We compute a collaborative equilibrium point, useful for understanding the resulting revenue of each member of the network. For solving the game, we employ an iterative method based on a proximal approach that involves time penalization. In our final contribution, we present results from a numerical example, which validates the proposed Markov game model and measures the benefits of the transfer pricing resource allocation.     

Sequencing and Scheduling Appointments with Potential Call‐In Patients

This paper studies appointment scheduling for a combination of routine patients who book well in advance and last‐minute patients who call for an appointment later that same day. We determine when these same‐day patients should be scheduled throughout the day, and how the prospect of their arrivals affects the appointment times of the routine patients. By formulating the problem as a stochastic linear program, we are able to incorporate random and heterogeneous service times and no‐show rates, ancillary physician tasks, and appointment delay costs for same‐day patients who prefer to see the doctor as early as possible. We find that the optimal patient sequence is quite sensitive to the no‐show probabilities and the expected number of same‐day patients. We also develop two simple heuristic solutions to this combinatorial sequencing problem.     

An Application of Master Schedule Smoothing and Planned Lead Time Control

Make‐to‐order (MTO) manufacturers must ensure concurrent availability of all parts required for production, as any unavailability may cause a delay in completion time. A major challenge for MTO manufacturers operating under high demand variability is to produce customized parts in time to meet internal production schedules. We present a case study of a producer of MTO offshore oil rigs that highlights the key aspects of the problem. The producer was faced with an increase in both demand and demand variability. Consequently, it had to rely heavily on subcontracting to handle production requirements that were in excess of its capacity. We focused on the manufacture of customized steel panels, which represent the main sub‐assemblies for building an oil rig. We considered two key tactical parameters: the planning window of the master production schedule and the planned lead time of each workstation. Under the constraint of a fixed internal delivery lead time, we determined the optimal planning parameters. This improvement effort reduced the subcontracting cost by implementing several actions: the creation of a master schedule for each sub‐assembly family of the steel panels, the smoothing of the master schedule over its planning window, and the controlling of production at each workstation by its planned lead time. We report our experience in applying the analytical model, the managerial insights gained, and how the application benefits the oil‐rig producer.