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.     

Iterated greedy algorithms for the blocking flowshop scheduling problem with makespan criterion

Recently, iterated greedy algorithms have been successfully applied to solve a variety of combinatorial optimization problems. This paper presents iterated greedy algorithms for solving the blocking flowshop scheduling problem (BFSP) with the makespan criterion. Main contributions of this paper can be summed up as follows. We propose a constructive heuristic to generate an initial solution. The constructive heuristic generates better results than those currently in the literature. We employ and adopt well-known speed-up methods from the literature for both insertion and swap neighborhood structures. In addition, an iteration jumping probability is proposed to change the neighborhood structure from insertion neighborhood to swap neighborhood. Generally speaking, the insertion neighborhood is much more effective than the swap neighborhood for the permutation flowshop scheduling problems. Instead of considering the use of these neighborhood structures in a framework of the variable neighborhood search algorithm, two powerful local search algorithms are designed in such a way that the search process is guided by an iteration jumping probability determining which neighborhood structure will be employed. By doing so, it is shown that some additional enhancements can be achieved by employing the swap neighborhood structure with a speed-up method without jeopardizing the effectiveness of the insertion neighborhood. We also show that the performance of the iterated greedy algorithm significantly depends on the speed-up method employed. The parameters of the proposed iterated greedy algorithms are tuned through a design of experiments on randomly generated benchmark instances. Extensive computational results on Taillard’s well-known benchmark suite show that the iterated greedy algorithms with speed-up methods are equivalent or superior to the best performing algorithms from the literature. Ultimately, 85 out of 120 problem instances are further improved with substantial margins.     

Estimation-based metaheuristics for the probabilistic traveling salesman problem

The probabilistic traveling salesman problem (PTSP) is a central problem in stochastic routing. Recently, we have shown that empirical estimation is a promising approach to devise highly effective local search algorithms for the PTSP. In this paper, we customize two metaheuristics, an iterated local search algorithm and a memetic algorithm, to solve the PTSP. This customization consists in adopting the estimation approach to evaluate the solution cost, exploiting a recently developed estimation-based local search algorithm, and tuning the metaheuristics parameters. We present an experimental study of the estimation-based metaheuristic algorithms on a number of instance classes. The results show that the proposed algorithms are highly effective and that they define a new state-of-the-art for the PTSP.     

解决作业车间调度的微粒群退火算法*

针对微粒群优化算法在求解作业车间调度问题时存在的易早熟、搜索准确度差等缺点,在微粒群优化算法的基础上引入了模拟退火算法,从而使得算法同时具有全局搜索和跳出局部最优的能力,并且增加了对不可行解的优化,从而提高了算法的搜索效率;同时,在模拟退火算法中引入自适应温度衰变系数,使得SA算法能根据当前环境自动调整搜索条件,从而避免了微粒群优化算法易早熟的缺点。对经典JSP问题的仿真实验表明,与其他算法相比,该算法是一种切实可行、有效的方法。     

Metaheuristics for the single machine weighted quadratic tardiness scheduling problem

This paper considers the single machine scheduling problem with weighted quadratic tardiness costs. Three metaheuristics are presented, namely iterated local search, variable greedy and steady-state genetic algorithm procedures. These address a gap in the existing literature, which includes branch-and-bound algorithms (which can provide optimal solutions for small problems only) and dispatching rules (which are efficient and capable of providing adequate solutions for even quite large instances). A simple local search procedure which incorporates problem specific information is also proposed.The computational results show that the proposed metaheuristics clearly outperform the best of the existing procedures. Also, they provide an optimal solution for all (or nearly all, in the case of the variable greedy heuristic) the smaller size problems. The metaheuristics are quite close in what regards solution quality. Nevertheless, the iterated local search method provides the best solution, though at the expense of additional computational time. The exact opposite is true for the variable greedy procedure, while the genetic algorithm is a good all-around performer.     

A three-fold approach for job shop problems: A divide-and-integrate strategy with immune algorithm

This paper presents a novel divide-and-integrate strategy based approach for solving large scale job-shop scheduling problems. The proposed approach works in three phases. First, in contrast to traditional job-shop scheduling approaches where optimization algorithms are used directly regardless of problem size, priority rules are deployed to decrease problem scale. These priority rules are developed with slack due dates and mean processing time of jobs. Thereafter, immune algorithm is applied to solve each small individual scheduling module. In last phase, integration scheme is employed to amalgamate the small modules to get gross schedule with minimum makespan. This integration is carried out in dynamic fashion by continuously checking the preceding module's machine ideal time and feasible slots (satisfying all the constraint). In this way, the proposed approach will increase the machine utilization and decrease the makespan of gross schedule. Efficacy of the proposed approach has been tested with extremely hard standard test instances of job-shop scheduling problems. Implementation results clearly show effectiveness of the proposed approach.     

Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates

In this paper, we consider an identical parallel machine scheduling problem with sequence-dependent setup times and job release dates. An improved iterated greedy heuristic with a sinking temperature is presented to minimize the maximum lateness. To verify the developed heuristic, computational experiments are conducted on a well-known benchmark problem data set. The experimental results show that the proposed heuristic outperforms the basic iterated greedy heuristic and the state-of-art algorithms on the same benchmark problem data set. It is believed that this improved approach will also be helpful for other applications.     

含有运输小车的柔性作业车间调度研究

在实际的柔性作业车间调度中,不但工件需要加工时间,而且工件在各个机器之间利用AGV(自动导引小车)转移也需要占用一定的时间,因此对柔性作业车间调度中考虑AGV运输时间的研究更具有实际意义。针对此问题,本文建立含有AGV的柔性作业车间调度的数学模型,针对问题自身特点对遗传算法进行改进,引入局部搜索策略加强局部寻优能力,将模拟退火算法作为局部搜索策略加入全局搜索中,增强了算法的收敛性能。通过在仿真实验平台上的实验数据结果可以看出,本算法有比较好的效果。     

Two-sided assembly line balancing problem of type I: Improvements,a simple algorithm and a comprehensive study

Many meta-heuristic methods have been applied to solve the two-sided assembly line balancing problem of type I with the objective of minimizing the number of stations, but some of them are very complex or intricate to be extended. In addition, different decoding schemes and different objectives have been proposed, leading to the different performances of these algorithms and unfair comparison. In this paper, two new decoding schemes with reduced search space are developed to balance the workload within a mated-station and reduce sequence-depended idle time. Then, graded objectives are employed to preserve the minor improvements on the solutions. Finally, a simple iterated greedy algorithm is extended for the two-sided assembly line balancing problem and modified NEH-based heuristic is introduced to obtain a high quality initial solution. And an improved local search with referenced permutation and reduced insert operators is developed to accelerate the search process. Computational results on benchmark problems prove the efficiency of the proposed decoding schemes and the new graded objectives. A comprehensive computational comparison among 14 meta-heuristics is carried out to demonstrate the efficiency of the improved iterated greedy algorithm.     

Memetic algorithms for the job shop scheduling problem with operators

The job-shop scheduling problem with operators (JSO) is an extension of the classic job-shop problem in which an operation must be assisted by one of a limited set of human operators, so it models many real life situations. In this paper we tackle the JSO by means of memetic algorithms with the objective of minimizing the makespan. We define and analyze a neighborhood structure which is then exploited in local search and tabu search algorithms. These algorithms are combined with a conventional genetic algorithm to improve a fraction of the chromosomes in each generation. We also consider two different schedule builders for chromosome decoding. All these elements are combined to obtain memetic algorithms which are evaluated over an extensive set of instances. The results of the experimental study show that they reach high quality solutions in very short time, comparing favorably with the state-of-the-art methods.     

Using metaheuristic algorithms for parameter estimation in generalized Mallows models

This paper deals with the problem of parameter estimation in the generalized Mallows model (GMM) by using both local and global search metaheuristic (MH) algorithms. The task we undertake is to learn parameters for defining the GMM from a dataset of complete rankings/permutations. Several approaches can be found in the literature, some of which are based on greedy search and branch and bound search. The greedy approach has the disadvantage of usually becoming trapped in local optima, while the branch and bound approach, basically A^* search, usually comes down to approximate search because of memory requirements, losing in this way its guaranteed optimality. Here, we carry out a comparative study of several MH algorithms (iterated local search (ILS) methods, variable neighborhood search (VNS) methods, genetic algorithms (GAs) and estimation of distribution algorithms (EDAs)) and a tailored algorithm A^* to address parameter estimation in GMMs. We use 22 real datasets of different complexity, all but one of which were created by the authors by preprocessing real raw data. We provide a complete analysis of the experiments in terms of accuracy, number of iterations and CPU time requirements.     

Evaluating a local genetic algorithm as context-independent local search operator for metaheuristics

Local genetic algorithms have been designed with the aim of providing effective intensification. One of their most outstanding features is that they may help classical local search-based metaheuristics to improve their behavior. This paper focuses on experimentally investigating the role of a recent approach, the binary-coded local genetic algorithm (BLGA), as context-independent local search operator for three local search-based metaheuristics: random multi-start local search, iterated local search, and variable neighborhood search. These general-purpose models treat the objective function as a black box, allowing the search process to be context-independent. The results show that BLGA may provide an effective and efficient intensification, not only allowing these three metaheuristics to be enhanced, but also predicting successful applications in other local search-based algorithms. In addition, the empirical results reported here reveal relevant insights on the behavior of classical local search methods when they are performed as context-independent optimizers in these three well-known metaheuristics.     

A new ILS algorithm for parallel machine scheduling problems

This paper addresses the non-preemptive scheduling problem of scheduling jobs on identical parallel machines to minimize the maximum completion time or makespan. The problem has been proved to be NP-hard in the strong sense. The NP-hardness of the problem motivates us to develop a new methodology to obtain near-optimal solutions. We formulate the problem as an integer programming and then propose a new iterated local search (ILS) algorithm based on a variable number of cyclic exchanges to solve it. The properties of the solutions are derived and the results are used to improve the computational efficiency of our algorithm. Computational experiments show that the cyclic exchange neighborhood embedded in an iterated local search framework is effective for solving the scheduling problems with up to 1000 jobs and 40 machines within a reasonable amount of computation time. Received: April 2005 / Accepted: January 2006     

基于混合微粒群优化的多目标柔性Job-shop调度

应用传统方法求解多目标柔性Job-shop调度问题是十分困难的,微粒群优化采用基于种群的搜索方式,融合了局部搜索和全局搜索,具有很高的搜索效率.模拟退火算法使用概率来避免陷入局部最优,整个搜索过程可由冷却表来控制.通过对这两种算法的合理组合,建立了一种快速且易于实现的新的混合优化算法.实例计算以及与其他算法的比较说明,该算法是求解多目标柔性Job-shop调度问题的可行且高效的方法.     

求解柔性作业车间调度问题的鸟群算法

柔性作业车间调度问题是生产调度领域中非常重要的一类带约束优化问题。根据其求解特性,提出一种基于改进的鸟群算法求解以最小化最大完工时间为目标的柔性作业车间调度问题的方法。该方法采用随机黑洞策略改进鸟群的觅食方式,自适应的动态调整策略改善鸟群的迁移步长,从而提高种群的多样性并加速算法的收敛速度;通过对关键路径上工序的领域搜索加强算法的局部搜索能力。最后利用实际制造企业的生产加工数据以及标准测试实例进行仿真实验,实验结果表明,该算法在问题的求解精度和收敛速度上具有一定的优势,是一种有效的求解柔性作业车间调度问题的新方法。     

改进人工蜂群算法求解模糊柔性作业车间调度问题

模糊柔性作业车间调度问题(FFJSP)是柔性作业车间调度问题(FJSP)的拓展,具有很强的现实意义.针对FFJSP,本文提出了一种基于领域搜索的改进人工蜂群算法.该算法以最小化最大模糊完工时间为目标.首先,为了提高初始种群的多样性,引入混沌理论来初始化种群.其次,为了提高算法的局部搜索能力,采用4种邻域结构对蜜源进行邻域搜索.为了进一步优化蜜源和加快种群的收敛速度,采用了一种新颖的交叉操作.并且在解码的过程中采用左移策略,从而很好地利用机器的空闲时间.最后,选取了3组通用数据集来测试算法的性能,并与代表性算法进行比较.结果表明,对于大部分实例,本文所提出的的算法的结果要优于与之对比的算法.     

一种求解车间调度问题的混沌遗传规划方法

作业车间调度问题是制造业的一个经典NP-hard组合优化难题。提出一种基于混沌遗传规划的调度算法,利用遗传规划进行染色体的结构设计,采用混沌序列改善初始种群质量,利用混沌扰动来维持进化群体的多样性,并自适应调整个体权重,使算法具有优良的综合求解性能。实验表明,算法对典型的标准调度测试问题具有较强的全局搜索能力,甘特图表明其获得的最优解优于当前已知的最优解历史记录,对比结果表明了该方法的有效性。     

Genetic algorithms for flowshop scheduling problems

In this paper, we apply a genetic algorithm to flowshop scheduling problems and examine two hybridizations of the genetic algorithm with other search algorithms. First we examine various genetic operators to design a genetic algorithm for the flowshop scheduling problem with an objective of minimizing the makespan. By computer simulations, we show that the two-point crossover and the shift change mutation are effective for this problem. Next we compare the genetic algorithm with other search algorithms such as local search, taboo search and simulated annealing. Computer simulations show that the genetic algorithm is a bit inferior to the others. In order to improve the performance of the genetic algorithm, we examine the hybridization of the genetic algorithms. We show two hybrid genetic algorithms: genetic local search and genetic simulated annealing. Their high performance is demonstrated by computer simulations.     

An iterative genetic algorithm for the assembly line worker assignment and balancing problem of type-II

In this study, we consider the assembly line worker assignment and balancing problem of type-II (ALWABP-2). ALWABP-2 arises when task times differ depending on operator skills and concerns with the assignment of tasks and operators to stations in order to minimize the cycle time. We developed an iterative genetic algorithm (IGA) to solve this problem. In the IGA, three search approaches are adopted in order to obtain search diversity and efficiency: modified bisection search, genetic algorithm and iterated local search. When designing the IGA, all the parameters such as construction heuristics, genetic operators and local search operators are adapted specifically to the ALWABP-2. The performance of the proposed IGA is compared with heuristic and metaheuristic approaches on benchmark problem instances. Experimental results show that the proposed IGA is very effective and robust for a large set of benchmark problems.     

Local search with edge weighting and configuration checking heuristics for minimum vertex cover

The Minimum Vertex Cover (MVC) problem is a well-known combinatorial optimization problem of great importance in theory and applications. In recent years, local search has been shown to be an effective and promising approach to solve hard problems, such as MVC. In this paper, we introduce two new local search algorithms for MVC, called EWLS (Edge Weighting Local Search) and EWCC (Edge Weighting Configuration Checking). The first algorithm EWLS is an iterated local search algorithm that works with a partial vertex cover, and utilizes an edge weighting scheme which updates edge weights when getting stuck in local optima. Nevertheless, EWLS has an instance-dependent parameter. Further, we propose a strategy called Configuration Checking for handling the cycling problem in local search. This is used in designing a more efficient algorithm that has no instance-dependent parameters, which is referred to as EWCC. Unlike previous vertex-based heuristics, the configuration checking strategy considers the induced subgraph configurations when selecting a vertex to add into the current candidate solution.A detailed experimental study is carried out using the well-known DIMACS and BHOSLIB benchmarks. The experimental results conclude that EWLS and EWCC are largely competitive on DIMACS benchmarks, where they outperform other current best heuristic algorithms on most hard instances, and dominate on the hard random BHOSLIB benchmarks. Moreover, EWCC makes a significant improvement over EWLS, while both EWLS and EWCC set a new record on a twenty-year challenge instance. Further, EWCC performs quite well even on structured instances in comparison to the best exact algorithm we know. We also study the run-time behavior of EWLS and EWCC which shows interesting properties of both algorithms.