Abstract: Abstract Efficient feasibility tests are important in many heuristics for routing problems. This paper considers several variants of pickup-and-delivery problems with trailers. Its contribution consists in the description of constant-time procedures for testing observance of capacity constraints when inserting tasks into routes. It is demonstrated that the presence of vehicles with detachable trailers makes capacity feasibility tests considerably more involved. PubDate: 2020-07-23

Abstract: Abstract In this paper, we study a single vendor-multiple buyer integrated inventory model with controllable lead time and backorders-lost sales mixture. Each buyer adopts a periodic review policy in which the review period is an integer fraction of the production cycle time of the vendor. To reflect the practical circumstance characterized by the lack of complete information about the demand distribution, we assume that only the first two moments of the demand during the protection interval are known. The long-run expected total cost per time unit is derived, which includes stockout costs. The problem is to determine the length of the inventory cycle of the vendor, the produce-up-to level for the vendor, the replenishment policy of each buyer, and the length of lead times that minimize the cost function under the minimax distribution-free approach. Two alternative heuristics are proposed. Numerical experiments have been carried out to investigate the performance of the heuristics and to study the sensitivity of the model. PubDate: 2020-07-16

Abstract: Abstract In this paper, we propose exact and heuristic solution approaches based on dynamic programming for an open lot streaming problem. We also present the first application of Lagrangian relaxation to compute strong lower bounds to such a problem. The application concerns the minimization of the total flow time for the discrete version of a single-job lot streaming problem from the literature in a two-machine flow shop with attached setup times. Computational results on benchmark instances illustrate the effectiveness of the proposed approaches and give evidence of the strength of the Lagrangian relaxation lower bounds. PubDate: 2020-07-10

Abstract: Abstract We consider the coordination of planning decisions of a single product in a supply chain composed of one supplier and one retailer, by using contracts. We assume that the retailer has the market power: he can impose his optimal replenishment plan to the supplier. Our aim is to minimize the supplier’s cost without increasing the retailer’s cost. To this end, the supplier (or a trusted third party) proposes to the retailer a contract, which is made of a replenishment plan and a side payment. This side payment compensates the increase of cost of the retailer due to the fact that the proposed replenishment plan may have a cost larger than the retailer’s optimal replenishment plan. We evaluate how much the supplier can gain by using contracts under several scenarios which depend on the side payment coverage. From a theoretical point of view, in all the scenarios, contracts may decrease the cost of the supplier by an arbitrarily large factor. We perfom experiments which measures the gain that can be obtained in practice on various instances types. If side payments are allowed, experiments show that the use of contracts decreases significantly the cost of the supplier, and that side payments on the holding costs are sufficient. We show that if there is no side payment, or if there is no constraint on the side payment, then the problem can be solved in polynomial time. On the contrary, if the side payment is limited to the holding costs of the retailer, then the problem is NP-hard. We extend this study to the case where the information is asymmetric (the supplier—or the trusted third entity—does not know all the costs of the retailer): in this case, the situation is modelled by a screening game. PubDate: 2020-06-06

Abstract: Abstract In this paper, we study the scheduling of proportional-linearly deteriorating jobs with positional due indices, release dates, deadlines and precedence relations on a single machine. The scheduling criteria studied in this paper include the makespan, maximum lateness, maximum tardiness, maximum flow time, maximum weighted completion time, maximum scheduling cost, total completion time, and the number of tardy jobs. By applying Lawler’s rule and Smith’s rule, polynomially solvable problems are processed by using two unified methods. We also present some new NP-hardness results when processing times of the jobs have no deterioration. Our results generalize a series of known achievements in the literature. PubDate: 2020-06-01

Abstract: Abstract In this work, we analyze the structural properties of the set of feasible bookings in the European entry–exit gas market system. We present formal definitions of feasible bookings and then analyze properties that are important if one wants to optimize over them. Thus, we study whether the sets of feasible nominations and bookings are bounded, convex, connected, conic, and star-shaped. The results depend on the specific model of gas flow in a network. Here, we discuss a simple linear flow model with arc capacities as well as nonlinear and mixed-integer nonlinear models of passive and active networks, respectively. It turns out that the set of feasible bookings has some unintuitive properties. For instance, we show that the set is nonconvex even though only a simple linear flow model is used. PubDate: 2020-06-01

Abstract: Abstract We provide decision-making models for a manufacturer which plans to produce multiple short life cycle products with the one-shot decision theory. The obtained optimal production quantities are based on the most appropriate scenarios for the manufacturer. Since the models are the bilevel programming problems with the max–min or min–max operator in the lower levels, we propose two approaches to translate them into general single-level optimization problems such that they can be solved via the commonly used optimization methods. The effectiveness of our approaches is examined from the theoretical and computational aspects. PubDate: 2020-06-01

Abstract: Abstract In this paper, we consider an unconstrained optimization problem and propose a new family of modified BFGS methods to solve it. As it is known, classic BFGS method is not always globally convergence for nonconvex functions. To overcome this difficulty, we introduce a new modified weak-Wolfe–Powell line search technique. Under this new technique, we prove global convergence of the new family of modified BFGS methods and the classic BFGS method, for nonconvex functions. Furthermore, all members of this family have at least \(o(\Vert s \Vert ^{5})\) error order. Our obtained results from numerical experiments on 77 standard unconstrained problems, indicate that the algorithms developed in this paper are promising and more effective than some similar algorithms. PubDate: 2020-06-01

Abstract: Abstract In online optimization, input data is revealed sequentially. Optimization problems in practice often exhibit this type of information disclosure as opposed to standard offline optimization where all information is known in advance. We analyze the performance of algorithms for online optimization with lookahead using a holistic distributional approach. To this end, we first introduce the performance measurement method of counting distribution functions. Then, we derive analytical expressions for the counting distribution functions of the objective value and the performance ratio in elementary cases of the online bin packing and the online traveling salesman problem. For bin packing, we also establish a relation between algorithm processing and the Catalan numbers. The paper shows that an exact analysis is strongly interconnected to the combinatorial structure of the problem and algorithm under consideration. Results further indicate that the value of lookahead heavily relies on the problem itself. The analysis also shows that exact distributional analysis could be used in order to discover key effects and identify related root causes in relatively simple problem settings. These insights can then be transferred to the analysis of more complex settings where the introduced performance measurement approach has to be used on an approximative basis (e.g., in a simulation-based optimization). PubDate: 2020-05-21

Abstract: Abstract Linear programming has had a tremendous impact in the modeling and solution of a great diversity of applied problems, especially in the efficient allocation of resources. As a result, this methodology forms the backbone of introductory courses in operations research. What students, and others, may not appreciate is that linear programming transcends its linear nomenclature and can be applied to an even wider range of important practical problems. The objective of this article is to present a selection, and just a selection, from this range of problems that at first blush do not seem amenable to linear programming formulation. The exposition focuses on the most basic models in these selected applications, with pointers to more elaborate formulations and extensions. Thus, our intent is to expand the modeling awareness of those first encountering linear programming. In addition, we hope this article will be of interest to those who teach linear programming and to seasoned academics and practitioners, alike. PubDate: 2020-05-07

Abstract: Abstract In this paper we propose an explicit algorithm for solving a variational inclusion problem of the sum of two operators, the one is maximally monotone and the other is monotone and Lipschitz continuous. The algorithm uses the variable stepsizes which are updated over each iteration by some cheap comptutations. These stepsizes are found without the prior knowledge of the Lipschitz constant of operator as well as without using lineseach procedure. The algorithm thus can be implemented easily. The convergence and the convergence rate of the algorithm are established under mild conditions. Several preliminary numerical results are provided to demonstrate the theoretical results and also to compare the new algorithm with some existing ones. PubDate: 2020-04-21

Abstract: Abstract Penalty shootout in soccer is recognized to be unfair because the team kicking first in all rounds enjoys a significant advantage. The so-called Catch-Up Rule has been suggested recently to solve this problem but is shown here not to be fairer than the simpler deterministic Alternating (ABBA) Rule that has already been tried. We introduce the Adjusted Catch-Up Rule by guaranteeing the first penalty of the possible sudden death stage to the team disadvantaged in the first round. It outperforms the Catch-Up and Alternating Rules, while remains straightforward to implement. A general measure of complexity for penalty shootout mechanisms is also provided as the minimal number of binary questions required to decide the first-mover in a given round without knowing the history of the penalty shootout. This quantification permits a two-dimensional evaluation of any mechanism proposed in the future. PubDate: 2020-04-20

Abstract: Abstract In vehicle routing problems (VRPs) the decisions to be taken concern the assignment of customers to vehicles and the sequencing of the customers assigned to each vehicle. Additional decisions may need to be jointly taken, depending on the specific problem setting. In this paper, after discussing the different kinds of decisions taken in different classes of VRPs, the class where the decision about when the routes start from the depot has to be taken is considered and the related literature is reviewed. This class of problems, that we call VRPs over time, includes the periodic routing problems, the inventory routing problems, the vehicle routing problems with release dates, and the multi-trip vehicle routing problems. PubDate: 2020-03-06