A robust branch-and-cut approach for the minimum-energy symmetric network connectivity problem

This paper considers the minimum-energy symmetric network connectivity problem (MESNC) in wireless sensor networks. The aim of the MESNC is to assign transmission power to each sensor node such that the resulting network, using only bidirectional links, is connected and the total energy consumption is minimized. We first present two new models of this problem and then propose new branch-and-cut algorithms. Based on an existing formulation, we present the first model by introducing additional constraints. These additional constraints allow us to relax certain binary variables to continuous ones and thus to reduce significantly the number of binary variables. Our second model strengthens the first one by adding an exponential number of lifted directed-connectivity constraints. We present two branch-and-cut procedures based on these proposed improvements. The computational results are reported and show that our approaches, using the proposed formulations, can efficiently solve instances with up to 120 nodes, which significantly improve our ability to solve much larger instances in comparison with other exact algorithms in the literature.     

A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem

In this paper, we propose an optimal algorithm for the Multiple-choice Multidimensional Knapsack Problem MMKP. The main principle of the approach is twofold: (i) to generate an initial feasible solution as a starting lower bound, and (ii) at different levels of the search tree to determine an intermediate upper bound obtained by solving an auxiliary problem called MMKP_aux and perform the strategy of fixing items during the exploration. The approach which we develop is of best-first search strategy. The method was able to optimally solve the MMKP. The performance of the exact algorithm is evaluated on a set of small and medium instances, some of them are extracted from the literature and others are randomly generated. This algorithm is parallelizable and it is one of its important feature.     

A stochastic programming model for production planning of perishable products with postponement

This study addresses the production planning problem for perishable products, in which the cost and shortage of products are minimised subject to a set of constraints such as warehouse space, labour working time and machine time. Using the concept of postponement, the production process for perishable products is differentiated into two phases to better utilise the resources. A two-stage stochastic programming with recourse model is developed to determine the production loading plan with uncertain demand and parameters. A set of data from a toy company shows the benefits of the postponement strategy: these include lower total cost and higher utilisation of resources. The impact of unit shortage cost under different probability distribution of economic scenarios on the total cost is analyzed. Comparative analysis of solutions with and without postponement strategies is also performed.     

A Lagrangian relaxation approach for the multiple sequence alignment problem

We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian subproblem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem. Furthermore, the quality of the alignments is among the best computed so far.     

Fix-and-optimize and variable neighborhood search approaches for multi-level capacitated lot sizing problems

In this paper, a new fix-and-optimize (FO) approach is proposed for two dynamic multi-level capacitated lot sizing problems (MLCLSP), the MLCLSP without setup carryover and the MLCLSP with setup carryover. Given an MIP model of a lot sizing problem, the approach iteratively solves a series of sub-problems of the model until no better solution can be found. Each sub-problem re-optimizes a subset of binary decision variables determined based on the interrelatedness of binary variables in the constraints of the model, while fixing the values of the other binary variables. Based on the FO, a variable neighbourhood search (VNS) approach for the MLCLSP without setup carryover is also developed, which can further improve the solution obtained by the FO by diversifying the search space. Numerical experiments on benchmark instances show that both our FO and VNS approaches can obtain a better solution for most instances compared with that found by the fix-and-optimize approach proposed by Helber and Sahling (International Journal of Production Economics 2010;123:247–256).     

A hierarchical production plan for a make-to-order steel fabrication plant

A three-tiered hierarchical production plan (HPP) for a strictly make-to-order steel fabrication plant with the objective of developing a production plan and master schedule for a set of product archetypes is implemented. Data are collected from an actual steel fabrication plant located in the Midwestern section of the US. An aggregate linear programming model, a non-linear disaggregate model and a master production schedule comprise the respective tiers. Appropriate models provide the forecasts needed in the first two tiers. A production plan and master schedule based on data collected at the plant, benefits expected for its implementation and practical limitations are reported.     

A robust optimization model for stochastic aggregate production planning

The aggregate production planning (APP) problem considers the medium-term production loading plans subject to certain restrictions such as production capacity and workforce level. It is not uncommon for management to often encounter uncertainty and noisy data, in which the variables or parameters are stochastic. In this paper, a robust optimization model is developed to solve the aggregate production planning problems in an environment of uncertainty in which the production cost, labour cost, inventory cost, and hiring and layoff cost are minimized. By adjusting penalty parameters, decision-makers can determine an optimal medium-term production strategy including production loading plan and workforce level while considering different economic growth scenarios. Numerical results demonstrate the robustness and effectiveness of the proposed model. The proposed model is realistic for dealing with uncertain economic conditions. The analysis of the tradeoff between solution robustness and model robustness is also presented.     

Coordinating pricing and production decisions for multiple products

We consider a dynamic problem of joint pricing and production decisions for a profit-maximizing firm that produces multiple products. We model the problem as a mixed integer nonlinear program, incorporating capacity constraints, setup costs, and dynamic demand. We assume demand functions to be convex, continuous, differentiable, and strictly decreasing in price. We present a solution approach which is more general than previous approaches that require the assumption of a specific demand function. Using real-world data from a manufacturer, we study problem instances for different demand scenarios and capacities and solve for optimal prices and production plans. We present analytical results that provide managerial insights on how the optimal prices change for different production plans and capacities. We extend some of the earlier works that consider single product problems to the case of multiple products and time variant production capacities. We also benchmark performance of proposed algorithm with a commercial solver and show that it outperforms the solver both in terms of solution quality and computational times.     

A column generation heuristic for dynamic capacitated lot sizing with random demand under a fill rate constraint

This paper deals with the dynamic multi-item capacitated lot-sizing problem under random period demands (SCLSP). Unfilled demands are backordered and a fill rate constraint is in effect. It is assumed that, according to the static-uncertainty strategy of Bookbinder and Tan [1], all decisions concerning the time and the production quantities are made in advance for the entire planning horizon regardless of the realization of the demands. The problem is approximated with the set partitioning model and a heuristic solution procedure that combines column generation and the recently developed _ABCβ${\mathit{ABC}}_{\beta }$ heuristic is proposed.     

Correct accounting for duty drawbacks with outward and inward processing in global production networks

We develop a new model for the correct accounting of customs duties levied on a product. We examine inward and outward processing – that is, processed components can be either imported or produced in a foreign country – in the strategic planning of a global production network. This complex modeling problem is structured with path variables, and the duty drawbacks can be simultaneously and correctly entered for n production stages in m market regions (with corresponding duty regions) for all products with a maximum n-level bill of materials. We present a case study from the automotive industry to examine whether or not the possibility of future duty rate changes or free trade agreements, such as one between the United States and the European Union, could affect the design of a production network and hence should be considered in strategic planning. We show that correctly accounting for duty drawbacks can lead to changes in the global footprint of production. We also demonstrate that intercontinental trade barriers (in the form of duties) diminish working capital and entail longer delivery routes. Eliminating these political trade barriers could increase the returns to capital while reducing both delivery lead times and environmental costs.     

A possibilistic aggregate production planning model for brass casting industry

This article discusses a possibilistic aggregate production planning (APP) model for blending problem in a brass factory; the problem computing optimal amounts of raw materials for the total production of several types of brass in a planning period. The model basically has a multi-blend model formulation in which demand quantities, percentages of the ingredient in some raw materials, cost coefficients, minimum and maximum procurement amounts are all imprecise and have triangular possibility distributions. A mathematical model and a solution algorithm are proposed for solving this model. In the proposed model, the Lai and Hwang's fuzzy ranking concept is relaxed by using ‘Either-or’ constraints. An application of the brass casting APP model to a brass factory demonstrates that the proposed model successfully solves the multi-blend problem for brass casting and determines the optimal raw material purchasing policies.     

A goal programming model for paper recycling system

The conflict between economic optimization and environmental protection has received wide attention in recent research programs for waste management system planning. This has also resulted in a set of new waste management goals in reverse logistics system planning. The purpose of this analysis is to formulate a mixed integer goal programming (MIGP) model to assist in proper management of the paper recycling logistics system. The model studies the inter-relationship between multiple objectives (with changing priorities) of a recycled paper distribution network. The objectives considered are reduction in reverse logistics cost; product quality improvement through increased segregation at the source; and environmental benefits through increased wastepaper recovery. The proposed model also assists in determining the facility location, route and flow of different varieties of recyclable wastepaper in the multi-item, multi-echelon and multi-facility decision making framework. The use of the model has been illustrated through a problem of paper recycling in India.     

An oracle-based algorithm for robust planning of production routing problems in closed-loop supply chains of beverage glass bottles

The demand for glass bottles is exhibiting an upward trend over time. The manufacturing of glass bottles is costlier in terms of time and resources and is associated with a higher level of heat generation and environmental pollution compared to recycling processes. In response to the aforementioned challenges, companies that use glass bottles need to implement strategies to manage their reverse supply chains in conjunction with their traditional supply chains, as the economic and environmental benefits of returned products are unquestionable. Closed-loop supply chains (CLSCs) integrate forward and reverse flows of products and information. This integration helps companies to have a broader view of the whole chain. Despite these advantages, managing CLSCs can be challenging as they are exposed to many uncertainties regarding supply and demand processes, travel times, and quantity/quality of returned products.In this study, we consider the production planning, inventory management, and vehicle routing decisions of a CLSC of beverage glass bottles. We propose an MILP model and rely on a multi-stage adjustable robust optimization (ARO) formulation to deal with the randomness in both the demand for filled bottles and the requests for pickups of empty bottles. We develop an exact oracle-based algorithm to solve the ARO problem and propose a heuristic search algorithm to reduce the solution time. Our numerical experiments not only show the incompetency of the customary method, namely the affine decision rule approach, but also illustrate how our algorithms can solve the small-size problems and significantly improve the quality of the obtained solution for large problems. Furthermore, our numerical results show that robust plans tend to be sparse, meaning the routes are chosen so that empty bottles are transported to production sites in such a way that fewer new bottles need to be ordered. Thus, robust planning makes the CLSCs more environmentally friendly.     

Supply chain configuration for diffusion of new products: An integrated optimization approach

We develop an integrated/hybrid optimization model for configuring new products’ supply chains while explicitly considering the impact of demand dynamics during new products’ diffusion. The hybrid model simultaneously determines optimal production/sales plan and supply chain configuration. The production and sales plan provides decisions on the optimal timing to launch a new product, as well as the production and sales quantity in each planning period. The supply chain configuration provides optimal selection of options and safety stock level kept at each supply chain function. Extensive computational experiments on randomly generated testbed problems indicate that the hybrid modeling and solution approach significantly outperforms non-hybrid alternative modeling and solution approaches under various diffusion and supply chain topologies. We provide insights on optimal production/sales plan and supply chain configuration for new products during their diffusion process. Also, managerial implications relevant to effectiveness of the hybrid approach are discussed.     

A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries

The vehicle routing problem with pickups and deliveries (VRPPD) extends the vehicle routing problem (VRP) by allowing customers to both send and receive goods. The main difficulty of the problem is that the load of vehicles is fluctuating rather than decreasing as in the VRP. We design a reactive tabu search metaheuristic that can check feasibility of proposed moves quickly and reacts to repetitions to guide the search. Several new best solutions are found for benchmark problems.     

Integrated retail decisions with multiple selling periods and customer segments: Optimization and insights

Integrating retail decisions on such aspects as assortment, pricing, and inventory greatly improves profitability. We examine a multi-period selling horizon where a retailer jointly optimizes assortment planning, pricing, and inventory decisions for a product line of substitutable products, in a market with multiple customer segments. Focusing on fast-moving retail products, the problem is modeled as a mixed-integer nonlinear program where demand is driven by exogenous consumer reservation prices and endogenous assortment and pricing decisions. A mixed-integer linear reformulation is developed, which enables an exact solution to large problem instances (with up to a hundred products) in manageable times. Empirical evidence is provided in support of a classical deterministic maximum-surplus consumer choice model. Computational results and managerial insights are discussed. We find that the optimal assortment and pricing decisions do not exhibit a simple, intuitive structure that could be analytically characterized, which reflects the usefulness of optimization approaches to numerically identify attractive trade-offs for the decision-maker. We also observe that suboptimal inventory policies significantly decrease profitability, which highlights the importance of integrated decision-making. Finally, we find that the seasonality of consumer preferences and supply costs present an opportunity for boosting the profit via higher inventory levels and wider assortments.     

基于双层规划的反恐应急设施选址模型及算法

恐怖袭击常以人流密集地区的平民作为袭击目标，并存在突发性和随机性等特点，极易造成严重的袭击后果。通过反恐应急设施的合理布局可以缩短救援人员和物资的到达时间，从而减轻袭击后果。首先，对反恐应急设施选址问题进行描述，并将其构造为一类离散双层规划模型。其中，上层规划是关于政府选址的0-1规划问题，下层规划则是关于恐怖分子袭击目标选择的0-1规划问题。其次，结合模型和问题的特征设计算法，利用分支定界算法实现上层选址变量的隐枚举，同时通过下层问题的求解来确定上下界并判断是否满足分枝或剪枝的条件。最后，结合南疆地区的交通拓扑网络进行算例分析，结果证明有效的选址方案可以大大降低袭击损失。     

Closed-loop supply chain configuration for new and reconditioned products: An integrated optimization model

Closed-Loop Supply Chain Management (CLSCM) is considered as a strategic response to the call for corporate sustainability while further expanding the scope of value creation to include product reconstruction. The Closed-Loop Supply Chain (CLSC) performance is directly related to the CLSC network design. The CLSC network design, with long-term and strategic connotations, involves selection of an integrated network of partner organizations to be engaged on one hand in the forward supply chain processes relevant to families of existing and new products and also involved in reverse supply chain activities relevant to reconstruction of the returned products. At the tactical level, Closed-Loop Supply Chain Configuration (CLSCC) attempts to address issues pertinent to launch of a new product and its reconstruction. The CLSC network design is well studied in the current literature, but addressing the CLSCC is neglected. To study the CLSCC problem we: (a) develop an integrated optimization model for problem; (b) present a real-world case study of a battery manufacturer; (c) based on the case study, we conduct a comprehensive set of computational experiments followed by a series of what-if analyses to compare profitability of the Forward Supply Chain Configuration (FSCC) versus the CLSCC; and (c) discuss the key observations and managerial implications drawn from the computational experiments, applicable to other real-world instances. The significant outcomes of the study suggest that: (i) performance of the firm׳s base case integrated CLSCC model is significantly better than the current supply chain model (ii) the sales-price ratio of new battery is found to be negatively related with the maximum acquiring price of used batteries; (iii) combination of sales price ratios of new and reconditioned batteries determines the total net profit for a given return rate. Finally, important managerial insights and scope for future research are discussed.     

Production planning and control for remanufacturing: exploring characteristics and difficulties with case studies

Production planning and control for remanufacturing is a major managerial challenge in the operations management. Researches demonstrate the need for decision-making methods in this context, which has generated theoretical and quantitative studies. However, this area still lacks empirical studies dealing with the practical, day-to-day difficulties of remanufacturers. The purpose of this paper is to link the literature and practice in a systematic in such a way that it is possible to show the similarities and differences between theoretically listed needs and real cases, thereby extending the results of previous research. For this purpose, four case studies are considered. The cases involve original equipment manufacturers (OEM) of automotive parts that have remanufacturing operations. The results indicate that these companies have difficulties that have not been addressed to date in the literature related to the uncertainties inherent in remanufacturing. In addition, we find that these companies use simplified decision-making approaches.     

A framework for production rescheduling in sociotechnical manufacturing environments

No plan survives contact with reality. Despite the rich research base regarding handling uncertainty in production planning and control systems, there is an intellectual gap between theory and practice with regard to handling unforeseen events generated by internal and external factors, such as unforeseen machine downtimes and changes in demand. Motivated by longitudinal observations in two industrial settings and an analysis of the relevant literature, a framework for rescheduling decision-making in the face of unforeseen production events is proposed. In practical settings, the effectiveness of decisions depends on a set of situational factors. The findings of this research can be utilised further to provide guidelines for developing effective decision support principles and systems, addressing the needs of organisational decision-makers.