A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem

This paper deals with the one-machine dynamic total completion time scheduling problem. This problem is known to be NP-hard in the strong sense. A polynomial time heuristic algorithm is proposed which applies the recently introduced Recovering Beam Search (RBS) approach. The algorithm is based on a beam search procedure with unitary beam width and includes a recovering subroutine that allows to overcome wrong decisions taken at higher levels of the beam search tree. It is shown that the total number of considered nodes is bounded by n where n is the jobsize. The proposed algorithm is able to solve in very short CPU time problems with up to 500 jobs outperforming the best state of the art heuristics.     

Multi‐level hierarchic Markov processes as a framework for herd management support

A general problem in relation to application of Markov decision processes to real world problems is the curse of dimensionality, since the size of the state space grows to prohibitive levels when information on all relevant traits of the system being modeled are included. In herd management, we face a hierarchy of decisions made at different levels with different time horizons, and the decisions made at different levels are mutually dependent. Furthermore, decisions have to be made without certainty about the future state of the system. These aspects contribute even further to the dimensionality problem. A new notion of a multilevel hierarchic Markov process specially designed to solve dynamic decision problems involving decisions with varying time horizon has been presented. The method contributes significantly to circumvent the curse of dimensionality, and it provides a framework for general herd management support instead of very specialized models only concerned with a single decision as, for instance, replacement. The applicational perspectives of the technique are illustrated by potential examples relating to the management of a sow herd and a dairy herd.     

Control decisions and personal beliefs: their effect on solving mathematical problems

The main purpose of this paper is to discuss how college students enrolled in a college level elementary algebra course exercised control decisions while working on routine and non-routine problems, and how their personal belief systems shaped those control decisions. In order to prepare students for success in mathematics we as educators need to understand the process steps they use to solve homework or examination questions, in other words, understand how they “do” mathematics. The findings in this study suggest that an individual’s belief system impacts how they approach a problem. Lack of confidence and previous lack of success combined to prompt swift decisions to stop working. Further findings indicate that students continue with unsuccessful strategies when working on unfamiliar problems due to a perceived dependence of solution strategies to specific problem types. In this situation, the students persisted in an inappropriate solution strategy, never reaching a correct solution. Control decisions concerning the pursuit of alternative strategies are not an issue if the students are unaware that they might need to make different choices during their solutions. More successful control decisions were made when working with familiar problems.     

A Solution Method for a Two-dispatch Delivery Problem with Stochastic Customers

We study a vehicle routing problem in which vehicles are dispatched multiple times a day for product delivery. In this problem, some customer orders are known in advance while others are uncertain but are progressively realized during the day. The key decisions include determining which known orders should be delivered in the first dispatch and which should be delivered in a later dispatch, and finding the routes and schedules for customer orders. This problem is formulated as a two-stage stochastic programming problem with the objective of minimizing the expected total cost. A worst-case analysis is performed to evaluate the potential benefit of the stochastic approach against a deterministic approach. Furthermore, a sample-based heuristic is proposed. Computational experiments are conducted to assess the effectiveness of the model and the heuristic.      

A hyperbolic smoothing approach to the Multisource Weber problem

The Multisource Weber problem, also known as the continuous location-allocation problem, or as the Fermat-Weber problem, is considered here. A particular case of the Multisource Weber problem is the minimum sum-of-distances clustering problem, also known as the continuous \(p\) -median problem. The mathematical modelling of this problem leads to a \(min-sum-min\) formulation which, in addition to its intrinsic bi-level nature, is strongly nondifferentiable. Moreover, it has a large number of local minimizers, so it is a typical global optimization problem. In order to overcome the intrinsic difficulties of the problem, the so called Hyperbolic Smoothing methodology, which follows a smoothing strategy using a special \( \, C^{\infty } \, \) differentiable class function, is adopted. The final solution is obtained by solving a sequence of low dimension \( \, C^{\infty } \, \) differentiable unconstrained optimization sub-problems which gradually approaches the original problem. For the purpose of illustrating both the reliability and the efficiency of the method, a set of computational experiments making use of traditional test problems described in the literature was performed. Apart from consistently presenting better results when compared to related approaches, the novel technique introduced here was able to deal with instances never tackled before in the context of the Multisource Weber problem.     

A Bayesian Approach to Estimating Decision Parameters in a Replacement Inventory System

This paper deals with the estimation of decision parameters in a special class of inventory systems in which the rate of stock depletion depends on the internal operations of the parent organization instead of market demands. Stocking decisions for this type of inventory systems are unique in that demands for the stocked items are internal demands, sporadic in some instances, infrequent in others, and almost never the direct results of conscious economic decisions. To cope with the peculiar situation, Bayesian point and interval estimation procedures are used. The estimated probability measures provide a basis on which stocking decisions pertinent to this type of inventory systems can be made or evaluated. Specific statistical postulates are made, and a numerical example is given for illustration. The possibility of applying the estimated results to one of the existing inventory models is briefly discussed at the end.     

When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem

The vertex k-center selection problem is a well known NP-Hard minimization problem that can not be solved in polynomial time within a \(\rho < 2\) approximation factor, unless \(P=NP\). Even though there are algorithms that achieve this 2-approximation bound, they perform poorly on most benchmarks compared to some heuristic algorithms. This seems to happen because the 2-approximation algorithms take, at every step, very conservative decisions in order to keep the approximation guarantee. In this paper we propose an algorithm that exploits the same structural properties of the problem that the 2-approximation algorithms use, but in a more relaxed manner. Instead of taking the decision that guarantees a 2-approximation, our algorithm takes the best decision near the one that guarantees the 2-approximation. This results in an algorithm with a worse approximation factor (a 3-approximation), but that outperforms all the previously known approximation algorithms on the most well known benchmarks for the problem, namely, the pmed instances from OR-Lib (Beasly in J Oper Res Soc 41(11):1069–1072, 1990) and some instances from TSP-Lib (Reinelt in ORSA J Comput 3:376–384, 1991). However, the \(O(n^4)\) running time of this algorithm becomes unpractical as the input grows. In order to improve its running time, we modified this algorithm obtaining a \(O(n^2 \log n)\) heuristic that outperforms not only all the previously known approximation algorithms, but all the polynomial heuristics proposed up to date.     

Some Enumeration Problems on Central Configurations at the Bifurcation Points

In “Counting central configurations at the bifurcation points,” we proposed an algorithm to rigorously count central configurations in some cases that involve one parameter. Here, we improve our algorithm to consider three harder cases: the planar \((3+1)\)-body problem with two equal masses; the planar 4-body problem with two pairs of equal masses which have an axis of symmetry containing one pair of them; the spatial 5-body problem with three equal masses at the vertices of an equilateral triangle and two equal masses on the line passing through the center of the triangle and being perpendicular to the plane containing it.While all three problems have been studied in two parameter cases, numerical observations suggest new results at some points on the bifurcation curves. Applying the improved version of our algorithm, we count at those bifurcation points. As a result, for the \((3+1)\)-body problem, we identify three points on the bifurcation curve where there are 8 central configurations, which adds to the known results of \(8,9,10\) ones. For our 4-body case, at the bifurcation points, there are 3 concave central configurations, which adds to the known results of \(2,4\) ones. For our 5-body case, at the bifurcation point, there is 1 concave central configuration, which adds to the known results of \(0,2\) ones.     

Multi-resource investment strategies: Operational hedging under demand uncertainty

Consider a firm that markets multiple products, each manufactured using several resources representing various types of capital and labor, and a linear production technology. The firm faces uncertain product demand and has the option to dynamically readjust its resource investment levels, thereby changing the capacities of its linear manufacturing process. The cost to adjust a resource level either up or down is assumed to be linear. The model developed here explicitly incorporates both capacity investment decisions and production decisions, and is general enough to include reversible and irreversible investment. The product demand vectors for successive periods are assumed to be independent and identically distributed. The optimal investment strategy is determined with a multi-dimensional newsvendor model using demand distributions, a technology matrix, prices (product contribution margins), and marginal investment costs. Our analysis highlights an important conceptual distinction between deterministic and stochastic environments: the optimal investment strategy in our stochastic model typically involves some degree of capacity imbalance which can never be optimal when demand is known.     

An efficient algorithm for the complete set partitioning problem

The complete set partitioning problem is the well known set partitioning problem with all possible nonzero binary columns in the constraint matrix. A highly specialized enumerative algorithm, which never requires the explicit maintenance of the constraint matrix, is presented. Computational results, with data reflecting a particular corporate tax payment scenario that can be modelled as a complete set partitioning problem, is also given.     

Routing and scheduling in a liquefied natural gas shipping problem with inventory and berth constraints

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.     

A two-player competitive discrete location model with simultaneous decisions

In this paper we will describe and study a competitive discrete location problem in which two decision-makers (players) will have to decide where to locate their own facilities, and customers will be assigned to the closest open facilities. We will consider the situation in which the players must decide simultaneously, unsure about the decisions of one another, and we will present the problem in a franchising environment. Most problems described in the literature consider sequential rather than simultaneous decisions. In a competitive environment, most problems consider that there is a set of known and already located facilities, and new facilities will have to be located, competing with the existing ones. In the presence of more than one decision-maker, most problems found in the literature belong to the class of Stackelberg location problems, where one decision-maker, the leader, locates first and then the other decision-maker, the follower, locates second, knowing the decisions made by the first. These types of problems are sequential and differ significantly from the problem tackled in this paper, where we explicitly consider simultaneous, non-cooperative discrete location decisions. We describe the problem and its context, propose some mathematical formulations and present an algorithmic approach that was developed to find Nash equilibria. Some computational tests were performed that allowed us to better understand some of the features of the problem and the associated Nash equilibria. Among other results, we conclude that worsening the situation of a player tends to benefit the other player, and that the inefficiency of Nash equilibria tends to increase with the level of competition.     

A graph theory approach to subcontracting, machine duplication and intercell moves in cellular manufacturing

We address in this paper the problem of finding an optimal strategy for dealing with bottleneck machines and bottleneck parts in the cell formation process in group technology. Three types of economic decisions are considered: subcontracting, machine duplication and intercell moves. The problem is formulated as a minimum weighted node covering problem in a hypergraph, and we show that it can be solved in polynomial time by finding a maximum weighted stable set in a bipartite graph. We extend this result to cellular manufacturing systems in which the sequence of operations of each part is known in advance.     

Network flow problems with pricing decisions

This paper considers a class of network flow problems in which the demand levels of the nodes are determined through pricing decisions representing the revenue received per unit demand at the nodes. We must simultaneously determine the pricing decisions and the network flow decisions in order to maximize profits, i.e., the revenues received from the pricing decisions minus the cost of the network flow decisions. Specializations of this class of problems have numerous applications in supply chain management. We show that the class of problems with a single pricing decision throughout the network can be solved in polynomial time under both continuous pricing restrictions and integer pricing restrictions. For the class of problems with customer-specific pricing decisions, we provide conditions under which the problem can be solved in polynomial-time for continuous pricing restrictions and prove that the problem is NP-hard for integer pricing restrictions.     

On the determination of boundary collocation points for solving some problems for the Laplace operator

Boundary collocation is a method for obtaining approximate solutions of boundary problems for linear partial differential equations, for which complete families of particular solutions are explicitly known. The method contains various decisions which are important for its performance, such as choice of solution subspace, choice of basis for the subspace, and choice of collocation points. Using a model problem, some particular strategies for the determination of collocation points are investigated.     

k-均值问题的差分隐私算法综述

$k$-均值问题是机器学习和组合优化领域十分重要的问题。它是经典的NP-难问题, 被广泛的应用于数据挖掘、企业生产决策、图像处理、生物医疗科技等领域。随着时代的发展, 人们越来越注重于个人的隐私保护:在决策通常由人工智能算法做出的情况下, 如何保证尽可能多地从数据中挖掘更多信息,同时不泄露个人隐私。近十年来不断有专家学者研究探索带隐私保护的$k$-均值问题, 得到了许多具有理论指导意义和实际应用价值的结果, 本文主要介绍关于$k$-均值问题的差分隐私算法供读者参考。     

An inventory model: What is the influence of the shape of the lead time demand distribution?

In this paper the influence of the shape of the lead time demand distribution is studied for a specific inventory model which is described in a preceding paper by Heuts and van Lieshout [4]. This continuous review inventory model uses as lead time demand distribution a Schmeiser-Deutsch distribution (S-D distribution) [9]. In a previous paper [4] an algorithm was given to solve the decision problem.In the literature attention is given to the following problem: what information on the demand during the lead time is necessary and sufficient to obtain good decisions. Using a (s, S) policy; Naddor [8] concluded that thespecific form of the lead time demand distribution is negligible, and that only its first two moments are essential. For a simple (s, q) control system Fortuin [3] comes to the same conclusion. Both authors analysed the case with known lead times and with given demand distributions from the class of two parameter distributions. So in fact their results are obvious, as the lead time demand distributions resulting from their suppositions are all nearly symmetric. We shall demonstrate that the skewness of the lead time demand distribution in our inventory model is also an important measure, which should be taken into account, as the cost differences with regard to the case where this skewness measure is not used, can be considerable.     

Joint optimization of level of repair analysis and spare parts stocks

In the field of after sales service logistics for capital goods, generally, METRIC type methods are used to decide where to stock spare parts in a multi-echelon repair network such that a target availability of the capital goods is achieved. These methods generate a trade-off curve of spares investment costs versus backorders. Backorders of spare parts lead to unavailability of the capital goods. Inputs in the spare parts stocking problem are decisions on (1) which components to repair upon failure and which to discard, and (2) at which locations in the repair network to perform the repairs and discards. The level of repair analysis (LORA) can be used to make such decisions in conjunction with the decisions (3) at which locations to deploy resources, such as test equipment that are required to repair, discard, or move components. Since these decisions significantly impact the spare parts investment costs, we propose to solve the LORA and spare parts stocking problems jointly. We design an algorithm that finds efficient solutions. In order for the algorithm to be exact and because of its computational complexity, we restrict ourselves to two-echelon, single-indenture problems. In a computational experiment, we show that solving the joint problem is worthwhile, since we achieve a cost reduction of over 43% at maximum (5.1% on average) compared with using a sequential approach of first solving a LORA and then the spare parts stocking problem.     

The transportation problem revisited—preprocessing before using the primal–dual algorithm

We give a necessary condition for the existence of a feasible solution for the transportation problem through a set of admissible cells, and an algorithm to find a set of admissible cells that satisfies the necessary condition. Either there exists a feasible solution through the admissible cells (which is therefore optimal since the complementary slackness conditions hold) or we could begin using the primal–dual algorithm (PDA) at this point. Our approach has two important advantages: Our O(mn) procedure for updating dual variables takes much less computing time than any procedure for solving a maximum flow problem in the primal phase of the PDA. We are never concerned by the degeneracy problem as we are not seeking basic solutions, but admissible cells. An example is presented for illustrating our approach. We finally provide computational results for a set of 30 randomly generated instances. Comparison of our method with the PDA reveals a real speed up.     

Capturing incomplete information in resource allocation problems through numerical patterns

We look at the problem of optimizing complex operations with incomplete information where the missing information is revealed indirectly and imperfectly through historical decisions. Incomplete information is characterized by missing data elements governing operational behavior and unknown cost parameters. We assume some of this information may be indirectly captured in historical databases through flows characterizing resource movements. We can use these flows or other quantities derived from these flows as “numerical patterns” in our optimization model to reflect some of the incomplete information. We develop our methodology for representing information in resource allocation models using the concept of pattern regression. We use a popular goodness-of-fit measure known as the Cramer–Von Mises metric as the foundation of our approach. We then use a hybrid approach of solving a cost model with a term known as the “pattern metric” that minimizes the deviations of model decisions from observed quantities in a historical database. We present a novel iterative method to solve this problem. Results with real-world data from a large freight railroad are presented.