A set partitioning based heuristic procedure for incremental cell formation with routing flexibility

One of the important issues regarding the implementation of cellular manufacturing relates to deciding whether to convert an existing job shop into a cellular manufacturing system comprehensively in a single go, or to convert in stages incrementally wherein the cells are formed one after the other taking the advantage of experiences of implementation. In this paper, a heuristic method based on iterative set partitioning is proposed for incremental cell formation where part operations can be processed on alternative machines. The objective is to minimize cycle time for a given number of workstations. The proposed method is numerically compared with the existing branch and bound technique and another heuristic algorithm based on multistage programming. It is found that the proposed method requires significantly less computational efforts to yield the optimal solution.     

直运越库物流的精确算法研究

多车辆直运越库调度问题的目标是最小化所有客户中的最晚到货时间.首先,建立了描述该问题的混合整数线性规划模型,并使用运筹优化工具ILOG CPLEX进行求解;其次,构造了基于LPT规则的启发式算法,为精确算法提供了初始可行解,并对分支定界算法进行详细的分析;最后,在数值实验部分,通过数学模型与分支定界的比较及算法性能的分析后,得出分支定界算法具有更高的效率,该分支定界算法在合理的时间内能够求解到11个供应商规模的问题.     

Location and sequencing of imperfect inspection operations in serial multi-stage production systems

An integrated approach to the problem of allocation of inspection effort in multistage production systems is presented. The problem addresses multiple inspection operations, different disposition policies and inspection, production and repair errors. Quality and cost transfer functions are developed to model production operations and different types of inspection operations in a unified manner and to facilitate the recursive computations required to evaluate alternative system configurations. We formulate the combined inspection location and sequencing problem as a nonlinear mathematical programming problem and solve it with a branch and bound technique, using a heuristic to generate a feasible solution and upper bound. These developments are illustrated with a numerical example.     

The Segregated Storage Problem: Some Properties and an Effective Heuristic

The segregated storage problem is formulated as an integer programming problem. Some special cases are shown to reduce to ordinary assignment problems. A special property of the integer formulation is used to develop a new heuristic procedure which produces near optimal solutions and which can be used as a tight bound in branch and bound procedures. Computational comparisons with heuristics proposed by other authors indicate this method to be superior in solving large problems.     

Approach to failure mode analysis of large structures

This paper deals with strategies for searching failure modes in large structures. At first, typical methods in this field are reviewed, i.e. the incremental loading method, the branch and bound technique, the β-unzipping method, mathematical programming, simulation methods and some heuristic techniques. Their features and applicability are compared. Then, a new selective search procedure combined with a genetic algorithm is discussed as a possibility to create more intelligent methods for generation of failure modes.     

Designing an Assembly Process with Stochastic Material Arrivals

Due to product proliferation and quick changes in manufacturing materials sourcing partnerships, assembly process in the electronic assembly industry is frequently altered or new processes are introduced. The most appropriate assembly process is critical for companies to maintain an effective supply chain. We study the problem of how to design an assembly process that relies on the stochastic arrival times of parts and components such that the probability of on-time delivery of finished products is maximized. We first provide some analytical results for cases that are polynomially solvable and then provide a branch and bound algorithm for deriving an optimal solution to the problem. We also provide heuristic algorithms to solve the problem. Finally, computational experiments show that our heuristic algorithms perform very well.     

A robust cell formation approach for varying product demands

In cellular manufacturing environments, manufacturing cells are generally formed based on deterministic product demands. In this paper, we consider a system configuration problem with product demands expressed in a number of probabilistic scenarios. An optimization model integrating cell formation and part allocation is developed to generate a robust system configuration to minimize machine cost and expected inter-cell material handling cost. A two-stage Tabu search based heuristic algorithm is developed to find the optimal or near optimal solutions to the NP-hard problem. Numerical examples show that this model leads to an appropriate compromise between system configuration costs and expected material handling costs to meet the varying product demands. These example problems also show that the proposed algorithm is effective and computationally efficient for small or medium size problems.     

An improved branch and bound procedure for scheduling a flow line manufacturing cell

This paper presents a new branch and bound procedure for scheduling a flow-line manufacturing cell. This procedure and an existing procedure are tested on several problem sets with varying numbers of families, jobs and machines, and varying setup time distributions. The results show that the new procedure solves small problems dramatically faster than the existing procedure. Three heuristic procedures, based on the new branch and bound procedure, are developed. These heuristic procedures as well as a tabu search procedure are tested on problem sets with larger problem sizes. The results show that one of the new procedures generates solutions with improved makespans compared to the tabu search procedure.     

Power distribution network expansion scheduling using dynamic programming genetic algorithm

A genetic algorithm that is dedicated to the expansion planning of electric distribution systems is presented, with incremental expansion scheduling along a time horizon of several years and treated as a dynamic programming problem. Such a genetic algorithm (called dynamic programming genetic algorithm) is endowed with problem-specific crossover and mutation operators, dealing with the problem through a heuristic search in the space of dynamic programming variables. Numerical tests have shown that the proposed algorithm has found good solutions that considerably enhance the solutions found by non-dynamic programming methods. The algorithm has also shown to work for problem sizes that would be computationally infeasible for exact dynamic programming techniques.     

Solving a multistage partial inspection problem using genetic algorithms

Traditionally, the multistage inspection problem has been formulated as consisting of a decision schedule where some manufacturing stages receive full inspection and the rest none. Dynamic programming and heuristic methods (like local search) are the most commonly used solution techniques. A highly constrained multistage inspection problem is presented where all stages must receive partial rectifying inspection and it is solved using a real-valued genetic algorithm. This solution technique can handle multiple objectives and quality constraints effectively.     

Exact and approximate algorithms for part-machine clustering based on a relationship between interval graphs and Robinson matrices

An important manufacturing cell formation problem requires permutations of the rows (parts) and columns (machines) of a part-machine incidence matrix such that the reordered matrix exhibits a block-diagonal form. Numerous objective criteria and algorithms have been proposed for this problem. In this paper, a new perspective is offered that is based on the relationship between the consecutive ones property associated with interval graphs and Robinson structure within symmetric matrices. This perspective enables the cell formation problem to be decomposed into two permutation subproblems (one for rows and one for columns) that can be solved optimally using dynamic programming or a branch-and-bound algorithm for matrices of nontrivial size. A simulated annealing heuristic is offered for larger problem instances. Results pertaining to the application of the proposed methods for a number of problems from the literature are presented.     

A priority rule-based constructive heuristic and an improvement method for balancing assembly lines with parallel multi-manned workstations

Assembly lines of big-size products such as buses, trucks and helicopters are very different from the lines studied in the literature. These products’ manufacturing processes have a lot of tasks most of which have long task times. Since traditional assembly line models including only one worker in each station (i.e. simple assembly lines) or at most two workers (two-sided assembly lines) may not be suitable for manufacturing these type of products, they need much larger shop floor for a number of stations and long product flow times. In this study, an assembly line balancing problem (ALBP) with parallel multi-manned stations is considered. Following the problem definition, a mixed integer programming formulation is developed. A detailed study of priority rules for simple ALBPs is also presented, and a new efficient constructive heuristic algorithm based on priority rules is proposed. In order to improve solutions found by the constructive heuristic, a genetic algorithm-based solution procedure is also presented. Benchmark instances in the literature are solved by using the proposed mathematical programming formulation. It has been seen that only some of the small-size instances can be solved optimally by this way. So the efficiency of the proposed heuristic method is verified in small-size instances whose optimal solutions are found. For medium- and big-size instances, heuristics’ results and CPU times are demonstrated. A comparative evaluation with a branch and bound algorithm that can be found in the literature is also carried out, and results are presented.     

A heuristic for multi-level lot-sizing problems with a bottleneck

A simple heuristic is proposed for multi-level lot-sizing problems where there is a bottleneck. Previous methods to solve this problem have formulated the problem as an integer programming problem and solved the problem using a Lagrangian relaxation embedded within the branch and bound procedure. In this paper we suggest that items to be produced can be grouped into two types and a simple but efficient heuristic can be used to determine the production quantities required. A program was developed to compute production levels and was found to require only a small fraction of the computer time required by the full integer programming approach, and to produce solutions of reasonable quality. The heuristic is simple to implement.     

ROBOT TASK SCHEDULING IN A FLEXIBLE MANUFACTURING CELL

Effective sequencing and scheduling of the material handling system can have a major impact on the productivity of the manufacturing system. This is especially true in the case where material handling times are on par with machine processing times. In a dynamic, real-time environment, the optimal solution of this scheduling problem may be computationally infeasible.

In this paper, we develop a branch and bound approach which is coupled with quick, effective bounds to optimize the movement of a robot which serves the material handling requirements within a manufacturing cell. Computational results are given which explore the tradeoff between computation time and deviation from optimal for different scenarios.     

Aggregate line capacity design for PWB assembly systems

In a multi-product, flexible manufacturing environment, line capacity of printed wiring board (PWB) assembly systems may need to be adjusted at the beginning of each aggregate planning period because of demand fluctuation over multiple periods. A model of production planning and equipment changeover scheduling at the aggregate level is developed. In the described model, three kinds of equipment changeover methods, i.e. adding machine, removing machine and transferring machine, are involved. Because the model is a large-scale integer programming problem, it cannot be solved directly. A solution approach is developed, which first solves a recursive linear programming problem to obtain a rough set of machines to be added and a rough set of machines to be removed for each machine line in each period, then applies a branch and bound heuristic to the rough sets to obtain near-optimal solutions to the equipment changeover scheduling problem. Computational studies show the financial benefit both on capital cost and equipment changeover costs.     

Fractional cell formation in group technology

Group Technology (GT) aims at improving productivity in batch manufacturing. Here components are divided into families and machines into cells such that every component in a part family visits maximum number of machines in the assigned cell with an objective of minimizing inter-cell movement. In situations where too many inter-cell moves exist, fractional cell formation using remainder cells can be used. Here, machines are grouped into GT cells and a remainder cell, which functions like a job shop. Component families are formed such that the components visit the assigned cell and the remainder cell and do not visit other cells. The fractional cell formation problem to minimise inter-cell moves is formulated as a linear integer programming problem. Here, movement between machine cells and remainder cells is not counted as inter-cell moves but movement of components among GT cells is considered as inter-cell movement. The fractional cell formation problem is solved using Simulated Annealing. A heuristic algorithm is developed to solve large sized GT matrices. These have applied to a variety of matrices from GT literature and tested on randomly generated matrices. Computational experiences with the algorithms are presented     

Schedules for a two-stage hybrid flowshop with parallel machines at the second stage

Approximate solution algorithms are developed to find a minimum makespan schedule in a two-stage hybrid flowshop when the second stage consists of multiple identical machines. Computational experience comparing the ‘approximate’ makespans with their respective global lower bounds for large problems indicates that proposed polynomially bounded approximate algorithms are quite effective. It is shown that the proposed heuristic algorithms can be used to improve the efficiency of an existing branch and bound algorithm.     

A within-cell utilization based heuristic for designing cellular manufacturing systems

The initial stage in the facilities design of cellular manufacturing systems involves the identification of part families and machine groups and forming cells possessing specific manufacturing capabilities. A new heuristic for the part family/machine group formation (PF/MGF) problem is presented in this paper. The distinguishing feature of this heuristic is its consideration of several practical criteria such as within-cell machine utilization, work load fractions, maximum number of machines that are assigned to a cell, and the percentage of operations of parts completed within a single cell. Computational results, based on several examples from the literature, show that this heuristic performs well with respect to more than one criteria. The heuristic also clarifies the source of various arguments in the literature concerning the ‘goodness’ of the solutions obtained by other researchers. An application of the heuristic to a large sample of industrial data involving 45 workcentres composed of 64 machines, and 305 parts is given, and the usefulness of the heuristic for trading-off several objectives is illustrated.     

Solving an apparel trim placement problem using a maximum cover problem approach

A trim placement problem from the apparel industry is presented and solved. The problem is related to cutting and packing problems, which have received attention in the literature for close to 40 years. The problem is motivated by a pants layout problem involving irregularly-shaped pieces. A two-stage strategy is commonly employed, with large pieces, or panels, arranged first, followed by smaller pieces, or trim. This paper assumes the panels have been arranged, and presents an approach for placing the trim pieces into unused “containers” of the stock material. Groups of trim pieces are first generated using existing polygon containment algorithms. Then, groups are assigned to containers to maximize a weighted function of the trim pieces. The mathematical programming formulation is developed, which is a generalization of the Maximum Cover Problem, a well-known problem in the location literature. Due to wide variability in branch and bound solution times, a Lagrangian Heuristic incorporating an improvement heuristic is developed. Computational experience demonstrates the effectiveness of the Lagrangian Heuristic on real pants markers. The optimal solution is found for all, and solution times are less than branch and bound in 10 out of 12 problem instances (considerably less in three), and only slightly more in the other two. Times are also less variable than branch and bound, an important characteristic with an interactive layout system.     

Forming effective worker teams for cellular manufacturing

Cellular manufacturing has been extensively adopted as a measure to reduce cycle time, increase productivity, and improve product quality. The past research in cellular manufacturing has focused on the methodology for identification of machine groups, part families, and determination of processing routes. The relocation of existing workers into cells and their training for a team-oriented, cellular manufacturing environment have largely been ignored. In this research, a mixed integer, goal programming model is formulated for guiding the worker assignment and training process to create worker teams with high team synergy and individual job fitness meeting cell requirements for technical and administrative skills. The model integrates psychological, organizational, and technical factors. Several solution methods including greedy heuristic, filtered beam search, and simulated annealing techniques are developed and tested. It appears that heuristics such as beam search are capable of obtaining good solutions with reasonable computational effort.