Disassembly to order system under uncertainty

This paper presents a multi-criteria optimization model of a disassembly-to-order (DTO) system under uncertainty. The goal of the proposed model is to determine the best combination of the number of each product type to be taken back from the last user and/or collectors. The EOL products are then disassembled for the retrieval of reusable components and materials and resold in order to meet a certain level of demand under a variety of physical, financial and environmental constraints. The surplus components are recycled, stored for usage in subsequent periods or properly disposed. The problem is modeled as a multi-criteria decision-making problem under uncertainty, where the aspiration levels for various goals are more likely to be in the “approximately more (less) than” and/or “more (less) is better” form. We employ fuzzy goal programming technique to solve the problem. When solved, the model provides the number of EOL products to be taken back as well as the number of items reused, recycled, stored and disposed. The values of a host of other performance measures are also obtained, including total profit, materials and items sales revenues, take back cost, transportation costs as well as costs of preparation of EOL products, destructive disassembly, non-destructive disassembly, recycling, storage and disposal. A case example is presented to illustrate the model's implementation.     

Approximability of the subset sum reconfiguration problem

The subset sum problem is a well-known NP-complete problem in which we wish to find a packing (subset) of items (integers) into a knapsack with capacity so that the sum of the integers in the packing is at most the capacity of the knapsack and at least a given integer threshold. In this paper, we study the problem of reconfiguring one packing into another packing by moving only one item at a time, while at all times maintaining the feasibility of packings. First we show that this decision problem is strongly NP-hard, and is PSPACE-complete if we are given a conflict graph for the set of items in which each vertex corresponds to an item and each edge represents a pair of items that are not allowed to be packed together into the knapsack. We then study an optimization version of the problem: we wish to maximize the minimum sum among all packings in a reconfiguration. We show that this maximization problem admits a polynomial-time approximation scheme, while the problem is APX-hard if we are given a conflict graph.     

Lower bounds on the adaptivity gaps in variants of the stochastic knapsack problem

We consider stochastic variants of the NP-hard 0/1 knapsack problem in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. The goal is to compute a policy for insertion of the items, that maximizes the expected value of the set of items placed in the knapsack. These variants that we study differ only in the formula for computing the value of the final solution obtained by the policy. We consider both nonadaptive policies (that designate a priori a fixed subset or permutation of items to insert) and adaptive policies (that can make dynamic decisions based on the instantiated sizes of the items placed in the knapsack thus far). Our work characterizes the benefit of adaptivity. For this purpose we use a measure called the adaptivity gap: the supremum over instances of the ratio between the expected value obtained by an optimal adaptive policy and the expected value obtained by an optimal non-adaptive policy. We show that while for the variants considered in the literature this quantity is bounded by a constant there are other variants where it is unbounded.     

Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing

In this paper, we study 1-space bounded multi-dimensional bin packing and hypercube packing. A sequence of items arrive over time, each item is a d-dimensional hyperbox (in bin packing) or hypercube (in hypercube packing), and the length of each side is no more than 1. These items must be packed without overlapping into d-dimensional hypercubes with unit length on each side. In d-dimensional space, any two dimensions i and j define a space P _ij . When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items, and 90^°-rotation on any plane P _ij is allowed. The objective is to minimize the total number of bins used for packing all these items in the sequence. In the 1-space bounded variant, there is only one active bin for packing the current item. If the active bin does not have enough space to pack the item, it must be closed and a new active bin is opened. For d-dimensional bin packing, an online algorithm with competitive ratio 4 ^d is given. Moreover, we consider d-dimensional hypercube packing, and give a 2 ^d+1-competitive algorithm. These two results are the first study on 1-space bounded multi dimensional bin packing and hypercube packing.     

Coordinated Replenishments from a Common Supplier

Coordinated replenishment strategies may be implemented by jointly ordering multiple items from a common supplier. A major benefit of coordinated replenishment is that it increases the size of shipments, permitting the buyer to enjoy transportation economies without a major increase in average inventory levels. The coordinated replenishment problem is complex because side constraints govern the attainment of transportation rate breaks. The problem is further complicated by the presence of purchase quantity discount opportunities. Thus, the buyer must decide which items to order independently, which items to include in a group order, and the order quantities of each item, governed by the frequency of independent or group orders. We present a mathematical model and a heuristic solution procedure that provide analytical support to the buyer seeking to minimize total costs of replenishing multiple items from a common supplier. The relevant costs are purchase prices, ordering costs, holding costs, and transportation costs. Coordinated replenishment provides nearly a 30 percent reduction in controllable costs relative to independent control. Experimentation with the heuristic has yielded optimal solutions over 88 percent of the time. When optimality was not obtained, the mean penalty was much less than one percent. The average heuristic search was more than two orders of magnitude faster than branch and bound, even for small problems, and possessed a much tighter distribution around the mean search time.     

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).     

Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions

Motivated by a real world application, we study the multiple knapsack problem with assignment restrictions (MKAR). We are given a set of items, each with a positive real weight, and a set of knapsacks, each with a positive real capacity. In addition, for each item a set of knapsacks that can hold that item is specified. In a feasible assignment of items to knapsacks, each item is assigned to at most one knapsack, assignment restrictions are satisfied, and knapsack capacities are not exceeded. We consider the objectives of maximizing assigned weight and minimizing utilized capacity.We focus on obtaining approximate solutions in polynomial computational time. We show that simple greedy approaches yield 1/3-approximation algorithms for the objective of maximizing assigned weight. We give two different 1/2-approximation algorithms: the first one solves single knapsack problems successively and the second one is based on rounding the LP relaxation solution. For the bicriteria problem of minimizing utilized capacity subject to a minimum requirement on assigned weight, we give an (1/3,2)-approximation algorithm.     

Bin packing with “Largest In Bottom” constraint: tighter bounds and generalizations

The (online) bin packing problem with LIB constraint is stated as follows: The items arrive one by one, and must be packed into unit capacity bins, but a bigger item cannot be packed into a bin which already contains a smaller item. The number of used bins has to be minimized as usually. We show that the absolute performance bound of algorithm First Fit is not worse than 2+1/6≈2.1666 for the problem, improving the previous best upper bound 2.5. Moreover, if the item sizes do not exceed 1/d, then we improve the previous best result 2+1/d to 2+1/d(d+2), for any d≥2. (Both previously best results are due to Epstein, Nav. Res. Logist. 56(8):780–786, 2009.) Furthermore, we define a problem with the generalized LIB constraint, where some incoming items cannot be packed into the bins of some already packed items. The (in)compatibility of the incoming item with the items already packed becomes known only at the arrival of the actual item, and is given by an undirected graph (and, as usual in case of online graph problems, we can see only that part of the graph what already arrived). We show that 3 is an upper bound for this general problem if some natural transitivity constraint is satisfied.     

Class‐Based Storage with a Finite Number of Items: Using More Classes is not Always Better

Class‐based storage is widely studied in the literature and applied in practice. It divides all stored items into a number of classes according to their turnover. A class of items with higher turnover is allocated to a region closer to the warehouse depot. In the literature, it has been shown that the use of more storage classes leads to a shorter travel time for storing and retrieving items. A basic assumption in this literature is that the required storage space for all items equals their average inventory level, which is valid only if an infinite number of items can be stored in each storage region. This study revisits class‐based storage by considering each storage space to contain only a finite number of items. We develop a travel time model and an algorithm that can be used for determining the optimal number and boundaries of storage classes in warehouses. Different from the conventional research, our findings illustrate that commonly a small number of classes is optimal. In addition, we find the travel time is fairly insensitive to the number of storage classes in a wide range around the optimum. This suggests that a manager can select a near‐optimal number of storage classes in an easy way and need not be worried about the impact of storage‐class reconfigurations. We validate our findings for various cases, including different ABC‐demand curves, space‐sharing factors, number of items, storage rack shapes, discrete storage locations, and stochastic item demand.     

An efficient FPRAS type group testing procedure to approximate the number of defectives

In many fault detection problems, we want to detect or identify defective items in a sample set by using the minimum number of tests. Group testing is for the scenario where each test is on a subset of items, and tells whether the subset contains at least one defective item or not. Another practically important problem is to estimate the number of defective items in a sample set. In this paper, we present an efficient FPRAS (fully polynomial-time randomized approximation scheme) type group testing procedure to approximate the number of defective items in a sample set.     

Machine learning for multi-criteria inventory classification applied to intermittent demand

Multi-criteria inventory classification groups inventory items into classes, each of which is managed by a specific re-order policy according to its priority. However, the tasks of inventory classification and control are not carried out jointly if the classification criteria and the classification approach are not robustly established from an inventory-cost perspective. Exhaustive simulations at the single item level of the inventory system would directly solve this issue by searching for the best re-order policy per item, thus achieving the subsequent optimal classification without resorting to any multi-criteria classification method. However, this would be very time-consuming in real settings, where a large number of items need to be managed simultaneously.

In this article, a reduction in simulation effort is achieved by extracting from the population of items a sample on which to perform an exhaustive search of best re-order policies per item; the lowest cost classification of in-sample items is, therefore, achieved. Then, in line with the increasing need for ICT tools in the production management of Industry 4.0 systems, supervised classifiers from the machine learning research field (i.e. support vector machines with a Gaussian kernel and deep neural networks) are trained on these in-sample items to learn to classify the out-of-sample items solely based on the values they show on the features (i.e. classification criteria). The inventory system adopted here is suitable for intermittent demands, but it may also suit non-intermittent demands, thus providing great flexibility. The experimental analysis of two large datasets showed an excellent accuracy, which suggests that machine learning classifiers could be implemented in advanced inventory classification systems.     

Coordinating replenishments in a supply chain with quality control considerations

We study the impact of coordinated replenishment, a popular supply chain initiative, on a quality control system. We use the (Q, S) policy to manage a two-item inventory control system. If the items are jointly replenished, the number ordered for each item varies from lot to lot. As the number varies, the sampling plan will also be changed. Companies have to determine sampling plans to minimize quality cost when the order is mixed with several items and the number of each item varies from order to order. Management's primary concern is to determine the optimal sampling sizes and acceptance numbers for all items in an order.     

一种基于证据理论的动态综合效绩评价实用方法

本文针对一体化管理体系综合绩效的多指标、多层次、评价标准模糊,且属性复杂等评价特点,建立了综合绩效评价体系;提出了基于证据理论的动态综合模糊评价方法;给出了具体的评价步骤;按指标属性将评价指标区分为定性和定量两类:对各指标进行量化、一致性和无量纲化处理;从评价体系准则层开始进行动态立体综合评价;逐层合成综合绩效值.最后通过实例说明该方法的实用性和科学性.     

A Framework for Facilitating Sourcing and Allocation Decisions for Make‐to‐Order Items

This paper provides a fundamental building block to facilitate sourcing and allocation decisions for make‐to‐order items. We specifically address the buyer's vendor selection problem for make‐to‐order items where the goal is to minimize sourcing and purchasing costs in the presence of fixed costs, shared capacity constraints, and volume‐based discounts for bundles of items. The potential suppliers for make‐to‐order items provide quotes in the form of single sealed bids or participate in a dynamic auction involving open bids. A solution to our problem can be used to determine winning bids amongst the single sealed bids or winners at each stage of a dynamic auction. Due to the computational complexity of this problem, we develop a heuristic procedure based on Lagrangian relaxation technique to solve the problem. The computational results show that the procedure is effective under a variety of scenarios. The average gap across 2,250 problem instances is 4.65%.     

A New Approach to the Group Ranking Problem: Finding Consensus Ordered Segments from Users’ Preference Data

The group ranking problem involves constructing coherent aggregated results from users’ preference data. The goal of most group ranking problems is to generate an ordered list of all items that represents the user consensus. There are, however, two weaknesses to this approach. First, a complete list of ranked items is always output even when there is no consensus or only a slight consensus. Second, due to similarity of performance, in many practical situations, it is very difficult to differentiate whether one item is really better than another within a set. These weaknesses have motivated us to apply the clustering concept to the group ranking problem, to output an ordered list of segments containing a set of similarly preferred items, called consensus ordered segments. The advantages of our approach are that (i) the list of segments is based on the users’ consensuses, (ii) the items with similar preferences are grouped together in the same segment, and (iii) the relationships between items can be easily seen. An algorithm is developed to construct the consensus of the ordered segments from the users’ total ranking data. Finally, the experimental results indicate that the proposed method is computationally efficient, and can effectively identify consensus ordered segments.     

A classification approach based on the outranking model for multiple criteria ABC analysis

The multiple criteria ABC analysis is widely used in inventory management, and it can help organizations to assign inventory items into different classes with respect to several evaluation criteria. Many approaches have been proposed in the literature for addressing such a problem. However, most of these approaches are fully compensatory in multiple criteria aggregation. This means that an item scoring badly on one or more key criteria could be placed in good classes because these bad performances could be compensated by other criteria. Thus, it is necessary to consider the non-compensation in the multiple criteria ABC analysis. To the best of our knowledge, the ABC classification problem with non-compensation among criteria has not been studied sufficiently. We thus propose a new classification approach based on the outranking model to cope with such a problem in this paper. However, the relational nature of the outranking model makes the search for the optimal classification solution a complex combinatorial optimization problem. It is very time-consuming to solve such a problem using mathematical programming techniques when the inventory size is large. Therefore, we combine the clustering analysis and the simulated annealing algorithm to search for the optimal classification. The clustering analysis groups similar inventory items together and builds up the hierarchy of clusters of items. The simulated annealing algorithm searches for the optimal classification on different levels of the hierarchy. The proposed approach is illustrated by a practical example from a Chinese manufacturer. Furthermore, we validate the performance of the approach through experimental investigation on a large set of artificially generated data at the end of the paper.     

Lot sizing in case of defective items with investments to increase the speed of quality control

In many cases the quality of each item in a lot is checked. Speeding up the quality checking process increases the responsiveness of the system and saves cost. The percentage of defective items is a random variable and two models are proposed. In one of the models the system remains always at the same state, while in the other one after each order cycle, the state of the system may change, thus the percentage of defective items may be different in consecutive periods. In both cases the speed of the quality checking is a variable, and procedures are provided to find the optimal lot sizes and screening speed for general and specific investment cost functions. The characteristics of the two model settings will largely be different when the percentage of defective items is high. Among the important managerial insights gained is that a high unit backlogging cost, especially spurs the system to invest more intensively into improving the quality checking process.     

A Model for Resource Constrained Production and Inventory Management

We present a general model for multi-item production and inventory management problems that include a resource restriction. The decision variables in the model can take on a variety of interpretations, but will typically represent cycle times, production batch sizes, number of production runs, or order quantities for each item. We consider environments where item demand rates are approximately constant and performing an activity such as producing a batch of a product or placing an order results in the consumption of a scarceresource that is shared among the items. Some examples of shared resources include limited machine capacity, a restriction on the amount of money that can be tied up in stock, orlimited storage capacity. We focus on the case where the decision variables must be integer valued or selected from a discrete set of choices, such as when an integer number of production runs is desired for each item, or in order quantity problems where the items come in pack sizes containing more than one unit and, therefore, the order quantities must be an integer multiple of the pack sizes. We develop a heuristic and a branch and bound algorithm for solving the problem. The branch and bound algorithm includes reoptimization procedures and the heuristic to improve its performance. Computational testing indicates that the algorithms are effective for solving the general model.     

A Fig Leaf for The Naked Corporation

The implementation of the Sarbanes-Oxley Act in the United States and the German Law of transparency and disclosure (TransPuG) lead to a claim for more disclosure of information with the goal of a “naked corporation” such that all information is available to the (potential) investors. In this article we pick up this debate and present arguments that the “naked corporation” does not offer an efficient degree of disclosure, as we have to distinguish between more and better information. Concerning the latter the new regulations are critical. Cognitive limitations and bounded rationality highlight the risk of information overload. Asymmetric information illustrates that self induced disclosure can do better than a mandatory one. Therefore the legislator should not be asked for specific informational contents but for regulations on the way of information provision.JEL Codes: K22, G34, D82     

Sensitivity of the Optimum to Perturbations of the Profit or Weight of an Item in the Binary Knapsack Problem

In the binary single constraint Knapsack Problem, denoted KP, we are given a knapsack of fixed capacity c and a set of n items. Each item j, j = 1,...,n, has an associated size or weight w_j and a profit p_j. The goal is to determine whether or not item j, j = 1,...,n, should be included in the knapsack. The objective is to maximize the total profit without exceeding the capacity c of the knapsack. In this paper, we study the sensitivity of the optimum of the KP to perturbations of either the profit or the weight of an item. We give approximate and exact interval limits for both cases (profit and weight) and propose several polynomial time algorithms able to reach these interval limits. The performance of the proposed algorithms are evaluated on a large number of problem instances.