An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers

This paper proposes an effective hybrid algorithm based on differential evolution (DE), namely HDE, to solve multi-objective permutation flow shop scheduling problem (MPFSSP) with limited buffers between consecutive machines, which is a typical NP-hard combinatorial optimization problem with strong engineering background. Firstly, to make DE suitable for solving scheduling problems, a largest-order-value (LOV) rule is presented to convert the continuous values of individuals in DE to job permutations. Secondly, after the DE-based exploration, an efficient local search, which is designed based on the landscape of MPFSSP with limited buffers, is applied to emphasize exploitation. Thus, not only does the HDE apply the parallel evolution mechanism of DE to perform effective exploration (global search) in the whole solution space, but it also adopts problem-dependent local search to perform thorough exploitation (local search) in the promising sub-regions. In addition, the concept of Pareto dominance is used to handle the updating of solutions in sense of multi-objective optimization. Moreover, the convergence property of HDE is analyzed by using the theory of finite Markov chain. Finally, simulations and comparisons based on benchmarks demonstrate the effectiveness and efficiency of the proposed HDE.     

An effective hybrid genetic algorithm for flow shop scheduling with limited buffers

As a typical manufacturing and scheduling problem with strong industrial background, flow shop scheduling with limited buffers has gained wide attention both in academic and engineering fields. With the objective to minimize the total completion time (or makespan), such an issue is very hard to solve effectively due to the NP-hardness and the constraint on the intermediate buffer. In this paper, an effective hybrid genetic algorithm (HGA) is proposed for permutation flow shop scheduling with limited buffers. In the HGA, not only multiple genetic operators based on evolutionary mechanism are used simultaneously in hybrid sense, but also a neighborhood structure based on graph model is employed to enhance the local search, so that the exploration and exploitation abilities can be well balanced. Moreover, a decision probability is used to control the utilization of genetic mutation operation and local search based on problem-specific information so as to prevent the premature convergence and concentrate computing effort on promising neighbor solutions. Simulation results and comparisons based on benchmarks demonstrate the effectiveness of the HGA. Meanwhile, the effects of buffer size and decision probability on optimization performances are discussed.     

An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers

In this paper, an effective hybrid algorithm based on particle swarm optimization (HPSO) is proposed for permutation flow shop scheduling problem (PFSSP) with the limited buffers between consecutive machines to minimize the maximum completion time (i.e., makespan). First, a novel encoding scheme based on random key representation is developed, which converts the continuous position values of particles in PSO to job permutations. Second, an efficient population initialization based on the famous Nawaz–Enscore–Ham (NEH) heuristic is proposed to generate an initial population with certain quality and diversity. Third, a local search strategy based on the generalization of the block elimination properties, named block-based local search, is probabilistically applied to some good particles. Moreover, simulated annealing (SA) with multi-neighborhood guided by an adaptive meta-Lamarckian learning strategy is designed to prevent the premature convergence and concentrate computing effort on promising solutions. Simulation results and comparisons demonstrate the effectiveness of the proposed HPSO. Furthermore, the effects of some parameters are discussed.     

A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion

This paper presents a hybrid discrete differential evolution (HDDE) algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion, which is not so well studied. The no-idle condition requires that each machine must process jobs without any interruption from the start of processing the first job to the completion of processing the last job. A novel speed-up method based on network representation is proposed to evaluate the whole insert neighborhood of a job permutation and employed in HDDE, and moreover, an insert neighborhood local search is modified effectively in HDDE to balance global exploration and local exploitation. Experimental results and a thorough statistical analysis show that HDDE is superior to the existing state-of-the-art algorithms by a significant margin.     

Flexible job shop scheduling using hybrid differential evolution algorithms

This paper proposes hybrid differential evolution (HDE) algorithms for solving the flexible job shop scheduling problem (FJSP) with the criterion to minimize the makespan. Firstly, a novel conversion mechanism is developed to make the differential evolution (DE) algorithm that works on the continuous domain adaptive to explore the problem space of the discrete FJSP. Secondly, a local search algorithm based on the critical path is embedded in the DE framework to balance the exploration and exploitation by enhancing the local searching ability. In addition, in the local search phase, the speed-up method to find an acceptable schedule within the neighborhood structure is presented to improve the efficiency of whole algorithms. Extensive computational results and comparisons show that the proposed algorithms are very competitive with the state of the art, some new best known solutions for well known benchmark instances have even been found.     

A novel differential evolution algorithm for bi-criteria no-wait flow shop scheduling problems

This paper presents a novel discrete differential evolution (DDE) algorithm for solving the no-wait flow shop scheduling problems with makespan and maximum tardiness criteria. First, the individuals in the DDE algorithm are represented as discrete job permutations, and new mutation and crossover operators are developed based on this representation. Second, an elaborate one-to-one selection operator is designed by taking into account the domination status of a trial individual with its counterpart target individual as well as an archive set of the non-dominated solutions found so far. Third, a simple but effective local search algorithm is developed to incorporate into the DDE algorithm to stress the balance between global exploration and local exploitation. In addition, to improve the efficiency of the scheduling algorithm, several speed-up methods are devised to evaluate a job permutation and its whole insert neighborhood as well as to decide the domination status of a solution with the archive set. Computational simulation results based on the well-known benchmarks and statistical performance comparisons are provided. It is shown that the proposed DDE algorithm is superior to a recently published hybrid differential evolution (HDE) algorithm [Qian B, Wang L, Huang DX, Wang WL, Wang X. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers. Computers & Operations Research 2009;36(1):209–33] and the well-known multi-objective genetic local search algorithm (IMMOGLS2) [Ishibuchi H, Yoshida I, Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation 2003;7(2):204–23] in terms of searching quality, diversity level, robustness and efficiency. Moreover, the effectiveness of incorporating the local search into the DDE algorithm is also investigated.     

Minimizing makespan for flow shop scheduling problem with intermediate buffers by using hybrid approach of artificial immune system

In this study, three new meta-heuristic algorithms artificial immune system (AIS), iterated greedy algorithm (IG) and a hybrid approach of artificial immune system (AIS-IG) are proposed to minimize maximum completion time (makespan) for the permutation flow shop scheduling problem with the limited buffers between consecutive machines. As known, this category of scheduling problem has wide application in the manufacturing and has attracted much attention in academic fields. Different from basic artificial immune systems, the proposed AIS-IG algorithm is combined with destruction and construction phases of iterated greedy algorithm to improve the local search ability. The performances of these three approaches were evaluated over Taillard, Carlier and Reeves benchmark problems. It is shown that the AIS-IG and AIS algorithms not only generate better solutions than all of the well-known meta heuristic approaches but also can maintain their quality for large scale problems.     

An effective hybrid teaching–learning-based optimization algorithm for permutation flow shop scheduling problem

Permutation flow shop scheduling (PFSP) is among the most studied scheduling settings. In this paper, a hybrid Teaching–Learning-Based Optimization algorithm (HTLBO), which combines a novel teaching–learning-based optimization algorithm for solution evolution and a variable neighborhood search (VNS) for fast solution improvement, is proposed for PFSP to determine the job sequence with minimization of makespan criterion and minimization of maximum lateness criterion, respectively. To convert the individual to the job permutation, a largest order value (LOV) rule is utilized. Furthermore, a simulated annealing (SA) is adopted as the local search method of VNS after the shaking procedure. Experimental comparisons over public PFSP test instances with other competitive algorithms show the effectiveness of the proposed algorithm. For the DMU problems, 19 new upper bounds are obtained for the instances with makespan criterion and 88 new upper bounds are obtained for the instances with maximum lateness criterion.     

批量流水线调度问题的混合差分进化算法

针对E/T指标的批量流水线调度问题,提出了差分进化调度算法。该算法采用基于实数的编码方式,利用最优目标个体的扰动产生变异个体,通过变异个体与目标个体的交叉产生试验个体,提高了最优目标个体信息共享,并结合模拟退火算法给出了两种混合求解策略。仿真试验表明了所得算法的可行性和高效性。     

Hybrid monkey search algorithm for flow shop scheduling problem under makespan and total flow time

This paper addresses a sub-population based hybrid monkey search algorithm to solve the flow shop scheduling problem which has been proved to be non-deterministic polynomial time hard (NP-hard) type combinatorial optimization problems. Minimization of makespan and total flow time are the objective functions considered. In the proposed algorithm, two different sub-populations for the two objectives are generated and different dispatching rules are used to improve the solution quality. To the best of our knowledge, this is the first application of monkey search algorithm to solve the flow shop scheduling problems. The performance of the proposed algorithm has been tested with the benchmark problems addressed in the literature. Computational results reveal that the proposed algorithm outperforms many other heuristics and meta-heuristics addressed in the literature.     

带不相关并行机和有限缓冲MHFS调度的混合启发式算法

研究每阶段含不相关并行机的多阶段混合流水车间问题(MHFSP),工件的加工时间取决于所分配的机器,相邻阶段之间缓冲区能力有限.鉴于直接求解该NP-hard问题较为困难,将其转化为带阻塞和不相关并行机的MHFSP (BMHFSP-UPM),建立整数规划模型,基于遗传算法(GA)和禁忌搜索(TS)提出一种混合启发式算法(HHGA&TS)进行求解.在该算法中,设计基于多阶段并行加工的二维矩阵编码方案,继而基于二维矩阵元胞组的初始解群体表述设计参数自适应策略;引入基于工件位-基因位的单点倒置交叉以及基于机器号的单点变异过程,利用GA求解机制完成解更新过程;设计机器号次序交换(MNE)、工件位置交换(JNE)、工件工序变异(JNM)三种邻域解移动规则,从而完成基于MNE-JNE-JNM的TS二次优化.仿真实验测试了多达120个工件的720组不同规模实例,结果表明,相较于GA、TS及NEH-IGA,所提出的混合启发式算法在解的质量方面表现更佳.     

A hybrid variable neighborhood search algorithm for solving the limited-buffer permutation flow shop scheduling problem with the makespan criterion

This paper investigates the limited-buffer permutation flow shop scheduling problem (LBPFSP) with the makespan criterion. A hybrid variable neighborhood search (HVNS) algorithm hybridized with the simulated annealing algorithm is used to solve the problem. A method is also developed to decrease the computational effort needed to implement different types of local search approaches used in the HVNS algorithm. Computational results show the higher efficiency of the HVNS algorithm as compared with the state-of-the-art algorithms. In addition, the HVNS algorithm is competitive with the algorithms proposed in the literature for solving the blocking flow shop scheduling problem (i.e., LBPFSP with zero-capacity buffers), and finds 54 new upper bounds for the Taillard's benchmark instances.     

Two-phase neighborhood search algorithm for two-agent hybrid flow shop scheduling problem

In this paper hybrid flow shop scheduling problem with two agents is studied and its feasibility model is considered. A two-phase neighborhood search (TNS) algorithm is proposed to minimize objectives of two agents simultaneously under the given upper bounds. TNS is constructed through the combination of multiple variable neighborhood mechanisms and a new perturbation strategy for new current solution. A new replacement principle is also applied to decide if the current solution can be updated. TNS is tested on a number of instances and compared with the existing methods. The computational results show the promising advantage of TNS on the considered problem.     

An effective neighborhood search algorithm for scheduling a flow shop of batch processing machines

This paper considers scheduling problem of flow shop with many batch processing machines and objective of maximum lateness. An effective neighborhood search algorithm (NSA) is proposed for the problem, in which a job permutation and a batch permutation are used to indicate the solution of two sub-problems, respectively. Each job permutation consists of several family-permutations for the representation of jobs from the same family. Two swaps are applied to two permutations to produce new solutions. NSA is applied to a number of instances and compared with some methods, and computational results validate the good performance of NSA.     

A tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers

This paper investigates the hybrid flowshop scheduling with finite intermediate buffers, whose objective is to minimize the sum of weighted completion time of all jobs. Since this problem is very complex and has been proven strongly NP-hard, a tabu search heuristic is proposed. In this heuristic there are two main features. One is that a scatter search mechanism is incorporated to improve the diversity of the search procedure. And the other is that a permutation of N jobs representing their processing order in the first stage instead of a complex complete schedule is used to denote a solution. Computational experiments on randomly generated instances with different structures show that the proposed tabu search heuristic can provide good solutions compared to both the lower bounds and the algorithm proposed for this problem in a lately published literature.     

基于混合差分进化算法的无等待流水车间总流水时间优化*

以调度的总流水时间为优化目标, 提出一种混合差分进化算法。 首先, 建立无等待流水车间调度的问题模型,并用快速方法评估总流水时间指标。 其次,采用LPV规则,实现离散问题的连续编码; 用差分进化算法对总流水时间指标执行优化;引入插入邻域和基于pairwise的局部搜索算法, 分别对差分进化算法产生的新个体和差分进化算法的最优解执行邻域搜索, 达到优化目标全局和局部的最优。 最后,通过计算标准算例, 并与其他算法比较, 验证该混合差分进化算法的有效性。     

Hybrid discrete differential evolution algorithm for biobjective cyclic hoist scheduling with reentrance

Cyclic hoist scheduling problems in automated electroplating lines and surface processing shops attract many attentions and interests both from practitioners and researchers. In such systems, parts are transported from a workstation to another by a material handling hoist. The existing literature mainly addressed how to find an optimal cyclic schedule to minimize the cycle time that measures the productivity of the lines. The material handling cost is an important factor that needs to be considered in practice but seldom addressed in the literature. This study focuses on a biobjective cyclic hoist scheduling problem to minimize the cycle time and the material handling cost simultaneously. We consider the reentrant workstations that are usually encountered in real-life lines but inevitably make the part-flow more complicated. The problem is formulated as a biobjective linear programming model with a given hoist move sequence and transformed into finding a set of Pareto optimal hoist move sequences with respect to the bicriteria. To obtain the Pareto optimal or near-optimal front, a hybrid discrete differential evolution (DDE) algorithm is proposed. In this hybrid evolutional algorithm, the population is divided into several subpopulations according to the maximal work-in-process (WIP) level of the system and the sizes of subpopulations are dynamically adjusted to balance the exploration and exploitation of the search. We propose a constructive heuristic to generate initial subpopulations with different WIP levels, hybrid mutation and crossover operators, an evaluation method that can tackle infeasible individuals and a one-to-one greedy tabu selection method. Computational results on both benchmark instances and randomly generated instances show that our proposed hybrid DDE algorithm outperforms the basic DDE algorithm and can solve larger-size instances than the existing ε-constraint method.     

An efficient memetic algorithm for solving the job shop scheduling problem

The job shop scheduling problem (JSP) is well known as one of the most complicated combinatorial optimization problems, and it is a NP-hard problem. Memetic algorithm (MA) which combines the global search and local search is a hybrid evolutionary algorithm. In this paper, an efficient MA with a novel local search is proposed to solve the JSP. Within the local search, a systematic change of the neighborhood is carried out to avoid trapping into local optimal. And two neighborhood structures are designed by exchanging and inserting based on the critical path. The objective of minimizing makespan is considered while satisfying a number of hard constraints. The computational results obtained in experiments demonstrate that the efficiency of the proposed MA is significantly superior to the other reported approaches in the literature.     

A new hybrid genetic algorithm for job shop scheduling problem

Job shop scheduling problem is a typical NP-hard problem. To solve the job shop scheduling problem more effectively, some genetic operators were designed in this paper. In order to increase the diversity of the population, a mixed selection operator based on the fitness value and the concentration value was given. To make full use of the characteristics of the problem itself, new crossover operator based on the machine and mutation operator based on the critical path were specifically designed. To find the critical path, a new algorithm to find the critical path from schedule was presented. Furthermore, a local search operator was designed, which can improve the local search ability of GA greatly. Based on all these, a hybrid genetic algorithm was proposed and its convergence was proved. The computer simulations were made on a set of benchmark problems and the results demonstrated the effectiveness of the proposed algorithm.     

Hybrid flow shop scheduling with not-all-machines options via local search with controlled deterioration

In this study we consider hybrid flow shop scheduling problem with a decision referring to the number of machines to be used. A simple way is used to decide the number of the used machines. A novel local search with controlled deterioration (CDLS) is proposed, which is composed of multiple neighborhood searches with the prefixed number of iterations and deterioration step. The deterioration step tries to obtain a new current solution with the controlled deteriorated degree on the solution quality. CDLS is tested on a number of instances and the computational results show that CDLS can provide the promising results for the considered problem.