The allocation of shared fixed costs

We consider the problem of sharing the fixed costs of facilities among a number of users. Typically the users have a benefit or revenue from the use of the facilities. Although the problem can be formulated and solved as an integer programme this provides limited accounting information. Such information is often needed in order to (i) decide on which facilities are viable and (ii) to charge the users. It is shown that it is impossible to meet both these needs in a satisfactory way. We examine different ways of partially meeting them. In addition, we consider the issue of fairness among different possible cost allocations and how such ‘fair’ costs may be derived.     

A Lagrangean heuristic algorithm for disassembly scheduling with capacity constraints

This paper considers the problem of determining the disassembly schedule (quantity and timing) of products in order to satisfy the demand of their parts or components over a finite planning horizon. The objective is to minimize the sum of set-up, disassembly operation, and inventory holding costs. As an extension of the uncapacitated versions of the problem, we consider the resource capacity restrictions over the planning horizon. An integer program is suggested to describe the problem mathematically, and to solve the problem, a heuristic is developed using a Lagrangean relaxation technique together with a method to find a good feasible solution while considering the trade-offs among different costs. The effectiveness of the algorithm is tested on a number of randomly generated problems and the test results show that the heuristic suggested in this paper can give near optimal solutions within a short amount of computation time.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （Part Ⅱ Heuristics for the General Case）

A single machine scheduling problem with controllable processing times and compression costs is considered. The objective is to find an optimal sequence to minimize the cost ofcompletion times and the cost of compression. The complexity of this problem is still unknown.In Part Ⅱ of this paper,the authors have considered a special case where the compression timesand the compression costs are equal among all jobs. Such a problem appears polynomiafiy solvable by developing an O(n^2) algorithm. In this part(Part Ⅱ ),a general case where the controllable processing times and the compression costs are not equal is discussed. Authors proposehere two heuristics with the first based on some previous work and the second based on the algorithm developed in Part Ⅱ . Computational results are presented to show the efficiency and therobustness of these heuristics.     

A facility location model with safety stock costs: analysis of the cost of single-sourcing requirements

We consider a supply chain setting where multiple uncapacitated facilities serve a set of customers with a single product. The majority of literature on such problems requires assigning all of any given customer??s demand to a single facility. While this single-sourcing strategy is optimal under linear (or concave) cost structures, it will often be suboptimal under the nonlinear costs that arise in the presence of safety stock costs. Our primary goal is to characterize the incremental costs that result from a single-sourcing strategy. We propose a general model that uses a cardinality constraint on the number of supply facilities that may serve a customer. The result is a complex mixed-integer nonlinear programming problem. We provide a generalized Benders decomposition algorithm for the case in which a customer??s demand may be split among an arbitrary number of supply facilities. The Benders subproblem takes the form of an uncapacitated, nonlinear transportation problem, a relevant and interesting problem in its own right. We provide analysis and insight on this subproblem, which allows us to devise a hybrid algorithm based on an outer approximation of this subproblem to accelerate the generalized Benders decomposition algorithm. We also provide computational results for the general model that permit characterizing the costs that arise from a single-sourcing strategy.     

Variance minimization for constrained discounted continuous-time MDPs with exponentially distributed stopping times

This paper deals with minimization of the variances of the total discounted costs for constrained Continuous-Time Markov Decision Processes (CTMDPs). The costs consist of cumulative costs incurred between jumps and instant costs incurred at jump epochs. We interpret discounting as an exponentially distributed stopping time. According to existing theory, for the expected total discounted costs optimal policies exist in the forms of randomized stationary and switching stationary policies. While the former is typically unique, the latter forms a finite set whose number of elements grows exponentially with the number of constraints. This paper investigates the problem when the process stops immediately after the first jump. For costs up to the first jump we provide an index for selection of actions by switching stationary policies and show that the indexed switching policy achieves a smaller variance than the randomized stationary policy. For problems without instant costs, the indexed switching policy achieves the minimum variance of costs up to the first jump among all the equivalent switching policies.     

Heuristics with guaranteed performance bounds for a manufacturing system with product recovery

We consider a manufacturing system with product recovery. The system manufactures a new product as well as remanufactures the product from old, returned items. The items remanufactured with the returned products are as good as new and satisfy the same demand as the new item. The demand rate for the new item and the return rate for the old item are deterministic and constant. The relevant costs are the holding costs for the new item and the returned item, and the fixed setup costs for both manufacturing and remanufacturing. The objective is to determine the lot sizes and production schedule for manufacturing and remanufacturing so as to minimize the long-run average cost per unit time. We first develop a lower bound among all classes of policies for the problem. We then show that the optimal integer ratio policy for the problem obtains a solution whose cost is at most 1.5% more than the lower bound.     

Inventory sharing in integrated network design and inventory optimization with low-demand parts

Service Parts Logistics (SPL) problems induce strong interaction between network design and inventory stocking due to high costs and low demands of parts and response time based service requirements. These pressures motivate the inventory sharing practice among stocking facilities. We incorporate inventory sharing effects within a simplified version of the integrated SPL problem, capturing the sharing fill rates in 2-facility inventory sharing pools. The problem decides which facilities in which pools should be stocked and how the demand should be allocated to stocked facilities, given full inventory sharing between the facilities within each pool so as to minimize the total facility, inventory and transportation costs subject to a time-based service level constraint. Our analysis for the single pool problem leads us to model this otherwise non-linear integer optimization problem as a modified version of the binary knapsack problem. Our numerical results show that a greedy heuristic for a network of 100 facilities is on average within 0.12% of the optimal solution. Furthermore, we observe that a greater degree of sharing occurs when a large amount of customer demands are located in the area overlapping the time windows of both facilities in 2-facility pools.     

Multicriteria ranking of alternative locations for small scale hydro plants

Since energy consumption and its costs have recently rapidly increased, ‘small scale’ hydroplants (HP) are being widely used as energy sources. Our objective is to deal with the problem of small HP construction in a wide area covering many regions. The problem is to select some locations for each region by using the same methodology in order to make the unit costs as low as possible. When considering this problem, besides economical criteria, some other criteria must also be taken into account, such as technical, social, environmental etc. Multicriteria analysis is a quite realistic approach to such a complex problem which includes, among the others, some conflicting criteria. We have found that the Promethee method is well adapted to this problem, since its flexibility enables the decision maker to express precisely his preferences and stable results can be easily obtained by a sensitivity analysis. In this paper the problem is formulated, the criteria are estimated and quantified, and location planning is obtained by using the Promethee methodology. The obtained solutions are discussed and the computational results are given.     

基于AGV的智能仓库系统订单分批问题研究

研究了基于自动引导小车(AGV)的“货到人”智能仓库订单分批拣选问题, 在同时考虑工作人员拣选商品成本和AGV搬运货架成本的前提下, 建立了以总成本极小化为目标函数的订单分批问题整数规划模型。根据订单中包含的商品信息和商品所在的货架信息构建了描述订单之间关系的加权相似度指标, 分析了加权相似度与总拣选成本之间的正相关关系。基于订单之间的加权相似度设计了求解模型的贪婪算法。利用具体算例进行模拟计算, 分析了加权系数的变化对订单分批结果的影响, 以及加权系数λ的取值与工作人员拣取一件商品的成本c₁和AGV搬运一次货架的成本c₂之间的关系, 得到了贪婪算法中加权系数λ的确定方法。进一步分析了贪婪算法的计算时间和计算效果, 结果显示, 通过适当选取加权系数, 利用贪婪算法可以在短时间内得到订单分批问题的近似最优解;对于小规模算例, 贪婪算法在最坏情况下近似比不超过1.35。利用本文的模型和算法进行订单分批, 兼顾了工作人员拣取商品的成本和AGV搬运货架的成本, 可以有效提高订单拣选效率, 降低订单拣选总成本。     

Bounds on stochastic convex allocation problems

We consider a stochastic convex program arising in a certain resource allocation problem. The uncertainty is in the demand for a resource which is to be allocated among several competing activities under convex inventory holding and shortage costs. The problem is cast as a two–period stochastic convex program and we derive tight upper and lower bounds to the problem using marginal distributions of the demands, which may be stochastically dependent. It turns out that these bounds are tighter than the usual bounds in the literature which are based on limited moment information of the underlying random variables. Numerical examples illustrate the bounds.     

Routing and capacity assignment in backbone communication networks under time varying traffic conditions

This paper studies the problem of assigning capacities to links in a backbone communication network and determining the routes used by messages for all communicating node pairs in the network under time varying traffic conditions. The best routes are to be chosen from among all possible routes in the network. Tradeoffs between link costs and response time to users are achieved by specifying an upper limit on the average link queueing delay in the network. The goal is to minimize total link fixed and variable costs. The topology of the network and the end-to-end traffic requirements during the different busy-hours are assumed to be known. The problem is formulated as a mathematical programming model. An efficient solution procedure based on a Lagrangian relaxation of the problem is developed. The results of extensive computational experiments across a variety of networks are reported. These results indicate that the solution procedure is effective for a wide range of traffic loads and cost structures.     

Allocating the fixed cost as a complement of other cost inputs: A DEA approach

In cost allocation problem, traditional DEA approaches allocate the fixed cost among a group of decision making units (DMUs), and treat the allocated cost as an extra input of each DMU. If costs except for the fixed cost are regarded as inputs in the cost allocation problem, then it is obvious that the fixed cost is a complement of other inputs rather than an extra independent input. Therefore it is necessary to combine the allocated cost with other cost measures in cost allocation problem. Based on this observation, this paper investigates the relationship between the allocated cost and the DEA efficiency score and develops a DEA-based approach to allocate the fixed cost among various DMUs. An example of allocating advertising expenditure between a car manufacturer and its dealers is presented to illustrate the method proposed in this paper.     

FLEXIBLE TECHNOLOGY AND THE COST OF IMPROVING GROUNDWATER QUALITY

Contamination of groundwater by agricultural and industrial chemicals is a significant public health problem in the United States and other nations. In recent years, regulations regarding acceptable groundwater quality, particularly for drinking water, have proliferated in response to heightened public awareness of health risks. To minimize the burden on the economy of providing high-quality water, it is necessary to be creative with regard to cleanup strategies. Making treatment technology flexible can reduce the cost of improving groundwater quality by avoiding unnecessary duplication of fixed costs. We consider two types of flexibility. The first is mobility of treatment technology among locations within a single water delivery system. We calculate the costs of compliance with drinking water quality regulations when treatment technologies are fixed and when they are mobile between locations, and show that mobility has significant economic advantages. The second type of flexibility is mobility among water delivery systems, which we capture through a regional rental market for treatment devices. We show that, under certain conditions, rental markets for treatment technology can lower the costs of improving water quality.     

A multi-stage and multi-supplier inventory model allowing different order quantities

This paper addresses a multi-stage inventory model that allows different order quantities among the selected suppliers to obtain the optimal solutions. To achieve the objective of the study, the single-objective and multi-objective methods are adopted for suitable real-world applications. With respect to a single-objective method, this paper aims to minimize the total ordering costs, holding costs, and purchasing costs, subject to the price, quality, and capacity. With respect to a multi-objective method, it focuses on cost minimization, as well as quality and capacity maximization. The proposed model not only considers the allocation of different order quantities among the selected suppliers, but also incorporates the multi-stage inventory problem. Furthermore, a numerical example is provided to illustrate the usefulness of the proposed model and a comparative understanding of various methods. In addition, a simulation test is performed to effectively validate the proposed model which outperforms the previous works. Finally, a sensitivity analysis is carried out to investigate the impact of supply chain cost.     

关于可靠性设施布局问题的近似算法

设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中, 受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障, 故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法, 是一个很大的进步.     

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.     

Minimizing fleet operating costs for a container transportation company

This paper focuses on a fleet management problem that arises in container trucking industry. From the container transportation company perspective, the present and future operating costs to minimize can be divided in three components: the routing costs, the resource (i.e., driver and truck) assignment costs and the container repositioning costs (i.e., the costs of restoring a given container fleet distribution over the serviced territory, as requested by the shippers that own the containers).This real-world problem has been modeled as an integer programming problem. The proposed solution approach is based on the decomposition of this problem in three simpler sub-problems associated to each of the costs considered above.Numerical experiments on randomly generated instances, as well as on a real-world data set of an Italian container trucking company, are presented.     

Matheuristic for the decentralized factories scheduling problem

In this study, a novel mixed integer linear programming (MILP) model is developed for the decentralized factories scheduling problem, where a set of transporters is used for shipping goods among parallel factories to minimize the production costs over all of the factories. Due to its typical features, such as multiple heterogeneous factories and transportation times, this problem is extremely difficult to solve, especially for large-scale problems. In order to address this difficulty, the main aim of this study is to develop a new solution algorithm based on the interoperation of metaheuristics and mathematical programming techniques to minimize the production costs for jobs. The algorithm comprises an electromagnetism-like algorithm and variable neighborhood search. In this hybridization based on MILP relaxation, the guiding principle involves the ordering of neighborhood structures. The results obtained by the proposed algorithm and MILP are analyzed and compared for various test problems.     

The inventory replenishment planning and staggering problem: a bi-objective approach

To the best of our knowledge, this paper is the first one to suggest formulating the inventory replenishment problem as a bi-objective decision problem where, in addition to minimizing the sum of order and inventory holding costs, we should minimize the required storage space. Also, it develops two solution methods, called the exploratory method (EM) and the two-population evolutionary algorithm (TPEA), to solve the problem. The proposed methods generate a near-Pareto front of solutions with respect to the considered objectives. As the inventory replenishment problem have never been formulated as a bi-objective problem and as the literature does not provide any method to solve the considered bi-objective problem, we compared the results of the EM to three versions of the TPEA. The results obtained suggest that although the TPEA produces good near-Pareto solutions, the decision maker can apply a combination of both methods and choose among all the obtained solutions.     

Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach

We study a vehicle routing problem with soft time windows and stochastic travel times. In this problem, we consider stochastic travel times to obtain routes which are both efficient and reliable. In our problem setting, soft time windows allow early and late servicing at customers by incurring some penalty costs. The objective is to minimize the sum of transportation costs and service costs. Transportation costs result from three elements which are the total distance traveled, the number of vehicles used and the total expected overtime of the drivers. Service costs are incurred for early and late arrivals; these correspond to time-window violations at the customers. We apply a column generation procedure to solve this problem. The master problem can be modeled as a classical set partitioning problem. The pricing subproblem, for each vehicle, corresponds to an elementary shortest path problem with resource constraints. To generate an integer solution, we embed our column generation procedure within a branch-and-price method. Computational results obtained by experimenting with well-known problem instances are reported.