ALBERT

Description: Huff location problems have been extensively analyzed within the field of competitive continuous location. In this work, two Huff location models on networks are addressed, by considering that users go directly to the facility or they visit the facility in their way to a destination. Since the problems are multimodal, a branch and bound algorithm is proposed, in which two different bounding strategies, based on Interval Analysis and DC optimization, are used and compared. Computational results are given for the two bounding procedures, showing that problems of rather realistic size can be solved in reasonable time.

Description: In a standard DIF due-date assignment model, customers may consider late due-dates as unacceptable, i.e., if a due-date is assigned later than a pre-specified lead time, the supplier is penalized. This note extends this setting by adding a lower bound on the acceptable lead-time, reflecting e.g., the time needed by the customer for preparation of storage space. Thus, in addition to the standard earliness/tardiness penalties of jobs, our model contains penalties for early and tardy due-dates. The objective is of a minmax type, i.e. we try to minimize the highest (job and due-date) cost. An efficient O ( n ) solution algorithm (where n is the number of jobs) is introduced.

Description: Online customer segmentation is a significant research topic of customer relationship management. Previous literatures mainly studied the differences between non-purchasers and purchasers, lacking further segmentation of online purchasers. There is still existing significant heterogeneity within purchaser-groups. This paper focuses on Chinese online purchaser segmentation based on large volume of real transaction data on Taobao.com, we firstly extracted and investigated Chinese online purchaser behavior indicators and classified them into six types by cluster analysis, these six categories are: economical purchasers, active-star purchasers, direct purchasers, high-loyalty purchasers, risk-averse purchasers and credibility-first purchasers; then we built an empirical model to estimate the sensitivity of each type of online purchasers to three mainstream promotion strategies (discount, advertising and word-of-mouth), and found that economical purchasers are the most sensitive to discount promotion; direct purchasers are the most sensitive to advertising promotion; active-star purchasers are the most sensitive to word-of-mouth promotion; finally, the implications of online purchaser classification for marketing strategies were discussed.

Description: The sectorization problem is a particular case of partitioning problems occurring in cartography. The aim is to partition a territory into sectors such that the statistical activity measure of each sector is as close as possible to a given target value. We model this as a problem of minimizing the maximum deviation among all the sectors between their activity measure and their target value. We propose a mathematical programming formulation for the problem, we add some valid inequalities to restrict the solution space and develop a preprocessing procedure to reduce the number of variables. Computational results on different maps highlight the strong efficiency of this reduction procedure.

Description: High dose-rate (HDR) brachytherapy is one kind of radiotherapy used to treat different forms of cancer, such as prostate cancer. When this treatment is used for prostate cancer, a radioactive source is moved through catheters implanted into the prostate. For each patient, a treatment plan is constructed. This plan determines for example catheter positions and dwell time distribution, that is, where to the radioactive source should stop and for how long. Mathematical optimization methods have been used to find dwell time distributions of high quality; however few optimization approaches that concern catheter positioning have been studied. In this article we present an integrated model that optimizes catheter positioning and dwell time distribution simultaneously. Our results show that integrating the catheter positioning yields a large reduction of the dwell time distribution objective value (15–94 %) and slight improvements in clinical quality measures. Since the presented model is computationally demanding to solve, we also present three heuristics: a tabu search, a variable neighbourhood search and a genetic algorithm. Of these, variable neighbourhood search is the best, and out-performs a state-of-the-art optimization software (CPLEX) and the two other heuristics.

Description: In this paper, we illustrate how to combine supervised machine learning algorithms and unsupervised learning techniques for sentiment analysis and opinion mining purposes. To this end, we describe a multi-stage method for the automatic detection of different opinion trends. The proposal has been tested on real textual data available from comments introduced in a weblog, connected to organizational and administrative affairs in a public educational institution. The use of the described tool, given its potential impact to obtain valuable knowledge from opinion streams created by commenters, may be straightforwardly extended, for example, to the detection of opinion trends concerning policy decision making or electoral campaigns.

Description: We consider the assortment and inventory decisions of a retailer under a locational consumer choice model where products can be differentiated both horizontally (e.g., color of a product) and vertically (e.g., quality of a product). The assortment and quantity decisions affect customer choice and, hence, the demand and sales for each product. In this paper, we investigate two different environments where product availability and assortment affect consumer choice and demand in different ways: make-to-order (MTO) and make-to-stock (MTS). In the MTO environment, customers order and purchase their most preferred product; that is, stockouts do not occur. In the MTS model, customers buy their most preferred product if it is in stock or do not buy if it is out of stock. In both environments we find conditions under which it is optimal to carry assortments of only a single quality level. In the MTS case, we show that an assortment of mixed quality levels can be optimal only within a narrow range of parameters.

Description: A matrix M ∈ R n × n is said to be a column sufficient matrix if the solution set of LCP( M , q ) is convex for every q ∈ R n . In a recent article, Qin et al. (Optim. Lett. 3:265–276, 2009 ) studied the concept of column sufficiency property in Euclidean Jordan algebras. In this paper, we make a further study of this concept and prove numerous results relating column sufficiency with the Z and Lypaunov-like properties. We also study this property for some special linear transformations.

Description: This paper presents a methodology of measuring greenhouse gas emissions (mainly CO 2 ) for the transportation sector and illustratively applies it in Korea. The transportation sector is one of the most critical sectors concerning environmental pollution and represents about 20 percent of the yearly total greenhouse gas emissions for the energy sector in Korea. In spite of the increasing importance of the transportation sector in the eco-environment, current methodologies to analyze greenhouse gas emissions use a Tier 1 method, which is the simplest type among the methodologies recommended by IPCC guidelines. For a new methodology, we consider characteristics of transportation modes and operational environments in Korea. The proposed methodology can analyze the amount of greenhouse gas emissions for each transport mode and integrate it through transportation environments. It also provides a decision-making tool for governments to make transportation polices. As a result, the Korean government can manage the transportation sector in an eco-friendly manner and improve the national eco-environment.

Description: To match products of different quality with end market preferences under supply uncertainty, it is crucial to integrate product quality information in logistics decision making. We present a case of this integration in a meat processing company that faces uncertainty in delivered livestock quality. We develop a stochastic programming model that exploits historical product quality delivery data to produce slaughterhouse allocation plans with reduced levels of uncertainty in received livestock quality. The allocation plans generated by this model fulfil demand for multiple quality features at separate slaughterhouses under prescribed service levels while minimizing transportation costs. We test the model on real world problem instances generated from a data set provided by an industrial partner. Results show that historical farmer delivery data can be used to reduce uncertainty in quality of animals to be delivered to slaughterhouses.

Description: The Swedish electoral system exhibits significant levels of proportionality compared with the systems used in other countries. However, it has several deficiencies that could be corrected. Therefore, this paper (a) evaluates the current Swedish electoral system by identifying the imbalances in the representation of political parties and the sizes of the electoral constituencies that can occur and (b) presents two proposals for improvement that seek to correct the previously identified deficiencies. The first proposal consists of a slight modification of the current system that applies when parties get more seats than they proportionally deserve according to their global number of votes, as occurred in the 2010 election. In this case, the proposal includes a criterion so that the overrepresented parties return their excess seats. The second proposal relies on the implementation of biproportional allotments and on the replacement of the electoral thresholds of 4 % of the total votes nationwide and 12 % of the votes in a given constituency by a new threshold based on a reduction in the number of votes of the parties. The application of any of these proposals to the Swedish election held in 2010 reveals that the deficiencies in the representation of political parties are eliminated. Furthermore, the second proposal also corrects the deficiencies in the sizes of the electoral constituencies for Sweden.

Description: The main goal in this study is to introduce a new linear model for multi-period portfolio optimization. The proposed optimization model can take both stocks and their respective American style options into consideration. Moreover, to hedge the resulting portfolio, the robust counterpart of this model is developed in which the level of robustness can be determined using the length and the type of the uncertainty set. The experiments results which are obtained based on the data of Dow Jones stock market verify the performance of the proposed models compared to what has been achieved using Bertsimas et al.’s optimization model.

Description: Wavelength Division Multiplexing (WDM) optical networks are increasingly used to build up backbone networks. In this paper we study the Multicast Routing Wavelength Assignment with Delay Constraints (MRWA-DC) problem: given a WDM network with heterogeneous splitting capabilities, we want to find an optimal light-forest that respects delay bound constraints. We propose a new Integer Linear Programming compact formulation and we derive from it a new extended formulation. We solve the Linear Programming relaxation of the latter formulation using a column generation algorithm, and to address the resulting pricing problem we propose two exact algorithms and a tabu search heuristic. Experimental results show that in most cases the solutions obtained from the Linear Programming relaxation of the extended formulation are integral and that the combination of exact and heuristic algorithms for the pricing problem allows to reduce the total computation time required by the column generation process. With respect to the previous literature on the same problem we significantly reduce the computation time required for solving instances of comparable dimension and we solve, within a reasonable computation time, new instances of larger size.

Description: In this paper, Markov models of repairable systems with repair time omission are considered whose finite state space is grouped into two sets, the set of working states, W , and the set of failed states, F . If the system enters failed states from a working state at any instance, and sojourns at the failed states F less than a given nonnegative critical value τ , then the repair interval can be omitted from downtime records. Otherwise, If the system enters failed states from a working state at any instance, and sojourns at the failed states F more than the given nonnegative critical value τ , then the repair interval cannot be omitted from downtime records. In terms of the assumption, a new model is developed. The focus of attention is the new model’s availability, interval reliability and interval unreliability. Several results are derived for these reliability indexes for the new model. Some special cases and numerical examples are given to illustrate the results obtained by using Maple software in the paper.

Description: In this paper we analyze a continuous review, lost sales ( S −1, S ) inventory system with two demand classes—high priority and low priority. We compare two different policies—one where the two classes of customers are treated exactly alike and the other where a threshold rationing policy is used. We prove that under certain conditions there is a sub-optimal rationing policy which yields a lower cost for the supplier and higher service levels for both the high priority and low priority customers than the optimal policy where the two customers are treated alike.

Description: We consider multicriteria allocation problems with linear sum objectives. Despite the fact that the single objective allocation problem is easily solvable, we show that already in the bicriteria case the problem becomes intractable, is NP-hard and has a non-connected efficient set in general. Using the equivalence to appropriately defined multiple criteria multiple-choice knapsack problems, an algorithm is suggested that uses partial dominance conditions to save computational time. Different types of enumeration schemes are discussed, for example, with respect to the number of necessary filtering operations and with regard to possible parallelizations of the procedure.

Description: Project risk management aims to provide insight into the risk profile of a project as to facilitate decision makers to mitigate the impact of risks on project objectives such as budget and time. A popular approach to determine where to focus mitigation efforts, is the use of so-called ranking indices (e.g., the criticality index, the significance index etc.). Ranking indices allow the ranking of project activities (or risks) based on the impact they have on project objectives. A distinction needs to be made between activity-based ranking indices (those that rank activities) and risk-driven ranking indices (those that rank risks). Because different ranking indices result in different rankings of activities and risks, one might wonder which ranking index is best. In this article, we provide an answer to this question. Our contribution is threefold: (1) we set up a large computational experiment to assess the efficiency of ranking indices in the mitigation of risks, (2) we develop two new ranking indices that outperform existing ranking indices and (3) we show that a risk-driven approach is more effective than an activity-based approach.

Description: This paper tackles a Nurse Scheduling Problem which consists of generating work schedules for a set of nurses while considering their shift preferences and other requirements. The objective is to maximize the satisfaction of nurses’ preferences and minimize the violation of soft constraints. This paper presents a new deterministic heuristic algorithm, called MAPA (multi-assignment problem-based algorithm), which is based on successive resolutions of the assignment problem. The algorithm has two phases: a constructive phase and an improvement phase. The constructive phase builds a full schedule by solving successive assignment problems, one for each day in the planning period. The improvement phase uses a couple of procedures that re-solve assignment problems to produce a better schedule. Given the deterministic nature of this algorithm, the same schedule is obtained each time that the algorithm is applied to the same problem instance. The performance of MAPA is benchmarked against published results for almost 250,000 instances from the NSPLib dataset. In most cases, particularly on large instances of the problem, the results produced by MAPA are better when compared to best-known solutions from the literature. The experiments reported here also show that the MAPA algorithm finds more feasible solutions compared with other algorithms in the literature, which suggest that this proposed approach is effective and robust.

Description: Performance evaluation is an importance issue in supply chain management. Yang et al. (Ann. Oper. Res. 38(6):195–211, 2011 ) defined two types of supply chain production possibility sets and proved the equivalence between them. Based on the sub-perfect CRS production possibility set, they proposed a supply chain DEA model to appraise the overall technical efficiency of supply chains. The relationship among efficiency scores of the proposed model, CCR models of system and subsystems are discussed. However, we find that the equivalence between the two types of supply chain production possibility sets is not correct. The proofs of their three theorems are all problematic. In this paper, we correct some results and give three new proofs.

Description: We consider the buffer content of a fluid queue or storage process. The buffer content varies in a way that depends on the state of an underlying three-state Markov process. In state 0 the buffer content increases at a rate α ( x ) that is a function of the current buffer level  x ; in states 1 and 2 it decreases linearly, with different speeds. We study the steady-state buffer content, by using level crossing theory and by exploiting relations between the fluid queue and queues with instantaneous input and/or output.

Description: Multi-criteria simple games constitute an extension of the basic framework of voting systems and collective decision-making. The study of power index plays an important role in the theory of multi-criteria simple games. Thus, in this paper, we propose the extended Banzhaf index for these games, as the natural generalization of this index in conventional simple games. This approach allows us to compare various criteria simultaneously. An axiomatic characterization of this power index is established. The Banzhaf index is computed by taking into account the minimal winning coalitions of each class. Since this index depends on the number of ways in which each player can effect a swing, one of the main difficulties for finding this index is that it involves a large number of computations. We propose a combinatorial procedure, based on generating functions, to obtain the Banzhaf index more efficiently for weighted multi-criteria simple games. As an application, the distribution of voting power in the European Union is calculated.

Description: Over the years, foreign direct investment (FDI) has not only promoted rapid economic growth in China, but also affected the country’s environmental quality through technology spillover. This paper tests the variables that may affect the ability of green innovation by using the Granger causality test. It extracts the variables passed the test as input variables, selects the number of patents as output variable, and evaluates the efficiency of various provinces in mainland China by examining their yearly technological progress variables. At the same time, technological progress is defined and divided into capital and environmental factors, and then panel data using the variable coefficients model was used to fit influencing factors to obtain impact coefficients of capital and environment. On this basis, this paper makes the determination of membership to replace the general sense of ‘threshold’ value by using fuzzy theory and proposes the concept of the ‘comprehensive threshold’ of economic development and environmental protection. The results show that less than a quarter of China’s provinces have crossed the comprehensive threshold. Finally, based on the conclusions of quantitative analysis, some suggestions are proposed that the Chinese government ought to enact different strategies for the introduction of FDI according to different development situations of different provinces.

Description: We study a problem of integrating the supply chain of roundwood with the supply chain of forest biomass. The developed optimization model is a multiperiod, multicommodity network planning problem with multiple sources of supply, i.e., harvest areas, and multiple types of destinations, i.e., sawmills, pulp mills, and heating plants. This paper presents an extension of previous work where the set of harvest areas was given and market prices for raw materials had linear relationship with corresponding volumes. In this paper, the assumption of predefined areas is removed, and we must make the selection of harvest areas. Instead of using a traditional sequential approach to first select areas and then determine the prices, we present a new synchronous approach that can jointly choose areas and define price levels for different assortments at those chosen supply points. We test the possible settings of discretized price and use sensitivity analysis to evaluate how the variation of fixed cost concerning log forwarding at each supply point affects the wood procurement decisions. A case study from Sweden is used to analyze the market prices in an integrated market. The computational results also highlight the advantage of the proposed synchronous approach over the sequential one in both solution quality and solution time.

Description: Directional distance function (DDF) is a recognized technique for measuring efficiency while incorporating undesirable outputs. This approach allows for desirable outputs to be expanded while undesirable outputs are contracted simultaneously. A drawback of the DDF approach is that the direction vector to the production boundary is fixed arbitrarily, which may not provide the best efficiency measure. Therefore, this study extends the previous framework of efficiency analysis to introduce a new slacks-based measure of efficiency called the scale directional distance function (SDDF) approach. This new approach determines the optimal direction to the frontier for each unit of analysis and provides dissimilar expansion and contraction factors to achieve a more reasonable eco-efficiency score. This new approach is employed to measure the eco-efficiency of the Malaysian manufacturing sector. In addition, the paper demonstrates the use of the new approach to establish target values for the reduction/expansion of outputs in order for the inefficient DMUs to achieve full eco-efficiency. The results indicate that Melaka, Pulau Pinang, Negeri Sembilan, Sabah, Sarawak and Labuan have attained full eco-efficiency while Terengganu is the least eco-efficient. The overall eco-efficiency of the manufacturing sector in Malaysia is 80.5 % with wide variations across the states.

Description: Traditionally, in the fashion industry, purchasing decisions for retailers are made based on various factors such as budget, profit target, and interest rate. Since the market demand is highly volatile, risk is inherently present and it is critically important to incorporate risk consideration into the decision making framework. Motivated by the observed industrial practice, we explore via a mean-variance approach the multi-period risk minimization inventory models for fashion product purchasing. We first construct a basic multi-period risk optimization model for the fashion retailer and illustrate how its optimal solution can be determined by solving a simpler problem. Then, we analytically find that the optimal ordering quantity is increasing in the expected profit target, decreasing in the number of periods of the season, and increasing in the market interest rate. After that, we propose and solve several extended models which consider realistic and timely industrial measures such as minimum ordering quantity, carbon emission tax, and carbon quota. We analytically derive the necessary and sufficient condition(s) for the existence of the optimal solution for each model and show how the purchasing budget, the profit target, and the market interest rate affect the optimal solution. Finally, we investigate the supply chain coordination challenge and analytically illustrate how an upstream manufacturer can offer implementable supply contracts to optimize the supply chain.

Description: The rapid development of social network theory provides a new perspective for the research on counter-terrorism, however, current research mostly relates to terrorists and terrorist organizations. Firstly, the “six-element” analysis method for terrorist activities based on social network is proposed in this paper, namely, a variety of sub-networks are constructed according to the correlation among the six elements—people, organization, time, location, manner and event. These sub-networks are assessed through using centrality analysis, cohesive subgroup analysis, spatial correlation analysis, invulnerability analysis and descriptive statistic analysis; the characteristics and laws of terrorist activities are revealed from several different perspectives. Then, the “six-element” analysis method is applied to conduct empirical research on “East Turkistan” terrorist activities since the founding of the People’s Republic of China, so as to effectively identify core people and key organizations of the “East Turkistan” terrorist activity network, to assess the invulnerability of the “East Turkistan” terrorist network and to reveal the temporal and spatial distribution rules as well as the characteristics of the means and manners adopted in all previous terrorist activities. Lastly, the analysis results are interpreted qualitatively. This research can provide a basis for decision making and an analysis method for the identification of core terrorists and key terrorist organizations, determination of the key alert period, location of counter-terrorism and the early warning of the means of major terrorist activities.

Description: This paper addresses the problem of open shop scheduling on two machines with resources constraints. In the context of our study, in order to be executed, a job requires first, for its preparation for a given period of time, a number of resources which cannot exceed a given resource capacity. Then, it goes onto its execution while the resources allocated to it become available again. We seek a schedule that minimizes the makespan. We first prove the $\mathcal{N}\mathcal{P}$ -hardness of several versions of this problem. Then, we present a well solvable case, lower bounds, and heuristic algorithms along with an experimental study.

Description: This paper studies the order-fulfillment process of a supplier producing multiple customized capital goods. The times when orders are confirmed by customers are random. The supplier can only work on one product at any time due to capacity constraints. The supplier must determine the optimal time to start the process for each order so that the total expected cost of having the goods ready before or after their orders are confirmed is minimized. We formulate this problem as a discrete time Markov decision process. The optimal policy is complex in general. It has a threshold-type structure and can be fully characterized only for some special cases. Based on our formulation, we compute the optimal policy and quantify the value of jointly managing the order fulfillment processes of multiple orders and the value of taking into account demand arrival time uncertainty.

Description: Supervised learning methods are powerful techniques to learn a function from a given set of labeled data, the so-called training data. In this paper the support vector machines approach for regression is investigated under a theoretical point of view that makes use of convex analysis and Fenchel duality. Starting with the corresponding Tikhonov regularization problem, reformulated as a convex optimization problem, we introduce a conjugate dual problem to it and prove that, whenever strong duality holds, the function to be learned can be expressed via the optimal solutions of the dual problem. Corresponding dual problems are then derived for different loss functions. The theoretical results are applied by numerically solving the regression task for two data sets and the accuracy of the regression when choosing different loss functions is investigated.

Description: This volume collects all eleven survey papers that appeared in volumes 7–10 (2009–2011) of the journal 4OR: A Quarterly Journal of Operations Research . We briefly introduce the collected surveys and those that were included in the first two volumes of this series.

Description: This paper deals with simultaneous auctions of two commonly ranked objects following the model studied in Menezes and Monteiro (J. Real Estate Finance Econ., 17(3):219–232, 1998 ). For these problems we introduce a parametric family of auction mechanisms which includes the three classic auctions (discriminatory-price auction, uniform-price auction and Vickrey auction) and we call it the $\mathcal{DUV}$ family. We provide the unique Bayesian Nash equilibrium for each auction in $\mathcal{DUV}$ and prove a revenue equivalence theorem for the parametric family. Likewise, we study the value at risk of the auctioneer as a reasonable decision criterion to determine which auctions in $\mathcal{DUV}$ may be better taking into account the interests of the auctioneer. We show that there are auction mechanisms in $\mathcal{DUV}$ which are better than the classic auction mechanisms with respect to this criterion.

Description: In this paper we propose an approach for solving problems of optimal resource capacity allocation to a collection of stochastic dynamic competitors. In particular, we introduce the knapsack problem for perishable items, which concerns the optimal dynamic allocation of a limited knapsack to a collection of perishable or non-perishable items. We formulate the problem in the framework of Markov decision processes, we relax and decompose it, and we design a novel index-knapsack heuristic which generalizes the index rule and it is optimal in some specific instances. Such a heuristic bridges the gap between static/deterministic optimization and dynamic/stochastic optimization by stressing the connection between the classic knapsack problem and dynamic resource allocation. The performance of the proposed heuristic is evaluated in a systematic computational study, showing an exceptional near-optimality and a significant superiority over the index rule and over the benchmark earlier-deadline-first policy. Finally we extend our results to several related revenue management problems.

Description: Given a graph G ( N , A ) with a cost (or benefit) and a delay on each arc, the constrained routing problem (CRP) aims to find a minimum-cost or a maximum-benefit path from a given source to a given destination node, subject to an end-to-end delay constraint. The problem (with a single constraint) is NP-hard, and has been studied by many researchers who found fully polynomial approximation schemes (FPAS) for this problem. The current paper focuses on a generalized CRP version, CRP with hop-wise constraints (CRPH). In the generalized version, instead of one constraint there are up to n −1 special-type constraints, where n is the number of nodes. An FPAS based on interval partitioning is proposed for both the minimization and the maximization versions of CRPH. For G ( N , A ) with n nodes and m arcs, the complexity of the algorithm is O( mn 2 / ε ).

Description: In this paper, we study the crane scheduling problem for a vessel after the vessel is moored on a terminal and develop both exact and heuristic solution approaches for the problem. For small-sized instances, we develop a time-space network flow formulation with non-crossing constraints for the problem and apply an exact solution approach to obtain an optimal solution. For medium-sized instances, we develop a Lagrangian relaxation approach that allows us to obtain tight lower bounds and near-optimal solutions. For large-sized instances, we develop two heuristics and show that the error bounds of our heuristics are no more than 100%. Finally, we perform computational studies to show the effectiveness of our proposed solution approaches.

Description: We study a multi-echelon joint inventory-location model that simultaneously determines the location of warehouses and inventory policies at the warehouses and retailers. The model is formulated as a nonlinear mixed-integer program, and is solved using a Lagrangian relaxation-based approach. The efficiency of the algorithm and benefits of integration are evaluated through a computational study.

Description: This paper develops an optimization modeling approach for analyzing the trade-off between the cost of a larger fleet of tractors and the cost of repositioning tractors for a trucking company operating a consolidation network, such as a less-than-truckload (LTL) company. Specifically, we analyze the value of using extra tractor repositioning moves (in addition to the ones required to balance resources throughout the network) to reduce the fixed costs of owning or leasing a tractor fleet during a planning horizon. We develop network flow optimization models, some with side constraints and nonlinear objective functions, using event-based, time-expanded networks to determine appropriate fleet sizes and extra repositioning moves under different repositioning strategies, and we compare the optimal costs of the strategies. For repositioning costs, two different cost schemes are explored: one linear and one nonlinear. Computational experiments using real data from a national LTL carrier compare the total system costs obtained with four different strategies and show that extra repositioning may indeed enable fleet size reductions and concomitant cost savings.

Description: We constructed a decision-support-system (DSS) to help the distribution network of Pfizer plan the daily deployment of finished goods inventory across its network. Utilizing databases, programming languages, spreadsheets and data inputs from the firm’s ERP; this system guides daily shipments of critical inventory between plants, distribution centers and copackers. This DSS improved the firm’s ability to effectively utilize its storage capacity and meet customer shipping requirements across a widely dispersed network.

Description: The Local Pickup and Delivery Problem (LPDP) has drawn much attention, and optimization models and algorithms have been developed to address this problem. However, for real world applications, the large-scale and dynamic nature of the problem causes difficulties in getting good solutions within acceptable time through standard optimization approaches. Meanwhile, actual dispatching solutions made by field experts in transportation companies contain embedded dispatching rules. This paper introduces a Data Mining-based Dispatching System (DMDS) to first learn dispatching rules from historical data and then generate dispatch solutions, which are shown to be as good as those generated by expert dispatchers in the intermodal freight industry. Three additional benefits of DMDS are: (1) it provides a simulation platform for strategic decision making and analysis; (2) the learned dispatching rules are valuable to combine with an optimization algorithm to improve the solution quality for LPDPs; (3) by adding optimized solutions to the training data, DMDS is capable to generate better-than-actuals solutions very quickly.

Description: This paper introduces a new model and solution methodology for a real-world production scheduling problem arising in the electronics industry. The production environment is a high volume, just-in-time, make-to-order facility with volatile demand over many product families that are assembled on flexible lines. A distinguishing characteristic of the problem is the presence of non-traditional sequence-dependant setup costs, which complicate our ability to find high-quality solutions. The scheduling problem arose when product variety exceeded the mix that the existing lines could accommodate. A nonlinear integer programming formulation is presented for the problem of minimizing setup costs, and a greedy randomized adaptive search procedure (GRASP) is developed to find solutions. To select the GRASP parameter values, an efficient, space-filling experimental design method is used based on nearly orthogonal Latin hypercubes. The proposed methodology is tested on actual factory data and compared to a prior heuristic presented in the literature; our heuristic provides a cost savings in 7 out of the 10 cases examined, and an average improvement of 17.39 % which is shown to be highly statistically significant. This improvement is due in part to the introduction of a pre-processing step to determine preferential and non-preferential line assignment information.

Description: We consider the problem faced by managers of critical civil interdependent infrastructure systems of restoring essential public services after a non-routine event causes disruptions to these services. In order to restore the services, we must determine the set of components (or tasks) that will be temporarily installed or repaired, assign these tasks to work groups, and then determine the schedule of each work group to complete the tasks assigned to it. These restoration planning and scheduling decisions are often undertaken in an independent, sequential manner. We provide mathematical models and optimization algorithms that integrate the restoration and planning decisions and specifically account for the interdependencies between the infrastructure systems. The objective function of this problem provides a measure of how well the services are being restored over the horizon of the restoration plan, rather than just focusing on the performance of the systems after all restoration efforts are complete. We test our methods on realistic data representing infrastructure systems in New York City. Our computational results demonstrate that we can provide integrated restoration and scheduling plans of high quality with limited computational resources. We also discuss the benefits of integrating the restoration and scheduling decisions.

Description: The stacking problem is a hard combinatorial optimization problem with high practical interest in, for example, steel storage or container port operations. In this problem, a set of items is stored in a warehouse for a period of time, and a crane is used to place them in a limited number of stacks. Since the entrance and exit of items occurs in an arbitrary order, items may have to be relocated in order to reach and deliver other items below them. The objective of the problem is to find a feasible sequence of movements that delivers all items, while minimizing the total number of movements. We study the scalability of an exact approach to this problem, and propose two heuristic methods to solve it approximately. The two heuristic approaches are a multiple simulation algorithm using semi-greedy construction heuristics, and a stochastic best-first tree search algorithm. The two methods are compared in a set of challenging instances, revealing a superior performance of the tree search approach in most cases.

Description: We consider a replenishment and disposal planning problem (RDPP) that arises in settings where customer returns are in as-good-as-new condition. These returns can be placed into inventory to satisfy future demand or can be disposed of, in case they lead to excess inventory. Our focus is on a multi-product setting with dynamic demands and returns over a finite planning horizon with explicit replenishment and disposal capacities. The problem is to determine the timing of replenishment and disposal setups, along with the associated quantities for the products, so as to minimize the total costs of replenishment, disposal, and inventory holding throughout the planning horizon. We examine two variants of the RDPP of interest both of which are specifically motivated by a spare part kitting application. In one variant, the replenishment capacity is shared among multiple products while the disposal capacity is product specific. In the other variant, both the replenishment and disposal capacities are shared among the products. We propose a Lagrangian Relaxation approach that relies on the relaxation of the capacity constraints and develop a smoothing heuristic that uses the solution of the Lagrangian problem to obtain near-optimal solutions. Our computational results demonstrate that the proposed approach is very effective in obtaining high-quality solutions with a reasonable computational effort.

Description: This paper proposes mathematical programming models with probabilistic constraints in order to address incident response and resource allocation problems for the planning of traffic incident management operations. For the incident response planning, we use the concept of quality of service during a potential incident to give the decision-maker the flexibility to determine the optimal policy in response to various possible situations. An integer programming model with probabilistic constraints is also proposed to address the incident response problem with stochastic resource requirements at the sites of incidents. For the resource allocation planning, we introduce a mathematical model to determine the number of service vehicles allocated to each depot to meet the resource requirements of the incidents by taking into account the stochastic nature of the resource requirement and incident occurrence probabilities. A detailed case study for the incident resource allocation problem is included to demonstrate the use of proposed model in a real-world context. The paper concludes with a summary of results and recommendations for future research.

Description: This paper considers a new class of stochastic resource allocation problems that requires simultaneously determining the customers that a capacitated resource must serve and the stock levels of multiple items that may be used in meeting these customers’ demands. Our model considers a reward (revenue) for serving each assigned customer, a variable cost for allocating each item to the resource, and a shortage cost for each unit of unsatisfied customer demand in a single-period context. The model maximizes the expected profit resulting from the assignment of customers and items to the resource while obeying the resource capacity constraint. We provide an exact solution method for this mixed integer nonlinear optimization problem using a Generalized Benders Decomposition approach. This decomposition approach uses Lagrangian relaxation to solve a constrained multi-item newsvendor subproblem and uses CPLEX to solve a mixed-integer linear master problem. We generate Benders cuts for the master problem by obtaining a series of subgradients of the subproblem’s convex objective function. In addition, we present a family of heuristic solution approaches and compare our methods with several MINLP (Mixed-Integer Nonlinear Programming) commercial solvers in order to benchmark their efficiency and quality.

Description: This paper presents a Hybrid Evolutionary Algorithm (HEA) to solve the Job Shop Scheduling Problem (JSP). Incorporating a tabu search procedure into the framework of an evolutionary algorithm, the HEA embraces several distinguishing features such as a longest common sequence based recombination operator and a similarity-and-quality based replacement criterion for population updating. The HEA is able to easily generate the best-known solutions for 90 % of the tested difficult instances widely used in the literature, demonstrating its efficacy in terms of both solution quality and computational efficiency. In particular, the HEA identifies a better upper bound for two of these difficult instances.

Description: This paper is the organizers’ report on the Third International Timetabling Competition (ITC2011), run during 2011–2012 with the aim of raising the profile of automated high school timetabling. Its participants tackled 35 instances of the high school timetabling problem, taken from schools in 10 countries. The paper describes the data model used, the competition, and the results.

Description: Liquefied natural gas (LNG) is natural gas that has been transformed to liquid form for the purpose of transportation, which is mainly done by specially built LNG vessels travelling from the production site to the consumers. We describe a real-life ship routing and scheduling problem from the LNG business, with both inventory and berth capacity constraints at the liquefaction port. We propose a solution method where the routing and scheduling decisions are decomposed. The routing decisions consist of deciding which vessels should service which cargoes and in what sequence. The scheduling decisions are then to decide when to start servicing the cargoes while satisfying inventory and berth capacity constraints. The proposed solution method has been tested on several problem instances based on the real-life problem. The results show that the proposed solution method is well suited to solve this LNG shipping problem.

Description: In this paper, we consider the problem of reconfiguring a section of the national airspace into appropriate sectors from the viewpoint of balancing the predicted air traffic controller workload. The given section of the airspace is specified as a convex polygon in two-dimensions (or a union of such structures), and contains a discretized set of weighted grid points representing localized sub-regions, where the weights reflect the associated air traffic controller monitoring and conflict resolution workloads. We describe four variants of a mixed-integer programming-based algorithmic approach to recursively partition the specified airspace region so as to balance the total weight distribution within each resulting sector. In addition, we augment the proposed model to further accommodate inter-sector coordination workload within this partitioning process, which accounts for the number of flight hand-offs between adjacent sectors. Some illustrative examples are presented to assess the proposed methodology and to investigate the relative computational efficiency and the quality of solutions produced by each algorithmic variant. One competitive procedure is then used to configure a region of airspace over the U.S. using realistic flight data. The main purpose of this work is to provide some modeling concepts and insights to complement the rich body of existing literature on this topic.

Description: Most technology companies are experiencing highly volatile markets with increasingly short product life cycles due to rapid technological innovation and market competition. Current supply-demand planning systems remain ineffective in capturing short life-cycle nature of the products and high volatility in the markets. In this study, we propose an alternative demand-characterization approach that models life-cycle demand projections and incorporates advanced demand signals from leading-indicator products through a Bayesian update. The proposed approach describes life-cycle demand in scenarios and provides a means to reducing the variability in demand scenarios via leading-indicator products. Computational testing on real-world data sets from three semiconductor manufacturing companies suggests that the proposed approach is effective in capturing the life-cycle patterns of the products and the early demand signals and is capable of reducing the uncertainty in the demand forecasts by more than 20%.

Description: The design of the underlying supply chain network can have a tremendous impact on the profitability, manageability, and level of risk of a global supply chain. Taxes, duties, and tariffs vary from country to country as well as trading bloc to trading bloc and can consume as much as 10% of the revenues of certain products. In the highly regulated business environment of agricultural chemicals, the country of origin of an active ingredient can determine where the final product can be marketed and the amount of taxes and duties applied to the product, making it necessary to trace all batches of product through many layers of the supply chain to their sources. This article presents a mixed integer linear programming model in use at Dow AgroSciences LLC that simultaneously optimizes the network design underlying global supply chains and the monthly production and shipping schedules for maximum profitability. This work contributes to the supply chain design literature by demonstrating a novel method of tracing products to their source for inventory valuation, taxation, and duty computation in a production environment where the products change into other products as they pass through nodes in the network. It also demonstrates an iterative scheme for determining unit fixed costs for fixed cost allocation for the same purposes. Finally, it provides a case study of a supply chain design initiative in a global enterprise.

Description: In this paper we consider the problem in which crude oil is shipped from platforms to terminals using oil tankers at minimum transportation cost. This subproblem, which arises in petroleum supply chain models, can be surprisingly expensive to solve with a straightforward formulation involving inventory balances. We present a reformulation that has a special structure defined in this paper as Cascading Knapsack Inequalities. This is used as the basis for deriving tight reformulations for special cases with a limited number of classes of tankers. Numerical results are presented to demonstrate that significant computational savings can be accomplished with the proposed reformulations.

Description: In many planning problems under uncertainty the uncertainties are decision-dependent and resolve gradually depending on the decisions made. In this paper, we address a generic non-convex MINLP model for such planning problems where the uncertain parameters are assumed to follow discrete distributions and the decisions are made on a discrete time horizon. In order to account for the decision-dependent uncertainties and gradual uncertainty resolution, we propose a multistage stochastic programming model in which the non-anticipativity constraints in the model are not prespecified but change as a function of the decisions made. Furthermore, planning problems consist of several scenario subproblems where each subproblem is modeled as a nonconvex mixed-integer nonlinear program. We propose a solution strategy that combines global optimization and outer-approximation in order to optimize the planning decisions. We apply this generic problem structure and the proposed solution algorithm to several planning problems to illustrate the efficiency of the proposed method with respect to the method that uses only global optimization.

Description: This paper surveys recent applications and advances of the Constraint Programming-based Column Generation framework, where the master subproblem is solved by traditional OR techniques, while the pricing subproblem is solved by Constraint Programming. This framework has been introduced to solve crew assignment problems, where complex regulations make the pricing subproblem demanding for traditional techniques, and then it has been applied to other contexts. The main benefits of using Constraint Programming are the expressiveness of its modeling language and the flexibility of its solvers. Recently, the Constraint Programming-based Column Generation framework has been applied to many other problems, ranging from classical combinatorial problems such as graph coloring and two dimensional bin packing, to application oriented problems, such as airline planning and resource allocation in wireless ad-hoc networks.

Description: We consider a problem where different classes of customers can book different types of services in advance and the service company has to respond immediately to the booking request confirming or rejecting it. Due to the possibility of cancellations before the day of service, or no-shows at the day of service, overbooking the given capacity is a viable decision. The objective of the service company is to maximize profit made of class-type specific revenues, refunds for cancellations or no-shows as well as the cost of overtime. For the calculation of the latter, information of the underlying appointment schedule is required. Throughout the paper we will relate the problem to capacity allocation in radiology services. Drawing upon ideas from revenue management, overbooking, and appointment scheduling we model the problem as a Markov decision process in discrete time which due to proper aggregation can be optimally solved with an iterative stochastic dynamic programming approach. In an experimental study we successfully apply the approach to a real world problem with data from the radiology department of a hospital. Furthermore, we compare the optimal policy to four heuristic policies, of whom one is currently in use. We can show that the optimal policy significantly improves the currently used policy and that a nested booking limit type policy closely approximates the optimal policy and is thus recommended for use in practice.

Description: Stochastic models for phenomena that can exhibit sudden changes involve the use of processes whose sample functions may have discontinuities. This paper provides some tools for working with such processes. We develop a sample path formula for the cumulative jump height over a given time interval. From this formula an expression for the expected value of the cumulative jump random variable is developed under reasonable conditions. The results are applied to finding the expected number of failures in the separate maintenance model over a stated time interval and to the expected number of occurrences of a regenerative event over a stated time interval.

Description: We propose an iterative gradient descent algorithm for solving scenario-based Mean-CVaR portfolio selection problem. The algorithm is fast and does not require any LP solver. It also has efficiency advantage over the LP approach for large scenario size.

Description: A queueing model consisting of two multi-server service systems is considered. Primary customers arrive at a multi-server queueing system-1 having an infinite buffer. The input flow is described by a MAP (Markovian Arrival Process). The service time of a primary customer has a PH (Phase-type) distribution. Besides the primary customers, a MAP of interruptions arrives to the system. An interruption removes one of the primary customers from the service if the state (phase) of its PH service process does not belong to some given set of so called protected phases when an interruption is successful. The interrupted customer leaves the system permanently with some probability. With complementary probability, the interrupted primary customer moves for service to system-2. This system consists of K independent identical servers and has no buffer. If all K servers are busy at the moment of a primary customer interruption, this customer will be lost. Otherwise, this primary customer starts the service in an arbitrary idle server of system-2. It is assumed that the service time of a primary customer by a server of system-2 has a PH distribution. Upon completion of the service at system-2, the customer becomes priority customer. If, at the service completion moment, there are free servers at system-1, the priority customer immediately starts getting the service at system-1. It is assumed that the service time of a priority customer by a server of system-1 has a PH distribution and this service can not be interrupted. If, at the moment when the primary customer finished the service at system-2, there are no idle servers at system-1, this customer is placed into the finite buffer for priority customers of capacity K . The customers will be picked up for the service according to the FIFO discipline. When a server of system-1 becomes free, it takes for service a priority customer from this buffer, if any. Type-1 customers are picked-up from the infinite buffer only if the buffer for priority customers is empty at the service completion moment at system-1. Behavior of this system is described by a multi-dimensional Markov chain. Algorithms for checking ergodicity condition and computing the stationary distribution are presented. Formulas for computing important performance measures of the system are derived.

Description: The generalization of classical results about convex sets in ℝ n to abstract convexity spaces, defined by sets of paths in graphs, leads to many challenging structural and algorithmic problems. Here we study the Radon number for the P 3 -convexity on graphs. P 3 -convexity has been proposed in connection with rumour and disease spreading processes in networks and the Radon number allows generalizations of Radon’s classical convexity result. We establish hardness results and describe efficient algorithms for trees.

Description: This paper presents a new hybrid evolutionary algorithm to solve multi-objective multicast routing problems in telecommunication networks. The algorithm combines simulated annealing based strategies and a genetic local search, aiming at a more flexible and effective exploration and exploitation in the search space of the complex problem to find more non-dominated solutions in the Pareto Front. Due to the complex structure of the multicast tree, crossover and mutation operators have been specifically devised concerning the features and constraints in the problem. A new adaptive mutation probability based on simulated annealing is proposed in the hybrid algorithm to adaptively adjust the mutation rate according to the fitness of the new solution against the average quality of the current population during the evolution procedure. Two simulated annealing based search direction tuning strategies are applied to improve the efficiency and effectiveness of the hybrid evolutionary algorithm. Simulations have been carried out on some benchmark multi-objective multicast routing instances and a large amount of random networks with five real world objectives including cost, delay, link utilisations, average delay and delay variation in telecommunication networks. Experimental results demonstrate that both the simulated annealing based strategies and the genetic local search within the proposed multi-objective algorithm, compared with other multi-objective evolutionary algorithms, can efficiently identify high quality non-dominated solution set for multi-objective multicast routing problems and outperform other conventional multi-objective evolutionary algorithms in the literature.

Description: Although there has been a fair amount of research in the area of school timetabling, this domain has not developed as well as other fields of educational timetabling such as university course and examination timetabling. This can possibly be attributed to the fact that the studies in this domain have generally been conducted in isolation of each other and have addressed different school timetabling problems. Furthermore, there have been no comparative studies on the success of different methodologies on a variety of school timetabling problems. As a way forward this paper provides an overview of the research conducted in this domain, details of problem sets which are publicly available and proposes areas for further research in school timetabling.

Description: We study a variant of the stochastic economic lot scheduling problem (SELSP) encountered in process industries, in which a single production facility must produce several different grades of a family of products to meet random stationary demand for each grade from a common finished-goods (FG) inventory buffer that has limited storage capacity. When the facility is set up to produce a particular grade, the only allowable changeovers are from that grade to the next lower or higher grade. Raw material is always available, and the production facility produces continuously at a constant rate even during changeover transitions. All changeover times are constant and equal to each other, and demand that cannot be satisfied directly from inventory is lost. There is a changeover cost per changeover occasion, a spill-over cost per unit of product in excess whenever there is not enough space in the FG buffer to store the produced grade, and a lost-sales cost per unit short whenever there is not enough FG inventory to satisfy the demand. We model the SELSP as a discrete-time Markov decision process (MDP), where in each time period the decision is whether to initiate a changeover to a neighboring grade or keep the set up of the production facility unchanged, based on the current state of the system, which is defined by the current set up of the facility and the FG inventory levels of all the grades. The goal is to minimize the (long-run) expected average cost per period. For problems with more than three grades, we develop a heuristic solution procedure which is based on decomposing the original multi-grade problem into several 3-grade MDP sub-problems, numerically solving each sub-problem using value iteration, and constructing the final policy for the original problem by combining parts of the optimal policies of the sub-problems. We present numerical results for problem examples with 2–5 grades. For the 2- and 3-grade examples, we numerically solve the exact MDP problem using value iteration to obtain insights into the structure of the optimal changeover policy. For the 4- and 5-grade examples, we compare the performance of the decomposition-based heuristic (DBH) solution procedure against that obtained by numerically solving the exact problem. We also compare the performance of the DBH method against the performance of three simpler parameterized heuristics. Finally, we compare the performance of the DBH and the exact solution procedures for the case where the FG inventory storage consists of a number of separate general-purpose silos capable of storing any grade as long as it is not mixed with any other grade.

Description: Evaluating the level of inconsistency of pairwise comparisons is often a crucial step in multi criteria decision analysis. Several inconsistency indices have been proposed in the literature to estimate the deviation of expert’s judgments from a situation of full consistency. This paper surveys and analyzes ten indices from the numerical point of view. Specifically, we investigate degrees of agreement between them to check how similar they are. Results show a wide range of behaviors, ranging from very strong to very weak degrees of agreement.

Description: We propose and analyze a new type of values for cooperative TU-games, which we call pyramidal values . Assuming that the grand coalition is sequentially formed, and all orderings are equally likely, we define a pyramidal value to be any expected payoff in which the entrant player receives a salary, and the rest of his marginal contribution to the just formed coalition is distributed among the incumbent players. We relate the pyramidal-type sharing scheme we propose with other sharing schemes, and we also obtain some known values by means of this kind of pyramidal procedures. In particular, we show that the Shapley value can be obtained by means of an interesting pyramidal procedure that distributes nonzero dividends among the incumbents. As a result, we obtain an alternative formulation of the Shapley value based on a measure of complementarity between two players. Finally, we introduce the family of proportional pyramidal values, in which an incumbent receives a dividend in proportion to his initial investment, measured by means of his marginal contribution.

Description: This paper studies the problem of how to effectively provide product service system (PSS) in a service-oriented manufacturing supply chain under asymmetric private demand information. The PSS in the supply chain is operated heterogeneously and complementarily, in which the manufacturer provides the product while the retailer who possesses private demand information is responsible for adding the necessary value-added service on the basic product. We address the issue of how different contracts affect the decisions and profitability of the supply chain members. Three types of contracts are developed to help supply chain partners to make decisions and enhance the supply chain’s efficiency. The first is the franchise fee (FF) contract, under which the manufacturer provides a two-part tariff contract (wholesale price and franchise fee) to influence the retailer’s decision and to detect her private demand information. The second is the franchise fee with service requirement (FFS) contract, under which the manufacturer specifies the service level required in addition to the two-part tariff contract terms. The third is the franchise fee with centralized service requirement (FFCS) contract, which is similar to the FFS contract but that the service level specified by the manufacturer is the system optimal solution. Our analytical results show that all three contracts enable the manufacturer to detect the retailer’s private demand information, with the FFCS contract achieving the greatest channel profit. Finally, numerical examples are presented, and sensitivity analysis of service level and profit are conducted to compare the performance of the three contracts under different settings. The paper provides managerial guidelines for the manufacturer in contract offering under different conditions.

Description: The paper deals with analytical modeling of transfer lines consisting of two machines decoupled by one finite buffer. In particular, the case in which a control policy (referred as “restart policy”) aiming to reduce the blocking frequency of the first machine is addressed. Such a policy consists of forcing the first machine to remain idle (it cannot process parts) each time the buffer gets full until it empties again. This specific behavior can be found in a number of industrial production systems, especially when some machines are affected by outage costs when stops occur. The two-machine one-buffer line is here modeled as a discrete time Markov process and the two machines are characterized by the same operation time. The analytical solution of the model is obtained and mathematical expressions of the most important performance measures are provided. Some significant remarks about the effect of the proposed restart policy on the behavior of the system are also pointed out.

Description: We present two stochastic failure models for the reliability evaluation of manufacturing equipment that degrades due to its complex operating environment. The first model examines the case when the environment is a temporally nonhomogeneous continuous-time Markov chain, and the second assumes the environment is a temporally homogeneous semi-Markov process on a finite space. Derived are transform expressions for the lifetime distributions. A few examples are provided to illustrate the main results.

Description: Multi-product manufacturing systems operating under CONWIP control are often modeled as closed queuing networks with synchronization stations. Performance analysis of these systems can be challenging, especially when batch size constraints are explicitly considered. This research develops a new approach for evaluating the performance of these systems based on parametric characterizations and traffic process approximations. The approach explicitly models the effect of batch size constraints on the departure process and waiting times at the different stations in the network to derive new characterization equations. These equations are used to derive a set of linking equations that is solved using an iterative algorithm to obtain estimates of network performance. Numerical studies indicate that the proposed method is yields fairly accurate performance estimates and can be useful in evaluating tradeoffs that guide managerial decisions.

Description: In this paper, a decomposition method for evaluating the performance of continuous flow lines with machines characterized by general Markovian fluid models and finite capacity buffers is proposed. This study uses the exact solution of general two-stage Markovian fluid models as a building block. Decomposition equations are provided to propagate the effect of partial and complete blocking and starvation phenomena throughout the system. A decomposition algorithm that solves the new decomposition equations is proposed. Numerical results prove the good accuracy of the developed method. In particular, a comparison with existing techniques shows that our method is generally more accurate, especially in the estimation of the average buffer levels. Moreover, additional information can be collected by the application of our approach which enables a deeper analysis of the system behavior. Finally, the generality of the approach allows for modeling and studying many different system configurations within a unique framework, also including several previously uninvestigated layouts.

Description: We consider problems of inventory and admission control for make-to-stock production systems with perishable inventory and impatient customers. Customers may balk upon arrival (refuse to place orders) and renege while waiting (withdraw delayed orders) during stockouts. Item lifetimes and customer patience times are random variables with general distributions. Processing, setup, and customer inter-arrival times are however assumed to be exponential random variables. In particular, the paper studies two models. In the first model, the system suspends its production when its stock reaches a safety level and can resume later without incurring any setup delay or cost. In the second model, the system incurs setup delays and setup costs; during stockouts, all arriving customers are informed about anticipated delays and either balk or place their orders but cannot withdraw them later. Using results from the queueing literature, we derive expressions for the system steady-state probabilities and performance measures, such as profit from sales and costs of inventory, setups, and delays in filling customer orders. We use these expressions to find optimal inventory and admission policies, and investigate the impact of product lifetimes and customer patience times on system performance.

Description: In this paper, we study a make-to-order production system with parallel, identical processing units. Each order needs to be satisfied on a single processing unit that is run by a crew. The inter-arrival time and the service time for each order are random variables. The system operates under a lead time performance constraint, which demands the completion of each order within a pre-determined lead time with a certain probability. The minimum number of processing units needed to satisfy this constraint is determined at the tactical level. Our research focuses on the cost savings that can be realized with the use of flexible crews via contractual hiring agreements with an External Labor Supply Agency (ELSA). The ELSA can periodically provide an agreed number of crews. The cost incurred for a flexible crew is higher than that for a permanent crew, and is decreasing in the period length. We model and analyze this system using the transient behavior analysis of multi-server queues and propose several empirically testable functions for the cost of flexible crews. In our computational study, we demonstrate possible cost savings of 2-level, threshold type hiring policies, relative to the fixed capacity system, under 9 scenarios with three demand-to-processing rate ratios and three lead time performance constraints, each of which reflects a different level of ambition. We observe that the maximum savings occur when the cost of a flexible crew is same as that of a permanent crew, and range from 29.38% to 50.56%. However, as the flexible crews become more expensive, the system may choose to employ permanent crews only. We observe that cost savings consist of two parts: savings due to the cancellation of the sclerosis of capacity discreteness, and savings due to the use of workload information in hiring actions. The latter part is higher for more ambitious lead time performance constraints, and for higher mean processing times. Finally, when there is an additional cost for transacting an agreement with the ELSA, we observe that the capacity flexibility option loses its charm, especially if the transaction cost is higher than the cost of a permanent crew.

Description: Pull systems are inherently easier to implement on the shop-floor; however, they are quite difficult to plan and design for optimal operation, leaving little guidelines to system designers and practitioners. In this paper we use an effective and relatively fast numerical method to understand the optimal configuration of a multi-stage, multi-product, decentralized, market-driven production/inventory system that minimizes average inventory holding subject to a service level constraint through selection of various production and procurement control parameters. We have also conducted a number of numerical experiments to understand how the control policies respond to changes in the system parameters, such as the number of stages, system workload, demand arrival rates of products, and inventory holding costs.

Description: In this paper, we study single-server tandem queues with general service times and finite buffers. Jobs are served according to the Blocking-After-Service protocol. To approximately determine the throughput and mean sojourn time, we decompose the tandem queue into single-buffer subsystems, the service times of which include starvation and blocking, and then we iteratively estimate the unknown parameters of the service times of each subsystem. The crucial feature of this approach is that in each subsystem successive service times are no longer assumed to be independent, but a successful attempt is made to include dependencies due to blocking by employing the concept of Markovian Arrival Processes. An extensive numerical study shows that this approach produces very accurate estimates for the throughput and mean sojourn time, outperforming existing methods, especially for longer tandem queues and for tandem queues with service times with a high variability.

Description: Quality risks determined by inspection economies represent a difficult controllable variable in complex manufacturing environments. Planning a quality strategy without being able to predict its effectiveness in all the stations of a system might eventually lead to a loss of time, money and resources. The use of one station to regularly select the samples for a production segment introduces relevant complexities in the analysis of the available quality measurements when they are referred to the other stations in that segment. The multiple streams of product through the parallel machines of the stations and the cycle time randomness, responsible for variation of the item sequence order at each production step, nullify the regularity of the sampling patterns at the machines of the non-sampling stations. This work develops a fundamental model which supports the prediction of the ‘quality risk’, at a given machine in the non-sampling stations, associated with a particular sampling policy for a multi-product, multi-stage, parallel processing manufacturing system subjected to sequence disorder and multiple stream effects. The rationale on which the model is based and successful applications of the model, to scenarios structurally different from those used for its development, give confidence in the general validity of the model here proposed for the quality risk prediction at non-sampling station machines.

Description: For production planning problems, cost parameters can be uncertain due to marketing activities and interest rate fluctuation. In this paper, we consider a single-item two-stage stochastic lot-sizing problem under cost parameter uncertainty. Assuming cost parameters will increase or decrease after time period p each with certain probability, we minimize the total expected cost for a finite horizon problem. We develop an extended linear programming formulation in a higher dimensional space that can provide integral solutions by showing that its constraint matrix is totally unimodular. We also project this extended formulation to a lower dimensional space and obtain a corresponding extended formulation in the lower dimensional space. Final computational experiments demonstrate that the extended formulation is more efficient and performs more stable than the two-stage stochastic mixed-integer programming formulation.

Description: We introduce a new operator for general rationing problems in which, besides conflicting claims, individual baselines play an important role in the rationing process. The operator builds onto ideas of composition, which are not only frequent in rationing, but also in related problems such as bargaining, choice, and queuing. We characterize the operator and show how it preserves some standard axioms in the literature on rationing. We also relate it to recent contributions in such literature.

Description: Companies that operate a commodity delivery service, lumber for instance, often own trucks to ship from a warehouse to their customers. One of these companies may consider purchasing new trucks to reduce operation costs, when operating new trucks is cheaper than operating old ones. That is, a company can save on future operational expenditures at the cost of purchasing new trucks. Once new trucks have been bought, the fleet consists of two sub-fleets: the subfleet of new and the subfleet of old trucks. The cheaper operation [currency units/min] of new trucks makes them preferable to old trucks. Thus, old trucks start servicing orders only when all new trucks are busy. For a given time horizon, the optimal cost of the project is a trade-off between the times serviced with old trucks, new trucks, and the cost of the new trucks to be purchased. This article puts forward a method to determine the number of new trucks to purchase that maximizes the expected present value of the project that applies to full payload deliveries. It uses historical information on hour-specific expected intensities of delivery requests and delivery services. Our approach can incorporate restrictions preventing deliveries to specific customers during certain time windows.

Description: The optimization of stochastic Discrete Event Systems (DESs) is a critical and difficult task. The search for the optimal system configuration ( optimization problem ) requires the assessment of the system performance ( simulation problem ), resulting in a simulation–optimization problem. In the past ten years, a noticeable research effort has been devoted to this area. Recently, mathematical programming has been proposed to integrate simulation and optimization for multi-stage open queueing networks. This paper proposes the application of this approach to closed queueing networks. In particular, the optimal pallet allocation problem is tackled through linear mathematical programming models for simulation–optimization.

Description: An insurance model, with realistic assumptions about coverage, deductible and premium, is studied. Insurance is shown to decrease the variance of the cost to the insured, but increase the expected cost, a tradeoff that places our model in the Markowitz mean-variance model.

Description: Machine learning exists in many realistic scheduling situations. This study focuses on permutation flow shop scheduling problems, where the actual processing time of a job is defined by a general non-increasing function of its scheduled position, i.e., general position-dependent learning effects. The objective functions are to minimize the total completion time, the makespan, the total weighted completion time, and the total weighted discounted completion time, respectively. To solve these problems, we present approximation algorithms based on the optimal permutations for the corresponding single machine scheduling problems and analyze their worst-case error bound.

Description: An intuitionistic fuzzy economic order quantity (EOQ) inventory model with backlogging is investigated using the score functions for the member and non-membership functions. The demand rate is varying with selling price and promotional effort (PE). A crisp model is formulated first. Then, intuitionistic fuzzy set and score function (or net membership function) are applied in the proposed model, considering selling price and PE as fuzzy numbers. To obtain the best inventory policy, ranking index method has been adopted, showing that the score function can maintain the ranking rule also. Moreover, optimization is made under the general fuzzy optimal (GFO) and intuitionistic fuzzy optimal (IFO) policy. Finally, a graphical illustration, numerical examples with sensitivity analysis and conclusion is made to justify the model.

Description: The present paper studies patient-to-room assignment planning in a dynamic context. To this end, an extension of the patient assignment (PA) problem formulation is proposed, for which two online ILP-models are developed. The first model targets the optimal assignment for newly arrived patients, whereas the second also considers future, but planned, arrivals. Both models are compared on an existing set of benchmark instances from the PA planning problem, which serves as the basic problem setting. These instances are then extended with additional parameters to study the effect of uncertainty on the patients’ length of stay, as well as the effect of the percentage of emergency patients. The results show that the second model provides better results under all conditions, while still being computationally tractable. Moreover, the results show that pro-actively transferring patients from one room to another is not necessarily beneficial.

Description: VoIP (“Voice Over Internet Protocol”) is the transmission of voice communication through the Internet via IP-based telephony networks. VoIP has become very popular over recent years due to the cost advantages for consumers and businesses compared to the traditional telephony networks. Since it is deployed on packet-based networks, one of the major Quality of Service (QoS) concerns of VoIP technology is the average end-to-end connection delay. The objective of this paper is to present a queuing model for obtaining the end-to-end delay of a VoIP connection. The paper first describes all the partial delay components, and their mathematical formulations. Subsequently, based on all the partial delay components, a queuing model for the end-to-end delay of a VoIP connection is presented. The proposed queueing model is analyzed using a generalized stochastic Petri net (GSPN) model. From the GSPN model, we obtain numerical results for the end-to-end delay, which are presented graphically. The results are in accordance with the expected behavior of delay in a VoIP network.

Description: In matrix theory, Fu and Markham showed using majorization technique that if a Hermitian matrix satisfies certain conditions, then the matrix must be block-diagonal. In this paper, we extend this result to the setting of simple Euclidean Jordan algebras by using the Cauchy interlacing theorem and the Schur complement Cauchy interlacing theorem.

Description: This paper sets out the development of a methodological framework for detailed evaluation of public health strategies for alcohol harm reduction to meet UK policy-makers needs. Alcohol is known to cause substantial harms, and controlling its affordability and availability are effective policy options. Analysis and synthesis of a variety of public and commercial data sources is needed to evaluate impact on consumers, health services, crime, employers and industry, so a sound evaluation of impact is important. We discuss the iterative process to engage with stakeholders, identify evidence/data and develop analytic approaches and produce a final model structure. We set out a series of steps in modelling impact including: classification and definition of population subgroups of interest, identification and definition of harms and outcomes for inclusion, classification of modifiable components of risk and their baseline values, specification of the baseline position on policy variables especially prices, estimating effects of changing policy variables on risk factors including price elasticities, quantifying risk functions relating risk factors to harms including 47 health conditions, crimes, absenteeism and unemployment, and monetary valuation. The most difficult model structuring decisions are described, as well as the final results framework used to provide decision support to national level policymakers in the UK. In the discussion we explore issues around the relationship between modelling and policy debates, valuation and scope, limitations of evidence/data, how the framework can be adapted to other countries and decisions. We reflect on the approach taken and outline ongoing plans for further development.

Description: This article presents two case studies, concerning the allocation of £Billions by a mechanism communicated via spreadsheet models. It argues that technical analytic skills as well as policy development skills are a vital component of governance. In the UK, Central Government uses funding formulae to distribute money to local service providers. One commonly stated goal of such formulae is equity of service provision. However, given the complexity of public services, together with variations in need, delivery style and the exercise of stakeholder judgement as to which needs should be met and how, such formulae frequently obscure the process by which equity has been taken into account. One policy ‘solution’ to managing such tensions is to seek ‘transparency’. With respect to funding formulae, this commonly involves publishing the underlying data and formulae in spreadsheets. This paper extends the argument that such ‘transparency’ requires an audience that understands the policy assumptions (and related conceptualisations), data sources, methodological approaches and interpretation of results. It demonstrates how the search for policy ‘transparency’ is also met by the technical quality assurance goals that the operational research community would recognise as best practice in the development both of software generally and spreadsheet models specifically. Illustrative examples of complex formulae acting to subvert equity are drawn from the English Fire and Rescue Service and Police Service allocation formulae. In the former, an increase in the amount of deprivation, as measured by one of six indicators, has the perverse effect of decreasing the financial allocation. In the latter, metropolitan areas such as London are found to gain most from the inclusion of variables measuring sparsity. The conclusion from these scenarios is that the steps needed to for technical quality assurance and policy transparency are mutually reinforcing goals, with policy analysts urged to make greater use of technical analytic skills in software development.

Description: We review our recent results in the development of optimal algorithms for the minimization of a strictly convex quadratic function subject to separable convex inequality constraints and/or linear equality constraints. A unique feature of our algorithms is the theoretically supported bound on the rate of convergence in terms of the bounds on the spectrum of the Hessian of the cost function, independent of representation of the constraints. When applied to the class of convex QP or QPQC problems with the spectrum in a given positive interval and a sparse Hessian matrix, the algorithms enjoy optimal complexity, i.e., they can find an approximate solution at the cost that is proportional to the number of unknowns. The algorithms do not assume representation of the linear equality constraints by full rank matrices. The efficiency of our algorithms is demonstrated by the evaluation of the projection of a point to the intersection of the unit cube and unit sphere with hyperplanes.

Description: This paper develops a model for an improved efficiency measure through directional distance formulation of data envelopment analysis. It deals with cases where positive and negative values co-exist as production factors. The developed model has properties such as scalar quantity for measuring efficiency and it identifies all sources of inefficiency. The measure is weakly monotonic; units and translation do not vary with respect to inputs and outputs. The proposed model, under some restrictions, reduces to basic Data Envelopment Analysis (DEA) models such as Charnes-Cooper-Rhodes (CCR), Banker-Charnes-Cooper (BCC), and a slack based model (SBM). In addition to the above, the proposed model includes the closest targets for a given inefficient unit to achieve efficiency with less effort. The proposed model is validated using a case study done on Information Technology firms operating in India.

Description: This paper considers a two-stage supply chain in which a supplier serves a set of stores in a retail chain. We consider a two-stage Stackelberg game in which the supplier must set price discounts for each period of a finite planning horizon under uncertainty in retail-store demand. As a mechanism to stimulate sales, the supplier offers periodic off-invoice price discounts to the retail chain. Based on the price discounts offered by the supplier, and after store demand uncertainty is resolved, the retail chain determines individual store order quantities in each period. Because the supplier offers store-specific prices, the retailer may ship inventory between stores, a practice known as diverting. We demonstrate that, despite the resulting bullwhip effect and associated costs, a carefully designed price promotion scheme can improve the supplier’s profit when compared to the case of everyday low pricing (EDLP). We model this problem as a stochastic bilevel optimization problem with a bilinear objective at each level and with linear constraints. We provide an exact solution method based on a Reformulation-Linearization Technique (RLT). In addition, we compare our solution approach with a widely used heuristic and another exact solution method developed by Al-Khayyal (Eur. J. Oper. Res. 60(3):306–314, 1992 ) in order to benchmark its quality.

Description: We present a full Nesterov and Todd step primal-dual infeasible interior-point algorithm for symmetric optimization based on Darvay’s technique by using Euclidean Jordan algebras. The search directions are obtained by an equivalent algebraic transformation of the centering equation. The algorithm decreases the duality gap and the feasibility residuals at the same rate. During this algorithm we construct strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main iteration of the algorithm consists of a feasibility step and some centering steps. The starting point in the first iteration of the algorithm depends on a positive number ξ and it is strictly feasible for a perturbed pair. The feasibility steps find strictly feasible iterates for the next perturbed pair. By using centering steps for the new perturbed pair, we obtain strictly feasible iterates close to the central path of the new perturbed pair. The algorithm finds an ϵ -optimal solution or detects infeasibility of the given problem. Moreover, we derive the currently best known iteration bound for infeasible interior-point methods.

Description: A short proof is given of the necessary and sufficient conditions for the convergence of the Iterative Proportional Fitting procedure. The input consists of a nonnegative matrix and of positive target marginals for row sums and for column sums. The output is a sequence of scaled matrices to approximate the biproportional fit, that is, the scaling of the input matrix by means of row and column divisors in order to fit row and column sums to target marginals. Generally it is shown that certain structural properties of a biproportional scaling do not depend on the particular sequence used to approximate it. Specifically, the sequence that emerges from the Iterative Proportional Fitting procedure is analyzed by means of the L 1 -error that measures how current row and column sums compare to their target marginals. As a new result a formula for the limiting L 1 -error is obtained. The formula is in terms of partial sums of the target marginals, and easily yields the other well-known convergence characterizations.

Description: Unlike ordinary outpatient clinics, an emergency care center sees a variety of patients with diverse diseases and injuries of different levels of severity. Since patients who are in a critical condition face serious consequences, target waiting times must be determined based on patient acuity levels. To reflect the special situation in emergency care centers included in this study, patient flows are formulated using an open Jackson network with multiple patient classes. This paper is unique because of the integration of pooling and prioritizing patient classes with the open Jackson network. In particular, a hybrid priority model is presented in which a first-come-first-served discipline is applied in some processes and a priority discipline is applied in other processes in the open Jackson network, in order to minimize waiting times for patients with more urgent concerns. A case study based on actual data from an emergency care center demonstrates that the proposed model of pooling and prioritizing patient classes is effective in decreasing waiting times for higher-priority classes without substantially sacrificing those for lower-priority classes.

Description: A recent paper by Prékopa (Ann. Oper. Res. 193(1):49–69, 2012 ) presented results in connection with Multivariate Value-at-Risk (MVaR) that has been known for some time under the name of p -quantile or p - Level Efficient Point (pLEP) and introduced a new multivariate risk measure, called Multivariate Conditional Value-at-Risk (MCVaR). The purpose of this paper is to further develop the theory and methodology of MVaR and MCVaR. This includes new methods to numerically calculate MCVaR, for both continuous and discrete distributions. Numerical examples with recent financial market data are presented.

Description: Farzipoor Saen (Ann. Oper. Res. 172(1):177–192, 2009 ) proposed a method based on Data Envelopment Analysis (DEA) for selecting the best supplier in the presence of cardinal and ordinal data, weight restrictions, and non-discriminatory factors. In the present note, we show that the DEA method proposed by Farzipoor Saen (Ann. Oper. Res. 172(1):177–192, 2009 ) cannot be used for selecting the best supplier in the presence of imprecise data. It is also shown that there are computational errors in calculating the amounts of the preference intensity parameter and the ratio parameter in Farzipoor Saen’s paper.

Description: We consider a manufacturer who sells both the new and remanufactured versions of a product over its life cycle. The manufacturer’s profit depends crucially on her ability to synchronize product returns with the sales of the remanufactured product. This gives rise to a challenging dynamic optimization problem where the size of both the market and the user pool are dynamic and their current values depend on the entire history. We provide an analytical characterization of the manufacturer’s optimal pricing, production, and inventory policies which lead to a practical threshold policy with a small optimality gap. In addition, our analysis offers a number of interesting insights. First, the timing of remanufacturing activity and its co-occurrence with new product manufacturing critically depends on remanufacturing cost benefits, attractiveness of the remanufactured product and product return rate. Second, there is a small upward jump in the price of the new product when remanufacturing is introduced. Third, the manufacturer keeps the new product longer on the market as the cost of remanufacturing decreases. Fourth, partially satisfying demand for the remanufactured item is never optimal, i.e., it is satisfied either fully or not at all. Finally, user pool and inventory of returned products are substitutes in ensuring the supply for future remanufacturing.

Description: Search-based advertising allows the advertisers to run special campaigns targeted to different groups of potential consumers at low costs. Google, Yahoo and Microsoft advertising programs allow the advertisers to bid for an ad position on the result page of a user’s query when the user searches for a keyword that the advertiser relates to its products or services. The expected revenue generated by the ad depends on the ad position, and the ad positions of the advertisers are concurrently determined after an instantaneous auction based on the bids of the advertisers. The advertisers are charged only when their ads are clicked by the users. To avoid excessive ad expenditures due to sudden surges in the keyword-search activities, each advertiser reserves a fixed finite daily budget, and the ads are not shown in the remainder of the day when the budget is depleted. Arrival times of keyword-search instances, ad positions, ad selections, and sales generated by the ads are random. Therefore, an advertiser faces a dynamic stochastic total net revenue optimization problem subject to a strict budget constraint. Here we formulate and solve this problem using dynamic programming. We show that there is always an optimal dynamic bidding policy. We describe an iterative numerical approximation algorithm that uniformly converges to the optimal solution at an exponential rate of the number of iterations. We illustrate the algorithm on numerical examples. Because dynamic programing calculations of the optimal bidding policies are computationally demanding, we also propose both static and dynamic alternative bidding policies. We numerically compare the performances of optimal and alternative bidding policies by systematically changing each input parameter. The relative percentage total net revenue losses of the alternative bidding policies increases with the budget loading, but were never more than 3.5 % of maximum expected total net revenue. The best alternative to the optimal bidding policy turned out to be a static greedy bidding policy. Finally, statistical estimation of the model parameters is visited.

Description: A wireless sensor network (WSN) consists of a large number of unattended sensors with limited storage, battery power, computation, and communication capabilities, where battery power (or energy) is the most crucial resource for sensor nodes. The information sensed by sensors needs to be transmitted to sink quickly especially for the applications with delay restriction. However, it is difficult to achieve optimal energy efficiency and source-to-sink delay simultaneously. So it is very necessary to find a power control solution based tradeoff between energy and delay. In this paper, a cooperative differential game model is proposed, and a power solution is obtained which determines a fair distribution of the total cooperative cost among sources.

Description: Tramp shipping companies are committed to transport a set of contracted cargoes and try to derive additional revenue from carrying optional spot cargoes. Here, we present a real life ship routing and scheduling problem for a shipping company operating in project shipping, a special segment of tramp shipping. This segment differs from more traditional tramp segments, as the cargoes are usually transported on a one-time basis. Because of the special nature of the cargoes, complicating requirements regarding stowage onboard the ships and cargo coupling must be considered while determining routes and schedules for the ships in the fleet. A mathematical model is presented and a tabu search heuristic is proposed to solve the problem. Computational results show that the tabu search heuristic provides optimal or near-optimal solutions in a reasonable amount of time, and that it can give significant improvements to manual planning for the shipping company.