The Joint Replenishment Problem with a Powers-of-Two Restriction

In this paper we consider the joint replenishment problem in the light of recent work by the second and third authors concerning the selection of realistic and consistent reorder intervals in production/ distribution systems. After stating a general dynamic programming formulation of the joint replenishment problem, we present its usual statement which assumes constant reorder intervals. We then restrict the problem further by assuming the constant reorder intervals are powers-of-two multiples of some base planning interval. We present an algorithm based on concepts we developed that solves the joint replenishment problem with the powers-of-two restriction. Like other algorithms proposed for this problem, it is a simple sorting algorithm. Finally, we establish that the algorithm yields a solution whose average annual cost is within 6% of the general problem's long-run minimum average annual cost.     

Lot sizing problems with strong set-up interactions

We address the problem of coordinated replenishment of products when the products can be produced only in fixed proportion to each other. Such problems commonly arise in the manufacture of sheet/plate metal parts or die-cast parts. The problem is a variant of the well-known Joint Replenishment Problem. We call this problem the Strong Interaction Problem (SIP). After giving a mathematical formulation of the problem, we show that the general problem is NP-hard. An important variant of the problem, in which products are unique to a family, is shown to be polynomially solvable. We present several lower bounds, an exact algorithm and a heuristic for the problem. Computational testing on randomly generated problems suggests that our exact algorithm performs very well when compared with a commercially available integer programming solver. The heuristic method also gives good solutions.     

A joint replenishment policy with individual control and constant size orders

We consider inventory systems with multiple items under stochastic demand and jointly incurred order setup costs. The problem is to determine the replenishment policy that minimises the total expected ordering, inventory holding, and backordering costs–the so-called stochastic joint replenishment problem. In particular, we study the settings in which order setup costs reflect the transportation costs and have a step-wise cost structure, each step corresponding to an additional transportation vehicle. For this setting, we propose a new policy that we call the (s, 𝒬) policy, under which a replenishment order of constant size 𝒬 is triggered whenever the inventory position of one of the items drops to its reorder point s. The replenishment order is allocated to multiple items so that the inventory positions are equalised as much as possible. The policy is designed for settings in which backorder and setup costs are high, as it allows the items to independently trigger replenishment orders and fully exploits the economies of scale by consistently ordering the same quantity. A numerical study is conducted to show that the proposed (s, 𝒬) policy outperforms the well-known (𝒬, S) policy when backorder costs are high and lead times are small.     

A dynamic lot-sizing model with multi-mode replenishments: polynomial algorithms for special cases with dual and multiple modes

This paper generalizes the classical dynamic lot-sizing model to consider the case where replenishment orders may be delivered by multiple shipment modes. Each mode may have a different lead time and is characterized by a different cost function. The model represents those applications in which products can be purchased through various suppliers or delivered from a single source using various transportation modes with different lead times and costs. The problem is challenging due to the consideration of cargo capacity constraints, i.e., the multiple set-ups cost structure, associated with a replenishment mode. The paper presents several structural optimality properties of the problem and develops efficient algorithms, based on the dynamic programming approach, to find the optimal solution. The special, yet practical, cases of the two-mode replenishment problem analyzed in this paper are analytically tractable, and hence, the respective problems can be solved in polynomial time.     

Multi-product batch replenishment strategies under stochastic demand and a joint capacity constraint

We analyze a multi-product inventory replenishment problem with Poisson demands where the aggregate inventory level at any time is restricted by a common budget or space limitation. We present a semi-Markov decision problem formulation, several heuristics for finding the replenishment quantities (given the current inventories) and a comparison from a cost performance perspective.     

Multi-item distribution network design problems under volume discount on transportation cost

This study considers the distribution network design problems of multi-echelon, multi-item supply chains under volume (weight) discounts on transportation costs. Minimising the total network cost requires determining the following: (1) the service area of distribution centres (DCs); (2) the assignment of retail stores to DCs; and (3) the inventory volume at DCs. This study compares various replenishment policies and discusses the effects of such policies on distribution network design. In general, the results show that single-cluster replenishment is superior to joint cluster replenishment. However, joint cluster replenishment may be superior to single-cluster replenishment under volume (weight) discounts on transportation costs. The results additionally show that single-item replenishment is inferior to multi-item replenishment under volume (weight) discounts on transportation costs. All the problems are formulated as piecewise non-linear programming models with multiple variables. Algorithms are proposed for solving these piecewise non-linear programming problems. Several numerical studies demonstrate the solution procedures and the effects of changing parameters on decision-making.     

A novel integer programming formulation with logic cuts for the U-shaped assembly line balancing problem

U-shaped assembly lines are regarded as an efficient configuration in Just-In-Time manufacturing. Balancing the workload in these lines is an unsolved problem that attracted significant research within the past two decades. We present a novel integer programming formulation for U-shaped line balancing problems, where cycle time, the interval between two consecutive outputs, is known and the aim is to minimize the number of workstations. To enhance the efficiency of the LP relaxation of the new formulation, we present three types of logic cuts (assignable-station-cuts, task-assignment-cuts and knapsack-cuts) that exploit the inherent logic of the problem structure. The new formulation and logic cuts are tested on an extensive set of benchmark problems to provide a comparative analysis with the existing models in the literature. The results show that our novel formulation augmented by assignable-station-cuts is significantly better than the previous formulations.     

Inventory-based dispatching of automated guided vehicles on container terminals

This paper deals with automated guided vehicles (AGVs) which transport containers between the quay and the stack on automated container terminals. The focus is on the assignment of transportation jobs to AGVs within a terminal control system operating in real time. First, we describe a rather common problem formulation based on due times for the jobs and solve this problem both with a greedy priority rule based heuristic and with an exact algorithm. Subsequently, we present an alternative formulation of the assignment problem, which does not include due times. This formulation is based on a rough analogy to inventory management and is solved using an exact algorithm. The idea behind this alternative formulation is to avoid estimates of driving times, completion times, due times, and tardiness because such estimates are often highly unreliable in practice and do not allow for accurate planning. By means of simulation, we then analyze the different approaches. We show that the inventory-based model leads to better productivity on the terminal than the due-time-based formulation.     

The Buyer-Vendor Coordination Problem: Modeling Inbound and Outbound Cargo Capacity and Costs

In this paper, we generalize the deterministic demand buyer-vendor coordination problem to simultaneously consider cargo capacity constraints and general inbound/outbound transportation costs. To this end, we first consider a replenishment cost structure that includes a fixed cost as well as a stepwise inbound freight cost for the vendor. We then extend our results to consider the case where both the vendor and the buyer are subject to this freight cost structure. Hence, in the second model, both the inbound and the outbound transportation costs/constraints of the buyer-vendor pair are modeled explicitly. For each case, we provide heuristic algorithms with promising error bounds. The error bounds for these heuristic methods are 6 and 25%, respectively. Using the costs of these heuristics as upper bounds, we also develop finite time exact solution procedures.     

Heuristics for the plate-cutting traveling salesman problem

In this paper we present a new problem that arises when parts are cut from large plates of metal or glass. We call this problem the plate-cutting traveling salesman problem (P-TSP) because it requires the determination of a minimum-length tour such that exactly one point must be visited on each of a number of given polygons. We present a mathematical formulation of the problem and show that the problem is a variation of the well-known traveling salesman problem. We examine the problem when the order in which parts are to be cut is known. For this problem we present a Lagrangean decomposition of the problem and develop lower bounds and heuristics based on this decomposition. Computational testing on problems with 5-40 polygons reveals that the heuristics give fairly good solutions. When the order in which polygons are to be cut is known, the heuristic solutions are within 3-4% of the optimal. The decomposition-based heuristics are embedded in a variable r-opt heuristic for the overall problem.     

Usage scenarios for design space exploration with a dynamic multiobjective optimization formulation

In a recent publication, we presented a new strategy for engineering design and optimization, which we termed formulation space exploration. The formulation space for an optimization problem is the union of all variable and design objective spaces identified by the designer as being valid and pragmatic problem formulations. By extending a computational search into this new space, the solution to any optimization problem is no longer predefined by the optimization problem formulation. This method allows a designer to both diverge the design space during conceptual design and converge onto a solution as more information about the design objectives and constraints becomes available. Additionally, we introduced a new way to formulate multiobjective optimization problems, allowing the designer to change and update design objectives, constraints, and variables in a simple, fluid manner that promotes exploration. In this paper, we investigate three usage scenarios where formulation space exploration can be utilized in the early stages of design when it is possible to make the greatest contributions to development projects. Specifically, we look at formulation space boundary exploration, Pareto frontier generation for multiple concepts in the formulation space, and a new way to perform targeted boundary expansion. The benefits of these methods are illustrated with the conceptual design of an impact driver.     

An integral equation method for non-self-adjoint eigenvalue problems and its applications to non-conservative stability problems

The aim of the work reported in this paper is to present the new formulation of the integral equation method for non-self-adjoint problems and to apply the method to stability problems of elastic continua subjected to non-conservative loadings. A general non-self-adjoint eigenvalue problem stated in terms of differential operators is transformed into a set of coupled integral equations. Our derivation of integral equations is based on an inverse formulation of a canonical form for the original problem and the corresponding fundamental solution pair. Three well-known non-conservative stability problems in elasticity are examined by this integral equation method as illustrative examples. The approximate values of the critical parameters of sample problems demonstrate a sufficient accuracy through a comparison of other values.     

A new decomposition algorithm for a liquefied natural gas inventory routing problem

We consider an inventory routing problem (IRP) in the liquefied natural gas (LNG) supply chain, called the LNG-IRP. Here, an actor is responsible for the LNG production and inventory management at the liquefaction plants, the routing and scheduling of a heterogeneous fleet of LNG ships, as well as the inventories and sales at the regasification terminals. Furthermore, all ports have a limited number of berths available for loading and unloading. The LNG-IRP is more complicated than many other maritime inventory routing problems because a constant rate of the cargo evaporates in the tanks each day and is used as fuel during transportation. In addition, a variable number of tanks are unloaded at the regasification terminals. We introduce a new path flow formulation for this problem arising from a novel decomposition scheme based on parts of a ship schedule, called duties. A ship schedule for the entire planning horizon can be divided into duties consisting of a visit to a liquefaction plant, then one or two visits to a regasification terminal before ending in a liquefaction plant. The solution method suggested is based on a priori generation of duties, and the formulation is strengthened by valid inequalities. The same problem was previously solved by a branch-price-and-cut algorithm for a schedule-based formulation. Computational results show that the new formulation provides tighter bounds than the previous schedule-based formulation. Furthermore, on a set of 27 benchmark instances, the proposed algorithm clearly outperforms the previous branch-price-and-cut algorithm both with regard to computational time and the number of problems solved within a 10-h time limit.     

A Lagrangean heuristic for integrated production and transportation planning problems in a dynamic, multi-item, two-layer supply chain

We present a Lagrangean-based decomposition that is used to generate solutions for an integrated production and transportation planning problem in a two-stage supply chain. This supply chain consists of a number of facilities, each capable of producing the final products, and a number of retailers. It is assumed that the retailers' demands are known and deterministic, and that there are production capacity constraints. The problem is formulated as a multi-commodity network flow problem with fixed charge costs which is a NP-hard problem. An alternative formulation is provided whose linear programming relaxation gives tighter lower bounds. The quality of the lower and upper bounds from the Lagrangean decomposition is tested on a large set of randomly generated problems.     

基于启发式算法的乘用车物流运输问题分析

伴随着汽车工业的高速崛起,乘用车物流运输问题也快速走进人们的视野。由于现在很多物流公司在制定运输计划时主要依赖调度人员的经验,在面对复杂的运输任务时,往往效率较低且运输成本不尽理想。考虑到影响乘用车物流运输成本的主要因素分别为轿运车的使用数量、轿运车的单价以及行驶里程数等等,本文采用建立逐级目标的模式,应用启发式算法,结合计算机软件,给出了求解乘用车物流运输问题的数学模型。应用此模型求解了2种不同类型的乘用车物流运输问题,提出了合理的运输方案。此项工作对今后物流公司处理此类运输问题提供了重要的参考价值。     

Optimal stocking strategies for inventory mechanism with a stochastic short-term price discount and partial backordering

Price discount is an important research topic in the field of inventory management. The existing research on this topic mainly considers fixed price discount, but ignores the situation in which stochastic short-term price discount may be involved. In this paper, we study an inventory problem considering stochastic short-term price discount and partial backordering. To address this problem, we propose an optimal replenishment and stocking model to maximise the retailers' profit. After that, a cost–benefit analysis-based heuristic method for solving the developed model is presented by considering two scenarios depending on whether a replenishment point belongs to a discount period or not. Furthermore, an algorithm is provided to elicit an optimal ordering policy from multiple solutions derived from the given heuristic solution method. Finally, a real case is offered to demonstrate the application of the proposed model, followed by a sensitivity analysis. The results indicate that a retailer can identify the optimal replenishment policy with the aim of achieving maximal profit in situations where stochastic short-term price discount and partial backordering are considered for certain inventory problems at hand. In addition, sensitivity analysis illustrates a fact that different values of the introduced parameters may influence the optimal replenishment policy.     

Finite element method used in contact problems with dry friction

In this paper, we present a formulation of numerical approximations of the frictional quasi-contact problem with dry friction between a deformable body and a foundation with possibility to consider the case of two deformable bodies. We consider numerical approximations of 3D static contact problem with dry friction, using finite contact elements. Saddle-point algorithm, Lagrange incremental multipliers method and penalty functions are used to enforce finite element surface contact constrains for incremental formulation of the frictional quasi-static problem. Some typical examples in the elastic contact problems with dry friction are presented.     

MCP算法与计算实现:一个示例

混合互补问题(MCP)可以用来描述多种类型的经济模型。本文介绍了MCP的一般形式,及由一般形式推导出的几种常用MCP表达形式。在此基础上,针对一个运输问题,分别采用线性规划与MCP方法求解。特别地,给出了求解该运输问题两种算法的GAMS代码,供读者借鉴。     

Optimal way of selecting cities and conveyances for supplying coal in uncertain environment

In this paper, the limitations and shortcomings of the existing methods for solving fuzzy solid transportation problem are pointed out and to overcome these shortcomings, a new method is proposed for solving fuzzy solid transportation problem. The advantages of the proposed method over the existing methods are discussed. To illustrate the proposed method, an existing fuzzy solid transportation problem is solved. Also, to show the application of the proposed method in real life problems an existing real life fuzzy solid transportation problem is solved by the proposed method.     

Compact Mathematical Formulation for Graph Partitioning

The graph partitioning problem consists of dividing the vertices of a graph into clusters, such that the weight of the edges crossing between clusters is minimized. We present a new compact mathematical formulation of this problem, based on the use of binary representation for the index of clusters assigned to vertices. This new formulation is almost minimal in terms of the number of variables and constraints and of the density of the constraint matrix. Its linear relaxation brings a very fast computational resolution, compared with the standard one.Experiments were conducted on classical large benchmark graphs designed for comparing heuristic methods. On one hand, these experiments show that the new formulation is surprisingly less time efficient than expected on general k-partitioning problems. On the other hand, the new formulation applied on bisection problems allows to obtain the optimum solution for about ten instances, where only best upper bounds were previously known.