The economic lot scheduling problem in limited-buffer flexible flow shops: Mathematical models and a discrete fruit fly algorithm

This paper considers the lot scheduling problem in the flexible flow shop with limited intermediate buffers to minimize total cost which includes the inventory holding and setup costs. The single available mathematical model by Akrami et al. (2006) for this problem suffers from not only being non-linear but also high size-complexity. In this paper, two new mixed integer linear programming models are developed for the problem. Moreover, a fruit fly optimization algorithm is developed to effectively solve the large problems. For model’s evaluation, this paper experimentally compares the proposed models with the available model. Moreover, the proposed algorithm is also evaluated by comparing with two well-known algorithms (tabu search and genetic algorithm) in the literature and adaption of three recent algorithms for the flexible flow shop problem. All the results and analyses show the high performance of the proposed mathematical models as well as fruit fly optimization algorithm.     

An improved particle swarm optimization algorithm for flowshop scheduling problem

The flowshop scheduling problem has been widely studied and many techniques have been applied to it, but few algorithms based on particle swarm optimization (PSO) have been proposed to solve it. In this paper, an improved PSO algorithm (IPSO) based on the “alldifferent” constraint is proposed to solve the flow shop scheduling problem with the objective of minimizing makespan. It combines the particle swarm optimization algorithm with genetic operators together effectively. When a particle is going to stagnate, the mutation operator is used to search its neighborhood. The proposed algorithm is tested on different scale benchmarks and compared with the recently proposed efficient algorithms. The results show that the proposed IPSO algorithm is more effective and better than the other compared algorithms. It can be used to solve large scale flow shop scheduling problem effectively.     

改进微粒群算法求解模糊交货期Flow-shop调度问题

针对模糊交货期Flow-shop调度问题的特点,论文提出用微粒群这种具有快速收敛、全局性能好的迭代优化算法进行求解,并使用惩罚函数、增加数据记忆库和自适应变异机制等方法对微粒群算法进行改进,减少了算法陷入局部极值的可能性。通过仿真实例,改进微粒群算法的全局寻优、收敛性和克服早熟的能力均优于遗传、启发式算法。     

微粒群优化算法在车间调度中的研究与应用

在对某印染企业的生产状况进行了深入调研和分析的基础上,对流水车间调度、混合流水车间调度进行了对比,同时对微粒群算法进行了深入研究,并根据实际情况对算法进行了部分改动和改进,使之能适用于离散的生产调度问题.最后将改进后的微粒群算法应用到印染企业的车间调度中,同时实现了甘特图的动态生成.研究结果可直接应用于企业流水车间调度和作业车间调度,具有一定的实际应用价值.     

A new ant colony algorithm for makespan minimization in permutation flow shops

The problem of scheduling in permutation flow shop with the objective of minimizing the maximum completion time, or makespan, is considered. A new ant colony optimization algorithm is developed for solving the problem. A novel mechanism is employed in initializing the pheromone trails based on an initial sequence. Moreover, the pheromone trail intensities are limited between lower and upper bounds which change dynamically. When a complete sequence of jobs is constructed by an artificial ant, a local search is performed to improve the performance quality of the solution. The proposed ant colony algorithm is applied to Taillard’s benchmark problems. Computational experiments suggest that the algorithm yields better results than well-known ant colony optimization algorithms available in the literature.     

Binary bat algorithm

Bat algorithm (BA) is one of the recently proposed heuristic algorithms imitating the echolocation behavior of bats to perform global optimization. The superior performance of this algorithm has been proven among the other most well-known algorithms such as genetic algorithm (GA) and particle swarm optimization (PSO). However, the original version of this algorithm is suitable for continuous problems, so it cannot be applied to binary problems directly. In this paper, a binary version of this algorithm is proposed. A comparative study with binary PSO and GA over twenty-two benchmark functions is conducted to draw a conclusion. Furthermore, Wilcoxon’s rank-sum nonparametric statistical test was carried out at 5 % significance level to judge whether the results of the proposed algorithm differ from those of the other algorithms in a statistically significant way. The results prove that the proposed binary bat algorithm (BBA) is able to significantly outperform others on majority of the benchmark functions. In addition, there is a real application of the proposed method in optical engineering called optical buffer design at the end of the paper. The results of the real application also evidence the superior performance of BBA in practice.     

Two-stage hybrid flow shop scheduling on parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes

In this paper, we investigate a specialized two-stage hybrid flow shop scheduling problem with parallel batching machines considering a job-dependent deteriorating effect and non-identical job sizes simultaneously. A novel concept of three-dimensional wasted volume based on the job normal processing time, job size, and job deteriorating rate is first proposed. Some structural properties, as well as a heuristic algorithm, are developed to solve the single parallel batching machine scheduling problem. Since the two-stage hybrid flow shop scheduling problem is NP-hard, a hybrid EDA-DE algorithm combining estimation of distribution algorithm (EDA) and differential evolution (DE) algorithm is proposed to tackle the studied problem. In addition, the Taguchi method of design of experiments (DOE) is implemented to tune the parameters of the EDA-DE. Finally, a series of computational experiments are carried out to compare the performance of the proposed hybrid EDA-DE algorithm and some recent existing algorithms from the literature, and the comparative results validate the effectiveness and efficiency of the proposed algorithm.     

批量无等待调度问题的微粒群蛙跳混合优化算法*

将离散微粒群与蛙跳算法相结合解决以最大完工时间为指标的批量无等待流水线调度问题.结合微粒群算法较强的全局收敛能力和蛙跳算法较强的深度搜索能力,设计了三种混合算法,平衡了算法的全局开发能力和局部探索能力.对随机生成不同规模的实例进行了广泛的实验,仿真实验结果的比较表明了所得混合算法的有效性和高效性.     

Optimal power flow using an Improved Colliding Bodies Optimization algorithm

This paper proposes Improved Colliding Bodies Optimization (ICBO) algorithm to solve efficiently the optimal power flow (OPF) problem. Several objectives, constraints and formulations at normal and preventive operating conditions are used to model the OPF problem. Applications are carried out on three IEEE standard test systems through 16 case studies to assess the efficiency and the robustness of the developed ICBO algorithm. A proposed performance evaluation procedure is proposed to measure the strength and robustness of the proposed ICBO against numerous optimization algorithms. Moreover, a new comparison approach is developed to compare the ICBO with the standard CBO and other well-known algorithms. The obtained results demonstrate the potential of the developed algorithm to solve efficiently different OPF problems compared to the reported optimization algorithms in the literature.     

微粒群算法在印染企业车间调度中的研究应用

在对某印染企业的生产状况进行了深入调研和分析的基础上,对流水车间调度、混合流水车间调度和作业车间调度进行了对比研究。同时对微粒群算法进行了深入研究,并根据实际情况对算法进行了部分改动和改进,使之能适用于离散的生产调度问题。最后将改进后的微粒群算法应用到花布印染企业的车间调度中,对加工任务进行优化调度,并实现甘特图的动态生成。论文的结果可直接应用于企业流水车间调度和作业车间调度,具有一定的实际应用价值。     

Modelling and scheduling multi-objective flow shop problems with interfering jobs

This paper studies multi-objective flow shop scheduling problems with interfering jobs. That is, there are two sets of jobs and each of which has its own objective. Some jobs are scheduled so as to minimize makespan while the others are to minimize total tardiness. In this case, the problem was mathematically modeled by a mixed integer linear program. Then, a novel biogeography-based optimization was developed to solve the problem. To evaluate the algorithm, its performance was compared with three well-known algorithms in the literature. The results of the present study show that the proposed algorithm outperforms the other tested algorithms.     

Metaheuristic methods in hybrid flow shop scheduling problem

Memetic algorithms are hybrid evolutionary algorithms that combine global and local search by using an evolutionary algorithm to perform exploration while the local search method performs exploitation. This paper presents two hybrid heuristic algorithms that combine particle swarm optimization (PSO) with simulated annealing (SA) and tabu search (TS), respectively. The hybrid algorithms were applied on the hybrid flow shop scheduling problem. Experimental results reveal that these memetic techniques can effectively produce improved solutions over conventional methods with faster convergence.     

Performance assessment of foraging algorithms vs. evolutionary algorithms

The class of foraging algorithms is a relatively new field based on mimicking the foraging behavior of animals, insects, birds or fish in order to develop efficient optimization algorithms. The artificial bee colony (ABC), the bees algorithm (BA), ant colony optimization (ACO), and bacterial foraging optimization algorithms (BFOA) are examples of this class to name a few. This work provides a complete performance assessment of the four mentioned algorithms in comparison to the widely known differential evolution (DE), genetic algorithms (GAs), harmony search (HS), and particle swarm optimization (PSO) algorithms when applied to the problem of unconstrained nonlinear continuous function optimization. To the best of our knowledge, most of the work conducted so far using foraging algorithms has been tested on classical functions. This work provides the comparison using the well-known CEC05 benchmark functions based on the solution reached, the success rate, and the performance rate.     

An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem

Hybrid flow shops (HFS) are common manufacturing environments in many industries, such as the glass, steel, paper and textile industries. In this paper, we present a particle swarm optimization (PSO) algorithm for the HFS scheduling problem with minimum makespan objective. The main contribution of this paper is to develop a new approach hybridizing PSO with bottleneck heuristic to fully exploit the bottleneck stage, and with simulated annealing to help escape from local optima. The proposed PSO algorithm is tested on the benchmark problems provided by Carlier and Néron. Experimental results show that the proposed algorithm outperforms all the compared algorithms in solving the HFS problem.     

Hybrid whale optimization algorithm enhanced with Lévy flight and differential evolution for job shop scheduling problems

The job shop scheduling problem (JSSP) has been a hot issue in manufacturing. For the past few decades, scholars have been attracted to research JSSP and proposed many novel meta-heuristic algorithms to solve it. Whale optimization algorithm (WOA) is such a novel meta-heuristic algorithm and has been proven to be efficient in solving real-world optimization problems in the literature. This paper proposes a hybrid WOA enhanced with Lévy flight and differential evolution (WOA-LFDE) to solve JSSP. By changing the expression of Lévy flight and DE search strategy, Lévy flight enhances the abilities of global search and convergence of WOA in iteration, while DE algorithm improves the exploitation and local search capabilities of WOA and keeps the diversity of solutions to escape local optima. It is then applied to solve 88 JSSP benchmark instances and compared with other state-of-art algorithms. The experimental results and statistical analysis show that the proposed algorithm has superior performance over contesting algorithms.     

Elucidating multiprocessors flow shop scheduling with dependent setup times using a twin particle swarm optimization

Particle swarm optimization (PSO) is a novel metaheuristic, which has been applied in a wide variety of production scheduling problems. Two basic characteristics of this algorithm are its efficiency and effectiveness in providing high-quality solutions. In order to improve the traditional PSO, this study proposes the incorporation of a local search heuristic into the basic PSO algorithm. The new, hybrid, metaheuristic is called “twin particle swarm optimization (TPSO)”. The proposed metaheuristic scheme is applied to a flow shop with multiprocessors scheduling problem, which can be considered a real world case regarding the production line. This study, as far as the multiprocessors flow shop production system is concerned, utilizes sequence dependent setup times as constraints. Finally, simulated data confirm the effectiveness and robustness of the proposed algorithm. The data test results indicate that TPSO has potential to replace PSO and become a significant heuristic algorithm for similar problems.     

Flow shop scheduling to minimize the total completion time with a permanently present operator: Models and ant colony optimization metaheuristic

This paper studies the one-operator m-machine flow shop scheduling problem with the objective of minimizing the total completion time. In this problem, the processing of jobs and setup of machines require the continuous presence of a single operator. We compare three different mathematical formulations and propose an ant colony optimization based metaheuristic to solve this flow shop scheduling problem. A series of experiments are carried out to compare the properties of three formulations and to investigate the performance of the proposed ant colony optimization metaheuristic. The computational results show that (1) an assignment-based formulation performs best, and (2) the ant colony optimization based metaheuristic is a computationally efficient algorithm.     

A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem

Job shop scheduling problem (JSP) which is widespread in the real-world production system is one of the most general and important problems in various scheduling problems. Nowadays, the effective method for JSP is a hot topic in research area of manufacturing system. JSP is a typical NP-hard combinatorial optimization problem and has a broad engineering application background. Due to the large and complicated solution space and process constraints, JSP is very difficult to find an optimal solution within a reasonable time even for small instances. In this paper, a hybrid particle swarm optimization algorithm (PSO) based on variable neighborhood search (VNS) has been proposed to solve this problem. In order to overcome the blind selection of neighborhood structures during the hybrid algorithm design, a new neighborhood structure evaluation method based on logistic model has been developed to guide the neighborhood structures selection. This method is utilized to evaluate the performance of different neighborhood structures. Then the neighborhood structures which have good performance are selected as the main neighborhood structures in VNS. Finally, a set of benchmark instances have been conducted to evaluate the performance of proposed hybrid algorithm and the comparisons among some other state-of-art reported algorithms are also presented. The experimental results show that the proposed hybrid algorithm has achieved good improvement on the optimization of JSP, which also verifies the effectiveness and efficiency of the proposed neighborhood structure evaluation method.     

Particle swarm optimisation in designing parameters of manufacturing processes: A review (2008–2018)

The evolutionary optimisation algorithms appeared as an effective alternative to conventional statistical methods that have certain limitations in optimising complex manufacturing processes. Considering works published in the last decade, this paper presents an analysis of the particle swarm optimisation (PSO) implementation in designing parameters of heterogeneous manufacturing processes, both conventional and emerging, new processes. The literature review and analysis was structured according to the complexity of the optimisation problem (single response and multiresponse problems), and the development of an objective function for PSO. The tuning of the PSO algorithm-specific parameters was analysed in detail. The PSO algorithm performance was benchmarked with the results of other methods, including evolutionary algorithms, in designing process parameters. The concerns in applying PSO for multiresponse manufacturing problems were highlighted, and recommendations for future research were drawn. Such a comprehensive review on the PSO application in optimising manufacturing processes, including the detailed discussion on the algorithm characteristics and benchmark with other optimisation procedures, has not been pursued so far. Therefore, this review analysis provides hands on information for researchers and engineers at one place, and it is believed that the findings could serve as a basis for the future research and implementation directions.     

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.