Exact and heuristic algorithms for solving the generalized minimum filter placement problem

We consider a problem of placing route-based filters in a communication network to limit the number of forged address attacks to a prescribed level. Nodes in the network communicate by exchanging packets along arcs, and the originating node embeds the origin and destination addresses within each packet that it sends. In the absence of a validation mechanism, one node can send packets to another node using a forged origin address to launch an attack against that node. Route-based filters can be established at various nodes on the communication network to protect against these attacks. A route-based filter examines each packet arriving at a node, and determines whether or not the origin address could be legitimate, based on the arc on which the packet arrives, the routing information, and possibly the destination. The problem we consider seeks to find a minimum cardinality subset of nodes to filter so that the prescribed level of security is achieved. We formulate a mixed-integer programming model for the problem and derive valid inequalities for this model by identifying polynomially-solvable subgraphs of the communication network. We also present three heuristics for solving the filter placement problem and evaluate their performance against the optimal solution provided by the mixed-integer programming model. The authors gratefully acknowledge the comments of two anonymous referees, whose input led to an improved version of this paper. Dr. Smith gratefully acknowledges the support of the Office of Naval Research under Grant #N00014-03-1-0510 and the Defense Advanced Research Projects Agency under Grant #N66001-01-1-8925.     

A mathematical model and genetic algorithm-based approach for parallel two-sided assembly line balancing problem

Assembly lines are usually constructed as the last stage of the entire production system and efficiency of an assembly line is one of the most important factors which affect the performance of a complex production system. The main purpose of this paper is to mathematically formulate and to provide an insight for modelling the parallel two-sided assembly line balancing problem, where two or more two-sided assembly lines are constructed in parallel to each other. We also propose a new genetic algorithm (GA)-based approach in alternatively to the existing only solution approach in the literature, which is a tabu search algorithm. To the best of our knowledge, this is the first formal presentation of the problem as well as the proposed algorithm is the first attempt to solve the problem with a GA-based approach in the literature. The proposed approach is illustrated with an example to explain the procedures of the algorithm. Test problems are solved and promising results are obtained. Statistical tests are designed to analyse the advantage of line parallelisation in two-sided assembly lines through obtained test results. The response of the overall system to the changes in the cycle times of the parallel lines is also analysed through test problems for the first time in the literature.     

Two new robust genetic algorithms for the flowshop scheduling problem

The flowshop scheduling problem (FSP) has been widely studied in the literature and many techniques for its solution have been proposed. Some authors have concluded that genetic algorithms are not suitable for this hard, combinatorial problem unless hybridization is used. This work proposes new genetic algorithms for solving the permutation FSP that prove to be competitive when compared to many other well known algorithms. The optimization criterion considered is the minimization of the total completion time or makespan (_Cmax$C_{\max }$). We show a robust genetic algorithm and a fast hybrid implementation. These algorithms use new genetic operators, advanced techniques like hybridization with local search and an efficient population initialization as well as a new generational scheme. A complete evaluation of the different parameters and operators of the algorithms by means of a Design of Experiments approach is also given. The algorithm's effectiveness is compared against 11 other methods, including genetic algorithms, tabu search, simulated annealing and other advanced and recent techniques. For the evaluations we use Taillard's well known standard benchmark. The results show that the proposed algorithms are very effective and at the same time are easy to implement.     

基于遗传算法的概率准则组合证券模拟求解

针对概率准则意义下的组合证券投资模型,采用随机模拟技术和遗传算法相结合的思 想, 设计出求解算法, 并用Matlab 语言实现. 求解算法适用于证券收益率服从任意分布的情 况, 甚至不考虑证券收益率分布, 用实际数据进行模拟和优化. 实例证明, 该算法有很好的 收敛性及较高的计算效率.     

An effective discrete dynamic convexized method for solving the winner determination problem

The winner determination problem (WDP) arises in combinatorial auctions. It is known to be NP-hard. In this paper, we propose a discrete dynamic convexized method for solving this problem. We first propose an adaptive penalty function to convert the WDP into an equivalent unconstrained integer programming problem. Based on the structure of the WDP, we construct an unconstrained auxiliary function, which is maximized iteratively using a local search and is updated whenever a better maximizer is found. By increasing the value of a parameter in the auxiliary function, the maximization of the auxiliary function can escape from previously converged local maximizers. To evaluate the performance of the dynamic convexized method, extensive experiments were carried out on realistic test sets from the literature. Computational results and comparisons show that the proposed algorithm improved the best known solutions on a number of benchmark instances.     

Adjusting MRP for dynamic differentiation of identical items for process customisation

In the make-to-order (MTO) environment, different customer orders often require similar products that share identical basic features but require different customisation processes. To achieve efficiency, these products are often manufactured in a group at the initial stages. A significant issue then emerges as to how to differentiate identical items at the intermediate stages so that they can be dispatched to different kinds of work centres for process customisation. This article adjusts the current material requirements planning (MRP) approach for the MTO mode. A yield-allocating approach is then proposed for adjusting the material demand plans according to real-time process quality information. An approach for dynamically differentiating identical customised items at intermediate stages is then presented. How to implement the proposed methodology in a computer-based environment is also briefly introduced. A case study demonstrates that the proposed methodology can fulfil the dynamical differentiation task and can result in more reasonable differentiation decisions than the traditional MRP approach.     

Priority algorithms for the subset-sum problem

Greedy algorithms are simple, but their relative power is not well understood. The priority framework (Borodin et al. in Algorithmica 37:295–326, 2003) captures a key notion of “greediness” in the sense that it processes (in some locally optimal manner) one data item at a time, depending on and only on the current knowledge of the input. This algorithmic model provides a tool to assess the computational power and limitations of greedy algorithms, especially in terms of their approximability. In this paper, we study priority algorithm approximation ratios for the Subset-Sum Problem, focusing on the power of revocable decisions, for which the accepted data items can be later rejected to maintain the feasibility of the solution. We first provide a tight bound of α≈0.657 for irrevocable priority algorithms. We then show that the approximation ratio of fixed order revocable priority algorithms is between β≈0.780 and γ≈0.852, and the ratio of adaptive order revocable priority algorithms is between 0.8 and δ≈0.893. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS 4598, pp. 504–514.     

A hierarchical production plan for a make-to-order steel fabrication plant

A three-tiered hierarchical production plan (HPP) for a strictly make-to-order steel fabrication plant with the objective of developing a production plan and master schedule for a set of product archetypes is implemented. Data are collected from an actual steel fabrication plant located in the Midwestern section of the US. An aggregate linear programming model, a non-linear disaggregate model and a master production schedule comprise the respective tiers. Appropriate models provide the forecasts needed in the first two tiers. A production plan and master schedule based on data collected at the plant, benefits expected for its implementation and practical limitations are reported.     

Target-guided algorithms for the container pre-marshalling problem

The container pre-marshalling problem (CPMP) aims to rearrange containers in a bay with the least movement effort; thus, in the final layout, containers are piled according to a predetermined order. Previous researchers, without exception, assumed that all the stacks in a bay are functionally identical. Such a classical problem setting is reexamined in this paper. Moreover, a new problem, the CPMP with a dummy stack (CPMPDS) is proposed. At terminals with transfer lanes, a bay includes a row of ordinary stacks and a dummy stack. The dummy stack is actually the bay space that is reserved for trucks. Therefore, containers can be shipped out from the bay. During the pre-marshalling process, the dummy stack temporarily stores containers as an ordinary stack. However, the dummy stack must be emptied at the end of pre-marshalling. In this paper, target-guided algorithms are proposed to handle both the classical CPMP and new CPMPDS. All the proposed algorithms guarantee termination. Experimental results in terms of the CPMP show that the proposed algorithms surpass the state-of-the-art algorithm.     

A genetic algorithm for determining optimal replenishment cycles to minimize maximum warehouse space requirements

In a supply chain, it is an important issue for logistic managers to offset the replenishment cycles of multiple products sharing a warehouse so as to minimize the maximum warehouse space requirement (MWSR). Most of the studies in the literature assume that warehouses replenish at the beginning of some basic planning period. In this paper, we relax this assumption by allowing the warehouse to replenish at any time. In order to solve this problem, we conduct theoretical analysis based on Fourier series and Fourier transforms and propose a procedure that is used to calculate MWSR efficiently for any given replenishment schedule. Then, we employ this procedure in a genetic algorithm (GA) to search for the optimal replenishment schedule. Using randomly generated instances, we show that the proposed GA significantly outperforms a previously published heuristic.     

Exact and approximate algorithms for the loop layout problem

Control parameters, such as order frequency, safety stock and safety time, are important tools to improve the logistic performance in material planning. In practice, the adjustment of control parameters appears to be very difficult. One of the reasons is the lack of relevant tactical control information: a simple, periodical and per-commodity integrated feedback of performance and process information often is not available to the logistic operator. Therefore, the material planner is offered a fairly limited overview and insight of the processes to be controlled. This problem has been investigated in several plants in the Netherlands. A solution to this problem is first to measure the performance, the frequency of process disturbances and the effect of the parameters on performance for all commodities involved. And second, to integrate this information and provide feedback to the responsible material planner. In this article a design for decision support is presented to integrate and give feedback of relevant tactical control information. Prototype information systems are now being tested in practice and in the laboratory. The expectation is that this type of decision support will help the operator to make more systematic and effective diagnoses.     

考虑风险规避的秘书问题求解的一个启发式方法

秘书问题是一类序贯观察与选择问题,描述了动态的信息搜索与决策过程.针对现有的以寻找满意解为目标的启发式方法存在诸多局限,提出了新的启发式方法,该方法基于当前观测中侯选项在已观察侯选项中的相对排名、待观测侯选项数量以及决策者的抱负水平,决策者可以通过设定抱负水平灵活决定该启发式方法的结果导向.推导了该启发式方法的性能指标,并通过仿真的方法与已有启发式方法的性能进行了比较.结果发现,该启发式方法在最终选择的侯选项的期望排名和稳定性,以及风险解的避免上均优于已有的启发式方法.     

A review of hierarchical production planning and its applicability for modern manufacturing

The hierarchical production planning (HPP) paradigm has become an accepted planning and control strategy for many medium-to-large manufacturing situations. While the paradigm appears intuitively obvious and appropriate for many factories, there are a number of modern manufacturing situations where the application of the HPP approach may not be appropriate. By understanding the fundamental principles and concepts inherent in the HPP approach, it is possible to identify situations suitable for HPP with little or no adaptation, and situations where HPP must be extensively modified before use. A poor understanding of HPP     

越库转运问题的自适应遗传算法研究

探讨一种固定运输模式下的越库转运问题--采用运输量不可拆分的单次运送方式以最小费用通过选择固定的运输路径将货物经过越库转运到目的地,其货物将可能在越库中停留甚至无法运到目的地,这将会导致库存成本和惩罚成本.文中证明了此类越库转运问题是强NP难题,因此本文针对该问题的特殊结构,提出一种采用了邻域搜索技术的自适应遗传算法(...     

A genetic algorithm for thepart family formation problem

Recently, there has been a lot of interest in group technology (GT) from researchers as well as from practitioners. This interest is explained by the fact that GT supports new manufacturing philosophies. One of the main issues in GT is the part family formation problem which is concerned with grouping similar products into same families. Many researchers have tackled this problem and many algorithms have been proposed for it. In this paper, we present a genetic technique-based heuristic for the quadratic integer programming model of the part family formation problem which was formulated by Kusiak et al. (1986). The heuristic is tested on several problems from the literature, and preliminary results are very promising.     

A rearrangement of adjacency matrix based approach for solving the crossing minimization problem

In this paper, we first present a binary linear programming formulation for the crossing minimization problem (CMP) in bipartite graphs. Then we use the models of a modified minimum cost flow problem (MMCF) and a travelling salesman problem (TSP) to approximatively solve the CMP by rearranging the adjacency matrix of the bipartite graph. Our approaches are useful for problems defined on dense bipartite graphs. In addition, we compute the exact crossing numbers for some general dense graphs.     

Decomposition algorithms for the integrated process planning and scheduling problem

There are several algorithms to solve the integrated process planning and scheduling (IPPS) problem (i.e., flexible job shop scheduling with process plan flexibility) in the literature. All the existing algorithms for IPPS are heuristic-based search methods and no research has investigated the use of exact solution methods for this problem. We develop several decomposition approaches based on the logic-based Benders decomposition (LBBD) algorithm. Our LBBD algorithm allows us to partition the decision variables in the IPPS problem into two models, master-problem and sub-problem. The master-problem determines process plan and operation-machine assignment, while the sub-problem optimizes sequencing and scheduling decisions. To achieve faster convergence, we develop two relaxations for the optimal makespan objective function and incorporate them into the master-problem. We analyze the performance and further enhance the algorithm with two ideas, a Benders optimality cut based on the critical path and a faster heuristic way to solve the sub-problem. 16 standard benchmark instances available in the literature are solved to evaluate and compare the performances of our algorithms with those of the state-of-the-art methods in the literature. The proposed algorithm either results in the optimal solution or improves the best-known solutions in all the existing instances, demonstrating its superiority to the existing state-of-the-art methods in literature.     

A branching method for the fixed charge transportation problem

This paper presents a branching method for the solution of the fixed charge transportation problem. Starting with a linear formulation of the problem, we develop the method which converges to the optimal solution. The method is based on the computation of a lower bound and an upper bound embedded within a branching process. We present a detailed numerical example to illustrate the proposed method.     

A structured procedure for materials planning during production transfer

This paper explores materials planning procedures to ensure the materials’ availability during production transfers. The paper defines a production transfer as the preparation, physical transfer and start-up of relocated production. A structured procedure of materials planning during production transfer is developed based on theory, and then validated and refined based on the analysis of four case studies. The paper shows that there is a need for a structured procedure of materials planning during production transfers. It also explains the importance of activities that create prerequisites for the materials’ availability during production transfer, such as updating and adapting documentation, planning and control systems, and describes the activities that ensure the materials’ availability, such as preventive and corrective actions. A valid estimation of the time needed to reach a steady state and a combination of several preventive actions improves the ability to ensure that materials are available. The cases showed differences across company size, because large companies took more and farther-reaching preventive actions.