Cell formation in group technology: A combinatorial search approach

This paper addresses the cell formation problem in group technology (GT). We develop two heuristic methods for generating solutions to the problem. These methods are based on two powerful combinatorial search methods simulated annealing and tabu search. The performance of the heuristics is examined using randomly generated, published and industry data. The results indicate that the simulated annealing based heuristic is the preferred technique in the context of the problem addressed in this paper. Further, we also demonstrate that the simulated annealing based heuristic generates near-optimal solutions to the cell formation model formulated in this paper.     

Unrelated parallel machine scheduling with job splitting

Scheduling jobs on unrelated parallel machines is an activity that is very much a part of industrial scheduling. We report a methodology for minimizing the total weighted tardiness of all jobs intended to be processed on unrelated parallel machines in the presence of dynamic job releases and dynamic machine availability. More importantly, the mixed (binary) integer linear programming model formulated for the problem incorporates a couple of “hard” operational constraints to ensure that just-in-time manufacturing practices are followed by controlling the work-in-process and/or finished goods inventories generated by split jobs mandated by a tight due date, a high priority, and/or a high workload. Four different methods based on simple and composite dispatching rules are used to identify an initial solution, which is then used by the tabu-search-based heuristic solution algorithm to ultimately find the best solution. Incorporating the various tabu search features led to the development of six different heuristics that were tested on eight small problem instances to compare the quality of their solutions to the optimal solutions. The results show that the proposed heuristics are capable of obtaining solutions of good quality in a remarkably short computation time with the best performer among them recording a percentage deviation of only 1.18%. A factorial experiment based on a split-plot design is performed to test the performance of the heuristics on problem structures, ranging from nine jobs and three machines to 60 jobs and 15 machines. The results show that the newly developed composite dispatching heuristic, referred to as the modified apparent tardiness cost, is capable of obtaining initial solutions that significantly accelerate the tabu-search-based heuristics to attain the best solution. The use of a long-term memory function is proven to be advantageous in solving all problem structures. In addition, the variable tabu list size is preferred for solving the small problem structure, while the fixed tabu list size is preferred as the problem size grows from small to medium and then large.     

A hybrid genetic algorithm for the multi-depot open vehicle routing problem

This paper studies the multi-depot open vehicle routing problem (MDOVRP), a variant of the vehicle routing problem (VRP), in which vehicles start from several depots and are not required to return to the depot. Despite the vast amount of literature about VRPs, the MDOVRP has received very little attention from researchers. In this paper, a new hybrid genetic algorithm is presented for finding the routes that minimize the traveling cost of the vehicles. Computational results on a number of test instances indicate the proposed algorithm dominates the CPLEX solver and the existing approach in the literature. Meanwhile, experiments are conducted on multi-depot VRP benchmarks, and the results are compared with a sophisticated tabu search approach and an exact method.     

New Tabu search heuristics for the dynamic facility layout problem

A manufacturing facility is a dynamic system that constantly evolves due to changes such as changes in product demands, product designs, or replacement of production equipment. As a result, the dynamic facility layout problem (DFLP) considers these changes and is defined as the problem of assigning departments to locations during a multi-period planning horizon such that the sum of the material handling and re-arrangement costs is minimised. In this paper, three tabu search (TS) heuristics are presented for this problem. The first heuristic is a simple TS heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic TS heuristic. To test the performances of the heuristics, two sets of test problems from the literature are used in the analysis. The results show that the second heuristic out-performs the other proposed heuristics and the heuristics available in the literature.     

Sequencing algorithms for multiple arc-welding robots considering thermal distortion

This paper focuses on sequencing welding lines in multiple arc-welding robot systems, which is the problem of assigning individual welding operations to robots as well as determining their sequences with the objective of minimizing the maximum completion time. Each welding operation is denoted by a weld line with two end-points, each of which can be a possible starting point for the welding operation. Thermal distortion is explicitly considered by introducing a delay between welding operations associated with weld lines near each other. Due to the complexity of the problem, this paper suggests three types of search heuristics, genetic algorithms, simulated annealing and tabu search, each of which incorporates new methods to generate neighbourhood solutions. To show the performances of the heuristics, computational experiments are performed on a number of randomly generated test problems, and the results are reported. In particular, some of the search heuristics outperform the exiting method.     

A hybrid adaptive large neighbourhood search for multi-depot open vehicle routing problems

In this paper we address the multi-depot open vehicle routing problem (MDOVRP), a complex and difficult problem arising in several real-life applications. In the MDOVRP vehicles start from several depots and do not need to return to the depot at the end of their routes. We propose a hybrid adaptive large neighbourhood search algorithm to solve the MDOVRP coupled with improvement procedures yielding a hybrid metaheuristic. The performance of the proposed metaheuristic is assessed on various benchmark instances proposed for this problem and its special cases, containing up to 48 customers (single-depot version) and up to six depots and 288 customers. The computational results indicate that the proposed algorithm is very competitive compared with the state-of-the-art methods and improves 15 best-known solutions for multi-depot instances and one best-known solution for a single-depot instance. A detailed sensitivity analysis highlights which components of the metaheuristic contribute most to the solution quality.     

Scheduling multistage hybrid flowshops with multiprocessor tasks by an effective heuristic

This study considers the scheduling problem of multistage hybrid flowshops with multiprocessor tasks, which is a core topic for numerous industrial applications. An effective and efficient heuristic, namely the heuristic of multistage hybrid flowshops (HMHF) is proposed to solve this problem. To verify the developed heuristic, computational experiments are conducted on a well-known benchmark problem set. The results are compared with 10 constructive heuristics and a tabu search (TS) based meta-heuristic from the relevant literature. These computational results show that the proposed HMHF heuristic is highly effective when compared to these algorithms for this problem on the same benchmark instances.     

Local search heuristics for the probabilistic dial-a-ride problem

This paper introduces the probabilistic dial-a-ride problem, and describes an efficient request-relocation neighborhood evaluation procedure for the problem. The running time of the procedure is O(n⁵){\mathcal{O}(n^5)} , compared to O(n⁶){\mathcal{O}(n^6)} for a straightforward approach. For solving the problem we embed the suggested evaluation procedure in a pure local search heuristic and in a tabu search heuristic. The quality of the solutions obtained by the two heuristics have been compared experimentally. Computational results confirm that our neighborhood evaluation technique is much faster than the straightforward one, and for cases with 144 users and 4 vehicles it is demonstrated that the computation time can be reduced by a factor larger than 27.     

Search heuristics for operation sequencing in process planning

The operation-sequencing problem in process planning is considered to produce a part with the objective of minimizing the sum of machine, setup and tool change costs. In general, the problem has combinatorial characteristics and complex precedence relations, which makes the problem difficult to solve. Six local search heuristics have been developed based on simulated annealing and tabu search to obtain good solutions for practical-sized problems within a reasonable amount of computation time. Application of the algorithms is illustrated using an example part. Also, computational experiments were done on randomly generated problems and the results show that the tabu search-based algorithms are better than the simulated annealing-based algorithms on overall average. In particular, one of the tabu search algorithms suggested here gave optimal solutions for most small-sized test problems within very short computation times.     

An implementation of the iterated tabu search algorithm for the quadratic assignment problem

In this paper, we describe an implementation of the iterated tabu search (ITS) algorithm for the quadratic assignment problem (QAP), which is one of the well-known problems in combinatorial optimization. The medium- and large-scale QAPs are not, to this date, practically solvable to optimality, therefore heuristic algorithms are widely used. In the proposed ITS approach, intensification and diversification mechanisms are combined in a proper way. The goal of intensification is to search for good solutions in the neighbourhood of a given solution, while diversification is responsible for escaping from local optima and moving towards new regions of the search space. In particular, the following enhancements were implemented: new formula for fast evaluation of the objective function and efficient data structure; extended intensification mechanisms (including randomized tabu criterion, combination of tabu search and local search, dynamic tabu list maintaining); enhanced diversification strategy using periodic tabu tenure and special mutation procedure. The ITS algorithm is tested on the different instances taken from the QAP library QAPLIB. The results from the experiments demonstrate promising efficiency of the proposed algorithm, especially for the random QAP instances.     

Heuristics for the generalised assignment problem: simulated annealing and tabu search approaches

The generalised assignment problem (GAP) is the problem of finding a minimum cost assignment of a set of jobs to a set of agents. Each job is assigned to exactly one agent. The total demands of all jobs assigned to any agent can not exceed the total resources available to that agent. A review of exact and heuristic methods is presented. A-generation mechanism is introduced. Different search strategies and parameter settings are investigated for the-generation descent, hybrid simulated annealing/tabu search and tabu search heuristic methods. The developed methods incorporate a number of features that have proven useful for obtaining optimal and near optimal solutions. The effectiveness of our approaches is established by comparing their performance in terms of solution quality and computional requirement to other specialized branch-and-bound tree search, simulated annealing and set partitioning heuristics on a set of standard problems from the literature.     

A methodology for solving the unequal area facility layout problem using distance and shape-based measures

This paper presents a methodology for solving the unequal area facility layout problem commonly encountered in industry practice. A mixed-binary nonlinear-programming model is formulated to capture the operational issues encountered on the shop floor. In particular, in addition to the distance measure that is typically used to quantify the material handling costs, the impact of geometry or the shape of the departments is quantified in the formulation of the model. A higher-level heuristic solution algorithm, based on a concept known as ‘tabu search’, is proposed to efficiently solve industry-relevant problems. The methodology not only considers the impact of both distance and shape-based measures simultaneously in the proposed initial solution finding mechanism, but also in the evaluation of the objective function during the entire search procedure, in the hope that it will lead to identifying a better final solution. Taking into consideration fixed and variable tabu list sizes, along with long-term memory with maximum and minimum frequencies, has led to developing six different heuristics for the solution algorithm. A single factor experiment based on randomized block design has been used to compare the performances of the six different heuristics on three different problem structures—small, medium, and large—using the total cost as the criterion. Based on this experiment, the characterizations of search procedures have been recommended to facilitate identifying the best solution for each problem structure. The proposed method is also compared with those in the published literature by solving fairly well known unequal area facility layout problems. When an improvement is observed, the comparison has led to identifying a percentage improvement in total cost of approximately 2.8% to 11.8%, thus demonstrating the effectiveness of the model and the algorithm.     

Response to Al-Hakim's note

Storage location assignment and interleaving policy are two closely related problems in warehousing management. This paper addresses the location assignment and interleaving problem at the same time in an automated storage/retrieval system with duration-of-stay based shared storage policy. Based on the heuristics for single command operation, a two-step procedure is developed to solve the problem. A tabu search algorithm is proposed to improve the solution for medium and large sized problems. The computational results indicate that the tabu search algorithm is effective in finding high quality solutions, and efficient in solving large sized problems.     

The Multi-Product Production Cycling Problem

The multi-product production cycling problem is concerned with the determination of a production/inventory policy for a single capacitated production facility which is dedicated to producing a family of products. This paper studies this problem assuming stochastic demand. The one-product problem may be analyzed as a Markov decision problem and solved as such. For the multi-product problem, a heuristic decision rule is proposed based on the analysis of the one-product problem, and a new notion: the composite product. This heuristic is then tested by simulation on a series of problems, and is shown to be the most effective of the heuristics considered for the set of test problems     

Efficient heuristic approaches to transform job shops into flow shops

In this paper, we address the problem of transforming a job shop layout into a flow shop with the objective of minimizing the length of the resulting flow line. Since this problem is NP-hard, we focus our attention on developing high quality approximate solutions. We start by reviewing existing heuristics for the problem as well as some heuristics developed for the Shortest Common Supersequence problem, a well-known stringology problem similar to the one under consideration. We then present a new decomposition approach for the problem that allows the application of local search techniques. We have embedded this approach into a tabu search procedure that is shown to be effective in subsequent computational experiments. Finally, we provide best-so-far solutions for classical job shop problem instances, so they can be used as benchmark instances for further research.     

Flexible job-shop scheduling problems with ‘AND’/‘OR’ precedence constraints

The purpose of this research is to solve flexible job-shop scheduling problems with ‘AND’/‘OR’ precedence constraints in the operations. We first formulate the problem as a Mixed-Integer Linear Program (MILP). The MILP can be used to compute optimal solutions for small-sized problems. We also developed a heuristic algorithm that can obtain a good solution for the problem regardless of its size. Moreover, we have developed a representation and schedule builder that always produces a legal and feasible solution for the problem, and developed genetic and tabu search algorithms based on the proposed schedule builder. The results of the computational experiments show that the developed meta-heuristics are very effective.     

带时限与回程的配送中心运输调度问题研究

在优化模型中将配送任务执行时间及每日调用车辆数量及路径作为决策对象,以车辆的固定费用、行驶费用、未按时完成服务产生的惩罚、存储费用等作为优化目标。在遗传算法中采用自然数编码形式以便于优化车辆数量,采用基于扫描算法的启发式算法构造更好的初始解,引入单亲遗传算子、重启机制及并行禁忌搜索以提高种群质量和深度寻优。经不同规模算例间对比测试,显示基于扫描算法的混合遗传算法具有最佳的优化性能。     

Modelling and optimization of the assembly process in a flexible cell for aircraft panel manufacturing

In this paper we consider a manufacturing problem arising in a robotic cell for aircraft panels assembly. An initial technological analysis has shown that some mechanical assembly phases, which involve a huge amount of riveting and screwing operations, can be automated. The motivation of this research is to find the most profitable sequencing of the operations from the viewpoint of throughput time. In particular, we focus on the set-up activities related to switching between operations. The problem is to find the permutation of operations such that the overall switching time is a minimum. In the situation on hand, major precedence constraints among the operations hold. The problem is formulated as an instance of the well-known 'sequential ordering problem', for which we propose a tabu search solution heuristic. In this paper we report on both the modelling process and the solution procedures.     

Evaluating artificial intelligence heuristics for a flexible Kanban system: simultaneous Kanban controlling and scheduling

This paper evaluates several artificial intelligence heuristics for a simultaneous Kanban controlling and scheduling on a flexible Kanban system. The objective of the problem is to minimise a total production cost that includes due date penalty, inventory, and machining costs. We show that the simultaneous Kanban controlling and scheduling is critical in minimising the total production cost (approximately 30% cost reduction over scheduling without a Kanban controlling). To identify the most effective search method for the simultaneous Kanban controlling and scheduling, we evaluated widely known artificial intelligence heuristics: genetic algorithm, simulated annealing, tabu search, and neighbourhood search. Computational results show that the tabu search performs the best in terms of solution quality. The tabu search also requires a much less computational time than the genetic algorithm and the simulated annealing. To further improve the solution quality and computational time for a simultaneous Kanban controlling and scheduling on a flexible Kanban system, we developed a two-stage tabu search. At the beginning of the tabu search process, an initial solution is constructed by utilising the customer due date information given by a decision support system. The two-stage tabu search performs better than the tabu search with a randomly generated initial solution in both the solution quality and computational time across all problem sizes. The difference in the solution quality is more pronounced at the early stages of the search.