A PSO and a Tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application

The assembly flowshop scheduling problem has been addressed recently in the literature. There are many problems that can be modeled as assembly flowshop scheduling problems including queries scheduling on distributed database systems and computer manufacturing. The problem has been addressed with respect to either makespan or total completion time criterion in the literature. In this paper, we address the problem with respect to a due date-based performance measure, i.e., maximum lateness. We formulate the problem and obtain a dominance relation. Moreover, we propose three heuristics for the problem: particle swarm optimization (PSO), Tabu search, and EDD. PSO has been used in the areas of function optimization, artificial neural network training, and fuzzy system control in the literature. In this paper, we show how it can be used for scheduling problems. We have conducted extensive computational experiments to compare the three heuristics along with a random solution. The computational analysis indicates that Tabu outperforms the others for the case when the due dates range is relatively wide. It also indicates that the PSO significantly outperforms the others for difficult problems, i.e., tight due dates. Moreover, for difficult problems, the developed dominance relation helps reduce error by 65%.     

A comparative study of heuristic algorithms on Economic Lot Scheduling Problem

The Economic Lot Scheduling Problem (ELSP) has been well-researched for more than 40 years. As the ELSP has been generally seen as NP-hard, researchers have focused on the development of efficient heuristic approaches. In this paper, we consider the time-varying lot size approach to solve the ELSP. A computational study of the existing solution algorithms, Dobson’s heuristic, Hybrid Genetic algorithm, Neighborhood Search heuristics, Tabu Search and the newly proposed Simulated Annealing algorithm are presented. The reviewed methods are first tested on two well-known problems, those of Bomberger’s [Bomberger, E. E. (1966). A dynamic programming approach to a lot size scheduling problem. Management Science 12, 778–784] and Mallya’s [Mallya, R (1992). Multi-product scheduling on a single machine: A case study. OMEGA: International Journal of Management Science 20, 529–534] problems. We show the Simulated Annealing algorithm finds the best known solution to these problems. A similar comparison study is performed on various problem sets previously suggested in the literature. The results show that the Simulated Annealing algorithm outperforms Dobson’s heuristic, Hybrid Genetic algorithm and Neighborhood search heuristics on these problem sets. The Simulated Annealing algorithm also shows faster convergence than the best known Tabu Search algorithm, yet results in solutions of a similar quality. Finally, we report the results of the design of experiment study which compares the robustness of the mentioned meta-heuristic techniques.     

Operation assignment and capacity allocation problem in automated manufacturing systems

We address an operation assignment and capacity allocation problem that arises in semiconductor industries and flexible manufacturing systems. We assume the automated machines have scarce time and tool magazine capacities and the tools are available in limited quantities. The aim is to select a subset of operations with maximum total weight. We show that the problem is NP-hard in the strong sense, develop two heuristics and a Tabu Search procedure. The results of our computational tests have revealed that our Tabu Search procedure produces near optimal solutions very quickly.     

Comparing descent heuristics and metaheuristics for the vehicle routing problem

Three improvement heuristics for the vehicle routing problem are considered: a descent heuristic and two metaheuristics Simulated Annealing and Tabu Search. In order to make an in-depth comparison of the performance of these improvement heuristics, their behavior is analyzed on a heuristic, time-sensitive level as well as on a parametric level. The design and the results of the experiments are outlined. The external validity of the conclusions is discussed.Scope and purposeTabu Search (TS) and Simulated Annealing (SA) have demonstrated to be appropriate metaheuristics for solving NP-hard combinatorial optimization problems, such as the vehicle routing problem with side-constraints. In order to compare the performances of both metaheuristics with each other and with a traditional descent implementation, a comparison of the best solution independent of computing times is fundamentally wrong because metaheuristics have no unambiguous stopping criteria, as opposed to traditional descent implementations.     

An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis

Clustering is a popular data analysis and data mining technique. A popular technique for clustering is based on k-means such that the data is partitioned into K clusters. However, the k-means algorithm highly depends on the initial state and converges to local optimum solution. This paper presents a new hybrid evolutionary algorithm to solve nonlinear partitional clustering problem. The proposed hybrid evolutionary algorithm is the combination of FAPSO (fuzzy adaptive particle swarm optimization), ACO (ant colony optimization) and k-means algorithms, called FAPSO-ACO–K, which can find better cluster partition. The performance of the proposed algorithm is evaluated through several benchmark data sets. The simulation results show that the performance of the proposed algorithm is better than other algorithms such as PSO, ACO, simulated annealing (SA), combination of PSO and SA (PSO–SA), combination of ACO and SA (ACO–SA), combination of PSO and ACO (PSO–ACO), genetic algorithm (GA), Tabu search (TS), honey bee mating optimization (HBMO) and k-means for partitional clustering problem.     

Heuristic methods for vehicle routing problem with time windows

This paper documents our investigation into various heuristic methods to solve the vehicle routing problem with time windows (VRPTW) to near optimal solutions. The objective of the VRPTW is to serve a number of customers within predefined time windows at minimum cost (in terms of distance travelled), without violating the capacity and total trip time constraints for each vehicle. Combinatorial optimisation problems of this kind are non-polynomial-hard (NP-hard) and are best solved by heuristics. The heuristics we are exploring here are mainly third-generation artificial intelligent (AI) algorithms, namely simulated annealing (SA), Tabu search (TS) and genetic algorithm (GA). Based on the original SA theory proposed by Kirkpatrick and the work by Thangiah, we update the cooling scheme and develop a fast and efficient SA heuristic. One of the variants of Glover's TS, strict Tabu, is evaluated and first used for VRPTW, with the help of both recency and frequency measures. Our GA implementation, unlike Thangiah's genetic sectoring heuristic, uses intuitive integer string representation and incorporates several new crossover operations and other advanced techniques such as hybrid hill-climbing and adaptive mutation scheme. We applied each of the heuristics developed to Solomon's 56 VRPTW 100-customer instances, and yielded 18 solutions better than or equivalent to the best solution ever published for these problems. This paper is also among the first to document the implementation of all the three advanced AI methods for VRPTW, together with their comprehensive results.     

A novel hybrid PSO–GA meta-heuristic for scheduling of DAG with communication on multiprocessor systems

This work presents a novel hybrid meta-heuristic that combines particle swarm optimization and genetic algorithm (PSO–GA) for the job/tasks in the form of directed acyclic graph (DAG) exhibiting inter-task communication. The proposed meta-heuristic starts with PSO and enters into GA when local best result from PSO is obtained. Thus, the proposed PSO–GA meta-heuristic is different than other such hybrid meta-heuristics as it aims at improving the solution obtained by PSO using GA. In the proposed meta-heuristic, PSO is used to provide diversification while GA is used to provide intensification. The PSO–GA is tested for task scheduling on two standard well-known linear algebra problems: LU decomposition and Gauss–Jordan elimination. It is also compared with other states-of-the-art heuristics for known solutions. Furthermore, its effectiveness is evaluated on few large sizes of random task graphs. Comparative study of the proposed PSO-GA with other heuristics depicts that the PSO–GA performs quite effectively for multiprocessor DAG scheduling problem.     

基于粒子群优化和禁忌搜索的混合调度算法

提出了用于解决作业车间调度问题的离散版粒子群优化算法。该算法采用基于先后表编码方案和新的位移更新模型,使具有连续本质的粒子群优化算法直接适用于车间调度问题。同时,利用粒子群优化算法的全局搜索能力和禁忌搜索算法的自适应优点,将粒子群优化算法和禁忌搜索结合起来,设计了广义粒子群优化算法和粒子群—禁忌搜索交替算法两种混合调度算法。实验结果表明,两种混合调度算法能够有效地、高质量地解决作业车间调度问题。     

Solving the multi-stage portfolio optimization problem with a novel particle swarm optimization

Solving the multi-stage portfolio optimization (MSPO) problem is very challenging due to nonlinearity of the problem and its high consumption of computational time. Many heuristic methods have been employed to tackle the problem. In this paper, we propose a novel variant of particle swarm optimization (PSO), called drift particle swarm optimization (DPSO), and apply it to the MSPO problem solving. The classical return-variance function is employed as the objective function, and experiments on the problems with different numbers of stages are conducted by using sample data from various stocks in S&P 100 index. We compare performance and effectiveness of DPSO, particle swarm optimization (PSO), genetic algorithm (GA) and two classical optimization solvers (LOQO and CPLEX), in terms of efficient frontiers, fitness values, convergence rates and computational time consumption. The experiment results show that DPSO is more efficient and effective in MSPO problem solving than other tested optimization tools.     

A study on particle swarm optimization and artificial bee colony algorithms for multilevel thresholding

Segmentation is a critical task in image processing. Bi-level segmentation involves dividing the whole image into partitions based on a threshold value, whereas multilevel segmentation involves multiple threshold values. A successful segmentation assigns proper threshold values to optimise a criterion such as entropy or between-class variance. High computational cost and inefficiency of an exhaustive search for the optimal thresholds leads to the use of global search heuristics to set the optimal thresholds. An emerging area in global heuristics is swarm-intelligence, which models the collective behaviour of the organisms. In this paper, two successful swarm-intelligence-based global optimisation algorithms, particle swarm optimisation (PSO) and artificial bee colony (ABC), have been employed to find the optimal multilevel thresholds. Kapur's entropy, one of the maximum entropy techniques, and between-class variance have been investigated as fitness functions. Experiments have been performed on test images using various numbers of thresholds. The results were assessed using statistical tools and suggest that Otsu's technique, PSO and ABC show equal performance when the number of thresholds is two, while the ABC algorithm performs better than PSO and Otsu's technique when the number of thresholds is greater than two. Experiments based on Kapur's entropy indicate that the ABC algorithm can be efficiently used in multilevel thresholding. Moreover, segmentation methods are required to have a minimum running time in addition to high performance. Therefore, the CPU times of ABC and PSO have been investigated to check their validity in real-time. The CPU time results show that the algorithms are scalable and that the running times of the algorithms seem to grow at a linear rate as the problem size increases.     

Single machine scheduling problem with interval processing times to minimize mean weighted completion time

The single resource scheduling problem is commonly applicable in practice not only when there is a single resource but also in some multiple-resource production systems where only one of the resources is bottle neck. Thus, the single resource (machine) scheduling problem has been widely addressed in the scheduling literature. In this paper, the single machine scheduling problem with uncertain and interval processing times is addressed. The objective is to minimize mean weighted completion time. The problem has been addressed in the literature and efficient heuristics have been presented. In this paper, some new polynomial time heuristics, utilizing the bounds of processing times, are proposed. The proposed and existing heuristics are compared by extensive computational experiments. The conducted experiments include a generalized simulation environment and several additional representative distributions in addition to the restricted experiments used in the literature. The results indicate that the proposed heuristics perform significantly better than the existing heuristics. Specifically, the best performing proposed heuristic reduces the error of the best existing heuristic in the literature by more than 75% while the computational time of the best performing proposed heuristic is less than that of the best existing heuristic. Moreover, the absolute error of the best performing heuristic is only about 1% of the optimal solution. Having a very small absolute error along with a negligible computational time indicates the superiority of the proposed heuristics.     

Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time

We consider the two-machine flowshop scheduling problem where jobs have random processing times which are bounded within certain intervals. The objective is to minimize total completion time of all jobs. The decision of finding a solution for the problem has to be made based on the lower and upper bounds on job processing times since this is the only information available. The problem is NP-hard since the special case when the lower and upper bounds are equal, i.e., the deterministic case, is known to be NP-hard. Therefore, a reasonable approach is to come up with well performing heuristics. We propose eleven heuristics which utilize the lower and upper bounds on job processing times based on the Shortest Processing Time (SPT) rule. The proposed heuristics are compared through randomly generated data. The computational analysis has shown that the heuristics using the information on the bounds of job processing times on both machines perform much better than those using the information on one of the two machines. It has also shown that one of the proposed heuristics performs as the best for different distributions with an overall average percentage error of less than one.     

An Evolutionary Parallel Tabu Search approach for distribution systems reinforcement planning

In this paper a new meta-heuristic optimisation technique is proposed. The method is based on the Parallel Tabu Search (PTS) algorithm and the application is the optimal electrical distribution systems reinforcement planning through the installation of photovoltaic plants, parallel cables, capacitor banks and transformers. The issue is a combinatorial optimisation problem; the objective function is a non-linear expression of a large number of variables. In these cases, meta-heuristics have proved to work well and one of the most efficient is the Tabu Search algorithm. For large-scale problems, parallelisation improves Tabu Search computational efficiency as well as its exploration ability. In this paper, an enhanced version of PTS, Evolutionary Parallel Tabu Search (EPTS), is proposed. It performs reproduction operators on sub-neighbourhoods directing the search towards more promising areas of the search space. The problem of distribution systems reinforcement planning has been studied in detail and the results of the application show that the EPTS outperforms the PTS and Particle Swarm Optimisation algorithms.The algorithm's performance is also tested on mathematical test functions and other properties of the proposed algorithm are examined.     

Performance evaluation of proposed Differential Evolution and Particle Swarm Optimization algorithms for scheduling m-machine flow shops with lot streaming

We consider n-job, m-machine lot streaming problem in a flow shop with equal size sub lots where the objective is to minimize the makespan and total flow time. Lot streaming (Lot sizing) is a technique that splits a production lot consisting of identical items into sub lots to improve the performance of a multi stage production system by over lapping the sub lots on successive machines. There is a scope for efficient algorithms for scheduling problems in m-machine flow shop with lot streaming. In recent years, much attention is given to heuristics and search techniques. To solve this problem, we propose a Differential Evolution Algorithm (DEA) and Particle Swarm Optimization (PSO) to evolve best sequence for makespan/total flow time criterion for m-machine flow shop involved with lot streaming and set up time. In this research, we propose the DEA and PSO algorithms for discrete lot streaming with equal sub lots. The proposed methods are tested and the performances were evaluated. The computational results show that the proposed algorithms are very competitive for the lot streaming flow shop scheduling problem.     

A genetic algorithm and a particle swarm optimizer hybridized with Nelder–Mead simplex search

This paper integrates Nelder–Mead simplex search method (NM) with genetic algorithm (GA) and particle swarm optimization (PSO), respectively, in an attempt to locate the global optimal solutions for the nonlinear continuous variable functions mainly focusing on response surface methodology (RSM). Both the hybrid NM–GA and NM–PSO algorithms incorporate concepts from the NM, GA or PSO, which are readily to implement in practice and the computation of functional derivatives is not necessary. The hybrid methods were first illustrated through four test functions from the RSM literature and were compared with original NM, GA and PSO algorithms. In each test scheme, the effectiveness, efficiency and robustness of these methods were evaluated via associated performance statistics, and the proposed hybrid approaches prove to be very suitable for solving the optimization problems of RSM-type. The hybrid methods were then tested by ten difficult nonlinear continuous functions and were compared with the best known heuristics in the literature. The results show that both hybrid algorithms were able to reach the global optimum in all runs within a comparably computational expense.     

Particle Swarm Optimization and Hill Climbing for the bandwidth minimization problem

In this paper, the problem of reducing the bandwidth of sparse matrices by permuting rows and columns is addressed and solved with a new hybrid heuristic which combines the Particle Swarm Optimization method with Hill Climbing (PSO-HC). This hybrid approach exploits a compact PSO in order to generate high-quality renumbering which is then refined by means of an efficient implementation of the HC local search heuristic. Computational experiments are carried out to compare the performance of PSO-HC with the well-known GPS algorithm, as well as some recently proposed methods, including WBRA, Tabu Search and GRASP_PR. PSO-HC proves to be extremely stable and reliable in finding good solutions to the bandwidth minimization problem, outperforming the currently known best algorithms in terms of solution quality, in reasonable computational time.     

A Tabu Search Algorithm for application placement in computer clustering

This paper presents and analyzes a model for the problem of placing applications on computer clusters (APP). In this problem, organizations requesting a set of software applications have to be assigned to computer clusters such that the costs of opening clusters and installing the necessary applications are minimized. This problem is related to known OR problems such as the multiproduct facility location problem and the generalized bin packing problem. We show that APP is NP-hard, and then propose a simple Tabu Search heuristic to solve it. The performance of the Tabu Search heuristic is assessed via extensive computational experiments, which indicate the promise of the proposed Tabu Search.     

A computational evaluation of constructive and improvement heuristics for the blocking flow shop to minimise total flowtime

This paper focuses on the blocking flow shop scheduling problem with the objective of total flowtime minimisation. This problem assumes that there are no buffers between machines and, due to its application to many manufacturing sectors, it is receiving a growing attention by researchers during the last years. Since the problem is NP-hard, a large number of heuristics have been proposed to provide good solutions with reasonable computational times. In this paper, we conduct a comprehensive evaluation of the available heuristics for the problem and for related problems, resulting in the implementation and testing of a total of 35 heuristics. Furthermore, we propose an efficient constructive heuristic which successfully combines a pool of partial sequences in parallel, using a beam-search-based approach. The computational experiments show the excellent performance of the proposed heuristic as compared to the best-so-far algorithms for the problem, both in terms of quality of the solutions and of computational requirements. In fact, despite being a relative fast constructive heuristic, new best upper bounds have been found for more than 27% of Taillard’s instances.     

A charging-scheme decision model for electric vehicle battery swapping station using varied population evolutionary algorithms

This paper proposes a new battery swapping station (BSS) model to determine the optimized charging scheme for each incoming Electric Vehicle (EV) battery. The objective is to maximize the BSS’s battery stock level and minimize the average charging damage with the use of different types of chargers. An integrated objective function is defined for the multi-objective optimization problem. The genetic algorithm (GA), differential evolution (DE) algorithm and three versions of particle swarm optimization (PSO) algorithms have been implemented to solve the problem, and the results show that GA and DE perform better than the PSO algorithms, but the computational time of GA and DE are longer than using PSO. Hence, the varied population genetic algorithm (VPGA) and varied population differential evolution (VPDE) algorithm are proposed to determine the optimal solution and reduce the computational time of typical evolutionary algorithms. The simulation results show that the performances of the proposed algorithms are comparable with the typical GA and DE, but the computational times of the VPGA and VPDE are significantly shorter. A 24-h simulation study is carried out to examine the feasibility of the model.