下料问题与运输问题联合优化建模

本文研究了考虑子材运输的标准一维下料问题。建立了由生产商负责运输时,标准一维下料与运输协调优化整数规划模型,最小化母材使用成本,子材库存成本及子材运输成本。采用拉格朗日松弛技术对有关约束进行松弛和模型分解,设计基于序列规则和FFD规则的混合启发式算法求解模型。该算法由两部分组成,分别用于求解标准一维下料子问题和卖方运输子问题。通过随机产生的1800个算例,验证模型合理性与算法的有效性。与基于列生成法的两阶段算法解进行比较,平均总成本降低了17.57%,表明集成算法优于两阶段算法。     

Supply Chain Scheduling: Distribution Systems

We study conflict and cooperation issues arising in a supply chain where a manufacturer makes products which are shipped to customers by a distributor. The manufacturer and the distributor each has an ideal schedule, determined by cost and capacity considerations. However, these two schedules are in general not well coordinated, which leads to poor overall performance. In this context, we study two practical problems. In both problems, the manufacturer focuses on minimizing unproductive time. The distributor minimizes customer cost measures in the first problem and minimizes inventory holding cost in the second problem. We first evaluate each party's conflict, which is the relative increase in cost that results from using the other party's optimal schedule. Since this conflict is often significant, we consider several practical scenarios about the level of cooperation between the manufacturer and the distributor. These scenarios define various scheduling problems for the manufacturer, the distributor, and the overall system. For each of these scheduling problems, we provide an algorithm. We demonstrate that the cost saving provided by cooperation between the decision makers is usually significant. Finally, we discuss the implications of our work for how manufacturers and distributors negotiate, coordinate, and implement their supply chain schedules in practice.     

CHEXPEDITE: A COMPUTER-BASED APPROACH TO THE BANK COURIER PROBLEM

This paper presents a successful computer-based approach to scheduling courier vehicles for the check collection system in multibranch commercial banks. The approach has been adopted by six large banks in the United States and has achieved dramatic cost savings at several of these banks. This paper begins by describing the bank courier problem and reviewing several approaches to the problem that have been proposed in the literature. A practical, computer-based approach to the bank courier problem is then presented. Finally, implementation experience at several banks is overviewed.     

Online bin packing of fragile objects with application in cellular networks

We study a specific bin packing problem which arises from the channel assignment problems in cellular networks. In cellular communications, frequency channels are some limited resource which may need to share by various users. However, in order to avoid signal interference among users, a user needs to specify to share the channel with at most how many other users, depending on the user’s application. Under this setting, the problem of minimizing the total channels used to support all users can be modeled as a specific bin packing problem as follows: Given a set of items, each with two attributes, weight and fragility. We need to pack the items into bins such that, for each bin, the sum of weight in the bin must be at most the smallest fragility of all the items packed into the bin. The goal is to minimize the total number of bins (i.e., the channels in the cellular network) used. We consider the on-line version of this problem, where items arrive one by one. The next item arrives only after the current item has been packed, and the decision cannot be changed. We show that the asymptotic competitive ratio is at least 2. We also consider the case where the ratio of maximum fragility and minimum fragility is bounded by a constant. In this case, we present a class of online algorithms with asymptotic competitive ratio at most of 1/4+3r/2, for any r>1. A preliminary version of this paper appeared in Proc. of Workshop on Internet and Network Economics (WINE’05, pp. 564–573). The research of W.-T.C. was supported in part by Hong Kong RGC grant HKU5172/03E. The research of F.Y.-L.C. was supported in part by Hong Kong RGC Grant HKU7142/03E. The research of D.Y. was supported by NSFC (10601048). The research of G.Z. was supported in part by NSFC (60573020).     

Logic-based Benders decomposition for an inventory-location problem with service constraints

We study an integrated inventory-location problem with service requirements faced by an aerospace company in designing its service parts logistics network. Customer demand is Poisson distributed and the service levels are time-based leading to highly non-linear, stochastic service constraints and a nonlinear, mixed-integer optimization problem. Unlike previous work in the literature, which propose approximations for the nonlinear constraints, we present an exact solution methodology using logic-based Benders decomposition. We decompose the problem to separate the location decisions in the master problem from the inventory decisions in the subproblem. We propose a new family of valid cuts and prove that the algorithm is guaranteed to converge to optimality. This is the first attempt to solve this type of problem exactly. Then, we present a new restrict-and-decompose scheme to further decompose the Benders master problem by part. We test on industry instances as well as random instances. Using the exact algorithm and restrict-and-decompose scheme we are able to solve industry instances with up to 60 parts within reasonable time, while the maximum number of parts attempted in the literature is 5.     

Inventory Control with a Fixed Cost and a Piecewise Linear Convex Cost

This paper studies the optimal policy for a periodic‐review inventory system in which the production costs consist of a fixed cost and a piecewise linear convex variable cost. Such a cost function can arise from alternate sources of supply or from the use of overtime production. We fully characterize the structure of the optimal policy for the single‐period problem. For the multi‐period problem, the optimal policy can have disconnected production regions and complicated optimal produce‐up‐to levels, which implies that implementation of the optimal policy may not be practical. Fortunately, careful investigation shows that the optimal policy has some interesting properties. The structure of the optimal policy outlined by these properties leads to a practical and close‐to‐optimal heuristic policy. In an extensive numerical study, the average gap is only 0.02% and the worst gap is 1.37%.     

基于动态博弈的闭环供应链回收质量控制研究

本文采用三阶段的动态博弈模型,研究了在单个制造商和单个销售商构成的分散式闭环供应链中,占主导地位的制造商如何制定质量处罚比例和质量抽检比例,从而对销售商回收的废旧产品数量和质量实施引导和控制。本文建立了相应的模型并给出了最优解,并通过算例讨论了不同的废旧产品缺陷率和监督成本对双方决策的影响。     

Bin packing under linear constraints

In this paper, we study a bin packing problem in which the sizes of items are determined by k linear constraints, and the goal is to decide the sizes of items and pack them into a minimal number of unit sized bins. We first provide two scenarios that motivate this research. We show that this problem is NP-hard in general, and propose several algorithms in terms of the number of constraints. If the number of constraints is arbitrary, we propose a 2-approximation algorithm, which is based on the analysis of the Next Fit algorithm for the bin packing problem. If the number of linear constraints is a fixed constant, then we obtain a PTAS by combining linear programming and enumeration techniques, and show that it is an optimal algorithm in polynomial time when the number of constraints is one or two. It is well known that the bin packing problem is strongly NP-hard and cannot be approximated within a factor 3 / 2 unless P = NP. This result implies that the bin packing problem with a fixed number of constraints may be simper than the original bin packing problem. Finally, we discuss the case when the sizes of items are bounded.     

Optimal Production and Admission Policies in Make‐to‐Stock/Make‐to‐Order Manufacturing Systems

In this article, we study optimal production and admission control policies in manufacturing systems that produce two types of products: one type consists of identical items that are produced to stock, while the other has varying features and is produced to order. The model is motivated by applications from various industries, in particular, the automobile industry, where a part supplier receives orders from both an original equipment manufacturer and the aftermarket. The product for the original equipment manufacturer is produced to stock, it has higher priority, and its demands are fully accepted. The aftermarket product is produced to order, and its demands can be either accepted or rejected. We characterize the optimal production and admission policies with a partial‐linear structure, and using computational analysis, we provide insights into the benefits of the new policies. We also investigate the impact of production capacity, cost structure, and demand structure on system performance.     

Integrated Order Scheduling and Packing

We consider an integrated production–distribution scheduling model in a make‐to‐order supply chain consisting of one supplier and one customer. The supplier receives a set of orders from the customer at the beginning of a planning horizon. The supplier needs to process all the orders at a single production line, pack the completed orders to form delivery batches, and deliver the batches to the customer. Each order has a weight, and the total weight of the orders packed in a batch must not exceed the capacity of the delivery batch. Each delivery batch incurs a fixed distribution cost. The problem is to find jointly a schedule for order processing and a way of packing completed orders to form delivery batches such that the total distribution cost (or equivalently, the number of delivery batches) is minimized subject to the constraint that a given customer service level is guaranteed. We consider two customer service constraints—meeting the given deadlines of the orders; or requiring the average delivery lead time of the orders to be within a given threshold. Several problems of the model with each of those constraints are considered. We clarify the complexity of each problem and develop fast heuristics for the NP‐hard problems and analyze their worst‐case performance bounds. Our computational results indicate that all the heuristics are capable of generating near optimal solutions quickly for the respective problems.     

Using branch-and-price approach to solve the directed network design problem with relays

We present node-arc and arc-path formulations, and develop a branch-and-price approach for the directed network design problem with relays (DNDR). The DNDR problem can be used to model many network design problems in transportation, service, and telecommunication system, where relay points are necessary. The DNDR problem consists of introducing a subset of arcs and locating relays on a subset of nodes such that in the resulting network, the total cost (arc cost plus relay cost) is minimized, and there exists a directed path linking the origin and destination of each commodity, in which the distances between the origin and the first relay, any two consecutive relays, and the last relay and the destination do not exceed a predefined distance limit. With the node-arc formulation, we can directly solve small DNDR instances using mixed integer programming solver. With the arc-path formulation, we design a branch-and-price approach, which is a variant of branch-and-bound with bounds provided by solving linear programs using column generation at each node of the branch-and-bound tree. We design two methods to efficiently price out columns and present computational results on a set of 290 generated instances. Results demonstrate that our proposed branch-and-price approach is a computationally efficient procedure for solving the DNDR problem.     

Average-Case Performance Analysis of a 2D Strip Packing Algorithm—NFDH

The two-dimensional strip packing problem is a generalization of the classic one-dimensional bin packing problem. It has many important applications such as costume clipping, material cutting, real-world planning, packing, scheduling etc. Average-case performance analysis of approximation algorithms attracts a lot of attention because it plays a crucial role in selecting an appropriate algorithm for a given application. While approximation algorithms for two-dimensional packing are frequently presented, the results of their average-case performance analyses have seldom been reported due to intractability. In this paper, we analyze the average-case performance of Next Fit Decreasing Height (NFDH) algorithm, one of the first strip packing algorithms proposed by Coffman, Jr. in 1980. We prove that the expected height of packing with NFDH algorithm, when the heights and widths of the rectangle items are independent and both obey (0, 1] uniform distribution, is about n/3, where n is the number of rectangle items. We also validate the theoretical result with experiments.This work is supported by National 973 Fundamental Research Project of China on NP Complete Problems and High Performance Software (No. G1998030403).     

Packing of Unequal Spheres and Automated Radiosurgical Treatment Planning

We study an optimization problem of packing unequal spheres into a three-dimensional (3D) bounded region in connection with radiosurgical treatment planning. Given an input (R, V, S, L), where R is a 3D bounded region, V a positive integer, S a multiset of spheres, and L a location constraint on spheres, we want to find a packing of R using the minimum number of spheres in S such that the covered volume is at least V; the location constraint L is satisfied; and the number of points on the boundary of R that are touched by spheres is maximized. Such a packing arrangement corresponds to an optimal radiosurgical treatment planning. Finding an optimal solution to the problem, however, is computationally intractable. In particular, we show that this optimization problem and several related problems are NP-hard. Hence, some form of approximations is needed. One approach is to consider a simplified problem under the assumption that spheres of arbitrary (integral) diameters are available with unlimited supply, and there are no location constraints. This approach has met with certain success in medical applications using a dynamic programming algorithm (Bourland and Wu, 1996; Wu, 1996). We propose in this paper an improvement to the algorithm that can greatly reduce its computation cost.     

An Approximation Scheme for Bin Packing with Conflicts

In this paper we consider the following bin packing problem with conflicts. Given a set of items V = {1,..., n} with sizes s₁,..., s (0,1) and a conflict graph G = (V, E), we consider the problem to find a packing for the items into bins of size one such that adjacent items (j, j) E are assigned to different bins. The goal is to find an assignment with a minimum number of bins. This problem is a natural generalization of the classical bin packing problem.We propose an asymptotic approximation scheme for the bin packing problem with conflicts restricted to d-inductive graphs with constant d. This graph class contains trees, grid graphs, planar graphs and graphs with constant treewidth. The algorithm finds an assignment for the items such that the generated number of bins is within a factor of (1 + ) of optimal provided that the optimum number is sufficiently large. The running time of the algorithm is polynomial both in n and in .     

End‐of‐Life Inventory Problem with Phaseout Returns

We consider the service parts end‐of‐life inventory problem of a capital goods manufacturer in the final phase of its life cycle. The final phase starts as soon as the production of parts terminates and continues until the last service contract expires. Final order quantities are considered a popular tactic to sustain service fulfillment obligations and to mitigate the effect of obsolescence. In addition to the final order quantity, other sources to obtain serviceable parts are repairing returned defective items and retrieving parts from phaseout returns. Phaseout returns happen when a customer replaces an old system platform with a next‐generation one and returns the old product to the original equipment manufacturer (OEM). These returns can well serve the demand for service parts of other customers still using the old generation of the product. In this study, we study the decision‐making complications as well as cost‐saving opportunities stemming from phaseout occurrence. We use a finite‐horizon Markov decision process to characterize the structure of the optimal inventory control policy. We show that the optimal policy consists of a time‐varying threshold level for item repair. Furthermore, we study the value of phaseout information by extending the results to cases with an uncertain phaseout quantity or an uncertain schedule. Numerical analysis sheds light on the advantages of the optimal policy compared to some heuristic policies.     

Vendor managed inventory in tramp shipping

This paper introduces a new problem to the OR community that combines traditional tramp shipping with a vendor managed inventory (VMI) service. Such a service may replace the more traditional contract of affreightment (COA) which for decades has been the standard agreement between a tramp shipping company and a charterer. We present a mathematical formulation describing the routing and scheduling problem faced by a tramp shipping company that offers a VMI service to its customers. The problem is formulated as an arc-flow model, and is then reformulated as a path-flow model which is solved using a hybrid approach that combines branch-and-price with a priori path-generation. To solve larger, and more realistic, instances we present a heuristic path-generation algorithm. Computational experiments show that the heuristic approach is much faster than the exact method, with insignificant reductions in solution quality. Further, we investigate the economic impact of introducing a VMI service, by comparing the results obtained with the new model with results obtained by solving the traditional routing and scheduling problem faced by tramp shipping companies using COA. The computational results show that it is possible to substantially increase supply chain profit and efficiency by replacing the traditional COAs with VMI services.     

Lowest Cost May Not Lower Total Cost: Using “Spackling” to Smooth Mass‐Customized Production

Consider a manufacturer who mass customizes variants of a product in make‐to‐order fashion, and also produces standard variants as make‐to‐stock. A traditional manufacturing strategy would be to employ two separate manufacturing facilities: a flexible plant for mass‐customized items and an efficient plant for standard items. We contrast this traditional focus strategy with an alternative that better utilizes capacity by combining production of mass‐customized and standard items in one of two alternate spackling strategies: (1) a pure‐spackling strategy, where the manufacturer produces everything in a (single) flexible plant, first manufacturing custom products as demanded each period, and then filling in the production schedule with make‐to‐stock output of standard products; or (2) a layered‐spackling strategy, which uses an efficient plant to make a portion of its standard items and a separate flexible plant where it spackles. We identify the optimal production strategy considering the tradeoff between the cost premium for flexible (versus efficient) production capacity and the opportunity costs of idle capacity. Spackling amortizes fixed costs of capacity more effectively and thus can increase profits from mass customization vis‐à‐vis a focus strategy, even with higher cost production for the standard goods. We illustrate our framework with data from a messenger bag manufacturer.     

Strategic supply network planning with vendor selection under consideration of risk and demand uncertainty

We present a stochastic version of a three-layer supply network planning problem that includes the selection of vendors that must be equipped with company-specific tools. The configuration of a supply network must be determined by using demand forecasts for a long planning horizon to meet a given service level. The risk induced by the uncertain demand is explicitly considered by incorporating the conditional value at risk. The objective is to maximize the weighted sum of the expected net present value of discounted cash flows and the conditional value at risk. This would lead to a non-linear model formulation that is approximated by a mixed-integer linear model. This approximation is realized by a piecewise linearization of the expected backlogs and physical inventory as non-linear functions of cumulative production quantities. A two-stage stochastic programming approach is proposed. Our numerical analysis of generic test instances indicates that solving the linearized model formulation yields a robust and stable supply network configuration when demand is uncertain.     

Piecewise linear approximations for the static–dynamic uncertainty strategy in stochastic lot-sizing

In this paper, we develop a unified mixed integer linear modelling approach to compute near-optimal policy parameters for the non-stationary stochastic lot sizing problem under static–dynamic uncertainty strategy. The proposed approach applies to settings in which unmet demand is backordered or lost; and it can accommodate variants of the problem for which the quality of service is captured by means of backorder penalty costs, non-stockout probabilities, or fill rate constraints. This approach has a number of advantages with respect to existing methods in the literature: it enables seamless modelling of different variants of the stochastic lot sizing problem, some of which have been previously tackled via ad hoc solution methods and some others that have not yet been addressed in the literature; and it produces an accurate estimation of the expected total cost, expressed in terms of upper and lower bounds based on piecewise linearisation of the first order loss function. We illustrate the effectiveness and flexibility of the proposed approach by means of a computational study.     

公平关切下基于网络平台销售、回收的E-闭环供应链的主导模式研究

在"互联网+"的大环境下,考虑网络平台的公平关切影响,对不同主导模式下的E-闭环供应链的销售、回收进行研究。文章构建了无公平关切制造商主导、无公平关切网络平台主导、考虑公平关切制造商主导、考虑公平关切网络平台主导的E-闭环供应链四种决策模式。针对每种模型,分析了相应的销售价格、服务水平、回收价格和最优利润等决策变量。研究发现：（1）无论网络平台是否考虑公平关切,制造商主导情况下的销售价格、服务水平和制造商利润均高于网络平台主导的情况;（2）闭环供应链的回收价格只与加工成本、回收再造成本和网络平台收取的回收服务佣金有关;（3）公平关切都会使产品销售价格、服务水平和制造商的利润降低;（4）当网络平台主导系统时,公平关切程度较低,网络平台的利润大于制造商主导时的利润,但当公平关切程度较大时,网络平台的利润则小于制造商主导时的利润。（5）当制造商主导系统时,网络平台的利润随其公平关切的程度先增后减。（6）公平关切相当于让利于消费者,且公平关切程度越大,对消费者的让利幅度越大,对制造商越不利。但在实际中,当网络平台主导系统时,网络平台并不会主动进行公平关切,而在制造商主导系统的情况下,网络平台会考虑一定程度的公平关切,或者由于受消费者的信任压力、政府部门的管理要求和竞争等因素的影响,而不得不考虑公平关切问题。文章的研究结论进一步丰富完善了E-闭环供应链的理论基础。