The impact of a rolling schedule in a multi-level MRP system

This paper presents a cost performance comparison of different lot-sizing algorithms under multi-level rolling schedule conditions. Most multi-level studies have focused on fixed horizon problems, omitting an important characteristic of an operating MRP system. The results indicate that, under certain conditions, the computationally simple Silver-Meal heuristic provides lower lot-sizing costs than the Wagner-Whitin algorithm. In addition, cost modifications are introduced which greatly enhance the multi-level performance of these single-level lot-sizing heuristics.     

A volume and material handling cost based heuristic for designing cellular manufacturing cells

One of the major problems in a group technology or cellular manufacturing environment is the formation of part groups and machine cells. Because of the combinatorial nature of the cell formation problem, it is difficult to solve the problem optimally. Most of the procedures related to cell design in cellular manufacturing operate on the part-machine incidence matrix in an attempt to identify block diagonality. If complete block diagonality does not exist, the decision about cell configuration is left to the subjective judgement of the designer. These procedures are also generally based on part routing only, and do not consider part volume and material handling costs.In this paper we develop an integer programming model, as well as a heuristic to effectively assign machines to cells. In these procedures we consider component volumes, costs related to movement of components between and within cells, and penalty for not using all machines in a cell visited by a component. Since the integer programming formulation becomes large even for small problems, an efficient heuristic is developed to solve larger problems. The heuristic solutions to 180 randomly generated small problems were compared against the optimal solutions obtained by the integer programming model. The heuristic has been found to identify optimal solutions in all 180 cases.This heuristic is also compared to several well known algorithms on 900 larger test problems. These problems were generated to cover a wide range of environmental situations such as varying levels of block diagonality in the part-machine incidence matrix, and diversity in the component volumes and material handling costs. In 99% of the problems our heuristic generated solutions which are better or as good as the best solution obtained by other algorithms. Further, in situations where complete block diagonality in the part-machine incidence matrix did not exist, our heuristic produced even better results. Since the maximum number of iterations required in our heuristic is the number of machines in the problem, the heuristic is computationally efficient.     

基于免疫—蚁群算法的应急物流配送网络优化研究

论文针对应急物流的配送车辆路径优化问题,建立以应急物流初期有限资源的分配达到整体的最优化（时间短、效率高、安全高、成本低）的多目标模型,结合模型的特点,利用免疫算法和蚁群算法相融合的启发式算法进行求解,最后进行算例分析,解决应急物流配送车辆路径选择的实际问题。     

An experimental comparison of human schedulers and heuristic algorithms for the traveling salesman problem

Vehicle routing and scheduling for laundry, courier, mail, and other service operations is a significant service industry problem. Several computer-based heuristic algorithms have been developed to assist schedulers in developing efficient delivery (and pick up) vehicle routes. This paper reports the results of an experiment that compared the performance of inexperienced human schedulers and seven heuristic vehicle routing algorithms. A large set of traveling salesman test problems ranging in size from 10 to 80 customers was used in the experiment. The results of the experiment suggest that inexperienced, untrained human schedulers can consistently find traveling salesman solutions as good as or better than all but one of the seven heuristic algorithms tested (including the widely used ClarkeWright distance saved heuristic and the recently published largest-angle insertion heuristic). The human schedulers found traveling salesman routes as good as the best heuristic tested (Lin 's 3-optimal) in 29 percent of the test problems. On average, the human schedulers' solution distances were only 2.8 percent above the 3-optimal heuristic solution distances.     

The method of elimination and substitution in the GMM estimation of mixed regressive,spatial autoregressive models

This paper proposes a computationally simple GMM for the estimation of mixed regressive spatial autoregressive models. The proposed method explores the advantage of the method of elimination and substitution in linear algebra. The modified GMM approach reduces the joint (nonlinear) estimation of a complete vector of parameters into estimation of separate components. For the mixed regressive spatial autoregressive model, the nonlinear estimation is reduced to the estimation of the (single) spatial effect parameter. We identify situations under which the resulting estimator can be efficient relative to the joint GMM estimator where all the parameters are jointly estimated.     

Production lot sizing for deterministic rolling schedules

In this article, we study production planning for a rolling horizon in which demands are known with certainty for a given number of periods in the future (the forecast window M). The rolling horizon approach implements only the earliest production decision before the model is rerun. The next production plan will again be based on M periods of future demand information, and its first lot-sizing decision will be implemented.Six separate lot-sizing methods were evaluated for use in a rolling schedule. These include the Wagner-Whitin algorithm, the Silver-Meal heuristic, Maximum Part-Period Gain of Karni, Heuristics 1 and 2 of Bookbinder and Tan, and Modification 1 to the Silver-Meal heuristic by Silver and Miltenburg.The performance of each lot-sizing rule was studied for demands simulated from the following distributions: normal, uniform (each with four different standard deviations); bimodal uniform (two types); and trend seasonal (both increasing and decreasing trends). We considered four values of the setup cost (leading to natural ordering cycles in an EOQ model of three, four, five, and six periods) and forecast windows in the range 2 M 20.Eight 300-period replications were performed for each combination of demand pattern, setup cost, and lot-sizing method. The analysis thus required consideration of 2304 300-period replications (6 lot-sizing methods × 12 demand patterns × 4 values of setup cost × 8 realizations), each of which was solved for nineteen different values of the forecast window M. The performance of the lot-sizing methods was evaluated on the basis of their average cost increase over the optimal solution to each 300-period problem, as though all these demands were known initially.For smaller forecast windows, say 4 M 8, the most effective lot-sizing rules were Heuristic 2 of Bookbinder and Tan and the modified Silver-Meal heuristic. Rolling schedules from each were generally 1% to 5% in total cost above that of the optimal 300-period solution. For larger forecast windows, M 10 or so, the most effective lot-sizing method was the Wagner-Whitin algorithm. In agreement with other research on this problem, we found that the value of M at which the Wagner-Whitin algorithm first becomes the most effective lot-sizing rule is a decreasing function of the standard deviation of the demand distribution.     

Cost-aware request routing in multi-geography cloud data centres using software-defined networking

Current geographically distributed cloud data centres (CDCs) require gigantic energy and bandwidth costs to provide multiple cloud applications to users around the world. Previous studies only focus on energy cost minimisation in distributed CDCs. However, a CDC provider needs to deliver gigantic data between users and distributed CDCs through internet service providers (ISPs). Geographical diversity of bandwidth and energy costs brings a highly challenging problem of how to minimise the total cost of a CDC provider. With the recently emerging software-defined networking, we study the total cost minimisation problem for a CDC provider by exploiting geographical diversity of energy and bandwidth costs. We formulate the total cost minimisation problem as a mixed integer non-linear programming (MINLP). Then, we develop heuristic algorithms to solve the problem and to provide a cost-aware request routing for joint optimisation of the selection of ISPs and the number of servers in distributed CDCs. Besides, to tackle the dynamic workload in distributed CDCs, this article proposes a regression-based workload prediction method to obtain future incoming workload. Finally, this work evaluates the cost-aware request routing by trace-driven simulation and compares it with the existing approaches to demonstrate its effectiveness.     

The part-period balancing algorithm and its look ahead-look back feature: A theoretical and experimental analysis of a single stage lot-sizing procedure

This paper investigates the discrete Part-Period Balancing (PPB) lot-sizing algorithm and its optional feature, the Look Ahead-Look Back tests. PPB is the most commonly used dynamic lot-sizing procedure in practice and it has also been tested extensively in simulation experiments. Although its overall cost performance, relative to other heuristics, have been fairly good, a fundamental flaw with the model has been noted in the literature. This deficiency leads to poor performance under certain conditions.In this paper a simple adjustment to the main algorithm is analytically derived under the assumptions of a constant demand rate and an infinite planning horizon. The adjustment leads to an optimal behavior for the PPB heuristic under the stated conditions. Subsequent experimental analysis through simulation of lot-sizing performance in environments with time-varying, discrete demand shows that the proposed adjustment leads to significant cost reductions.This paper also analyzes the Look Ahead-Look Back tests which is the distinguishing feature between the PPB procedure and the Least Total Cost algorithm. The tests were devised to improve the cost performance of the PPB heuristic by marginally adjusting each tentative lot-size. The effect of the Look Ahead-Look Back tests have, however, never been verified in the literature. The tests have undergone some changes over time, when they have been included in commercial software packages for inventory management. We suggest yet another modified version in this paper.In the last portion of the paper, the cost effectiveness of the Look Ahead-Look Back tests is confirmed through simulation. That is, when used together with the original PPB procedure, they lead to an improved cost performance. It is also shown that a combination of these tests and the adjustment to the PPB procedure mentioned earlier leads to an even lower average total cost. All cost improvements are statistically significant. It is finally noted that the Look Ahead-Look Back tests perform poorly in certain constant demand situations. Additional analytic and experimental analysis shows that these results stem from a dominance of the Look Back test over the Look Ahead test, leading to the former test being performed more often. This can easily be corrected, however, by checking for sufficient variability in the data before the Look Back test is employed.     

一类多车场集送货一体化问题的最优调度研究

针对江浙沪一带中小型配送中心提供集送货一体化服务增多、运营成本增加这一现象,通过建立该配送类型的车辆调度模型,然后利用分派启发式算法和改进的节约算法设计混合启发式算法来解决这一类问题。并给出算例,验证该算法的可操作性。     

Models of Quality‐Adjusted Life Years when Health Varies Over Time: Survey and Analysis

Abstract.  Quality‐adjusted life year (QALY) models are widely used for economic evaluation in the health care sector. In the first part of the paper, we establish an overview of QALY models where health varies over time and provide a theoretical analysis of model identification and parameter estimation from time trade‐off (TTO) and standard gamble (SG) scores. We investigate deterministic and probabilistic models and consider five different families of discounting functions in all. The second part of the paper discusses four issues recurrently debated in the literature. This discussion includes questioning the SG method as the gold standard for estimation of the health state index, re‐examining the role of the constant‐proportional trade‐off condition, revisiting the problem of double discounting of QALYs, and suggesting that it is not a matter of choosing between TTO and SG procedures as the combination of these two can be used to disentangle risk aversion from discounting. We find that caution must be taken when drawing conclusions from models with chronic health states to situations where health varies over time. One notable difference is that in the former case, risk aversion may be indistinguishable from discounting.     

基于鲍摩-瓦尔夫模型的配送中心选址

文中以总成本最低为目标,建立鲍摩——瓦尔夫模型,对物流配送中心进行选址。该模型在考虑运输成本的同时还考虑可变成本和固定成本,并用启发式算法对其进行就求解,最后通过具体的实例说明模型的可行性。     

A new three-dimensional manufacturing service composition method under various structures using improved Flower Pollination Algorithm

With the growing complexity of customer requirements and the increasing scale of manufacturing services, how to select and combine the single services to meet the complex demand of the customer has become a growing concern. This paper presents a new manufacturing service composition method to solve the multi-objective optimization problem based on quality of service (QoS). The proposed model not only presents different methods for calculating the transportation time and transportation cost under various structures but also solves the three-dimensional composition optimization problem, including service aggregation, service selection, and service scheduling simultaneously. Further, an improved Flower Pollination Algorithm (IFPA) is proposed to solve the three-dimensional composition optimization problem using a matrix-based representation scheme. The mutation operator and crossover operator of the Differential Evolution (DE) algorithm are also used to extend the basic Flower Pollination Algorithm (FPA) to improve its performance. Compared to Genetic Algorithm, DE, and basic FPA, the experimental results confirm that the proposed method demonstrates superior performance than other meta heuristic algorithms and can obtain better manufacturing service composition solutions.     

一种分层A~*路径搜索算法及性能

基于层次道路网提出了一种分层A*路径搜索算法,其特点是在同一层路网中采用A*算法,而在层次切换时采用一种启发式定向搜索入口节点的方法。既顾及了道路等级性和朝着目标行进等驾驶员的心理因素,又可以获得比传统算法更快的求解速度。实验表明,该算法是可行的、高效的。     

多源点物流配送车辆调度模型探讨

根据问题的复杂性,考虑车辆条件的约束,建立了以总费用最小为目标的数学模型,并根据模型的特点设计出相应的启发式算法,使问题在合理的时间内得出由多个配送中心为所有需求点配送货物的车辆分派方案。实例证明,该模型符合实际问题,算法合理,具有实际应用价值。     

基于JIT看板管理的混合型供应链系统库存研究

文章分析了现实中供应链系统结构的复杂性,考虑了供应链系统中生产费用、运输费用、库存费用和订货费用之间相互影响的因素,以降低整个供应链系统总费用为目标,提出了基于JIT看板管理的混合型供应链系统库存问题的数学模型,该数学模型属于混合整数非线性规划问题,混合整数非线性规划问题求解时间与整数变量数量的关系是F=∑n!,文章设计了基于分解技术的算法,通过实例证明了该算法对于大规模混合整数非线性规划问题的有效性和适用性。     

Scheduling independent jobs on nonuniform, unequal processors

The problem of scheduling n independent jobs on a single processor to minimize the total tardiness of the assignment has attracted much attention. Solution algorithms, both exact and approximate, have been reported, but no polynomial time exact algorithm has yet been found, nor has the problem been proven NP-complete.In this paper we consider the more general case of scheduling n independent jobs on m unequal processors to minimize total tardiness. Since this problem is more complex than the corresponding single-processor problem, no polynomial-time algorithm is in sight. For problems of this nature, approximate algorithms may be more valuable than exact algorithms in terms of applications. A heuristic algorithm is developed to solve the multiple-processor problem. Computational experiments show that the heuristic algorithm is efficient, fast, and easy to implement.     

An algorithm for the generalized transportation problem

This paper describes a new computational technique for solving spatial economic equilibrium problems which are generalizations of the classic transportation problem. This technique makes use of a type of algorithm which has been developed in recent years to compute Kakutani fixed points and solve related problems. Existing algorithms for the generalized transportation problem employ quadratic programming, and therefore require that demand and supply functions be linear. By contrast, the algorithm of this paper can handle demand and supply relationships which are nonlinear or even semi-continuous. It can also handle non-constant transport costs and various other complications. The technique is capable of yielding highly accurate solutions, and appears to be computationally efficient on problems of reasonable size.     

运输商选择与配送中心选址联合优化研究——基于供应链系统观念

系统观念是供应链管理的一个重要思想,它要求将供应链做为一个各环节相互联系的有机整体,而不是孤立的阶段.本文基于供应链管理的系统观念,将传统上孤立研究的运输商选择问题与配送中心选址问题结合起来,考虑供应链核心企业管理多个运输商的成本（文中称为C成本）,建立运输商--配送中心联合优化模型[TDJOM],以实现供应链中这两个问题领域的联合优化,实现整体最优,同时设计了一种启发式算法,将非线性规划转为线性规划求解,避免了现有的各种非线性规划求解算法往往只能求得近似最优解的缺陷.本文用算例证明了模型和算法的有效性.     

An enhanced dynamic hash TRIE algorithm for lexicon search

Information retrieval (IR) is essential to enterprise systems along with growing orders, customers and materials. In this article, an enhanced dynamic hash TRIE (eDH-TRIE) algorithm is proposed that can be used in a lexicon search in Chinese, Japanese and Korean (CJK) segmentation and in URL identification. In particular, the eDH-TRIE algorithm is suitable for Unicode retrieval. The Auto-Array algorithm and Hash-Array algorithm are proposed to handle the auxiliary memory allocation; the former changes its size on demand without redundant restructuring, and the latter replaces linked lists with arrays, saving the overhead of memory. Comparative experiments show that the Auto-Array algorithm and Hash-Array algorithm have better spatial performance; they can be used in a multitude of situations. The eDH-TRIE is evaluated for both speed and storage and compared with the naïve DH-TRIE algorithms. The experiments show that the eDH-TRIE algorithm performs better. These algorithms reduce memory overheads and speed up IR.     

基于分支冻结算法的供应商选择与订单分配

针对已有研究供应商选择与订单分配的特点,建立更加符合实际情况需求的供应商选择与订单分配混合整数规划模型,其优化目标为最小总成本.考虑到模型求解的复杂程度,设计一种分支冻结算法,并结合启发式算法的原则避免出现大量的非存在解.实验算例表明所建立的模型能够反映供应商选择与订单分配过程中的产品生产成本过大现象,其算法能够在允许...