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.     

Blocking in Healthcare Operations: A New Heuristic and an Application

We consider the problem of optimal capacity allocation in a hospital setting, where patients pass through a set of units, for example intensive care and acute care (AC), or AC and post‐acute care. If the second stage is full, a patient whose service at the first stage is complete is blocked and cannot leave the first stage. We develop a new heuristic for tandem systems to efficiently evaluate the effects of such blocking on system performance and we demonstrate that this heuristic performs well when compared with exact solutions and other approaches presented in the literature. In addition, we show how our tandem heuristic can be used as a building block to model more complex multi‐stage hospital systems with arbitrary patient routing, and we derive insights and actionable capacity strategies for a real hospital system where such blocking occurs between units.     

基于免疫遗传算法和列生成的多项目人力资源调度研究

主要研究列生成法求解带有人力资源约束的多项目多模式进度管理问题。首先根据问题建立了相应的数学模型,模型中考虑了多种约束,如项目对人员能力、水平的不同要求,目标为满足约束的条件下成本最小化,其中包含固定和可变两类成本。模型分解后,按照列生成法流程求解。由于问题的复杂性,采用启发式算法求解每个子问题:首先由基于优先原则的启发式方法给出问题的初始解,再由免疫遗传算法寻优。通过数值实验分析了算法性能、模型改进情况,不同优先原则组合对目标成本和各项目间时间分配的影响。     

An improved MIP heuristic for the intermodal hub location problem

Optimization methods have been commonly developed for the intermodal hub location problem because it has a broad range of practical applications. These methods include exact methods (limited on solving large-size problems) and heuristics (no guarantee on solution quality). In order to avoid their weakness but to leverage their strength, we develop an improved MIP heuristic combining branch-and-bound, Lagrangian relaxation, and linear programming relaxation. In the heuristic, we generate a population of initial feasible solutions using the branch-and-bound and Lagrangian relaxation methods and create a linear-relaxed solution using the linear programming relaxation method. We combine these feasible and linear-relaxed solutions to fix a portion of hub location variables so as to create a number of restricted hub location subproblems. We then combine the branch-and-bound method to solve these restricted subproblems for iteratively improving solution quality. We discuss in detail the application of the method to the intermodal hub location problem. The discussion is followed by extensive statistical analysis and computational tests, where the analysis shows statistical significance of solutions for guiding the heuristic search and comparisons with other methods indicate that the proposed approach is computationally tractable and is able to obtain competitive results.     

A flight scheduling model for Taiwan airlines under market competitions

In this research, we develop a short-term flight scheduling model with variable market shares in order to help a Taiwan airline to solve for better fleet routes and flight schedules in today's competitive markets. The model is formulated as a non-linear mixed integer program, characterized as an NP-hard problem, which is more difficult to solve than the traditional fixed market share flight scheduling problems, often formulated as integer/mixed integer linear programs. We develop a heuristic method to efficiently solve the model. The test results, mainly using the data from a major Taiwan airline's operations, show the good performance of the model and the solution algorithm.     

Managing Production and Distribution for Supply Chains in the Processed Food Industry

We develop and evaluate a modeling approach for making periodic review production and distribution decisions for a supply chain in the processed food industry. The supply chain faces several factors, including multiple products, multiple warehouses, production constraints, high transportation costs, and limited storage at the production facility. This problem is motivated by the supply chain structure at Amy's Kitchen, one of the leading producers of natural and organic foods in the United States. We develop an enhanced myopic two‐stage approach for this problem. The first stage determines the production plan and uses a heuristic, and the second stage determines the warehouse allocation plan and uses a non‐linear optimization model. This two‐stage approach is repeated every period and incorporates look‐ahead features to improve its performance in future periods. We validate our model using actual data from one factory at Amy's Kitchen and compare the performance of our model to that of the actual operation. We find that our model significantly reduces both inventory levels and stockouts relative to those of the actual operation. In addition, we identify a lower bound on the total costs for all feasible solutions to the problem and measure the effectiveness of our model against this lower bound. We perform sensitivity analysis on some key parameters and assumptions of our modeling approach.     

An investigation into the vehicle routing problem with time windows and link capacity constraints

In this work, we investigate a new, yet practical, variant of the vehicle routing problem called the vehicle routing problem with time windows and link capacity constraints (VRPTWLC). The problem considers new constraints imposed on road links with regard to vehicle passing tonnage, which is motivated by a business project with a Hong Kong transportation company that transports hazardous materials (hazmats) across the city and between Hong Kong and mainland China. In order to solve this computationally challenging problem, we develop a tabu search heuristic with an adaptive penalty mechanism (TSAP) to help manage the company's vehicle fleet. A new data set and its generation scheme are also presented to help validate our solutions. Extensive computational experiments are conducted, showing the effectiveness of the proposed solution approach.     

The Retail Planning Problem Under Demand Uncertainty

We consider the retail planning problem in which the retailer chooses suppliers and determines the production, distribution, and inventory planning for products with uncertain demand to minimize total expected costs. This problem is often faced by large retail chains that carry private‐label products. We formulate this problem as a convex‐mixed integer program and show that it is strongly NP‐hard. We determine a lower bound by applying a Lagrangian relaxation and show that this bound outperforms the standard convex programming relaxation while being computationally efficient. We also establish a worst‐case error bound for the Lagrangian relaxation. We then develop heuristics to generate feasible solutions. Our computational results indicate that our convex programming heuristic yields feasible solutions that are close to optimal with an average suboptimality gap at 3.4%. We also develop managerial insights for practitioners who choose suppliers and make production, distribution, and inventory decisions in the supply chain.     

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.     

A Framework for Facilitating Sourcing and Allocation Decisions for Make‐to‐Order Items

This paper provides a fundamental building block to facilitate sourcing and allocation decisions for make‐to‐order items. We specifically address the buyer's vendor selection problem for make‐to‐order items where the goal is to minimize sourcing and purchasing costs in the presence of fixed costs, shared capacity constraints, and volume‐based discounts for bundles of items. The potential suppliers for make‐to‐order items provide quotes in the form of single sealed bids or participate in a dynamic auction involving open bids. A solution to our problem can be used to determine winning bids amongst the single sealed bids or winners at each stage of a dynamic auction. Due to the computational complexity of this problem, we develop a heuristic procedure based on Lagrangian relaxation technique to solve the problem. The computational results show that the procedure is effective under a variety of scenarios. The average gap across 2,250 problem instances is 4.65%.     

OPTIMAL AND HEURISTIC SOLUTIONS FOR THE MULTI‐ITEM NEWSVENDOR PROBLEM WITH A SINGLE CAPACITY CONSTRAINT

This research considers a multi‐item newsvendor problem with a single capacity constraint. While this problem has been addressed in the literature, the focus here is on developing simple, closed‐form expressions for the order quantities. The benefit of such an approach is that the solutions are straightforward to calculate and have managerial appeal. Additionally, we show these expressions to be optimal under a variety of conditions. For more general cases when these optimality conditions do not hold, we use these expressions as heuristic solutions. Via computational studies, we demonstrate that these heuristics are extremely effective when the optimality conditions are not satisfied.     

An integrated strategy for a production planning and warehouse layout problem: Modeling and solution approaches

We study a real-world production warehousing case, where the company always faces the challenge to find available space for its products and to manage the items in the warehouse. To resolve the problem, an integrated strategy that combines warehouse layout with the capacitated lot-sizing problem is presented, which have been traditionally treated separately in the existing literature. We develop a mixed integer linear programming model to formulate the integrated optimization problem with the objective of minimizing the total cost of production and warehouse operations. The problem with real data is a large-scale instance that is beyond the capability of optimization solvers. A novel Lagrangian relax-and-fix heuristic approach and its variants are proposed to solve the large-scale problem. The preliminary numerical results from the heuristic approaches are reported.     

A near-optimal heuristic for the sequencing problem in multiple-batch flow-shops with small equal sublots

In this paper, we consider the lot-streaming problem of sequencing a set of batches, to be processed in equal sublots, in a flow-shop, so as to minimize makespan. A new heuristic procedure, called the bottleneck minimal idleness heuristic, is developed. Results of an experimental study are presented. It is shown that the proposed procedure generates solutions that are very close to the optimal solutions, and that the solutions generated are better than those obtained by using the fast insertion heuristic, considered to be a good heuristic for solving the flow-shop scheduling problem, when applied to the problem on hand.     

Bounding Optimal Expected Revenues for Assortment Optimization under Mixtures of Multinomial Logits

We consider assortment problems under a mixture of multinomial logit models. There is a fixed revenue associated with each product. There are multiple customer types. Customers of different types choose according to different multinomial logit models whose parameters depend on the type of the customer. The goal is to find a set of products to offer so as to maximize the expected revenue obtained over all customer types. This assortment problem under the multinomial logit model with multiple customer types is NP‐complete. Although there are heuristics to find good assortments, it is difficult to verify the optimality gap of the heuristics. In this study, motivated by the difficulty of finding optimal solutions and verifying the optimality gap of heuristics, we develop an approach to construct an upper bound on the optimal expected revenue. Our approach can quickly provide upper bounds and these upper bounds can be quite tight. In our computational experiments, over a large set of randomly generated problem instances, the upper bounds provided by our approach deviate from the optimal expected revenues by 0.15% on average and by less than one percent in the worst case. By using our upper bounds, we are able to verify the optimality gaps of a greedy heuristic accurately, even when optimal solutions are not available.     

A market regulation bilevel problem: A case study of the Mexican petrochemical industry

In this paper, a bilevel programming model is proposed to study a problem of market regulation through government intervention. One of the main characteristics of the problem herein analyzed is that the government monopolizes the raw material in one industry, and competes in another industry with private firms for the production of commodities. Under this scheme, the government controls a state-owned firm to balance the market; that is, to minimize the difference between the produced and demanded commodities. On the other hand, a regulatory organization that coordinates private firms aims to maximize the total profit by deciding the amount of raw material bought from the a state-owned firm. Two equivalent single-level reformulations are proposed to solve the problem. The first reformulation is based on the strong duality condition of the lower level and results in a continuous non-linear model. The second reformulation resorts to the complementarity slackness optimality constraints yielding a mixed-integer linear model. Additionally, three heuristic algorithms are designed to obtain good-quality solutions with low computational effort. In this problem, the feasible region of the dual problem associated to the follower is independent from the leader’s decision. Therefore, the proposed heuristics exploit this particular characteristic of the bilevel model. Moreover, the third heuristic hybridizes the other two algorithms to enhance its performance. Extensive computational experimentation is carried out to measure the efficiency of the proposed solution methodologies. A case study based on the Mexican petrochemical industry is presented. Additional instances generated from the case study are considered to validate the robustness of the proposed heuristic algorithms. Numerical results indicate that the hybrid algorithm outperforms the other two heuristics. However, all of them demonstrate to be good alternatives for solving the problem. Additionally, optimal solutions of all the instances are obtained by using good quality solutions (given by the hybrid algorithm) as initial solutions when solving the second reformulation via a general purpose solver.     

The selective minimum latency problem under travel time variability: An application to post-disaster assessment operations

In this paper, we consider a new selective routing problem, where a subset of customers should be serviced by a limited fleet of vehicles with the aim of minimizing the total latency. A service level constraint is added to guarantee that a minimum system performance is achieved. Assuming that the travel times are uncertain, we address the problem through a mean-risk approach. The inclusion of risk in the objective function makes the problem computationally challenging. To solve it, we propose an efficient heuristic, relying on a variable neighbourhood search mechanism, able to strike the balance between service level and latency. A detailed discussion of the model, which includes simulation tests and a sensitivity analysis, is carried out to illustrate the applicability of our approach in a post-disaster scenario, taking as a case study the Haiti earthquake in 2010. Additional computational experiments show that the proposed heuristic is effective for this difficult problem and often matches optimal solutions for small and medium-scale benchmark instances.     

Minimization of maximum lateness under linear deterioration

This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be -hard in the literature. In this paper, we design a branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding process such that the algorithm can solve problems of 100 jobs within 1 min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases.     

A shelf-space optimization model when demand is stochastic and space-elastic

The more customer demand is impulse-driven, the more it is space-dependent and the more it is subject to variation. We investigate the corresponding problem of retail shelf-space planning when demand is stochastic and sensitive to the number and position of facings. We develop a model to maximize a retailer׳s profit by selecting the number of facings and their shelf position under the assumption of limited space. The model is particularly applicable to promotional or temporary products.We develop the first optimization model and solution approach that takes stochastic demand into account, since the current literature applies deterministic models for shelf-space planning. By the means of an innovative modeling approach for the case with space- and positioning effects and the conversion of our problem into a mixed-integer problem, we obtain optimal results within very short run times for large-scale instances relevant in practice. Furthermore, we develop a solution approach to account for cross-space elasticity, and solve it using an own heuristic, which efficiently yields near-optimal results. We demonstrate that correctly considering space elasticity and demand variation is essential. The corresponding impacts on profits and solution structures become even more significant when space elasticity and stochastic demand interact, resulting in up to 5% higher profits and up to 80% differences in solution structures, if both effects are correctly accounted for. We develop an efficient modeling approach, compare the model results with approaches applied in practice and derive rules-of-thumb for planners.     

A heuristic algorithm for minimizing maintenance workforce level

We develop a heuristic algorithm for minimizing the workforce level required to accommodate all the maintenance jobs requested within a specific time interval. Each maintenance job has its own release and due dates as well as the required man-days, and must be scheduled in a noninterrupted time interval, i.e. without preemption. However, the duration of each job is not fixed, but to be determined within a specific range. We show that this problem can be seen as a variant of the two-dimensional bin-packing problem with some additional constraints. We develop a non-linear mixed integer programming model for the proposed problem, and employ some well-known bin-packing algorithms to develop an efficient heuristic algorithm. In order to evaluate the performance of the proposed heuristic, we present a computationally efficient scheme for getting a good lower bound for the actual minimum. The computational experiment shows that the proposed heuristic algorithm performs quite satisfactorily in practice.     

Optimal Selection Strategy for the Group Interview Problem

We propose a more generalized version of the secretary problem, called the group interview problem, in which each group contains several alternatives and each group of alternatives is presented and evaluated sequentially over time. Using the assumptions corresponding to the classical secretary problem, we derive an optimal selection strategy which maximizes the probability of winning or selecting the single best choice in a given sequence of groups. We further address the problem of choosing at the beginning of the evaluation process a sequence of groups to maximize the winning probability. Because of formidable computational requirements to obtain an optimal solution to this sequencing problem, we then develop a heuristic algorithm based on several properties inherent in an optimal selection strategy. The heuristic procedure is evaluated experimentally using Monte Carlo simulation and is shown to be effective in obtaining near-optimal (within 5 percent) solutions.