Scheduling policies for a repair shop problem

In this paper, we analyze a repair shop serving several fleets of machines that fail from time to time. To reduce downtime costs, a continuous-review spare machine inventory is kept for each fleet. A spare machine, if available on stock, is installed instantaneously in place of a broken machine. When a repaired machine is returned from the repair shop, it is placed in inventory for future use if the fleet has the required number of machines operating. Since the repair shop is shared by different fleets, choosing which type of broken machine to repair is crucial to minimize downtime and holding costs. The optimal policy of this problem is difficult to characterize, and, therefore, is only formulated as a Markov Decision Process to numerically compute the optimal cost and base-stock level for each spare machine inventory. As an alternative, we propose the dynamic Myopic(R) policy, which is easy to implement, yielding costs very close to the optimal. Most of the time it outperforms the static first-come-first-served, and preemptive-resume priority policies. Additionally, via our numerical study, we demonstrate that repair shop pooling is better than reserving a repair shop for each fleet.     

Capacitated location model with online demand pooling in a multi-channel supply chain

This paper presents a location model that assigns online demands to the capacitated regional warehouses currently serving in-store demands in a multi-channel supply chain. The model explicitly considers the trade-off between the risk pooling effect and the transportation cost in a two-echelon inventory/logistics system. Keeping the delivery network of the in-store demands unchanged, the model aims to minimize the transportation cost, inventory cost, and fixed handling cost in the system when assigning the online demands. We formulate the assignment problem as a non-linear integer programming model. Lagrangian relaxation based procedures are proposed to solve the model, both the general case and an important special case. Numerical experiments show the efficiency of our algorithms. Furthermore, we find that because of the pooling effect the variance of in-store demands currently served by a warehouse is an important parameter of the warehouse when it is considered as a candidate for supplying online demands. Highly uncertain in-store demands, as well as low transportation cost per unit, can make a warehouse appealing. We illustrate with numerical examples the trade-off between the pooling effect and the transportation cost in the assignment problem. We also evaluate the cost savings between the policy derived from the model, which integrates the transportation cost with the pooling effect, and the commonly used policy, which is based only on the transportation cost. Results show that the derived policy can reduce 1.5–7.5% cost in average and in many instances the percentage of cost savings is more than 10%.     

Minimizing the Total Cost in an Integrated Vendor—Managed Inventory System

In this paper we consider a complex production-distribution system, where a facility produces (or orders from an external supplier) several items which are distributed to a set of retailers by a fleet of vehicles. We consider Vendor-Managed Inventory (VMI) policies, in which the facility knows the inventory levels of the retailers and takes care of their replenishment policies. The production (or ordering) policy, the retailers replenishment policies and the transportation policy have to be determined so as to minimize the total system cost. The cost includes the fixed and variable production costs at the facility, the inventory costs at the facility and at the retailers and the transportation costs, that is the fixed costs of the vehicles and the traveling costs. We study two different types of VMI policies: The order-up-to level policy, in which the order-up-to level quantity is shipped to each retailer whenever served (i.e. the quantity delivered to each retailer is such that the maximum level of the inventory at the retailer is reached) and the fill-fill-dump policy, in which the order-up-to level quantity is shipped to all but the last retailer on each delivery route, while the quantity delivered to the last retailer is the minimum between the order-up-to level quantity and the residual transportation capacity of the vehicle. We propose two different decompositions of the problem and optimal or heuristic procedures for the solution of the subproblems. We show that, for reasonable initial values of the variables, the order in which the subproblems are solved does not influence the final solution. We will first solve the distribution subproblem and then the production subproblem. The computational results show that the fill-fill-dump policy reduces the average cost with respect to the order-up-to level policy and that one of the decompositions is more effective. Moreover, we compare the VMI policies with the more traditional Retailer-Managed Inventory (RMI) policy and show that the VMI policies significantly reduce the average cost with respect to the RMI policy.     

Equilibria for Pooling Situations

This paper deals with pooling situations, which can be considered as exchange economies with indivisible goods and money, and two related cooperative games which we refer to as pooling games with individual rights and pooling games without individual rights. It is shown that the classes of pooling games without individual rights and transportation games coincide and are contained in the class of pooling games with individual rights. With tools from discrete convexity theory, it is proved that competitive equilibria for pooling situations exist. As a consequence, an alternative proof of the nonemptiness of the core of pooling games is provided.     

The stochastic location model with risk pooling

In this paper, we present a stochastic version of the location model with risk pooling (LMRP) that optimizes location, inventory, and allocation decisions under random parameters described by discrete scenarios. The goal of our model (called the stochastic LMRP, or SLMRP) is to find solutions that minimize the expected total cost (including location, transportation, and inventory costs) of the system across all scenarios. The location model explicitly handles the economies of scale and risk-pooling effects that result from consolidating inventory sites. The SLMRP framework can also be used to solve multi-commodity and multi-period problems.     

Partial Pooling in Tandem Lines with Cooperation and Blocking

For a tandem line of finite, single-server queues operating under the production blocking mechanism, we study the effects of pooling several adjacent stations and the associated servers into a single station with a single team of servers. We assume that the servers are cross-trained (so that they can work at several different stations) and that two or more servers can cooperate on the same job. For such a system, we provide sufficient conditions on the service times and sizes of the input and output buffers at the pooled station under which pooling will decrease the departure time of each job from the system (and hence increase the system throughput). We also show that pooling decreases the total number of jobs in the system at any given time and the sojourn time of each job in the system if the departure time of each job from the system is decreased by pooling and there is an arrival stream at the first station. Moreover, we provide sufficient conditions under which pooling will improve the holding cost of each job in the system incurred before any given time, and extend our results to closed tandem lines and to queueing networks with either a more general blocking mechanism or probabilistic routing. Finally, we present a numerical study aimed at quantifying the improvements in system performance obtained through pooling and at understanding which stations should be pooled to achieve the maximum benefit. Our results suggest that the improvements gained by pooling may be substantial and that the bottleneck station should be among the pooled stations in order to obtain the greatest benefit. AMS subject classification: 90B22     

Ad hoc heuristic for the cover printing problem

We address an NP-hard combinatorial optimization problem arising in a printing shop. An impression grid is composed by a set of plates. The cover printing problem consists in designing the composition of impression grids, and determining the number of times each grid is to be printed in order to fulfill the demand of different book covers at minimum total printing cost; the latter comes from three fixed costs: for printing one sheet, for producing one plate, and for composing one impression grid. For each cover an unlimited number of plates can be made. To deal with this challenging problem we present an ad hoc heuristic that outperforms all previously proposed approaches, including genetic algorithms, GRASP, and simulated annealing.     

Cooperative game theory approach to allocating benefits of horizontal cooperation

Logistics costs in general, and transportation costs in particular, represent a large fraction of the operating costs of many companies. One way to try to reduce these costs is through horizontal cooperation among shippers. Thus, when the transportation needs of two or more companies are merged, their collective transportation requirements can be met at lower cost. The attainable cost savings are due to economies of scale, which translate into cheaper rates due to increased negotiation power, use of larger vehicles and bundling of shipments. In this paper, a linear model is presented and used to study the cost savings that different companies may achieve when they merge their transportation requirements. On the one hand, solving this optimization model for different collaboration scenarios allows testing and quantifying the synergies among different potential partners, thus identifying the most profitable collaboration opportunities. On the other, the problem of allocating the joint cost savings of the cooperation is tackled using cooperative game theory. The proposed approach is illustrated with an example in which different cooperative game solution concepts are compared. Extensive numerical experiments have also been carried out to gain insight into the properties of the corresponding cost savings game and the behavior of the different solution concepts.     

基于离散与连续选址相结合的平面选址问题研究——以华北石油局大牛地气田污水处理厂选址为例

选址问题的研究中,大多考虑的是理论距离(例如欧式距离等);但在实际问题中,真实的公路运输距离和理论距离有较大差异,并且修建公路的成本较高.在尽量利用当前的公路交通网络同时,又能得到最优选址,在现实中具有重要意义.以华北石油局大牛地气田第一采气厂污水处理厂选址为例,分别采用重心法选址、最大值最小化选址、多目标选址等选址的方法得到污水处理厂的备选点,并结合实际距离模拟出了各个备选点的运输费用,再综合考虑当地政策和交通状况等因素,最终得到了使得运输费用最低的新的污水处理厂的位置坐标P(9.33,11.79),在该位置建立污水处理厂比之前的运输方案每年大约可节约511万元的运输费用.方法最大的优点是减小了在选址过程中理论距离与实际距离的误差,在现实中具有一定的指导意义.     

A combinatorial approach to level of repair analysis

This paper presents an approach to optimise level of repair decisions taking into account submodular properties of standard life cycle cost functions, which include fixed and variable costs. It proposes an integer programming formulation to solve level of repair problems for multi-echelon multi-indenture level systems. The method converges quickly to the optimum solution relying on heuristics to obtain tight bounds for a subsequent branch-and-bound procedure. A software package called level of repair optimisation model (LOROM) was developed to implement the branch-and-bound method that does not rely on linear programming relaxations. This approach is rather generic and can be applied to a wide class of problems with convex total cost functions such as plant location problems or transportation problems with fixed costs.     

Location-allocation on a line with demand-dependent costs

This paper extends the location-allocation formulation by making the cost charged to users by a facility a function of the total number of users patronizing the facility. Users select their facility based on facility charges and transportation costs. We explore equilibria where each customer selects the least expensive facility (cost and transportation) and where the facility is at a point that minimizes travel costs for its customers. The problem in its general form is quite complex. An interesting special case is studied: facilities and customers are located on a finite line segment and demand is distributed on the line by a given density function.     

Layout designs in cellular manufacturing

Cellular manufacturing (CM) is now an established international practice to integrate: equipment, people, and systems into `focused factories', `mini-businesses' or `cells' with clear customers, responsibilities and boundaries. The major elements in exploiting the benefits of CM is efficient layout designs. This paper presents the application of recently developed multi-objective inter- and intra-cell layout designs methodologies in a CM environment by the author to a dynamic food manufacturing and packaging company in Australia. Some of the problems expressed by the company were large and unnecessary volume of shop floor material handling cost, difficulties and confusion over production planning, long products lead times resulting in losing customers and high overhead costs. Furthermore the company was deeply concerned about the increasing number of accidents and injuries on the shop floor caused by poor layout of machinery and the lack of proper aisle structures for movement of the lift-trucks. This paper shows the process of developing the final inter-cell layout designs by providing the management with multiple layout configurations and showing the impact of each design on the material handling cost at each stage. These solutions not only provide a safer shop floor but also significant reductions in material handling cost, waste, need for large capital investment and the number of lift-trucks needed on the shop floor.     

Controlling multi-indenture repairable inventories of multiple aircraft parts

This paper presents a model for determining stock levels of repairable items supporting a fleet of commercial aircraft operated by a transportation company in the Philippines. The items are characterised by infrequent demand, high cost and a hierarchical (or indentured) structure. The system has three re-supply sources of serviceable parts, namely, the in-house repair shop, the out-house repair shops, and the suppliers. Non-repairable items are scrapped and replaced with new items on a one-for-one basis. The model considers two levels of indenture represented by modules and components. The objective is to minimise the total expected steady-state annual cost of holding inventories and of aircraft delays. A minimum requirement on module availability is also applied. The formulation is such that the regular discrete optimisers available could not be readily used to solve it. The model is implemented on an illustrative problem, employing an integer search for the item stock levels within a limited range.     

Lower bounds for the two-stage uncapacitated facility location problem

In the two-stage uncapacitated facility location problem, a set of customers is served from a set of depots which receives the product from a set of plants. If a plant or depot serves a product, a fixed cost must be paid, and there are different transportation costs between plants and depots, and depots and customers. The objective is to locate plants and depots, given both sets of potential locations, such that each customer is served and the total cost is as minimal as possible. In this paper, we present a mixed integer formulation based on twice-indexed transportation variables, and perform an analysis of several Lagrangian relaxations which are obtained from it, trying to determine good lower bounds on its optimal value. Computational results are also presented which support the theoretical potential of one of the relaxations.     

Optimisation of integrated reverse logistics networks with different product recovery routes

The awareness of importance of product recovery has grown swiftly in the past few decades. This paper focuses on a problem of inventory control and production planning optimisation of a generic type of an integrated Reverse Logistics (RL) network which consists of a traditional forward production route, two alternative recovery routes, including repair and remanufacturing and a disposal route. It is assumed that demand and return quantities are uncertain. A quality level is assigned to each of the returned products. Due to uncertainty in the return quantity, quantity of returned products of a certain quality level is uncertain too. The uncertainties are modelled using fuzzy trapezoidal numbers. Quality thresholds are used to segregate the returned products into repair, remanufacturing or disposal routes. A two phase fuzzy mixed integer optimisation algorithm is developed to provide a solution to the inventory control and production planning problem. In Phase 1, uncertainties in quantity of product returns and quality of returns are considered to calculate the quantities to be sent to different recovery routes. These outputs are inputs into Phase 2 which generates decisions on component procurement, production, repair and disassembly. Finally, numerical experiments and sensitivity analysis are carried out to better understand the effects of quality of returns and RL network parameters on the network performance. These parameters include quantity of returned products, unit repair costs, unit production cost, setup costs and unit disposal cost.     

Inventory sharing via circular unidirectional chaining

This research studies the performance of circular unidirectional chaining – a “lean” configuration of lateral inventory sharing among retailers or warehouses – and compares its performance to that of no pooling and complete pooling in terms of expected costs and optimal order quantities. Each retailer faces uncertain demand, and we wish to minimize procurement, shortage and transshipment costs. In a circular unidirectional chain all retailers are connected in a closed loop, so that each retailer can cooperate with exactly two others as follows: receive units (if needed?available) from the left “neighbor” and send units (if needed?available) to the right, and a retailer who receives units from one neighbor is not allowed to send any units to its other neighbor. If the chain consists of at least three nodes and demands across nodes are i.i.d., its performance turns out to be independent of the number of nodes. The optimal stocking is therefore solved analytically. Analytical comparative statics with respect to cost parameters and demand distributions are provided. We also examine thoroughly the cases of uniform demand distribution (analytically) and normal demand distribution (numerically). In the uniform case with free transshipment, a unidirectional chain can save up to 1/3 of the expected cost of separate newsvendors caused by uncertainty. For three nodes, the advantage of complete pooling over unidirectional chaining does not exceed 19%.     

Complexity of flow shop scheduling problems with transportation constraints

In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another by transporters such as Automated Guided Vehicles, robots and conveyors, and finished jobs are delivered to warehouses or customers by vehicles such as trucks.This paper investigates two-machine flow shop scheduling problems taking transportation into account. The finished jobs are transferred from the processing facility and delivered to customers by truck. Both transportation capacity and transportation times are explicitly taken into account in these models. We study the class of flow shop problems by analysing their complexity. For the makespan objective function, we prove that this problem is strongly NP-hard when the capacity of a truck is limited to two or three parts with an unlimited buffer at the output of the each machine. This problem with additional constraints, such as blocking, is also proven to be strongly NP-hard.     

Cost allocation in inventory transportation systems

In this paper, we deal with the cost allocation problem arising in an inventory transportation system with a single item and multiple agents that place joint orders using an EOQ policy. In our problem, the fixed-order cost of each agent is the sum of a first component (common to all agents) plus a second component which depends on the distance from the agent to the supplier. We assume that agents are located on a line route, in the sense that if any subgroup of agents places a joint order, its fixed cost is the sum of the first component plus the second component of the agent in the group at maximal distance from the supplier. For these inventory transportation systems, we introduce and characterize a rule which allows us to allocate the costs generated by the joint order. This rule has the same flavor as the Shapley value, but requires less computational effort. We show that our rule has good properties from the point of view of stability.     

Solving the robust two-stage capacitated facility location problem with uncertain transportation costs

In this study, we start from a multi-source variant of the two-stage capacitated facility location problem (TSCFLP) and propose a robust optimization model of the problem that involves the uncertainty of transportation costs. Since large dimensions of the robust TSCFLP could not be solved to optimality, we design a memetic algorithm (MA), which represents a combination of an evolutionary algorithm (EA) and a modified simulated annealing heuristic (SA) that uses a short-term memory of undesirable moves from previous iterations. A set of computational experiments is conducted to examine the impact of different protection levels on the deviation of the objective function value. We also investigate the impact of variations of transportation costs that may occur on both transhipment stages on the total cost for a fixed protection level. The obtained results may help in identifying a sustainable and efficient strategy for designing a two stage capacitated transportation network with uncertain transportation costs, and may be applicable in the design and management of similar transportation networks.     

A multi-commodity flow formulation for the generalized pooling problem

The pooling problem is an extension of the minimum cost network flow problem where the composition of the flow depends on the sources from which it originates. At each source, the composition is known. In all other nodes, the proportion of any component is given as a weighted average of its proportions in entering flow streams. The weights in this average are simply the arc flow. At the terminals of the network, there are bounds on the relative content of the various components. Such problems have strong relevance in e.g. planning models for oil refining, and in gas transportation models with quality constraints at the reception side. Although the pooling problem has bilinear constraints, much progress in solving a class of instances to global optimality has recently been made. Most of the approaches are however restricted to networks where all directed paths have length at most three, which means that there is no connection between pools. In this work, we generalize one of the most successful formulations of the pooling problem, and propose a multi-commodity flow formulation that makes no assumptions on the network topology. We prove that our formulation has stronger linear relaxation than previously suggested formulations, and demonstrate experimentally that it enables faster computation of the global optimum.