An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem

Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. Although the traditional optimization algorithms could obtain preferable results in solving the mono-objective FJSP. However, they are very difficult to solve multi-objective FJSP very well. In this paper, a particle swarm optimization (PSO) algorithm and a tabu search (TS) algorithm are combined to solve the multi-objective FJSP with several conflicting and incommensurable objectives. PSO which integrates local search and global search scheme possesses high search efficiency. And, TS is a meta-heuristic which is designed for finding a near optimal solution of combinatorial optimization problems. Through reasonably hybridizing the two optimization algorithms, an effective hybrid approach for the multi-objective FJSP has been proposed. The computational results have proved that the proposed hybrid algorithm is an efficient and effective approach to solve the multi-objective FJSP, especially for the problems on a large scale.     

An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems

This paper proposes an effective hybrid tabu search algorithm (HTSA) to solve the flexible job-shop scheduling problem. Three minimization objectives – the maximum completion time (makespan), the total workload of machines and the workload of the critical machine are considered simultaneously. In this study, a tabu search (TS) algorithm with an effective neighborhood structure combining two adaptive rules is developed, which constructs improved local search in the machine assignment module. Then, a well-designed left-shift decoding function is defined to transform a solution to an active schedule. In addition, a variable neighborhood search (VNS) algorithm integrating three insert and swap neighborhood structures based on public critical block theory is presented to perform local search in the operation scheduling component. The proposed HTSA is tested on sets of the well-known benchmark instances. The statistical analysis of performance comparisons shows that the proposed HTSA is superior to four existing algorithms including the AL + CGA algorithm by Kacem, Hammadi, and Borne (2002b), the PSO + SA algorithm by Xia and Wu (2005), the PSO + TS algorithm by Zhang, Shao, Li, and Gao (2009), and the Xing’s algorithm by Xing, Chen, and Yang (2009a) in terms of both solution quality and efficiency.     

A hierarchic approach to production planning and scheduling of a flexible manufacturing system

The paper deals with the problem of improving the machine utilization of a flexible manufacturing cell. Limited tool magazine space of the machines turns out to be a relevant bottleneck. A hierarchic approach for this problem is proposed. At the upper level, sets of parts that can be concurrently processed (batches) are determined. At the lower levels, batches are sequenced, linked, and scheduled. Methods taken from the literature are used for the solution of the latter subproblems, and an original mixed integer programming model is formulated to determine batches. The proposed methods are discussed on the basis of computational experience carried out on real instances.     

An optimal batch size for a production system operating under periodic delivery policy

A manufacturing system that procures raw materials from suppliers in a lot and processes them into a finished product is considered in this research. An ordering policy is proposed for raw materials to meet the requirements of a production facility which, in turn, must deliver finished products demanded by outside buyers at fixed points in time. First, a general cost model is formulated considering both raw materials and finished products. Then, using this model, a simple procedure is developed to determine an optimal ordering policy for procurement of raw materials, and the manufacturing batch size, to minimize the total cost of meeting customer demands in time. The dependent relationships between production batch size and rawmaterial purchasing quantity, and various delivery patterns considered in recent literature are critically reviewed. The quality of the solution is evaluated. Numerical examples are provided.     

基于TS/VDS算法的涤纶短纤维生产调度优化

采用禁忌搜索（ＴＳ）／变深度搜索（ＶＤＳ）混合算法对涤纶短纤维生产调度优化问题进行优化．混合算法通过改变常规ＴＳ算法邻域,采用变深度搜索技术增强了算法寻优能力．某大型石化企业实际数据的实验结果表明,该算法在寻优能力和求解时间上比常规ＴＳ算法更加有效,能够在更短的时间内获得满意解,对于解决多产品多阶段连续生产调度问题具有实用价值．     

A deterministic tabu search algorithm for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a difficult optimisation problem in vehicle routing with applications where a service must be provided by a set of vehicles on specified roads. A heuristic algorithm based on tabu search is proposed and tested on various sets of benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature.     

An adaptive tabu search approach for buffer allocation problem in unreliable non-homogenous production lines

The buffer allocation problem, i.e. how much buffer storage to allow and where to place it within the line, is an important research issue in designing production lines. In this study, a novel adaptive tabu search approach is proposed for solving buffer allocation problem in unreliable and non-homogeneous production lines. The objective is to maximize the throughput of the line, which is constrained by the capacity of each buffer space and also the total buffer capacity to allocate to these spaces. Besides proposing a new strategy to tune the parameters of tabu search adaptively during the search, an experimental study is carried out to select an intelligent initial solution scheme among three alternatives so as to decrease the search effort to obtain the best solutions. The performance of the proposed approach is evaluated by computational tests and very promising results are obtained.     

New local diversification techniques for flexible job shop scheduling problem with a multi-agent approach

The Flexible Job Shop problem is among the hardest scheduling problems. It is a generalization of the classical Job Shop problem in that each operation can be processed by a set of resources and has a processing time depending on the resource used. The objective is to assign and to sequence the operations on the resources so that they are processed in the smallest time. In our previous work, we have proposed two Multi-Agent approaches based on the Tabu Search (TS) meta-heuristic. Depending on the location of the optimisation core in the system, we have distinguished between the global optimisation approach where the TS has a global view on the system and the local optimisation approach (FJS MATSLO) where the optimisation is distributed among a collection of agents, each of them has its own local view. In this paper, firstly, we propose new diversification techniques for the second approach in order to get better results and secondly, we propose a new promising approach combining the two latter ones. Experimental results are also presented in this paper in order to evaluate these new techniques.     

Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem

The multi-objective flexible job shop scheduling problem is solved using a novel path-relinking algorithm based on the state-of-the-art Tabu search algorithm with back-jump tracking. A routing solution is identified by problem-specific neighborhood search, and is then further refined by the Tabu search algorithm with back-jump tracking for a sequencing decision. The resultant solution is used to maintain the medium-term memory where the best solutions are stored. A path-relinking heuristics is designed to generate diverse solutions in the most promising areas. An improved version of the algorithm is then developed by incorporating an effective dimension-oriented intensification search to find solutions that are located near extreme solutions. The proposed algorithms are tested on benchmark instances and its experimental performance is compared with that of algorithms in the literature. Comparison results show that the proposed algorithms are competitive in terms of its computation performance and solution quality.     

A hybrid Jaya algorithm for solving flexible job shop scheduling problem considering multiple critical paths

As an extension of the classical job shop scheduling problem, flexible job shop scheduling problem (FJSP) is considered as a challenge in manufacturing systems for its complexity and flexibility. Meta-heuristic algorithms are shown effective in solving FJSP. However, the multiple critical paths issue, which has not been formally discussed in the existing literature, is discovered to be a primary obstacle for further optimization by meta-heuristics. In this paper, a hybrid Jaya algorithm integrated with Tabu search is proposed to solve FJSP for makespan minimization. Two Jaya operators are designed to improve solutions under a two-vector encoding scheme. During the local search phase, three approaches are proposed to deal with multiple critical paths and have been evaluated by experimental study and qualitative analyses. An incremental parameter setting strategy and a makespan estimation method are employed to speed up the searching process. The proposed algorithm is compared with several state-of-the-art algorithms on three well-known FJSP benchmark sets. Extensive experimental results suggest its superiority in both optimality and stability. Additionally, a real world scheduling problem, including six instances with different scales, is applied to further prove its ability in handling large-scale scheduling problems.     

An efficient search method for multi-objective flexible job shop scheduling problems

Flexible job shop scheduling is very important in both fields of production management and combinatorial optimization. Owing to the high computational complexity, it is quite difficult to achieve an optimal solution to this problem with traditional optimization approaches. Motivated by some empirical knowledge, we propose an efficient search method for the multi-objective flexible job shop scheduling problems in this paper. Through the work presented in this work, we hope to move a step closer to the ultimate vision of an automated system for generating optimal or near-optimal production schedules. The final experimental results have shown that the proposed algorithm is a feasible and effective approach for the multi-objective flexible job shop scheduling problems.     

Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem

In this paper, we develop an extended guided tabu search (EGTS) and a new heuristic packing algorithm for the two-dimensional loading vehicle routing problem (2L-CVRP). The 2L-CVRP is a combination of two well-known NP-hard problems, the capacitated vehicle routing problem, and the two-dimensional bin packing problem. It is very difficult to get a good performance solution in practice for these problems. We propose a meta-heuristic methodology EGTS which incorporates theories of tabu search and extended guided local search (EGLS). It has been proved that tabu search is a very good approach for the CVRP, and the guiding mechanism of the EGLS can help tabu search to escape effectively from local optimum. Furthermore, we have modified a collection of packing heuristics by adding a new packing heuristic to solve the loading constraints in 2L-CVRP, in order to improve the cost function significantly. The effectiveness of the proposed algorithm is tested, and proven by extensive computational experiments on benchmark instances.     

Using tabu search with ranking candidate list to solve production planning problems with setups

This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. It can be formulated as a mixed integer program (MIP). Solving a realistic MIP production planning problem is NP-hard; therefore, we use tabu search methods to solve such a difficult problem. Furthermore, we improve tabu search by a new candidate list strategy, which sorts the neighbor solutions using post-optimization information provided by the final tableau of the linear programming simplex algorithm. A neighbor solution with higher priority in the ranking sequence has a higher probability of being the best neighbor solution of a current solution. According to our experiments, the proposed candidate list strategy tabu search produces a good solution faster than the traditional simple tabu search. This study also suggests that if the evaluation of the entire neighborhood space in a tabu search algorithm takes too much computation and if an efficient and effective heuristic to rank the neighbor solutions can be developed, the speed of tabu search algorithm could be significantly increased by using the proposed candidate list strategy.     

Parallel hybrid metaheuristics for the flexible job shop problem

A parallel approach to flexible job shop scheduling problem is presented in this paper. We propose two double-level parallel metaheuristic algorithms based on the new method of the neighborhood determination. Algorithms proposed here include two major modules: the machine selection module refer to executed sequentially, and the operation scheduling module executed in parallel. On each level a metaheuristic algorithm is used, therefore we call this method meta²heuristics. We carry out a computational experiment using Graphics Processing Units (GPU). It was possible to obtain the new best known solutions for the benchmark instances from the literature.     

A Tabu-enhanced genetic algorithm approach for assembly process planning

Over the past decade, much work has been done to optimize assembly process plans to improve productivity. Among them, genetic algorithms (GAs) are one of the most widely used techniques. Basically, GAs are optimization methodologies based on a direct analogy to Darwinian natural selection and genetics in biological systems. They can deal with complex product assembly planning. However, during the process, the neighborhood may converge too fast and limit the search to a local optimum prematurely. In a similar domain, Tabu search (TS) constitutes a meta-procedure that organizes and directs the operation of a search process. It is able to systematically impose and release constraints so as to permit the exploration of otherwise forbidden regions in a search space. This study attempts to combine the strengths of GAs and TS to realize a hybrid approach for optimal assembly process planning. More robust search behavior can possibly be obtained by incorporating the Tabus intensification and diversification strategies into GAs. The hybrid approach also takes into account assembly guidelines and assembly constraints in the derivation of near optimal assembly process plans. A case study on a cordless telephone assembly is used to demonstrate the approach. Results show that the assembly process plans obtained are superior to those derived by GA alone. The details of the hybrid approach and the case study are presented.     

Tabu search algorithm for DNA sequencing by hybridization with multiplicity information available

The classical DNA sequencing by hybridization (SBH) uses a binary information about oligonucleotide presence in an analyzed DNA sequence. A given oligonucleotide is or is not a part of the sequence. However, the development of the DNA chip technology allows to take into consideration some information about repetitions in the target sequence. Currently, it is not possible to determine the exact data of such type but even partial multiplicity information should be very useful.In this paper two simple but realistic multiplicity information models are taken into account. The first one assumes that it is known if a given oligonucleotide occurs in the analyzed sequence once or more than once. According to the second model it is possible to determine if a given oligonucleotide appears in the target sequence once, twice or at least three times. A tabu search algorithm has been implemented to verify these models. It solves the problem with any kind of hybridization errors. Computational experiment results confirm that the additional information leads to an improvement of the reconstruction process. They also show that the more precise model of information increases the quality of the obtained solutions.Test data sets and the implemented tabu search algorithm are available on: http://bio.cs.put.poznan.pl/files/52234a7c9dfb89b808000001/download.     

一类Job- shop 车间生产计划和调度的集成优化

讨论一类Job—shop车间的生产计划和调度的集成优化问题，给出了该问题的非线性混合整数规划模型，并采用混合遗传算法进行求解。该模型利用调度约束来细化生产计划，以保证得到可行的调度解。在混合算法中，利用启发式规则来改善初始解集，并采用分段编码策略将计划和调度解映射为染色体。算例研究表明，该算法对求解该类问题具有很好的效果。     

Hierarchical stochastic production planning for flexible automation workshops

This paper presents the hierarchical stochastic production planning (HSPP) problem for flexible automation workshops (FAWs) in agile manufacturing environments, which is a multiple-period multiple-product problem with random material supply, demands, capacities, processing times, rework and waste products. To solve the HSPP problem, a mathematical model is built up first. Then, an algorithm for HSPP is deduced in detail by using a stochastic interaction/prediction approach. The corresponding software package named as stochastic interaction/prediction algorithm (SIPA) has been developed and is presented in this paper, through which examples of HSPP have been studied, and which show that the algorithm can optimally decompose medium-term random product demand plans of an FAW into short-term stochastic production plans to be executed by FMSs in the FAW. Finally, the application of the algorithm is presented in detail through one of those examples.     

A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service

The vehicle routing problem with simultaneous pick-up and delivery (VRP_SPD) is a variant of the classical vehicle routing problem (VRP) where clients require simultaneous pick-up and delivery service. Deliveries are supplied from a single depot at the beginning of the vehicle's service, while pick-up loads are taken to the same depot at the conclusion of the service. One important characteristic of this problem is that a vehicle's load in any given route is a mix of pick-up and delivery loads.