One-dimensional machine location problems in a multi-product flowline with equidistant locations

An assignment of machines to locations along a straight track is required to optimize material flow in many manufacturing systems. The assignment of M unique machines to M locations along a linear material handling track with the objective of minimizing the total machine-to-machine material transportation cost is formulated as a quadratic assignment problem (QAP). The distance matrix in problems involving equally-spaced machine locations in one dimension is seen to possess some unique characteristics called amoebic properties. Since an optimal solution to a problem with large M is computationally intractable (the QAP is NP-hard), a number of the amoebic properties are exploited to devise heuristics and a lower bound on the optimal solution. Computational results which demonstrate the performance of the heuristics and the lower bound are presented.     

Modeling and analysis of machine sharing in manufacturing systems

The issue of machine sharing arises quite frequently in the design and operation of automated manufacturing systems. It is often championed as a mechanism for enhancing the flexibility and versatility of these systems. However despite its importance, our understanding of machine sharing and of its effect on system performance has remained inadequate, relying mainly on anecdotal data or limited empirical evidence. In this paper, we present an analytical model that captures the various dimensions of machine sharing and use this model to study the effect of machine sharing on performance of manufacturing systems. In particular, we examine the relationship between machine sharing and several performance measures, such as production rate, machine utilization, flow time and work-in-process inventory, for varying assumptions of system utilization, setup times, batch sizes and demand and processing variability. These relationships are then used to identify conditions under which machine sharing is of value and to determine the corresponding optimal sharing levels.     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

Minimizing makespan in parallel flowshops

In this study, a new class of proportional parallel flow shop problems with the objective of minimizing the makespan has been addressed. A special case for this problem in which jobs are processed on only one machine as opposed to two or more machines in a flow shop, is the well-known multiple processor problem which is NP-complete. The parallel processor problem is a restricted version of the problems addressed in this paper and hence are NP-complete. We develop and test heuristic and simulation approaches to solve large scale problems, while using exact procedures for smaller problems. The performance of the heuristics relative to the LP lower bound as well as a comparison with the truncated integer programming solution are reported. The performance of the heuristics and the simulation results were encouraging.     

Exploiting process plan flexibility in production scheduling: A multi-objective approach

When solving a product/process design problem, we must exploit the available degrees of freedom to cope with a variety of issues. Alternative process plans can be generated for a given product, and choosing one of them has implications on manufacturing functions downstream, including planning/scheduling. Flexible process plans can be exploited in real time to react to machine failures, but they are also relevant for off-line scheduling. On the one hand, we should select a process plan in order to avoid creating bottleneck machines, which would deteriorate the schedule quality; on the other one we should aim at minimizing costs. Assessing the tradeoff between these possibly conflicting objectives is difficult; actually, it is a multi-objective problem, for which available scheduling packages offer little support. Since coping with a multi-objective scheduling problem with flexible process plans by an exact optimization algorithm is out of the question, we propose a hierarchical approach, based on a decomposition into a machine loading and a scheduling sub-problem. The aim of machine loading is to generate a set of efficient (non-dominated) solutions with respect to the load balancing and cost objectives, leaving to the user the task of selecting a compromise solution. Solving the machine loading sub-problem essentially amounts to selecting a process plan for each job and to routing jobs to the machines; then a schedule must be determined. In this paper we deal only with the machine loading sub-problem, as many scheduling methods are already available for the problem with fixed process plans. The machine loading problem is formulated as a bicriterion integer programming model, and two different heuristics are proposed, one based on surrogate duality theory and one based on a genetic descent algorithm. The heuristics are tested on a set of benchmark problems.     

Heuristics for scheduling in a flow shop with multiple processors

This study investigates the performance of scheduling heuristics in a flow shop with multiple processors. We investigated five better performing flow shop heuristics for their performances of makespan and mean flow time criteria in a flow shop with multiple processors. The study examined the effects of problem characteristics (number of jobs, number of machine stages and number of parallel processors at each stage) and the performance of heuristics using regression analysis. We found that although structural characteristics explain most of the variation in performance, heuristics also had an effect. The experimental results showed that flow shop heuristics developed by Nawaz, Enscore, and Ham and that of Ho were comparable in performance in a flow shop with multiple processors. However, the former was slightly more consistent in results for both criteria.     

带时效性约束的配送中心多源选址问题研究

应用启发式算法求解带时效性约束的多源选址问题.分析物流配送的时效性问题,建立带时效性约束的配送中心多源选址模型.构造两步启发式算法:1)借助传统迭代算法,求解物流服务分配矩阵,把多源选址问题转化为单源选址问题;2)基于M ATLAB函数,设计优化程序,计算带时效性约束的单源选址模型.并给出算例,验证模型和算法的可行性.研究表明两步启发式算法是求解带时效性约束的物流配送中心多源连续选址问题的有效算法.     

Modeling and solving profitable location and distribution problems

In this paper we present a general framework for tackling combined location and routing problems (LRPs), involving both costs and profits at the same time. Our framework is based on an extended model and a unified branch-and-cut-and-price method, using dynamic programming pricing routines, strengthening cuts, primal heuristics, stabilization and ad-hoc branching rules to exactly solve LRPs. First we describe our framework, discussing its algorithmic components. Then, we consider as a test case three problems from the literature, with increasing relative importance of the location decisions over the routing ones, and we analyze the performance of our framework for solving them. The first result of our investigation is to assess the tradeoff between modeling detail and computational effectiveness in tackling LRPs. At the same time, we also show that our integrated exact approach is effective for these problems.     

Capacitated facility location: Separation algorithms and computational experience

We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

An analysis of generalised heuristics for vehicle routing and personnel rostering problems

The present study investigates the performance of heuristics while solving problems with routing and rostering characteristics. The target problems include scheduling and routing home care, security and maintenance personnel. In analysing the behaviour of the heuristics and determining the requirements for solving the aforementioned problems, the winning hyper-heuristic from the first International Cross-domain Heuristic Search Challenge (CHeSC 2011) is employed. The completely new application of a hyper-heuristic as an analysis tool offers promising perspectives for supporting dedicated heuristic development. The experimental results reveal that different low-level heuristics perform better on different problems and that their performance varies during a search process. The following characteristics affect the performance of the heuristics: the planning horizon, the number of activities and lastly the number of resources. The body of this paper details both these characteristics and also discusses the required features for embedding in an algorithm to solve problems particularly with a vehicle routing component.     

煤矿物资多车型配送的改进遗传算法求解

首先根据郑州煤电物资供销有限公司的实际情况建立单车场多车型车辆路径问题的模型,在此模型的基础上,用本文提出的改进遗传算法(IGA)对其求解,最后通过和传统的启发式算法(CHA)、扫描法(SA)的求解从配送费用、配送车辆数和运算时间上进行了综合比较,得出IGA算法求得的总运输费用最低,SA算法次之,CHA算法最高;但从所需参与配送的车辆数目来看,CHA求得的最好解所需的车辆数最少,其次是SA,IGA最多;在平均计算时间上,CHA的优势最明显,仅为SA的,IGA的.     

Heuristics for multi-attribute vehicle routing problems: A survey and synthesis

The attributes of vehicle routing problems are additional characteristics or constraints that aim to better take into account the specificities of real applications. The variants thus formed are supported by a well-developed literature, including a large variety of heuristics. This article first reviews the main classes of attributes, providing a survey of heuristics and meta-heuristics for Multi-Attribute Vehicle Routing Problems (MAVRP). It then takes a closer look at the concepts of 64 remarkable meta-heuristics, selected objectively for their outstanding performance on 15 classic MAVRP with different attributes. This cross-analysis leads to the identification of “winning strategies” in designing effective heuristics for MAVRP. This is an important step in the development of general and efficient solution methods for dealing with the large range of vehicle routing variants.     

Interactive optimization

Optimization algorithms or heuristics in which the user interacts significantly either during the solution process or as part of post-optimality analysis are becoming increasingly popular. An important underlying premise of such man/machine systems is that there are some steps in solving a problem in which the computer has an advantage and other steps in which a human has an advantage. This paper first discusses how man/machine systems can be useful in facilitating model specification and revision, coping with aspects of a problem that are difficult to quantify and assisting in the solution process. We then survey successful systems that have been developed in the areas of vehicle scheduling, location problems, job shop scheduling, course scheduling, and planning language-based optimization.     

Interactive optimization

Optimization algorithms or heuristics in which the user interacts significantly either during the solution process or as part of post-optimality analysis are becoming increasingly popular. An important underlying premise of such man/ machine systems is that there are some steps in solving a problem in which the computer has an advantage and other steps in which a human has an advantage. This paper first discusses how man/machine systems can be useful in facilitating model specification and revision, coping with aspects of a problem that are difficult to quantify and assisting in the solution process. We then survey successful systems that have been developed in the areas of vehicle scheduling, location problems, job shop scheduling, course scheduling, and planning language-based optimization.     

Particle swarm optimization for the Steiner tree in graph and delay-constrained multicast routing problems

This paper presents the first investigation on applying a particle swarm optimization (PSO) algorithm to both the Steiner tree problem and the delay constrained multicast routing problem. Steiner tree problems, being the underlining models of many applications, have received significant research attention within the meta-heuristics community. The literature on the application of meta-heuristics to multicast routing problems is less extensive but includes several promising approaches. Many interesting research issues still remain to be investigated, for example, the inclusion of different constraints, such as delay bounds, when finding multicast trees with minimum cost. In this paper, we develop a novel PSO algorithm based on the jumping PSO (JPSO) algorithm recently developed by Moreno-Perez et al. (Proc. of the 7th Metaheuristics International Conference, 2007), and also propose two novel local search heuristics within our JPSO framework. A path replacement operator has been used in particle moves to improve the positions of the particle with regard to the structure of the tree. We test the performance of our JPSO algorithm, and the effect of the integrated local search heuristics by an extensive set of experiments on multicast routing benchmark problems and Steiner tree problems from the OR library. The experimental results show the superior performance of the proposed JPSO algorithm over a number of other state-of-the-art approaches.     

A repeated matching heuristic for the single-source capacitated facility location problem

Facility location models form an important class of integer programming problems, with application in many areas such as the distribution and transportation industries. An important class of solution methods for these problems are so-called Lagrangean heuristics which have been shown to produce high quality solutions and which are at the same time robust. The general facility location problem can be divided into a number of special problems depending on the properties assumed. In the capacitated location problem each facility has a specific capacity on the service it provides. We describe a new solution approach for the capacitated facility location problem when each customer is served by a single facility. The approach is based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied. The method generates feasible solutions in each iteration in contrast to Lagrangean heuristics where problem dependent heuristics must be used to construct a feasible solution. Numerical results show that the approach produces solutions which are of similar and often better than those produced using the best Lagrangean heuristics.     

A Tabu search-based approach for scheduling job-shop type flexible manufacturing systems

The problem of scheduling parts in a job-shop type flexible manufacturing system (FMS) is investigated when each part can have alternative process plans and each operation required of a part can be performed on alternative machines. The mixed-(binary) integer programming model developed for the problem is proven strongly NP-hard. A higher-level heuristic solution algorithm based on a concept known as ‘tabu search’ is developed to determine the best (near-optimal) solution for problems of industrial merit. A comparison of six different versions of tabu search-based heuristics (TSH 1-TSH 6) is performed to investigate the impact of using long-term memory and the use of fixed versus variable tabu-list sizes. A carefully constructed statistical experiment, based on randomized complete-block design, is used to test the performance on four problem structures ranging from 4–14 parts. The results show that, as the problem size increases, TSH 3 with fixed tabu-list size and long-term memory is preferred over the other heuristics. Further, the branch-and-bound technique, by failing to identify as good a solution as that determined by the heuristics (TSH 1-TSH 6), let alone an optimal solution, for a small problem reinforces the need for developing efficient heuristics for solving real problems encountered in industry practice.     

New assignment algorithms for the multi-depot vehicle routing problem

This paper considers the design and analysis of algorithms for the multi-depot vehicle routing problem with time windows (MDVRPTW). Given the intrinsic difficulty of this problem class, approximation methods of the type ‘cluster first, route second’ (two-step approaches) seem to offer the most promise for practical size problems. After describing six heuristics for the cluster part (assignment of customers to depots) an initial computational study of their performance is conducted. Finding, as expected, that the heuristics with the best results (in terms of the routing results) are those with the largest computational efforts.     

Optimal and Heuristic Procedures for Row Layout Problems in Automated Manufacturing Systems

In many automated manufacturing environments, particularly flowlines and flexible manufacturing systems (FMSs), machines are arranged along a straight material handling track with a material handling device moving jobs from one machine to aother. These layouts are referred to as row machine layouts. In this paper we study the Row Layout Problem (RLP) under the design objective of minimizing the total backtracking distance of the material handling device, which is a NP-complete problem. We propose the use of a dynamic programming algorithm for its solution. Special cases of the problem, usually encountered in flexible manufacturing cells and which can be solved with polynomial procedures, are also discussed. For the equidistant case (i.e., successive candidate locations are in equal distances), we formulate the problem as an integer linear program. The use of standard mathematical programming codes can efficiently solve this formulation. Two effective heuristic procedures, which explore simple ideas based on local optimality conditions, are also presented. Extensive computational results demonstrate the effectiveness of such heuristics.     

A graph-theoretic approach to interval scheduling on dedicated unrelated parallel machines

We study the problem of scheduling n non-preemptive jobs on m unrelated parallel machines. Each machine can process a specified subset of the jobs. If a job is assigned to a machine, then it occupies a specified time interval on the machine. Each assignment of a job to a machine yields a value. The objective is to find a subset of the jobs and their feasible assignments to the machines such that the total value is maximized. The problem is NP-hard in the strong sense. We reduce the problem to finding a maximum weight clique in a graph and survey available solution methods. Furthermore, based on the peculiar properties of graphs, we propose an exact solution algorithm and five heuristics. We conduct computer experiments to assess the performance of our and other existing heuristics. The computational results show that our heuristics outperform the existing heuristics.