A machine-learning based memetic algorithm for the multi-objective permutation flowshop scheduling problem

In recent years, the historical data during the search process of evolutionary algorithms has received increasing attention from many researchers, and some hybrid evolutionary algorithms with machine-learning have been proposed. However, the majority of the literature is centered on continuous problems with a single optimization objective. There are still a lot of problems to be handled for multi-objective combinatorial optimization problems. Therefore, this paper proposes a machine-learning based multi-objective memetic algorithm (ML-MOMA) for the discrete permutation flowshop scheduling problem. There are two main features in the proposed ML-MOMA. First, each solution is assigned with an individual archive to store the non-dominated solutions found by it and based on these individual archives a new population update method is presented. Second, an adaptive multi-objective local search is developed, in which the analysis of historical data accumulated during the search process is used to adaptively determine which non-dominated solutions should be selected for local search and how the local search should be applied. Computational results based on benchmark problems show that the cooperation of the above two features can help to achieve a balance between evolutionary global search and local search. In addition, many of the best known Pareto fronts for these benchmark problems in the literature can be improved by the proposed ML-MOMA.     

置换流水车间调度问题的两阶段分布估计算法

针对置换流水车间调度问题,以最小化总流水时间为目标,提出了一种新颖的两阶段分布估计算法。第一阶段先利用NEH（Nawaz-Enscore-Ham,NEH）启发式构造一个较优的初始个体,然后随机生成初始种群,为保留种群的多样性,提出一种择优机制来选择个体并建立概率模型,同时在当代种群中利用精英机制保留当代种群中的最优解,最后利用概率模型采样并生成下一代种群。第二阶段采用插入、互换操作算子对第一阶段得到的最优解进行邻域搜索,来提高分布估计算法的全局搜索能力,阻止其陷入局部最优解。通过对算例进行实验、对比和分析,证明该算法的可行性和有效性。     

变量块内部迭代算法求解零空闲流水车间问题

零空闲流水车间问题（NIFSP）是流水车间问题中带有约束条件的典型NP-hard问题,在大多数现实场景下,零空闲约束是对机器的基本要求。而目前关于NIFSP问题提出的算法对于较大规模算例、综合性能及参数调整的灵活性较差。为此,以最小化最大完工时间为目标,提出了一种可变内部迭代算法VIIA。在VIIA的初始化阶段,使用改进的FRB5产生初始解,提高了FRB5的效率,在保证算法性能的同时极大地缩短了CPU消耗时间。在破坏重建阶段,通过增加对移除工件块数量的内部迭代,从而灵活调整参数值。VIIA增大了邻域搜索,以适应不同规模的算例。为了验证VIIA算法的性能,将该算法与在流水车间调度问题中表现优秀的几种算法进行了比较。实验结果证明了VIIA在NIFSP问题求解上性能的优越性,并且在最优解的搜索上,性能明显优于对比算法。     

A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem

This paper presents a variable iterated greedy algorithm (IG) with differential evolution (vIG_DE), designed to solve the no-idle permutation flowshop scheduling problem. In an IG algorithm, size d of jobs are removed from a sequence and re-inserted into all possible positions of the remaining sequences of jobs, which affects the performance of the algorithm. The basic concept behind the proposed vIG_DE algorithm is to employ differential evolution (DE) to determine two important parameters for the IG algorithm, which are the destruction size and the probability of applying the IG algorithm to an individual. While DE optimizes the destruction size and the probability on a continuous domain by using DE mutation and crossover operators, these two parameters are used to generate a trial individual by directly applying the IG algorithm to each target individual depending on the probability. Next, the trial individual is replaced with the corresponding target individual if it is better in terms of fitness. A unique multi-vector chromosome representation is presented in such a way that the first vector represents the destruction size and the probability, which is a DE vector, whereas the second vector simply consists of a job permutation assigned to each individual in the target population. Furthermore, the traditional IG and a variable IG from the literature are re-implemented as well. The proposed algorithms are applied to the no-idle permutation flowshop scheduling (NIPFS) problem with the makespan and total flowtime criteria. The performances of the proposed algorithms are tested on the Ruben Ruiz benchmark suite and compared to the best-known solutions available at http://soa.iti.es/rruiz as well as to those from a recent discrete differential evolution algorithm (HDDE) from the literature. The computational results show that all three IG variants represent state-of-art methods for the NIPFS problem.     

A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem

This paper deals with a bi-objective flowshop scheduling problem minimizing the makespan and total weighted tardiness, in which all jobs may not be processed by all machines. Furthermore, we consider transportation times between machines. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time by using traditional approaches and optimization tools is extremely difficult. This paper presents a new multi-objective electromagnetism algorithm (MOEM). The motivation behind this algorithm has risen from the attraction–repulsion mechanism of electromagnetic theories. Along with MOEA, we apply simulated annealing to solve the given problem. A set of experimental instances are carried out to evaluate the algorithm by advanced multi-objective performance measures. The related results show that a variant of our proposed MOEM provides sound performance comparing with other algorithms.     

改进的粒子群算法求解置换流水车间调度问题

针对置换流水车间调度问题,提出了一种改进的粒子群算法进行求解。改进算法引入了判断粒子群早熟的方法,并在发现粒子群早熟后采用逆转策略对种群最优粒子进行变异,利用模拟退火思想概率接收新的最优粒子。种群最优粒子的改变会引导粒子群跳出局部极值的约束,从而克服粒子群的早熟状态。通过对置换流水车间调度问题中Car系列和Rec系列部分基准数据的测试,证明了该算法的有效性。     

基于新邻域结构的Memetic 算法求解流水车间调度问题

流水车间调度是一类典型的生产调度问题,属于NP-难问题.针对传统的最优化方法难以求解大规模问题,提出了一个Memetic算法,在算法的局部搜索中使用一种新型的基于NEH的邻域结构,并且其邻域规模随着搜索的进行能够动态变化,可以大大提高算法的搜索能力.通过对标准Benchmark问题的测试,所得结果表明提出的基于新邻域结构的Memetic算法具有较好的性能,并且优于已有文献中的粒子群算法.     

基于TSP方法求解等待时间受限的置换流水车间调度

等待时间受限的置换流水车间调度问题要求工件在连续两个机器间的等待时间满足上限值约束.对此,分析了工件序列中相邻工件的加工持续时间及其上下界关系,并且提出一种启发式方法.首先,建立旅行商间题（TSP）以生成初始调度;然后,采用扩展插入方法优化调度解.为了衡量算法性能,给出问题下界的计算方法和相关评价指标,并通过数据实验验证了该启发式和下界计算方法的可行性和有效性.     

Memetic algorithm with node and edge histogram for no-idle flow shop scheduling problem to minimize the makespan criterion

This paper presents a memetic algorithm with hybrid node and edge histogram (MANEH) to solve no-idle permutation flow shop scheduling problem (NIPFSP) with the criterion to minimize the maximum completion time (the makespan criterion). The MANEH mainly composes of two components: population-based global search and local refinements for individuals. At the initialization stage, a modified speed-up NEH method and the random initialization are utilized to generate more promising solutions with a reasonable running time. At the population-based global search stage, a random sample crossover is first proposed to construct a hybrid node and edge histogram matrix (NEHM) with superior solutions in the population, and then a new sequence is generated by sampling the NEHM or selecting jobs from a template sequence. At the local refinements stage, an improved general variable neighborhood search with the simulated annealing acceptance (GVNS-SA) is developed to improve the current best individual. The GVNS-SA adopts a random referenced local search in the inner loop and the probability of SA to decide whether accept the incumbent solution for the next iteration. Moreover, the influence of key parameters in the MANEH is investigated based on the approach of a design of experiments (DOE). Finally, numerical simulation based on the benchmark of Ruiz and thorough statistical analysis are provided. The comparisons between MANEH and some existing algorithms as well as MA-based algorithms demonstrate the effectiveness and superiority of the proposed MANEH in solving the NIPFSP. Furthermore, the MANEH improves 89 out of the 250 current best solutions reported in the literature.     

A three-phase algorithm for flowshop scheduling with blocking to minimize makespan

This paper proposes a three-phase algorithm (TPA) for the flowshop scheduling problem with blocking (BFSP) to minimize makespan. In the first phase, the blocking nature of BFSP is exploited to develop a priority rule that creates a sequence of jobs. Using this as the initial sequence and a variant of the NEH-insert procedure, the second phase generates an approximate solution to the problem. Then, utilizing a modified simulated annealing algorithm incorporated with a local search procedure, the schedule generated in the second phase is improved in the third phase. A pruning procedure that helps evaluate most solutions without calculating their complete makespan values is introduced in the local search to further reduce the computational time needed to solve the problem. Results of the computational experiments with Taillard's benchmark problem instances show that the proposed TPA algorithm is relatively more effective and efficient in minimizing makespan for the BFSP than the state-of-the-art procedures. Utilizing these results, 53 out of 60 new tighter upper bounds have been found for large-sized Taillard's benchmark problem instances.     

The distributed permutation flowshop scheduling problem

This paper studies a new generalization of the regular permutation flowshop scheduling problem (PFSP) referred to as the distributed permutation flowshop scheduling problem or DPFSP. Under this generalization, we assume that there are a total of F identical factories or shops, each one with m machines disposed in series. A set of n available jobs have to be distributed among the F factories and then a processing sequence has to be derived for the jobs assigned to each factory. The optimization criterion is the minimization of the maximum completion time or makespan among the factories. This production setting is necessary in today's decentralized and globalized economy where several production centers might be available for a firm. We characterize the DPFSP and propose six different alternative mixed integer linear programming (MILP) models that are carefully and statistically analyzed for performance. We also propose two simple factory assignment rules together with 14 heuristics based on dispatching rules, effective constructive heuristics and variable neighborhood descent methods. A comprehensive computational and statistical analysis is conducted in order to analyze the performance of the proposed methods.     

A linkage mining in block-based evolutionary algorithm for permutation flowshop scheduling problem

A genetic algorithm is a type of heuristic algorithm used to solve permutation flowshop scheduling problems (PFSPs). Producing an optimal offspring with a variety of genes is difficult because of the evolution of the gene selection and a crossover mechanism that leads to local optima. This study proposes a linkage mining in block-based evolutionary algorithm (LMBBEA) for solving the PFSP, in which the association rule extracts various good genes and increases gene diversity. These genes are used to generate various blocks for artificial chromosome combinations. The generated blocks not only improve the chance of finding optimal solutions but also enhance the efficiency of convergence. The proposed LMBBEA is compared with other algorithms through numerical experiments, namely the Taillard and Reeves experiments in the OR-Library. To compare with other algorithms, the solutions produced by the proposed LMBBEA are closest to the optimal solution. The LMBBEA has a high convergence speed and a better solution quality due to an increase in the diversity of solutions.     

A grasp algorithm for m-machine flowshop scheduling problem with bicriteria of makespan and maximum tardiness

In this paper we address the problem of minimizing the weighted sum of makespan and maximum tardiness in an m-machine flow shop environment. This is a NP-hard problem in the strong sense. An attempt has been made to solve this problem using a metaheuristic called Greedy Randomized Adaptive Search Procedure (GRASP). GRASP is a competitive algorithm and is a meta-heuristic for solving combinatorial optimization problems. We have customized the basic concepts of GRASP algorithm to solve a bicriteria flow shop problem and a new algorithm named B-GRASP (Bicriteria GRASP algorithm) is proposed. The new proposed algorithm is evaluated using benchmark problems taken from Taillard and compared with the existing simulated annealing based heuristic developed by Chakravarthy and Rajendran. Computational experiments indicate that the proposed algorithm is much better than the existing one in all cases.     

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.     

蛙跳算法与批量无等待流水线调度问题的优化*

针对以makespan为指标的批量无等待流水线调度问题,提出了一种有效的离散蛙跳算法。首先采用基于工序的编码方式使蛙跳算法直接应用于调度问题;其次采用基于NEH与改进NEH和随机产生相结合的初始化方法,保证了初始解的高质量和分布性;再次采用交叉或变异方法产生新解,保持了种群的优越性和多样性;最后对全局最优解执行快速局部搜索,有效地降低了算法的时间复杂度,平衡算法的全局和局部开发能力。对随机生成不同规模的实例进行广泛的实验,通过仿真实验结果的比较,表明所得蛙跳算法的有效性和高效性。     

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.     

Flexible open shop scheduling problem to minimize makespan

This study investigates the static and dynamic versions of the flexible open shop scheduling problem with the goal of minimizing makespan. The asymptotic optimality of the general dense scheduling (GDS) algorithm is proven by the boundedness hypothesis. For large-scale problems, the GDS-based heuristic algorithms are presented to accelerate convergence. For moderate-scale problems, the differential evolution algorithm is employed to obtain high-quality solutions. A series of random experiments are conducted to demonstrate the effectiveness of the proposed algorithms.     

A hybrid estimation of distribution algorithm for simulation-based scheduling in a stochastic permutation flowshop

The permutation flowshop scheduling problem (PFSP) is NP-complete and tends to be more complicated when considering stochastic uncertainties in the real-world manufacturing environments. In this paper, a two-stage simulation-based hybrid estimation of distribution algorithm (TSSB-HEDA) is presented to schedule the permutation flowshop under stochastic processing times. To deal with processing time uncertainty, TSSB-HEDA evaluates candidate solutions using a novel two-stage simulation model (TSSM). This model first adopts the regression-based meta-modelling technique to determine a number of promising candidate solutions with less computation cost, and then uses a more accurate but time-consuming simulator to evaluate the performance of these selected ones. In addition, to avoid getting trapped into premature convergence, TSSB-HEDA employs both the probabilistic model of EDA and genetic operators of genetic algorithm (GA) to generate the offspring individuals. Enlightened by the weight training process of neural networks, a self-adaptive learning mechanism (SALM) is employed to dynamically adjust the ratio of offspring individuals generated by the probabilistic model. Computational experiments on Taillard’s benchmarks show that TSSB-HEDA is competitive in terms of both solution quality and computational performance.     

A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem

In this paper, a discrete particle swarm optimization (DPSO) algorithm is presented to solve the no-wait flowshop scheduling problem with both makespan and total flowtime criteria. The main contribution of this study is due to the fact that particles are represented as discrete job permutations and a new position update method is developed based on the discrete domain. In addition, the DPSO algorithm is hybridized with the variable neighborhood descent (VND) algorithm to further improve the solution quality. Several speed-up methods are proposed for both the swap and insert neighborhood structures. The DPSO algorithm is applied to both 110 benchmark instances of Taillard [Benchmarks for basic scheduling problems. European Journal of Operational Research 1993;64:278–85] by treating them as the no-wait flowshop problem instances with the total flowtime criterion, and to 31 benchmark instances provided by Carlier [Ordonnancements a contraintes disjonctives. RAIRO Recherche operationelle 1978;12:333–51], Heller [Some numerical experiments for an M×J$\mathrm{M}\times \mathrm{J}$ flow shop and its decision-theoretical aspects. Operations Research 1960;8:178–84], and Revees [A genetic algorithm for flowshop sequencing. Computers and Operations Research 1995;22:5–13] for the makespan criterion. For the makespan criterion, the solution quality is evaluated according to the reference makespans generated by Rajendran [A no-wait flowshop scheduling heuristic to minimize makespan. Journal of the Operational Research Society 1994;45:472–8] whereas for the total flowtime criterion, it is evaluated with the optimal solutions, lower bounds and best known solutions provided by Fink and Voß [Solving the continuous flow-shop scheduling problem by metaheuristics. European Journal of Operational Research 2003;151:400–14]. The computational results show that the DPSO algorithm generated either competitive or better results than those reported in the literature. Ultimately, 74 out of 80 best known solutions provided by Fink and Voß [Solving the continuous flow-shop scheduling problem by metaheuristics. European Journal of Operational Research 2003;151:400–14] were improved by the VND version of the DPSO algorithm.     

Efficient non-population-based algorithms for the permutation flowshop scheduling problem with makespan minimisation subject to a maximum tardiness

This paper focuses on the problem of scheduling jobs in a permutation flowshop with the objective of makespan minimisation subject to a maximum allowed tardiness for the jobs, a problem that combines two desirable manufacturing objectives related to machine utilisation and to customer satisfaction. Although several approximate algorithms have been proposed for this NP-hard problem, none of them can use the excellent speed-up method by Taillard (1990) [22] for makespan minimisation due to the special structure of the problem under consideration. In this paper, several properties of the problem are defined in order to be able to partly apply Taillard׳s acceleration. This mechanism, together with a novel feasible tabu local search method, allows us to further exploit the structure of solutions of the problem, and are incorporated in two proposed algorithms: a bounded-insertion-based constructive heuristic and an advanced non-population-based algorithm. These algorithms are compared with state-of-the-art algorithms under the same computer conditions. The results show that both algorithms improve existing ones and therefore, constitute the new state-of-art approximate solution procedures for the problem.