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.     

Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan

The multistage hybrid flow shop (HFS) scheduling problems are considered in this paper. Hybrid flowshop scheduling problems were proved to be NP-hard. A recently developed cuckoo search (CS) metaheuristic algorithm is presented in this paper to minimize the makespan for the HFS scheduling problems. A constructive heuristic called NEH heuristic is incorporated with the initial solutions to obtain the optimal or near optimal solutions rapidly in the improved cuckoo search (ICS) algorithm. The proposed algorithm is validated with the data from a leading furniture manufacturing company. Computational results show that the ICS algorithm outperforms many other metaheuristics.     

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.     

自适应混合粒子群算法求解置换流水车间调度问题

为更有效地解决以最大完工时间最小化为目标的置换流水车间调度问题,提出了一种自适应混合粒子群算法（SHPSO）。该算法结合Q学习设计了参数自适应更新策略,以平衡算法的探索和开发;同时引入粒子停滞判断方法,使用平局决胜机制和Taillard加速算法改进基于迭代贪婪的局部搜索策略,对全局极值进行局部搜索,帮助粒子跳出局部最优。实验结果表明,SHPSO算法取得的平均相对百分偏差（RPDavg）对比其他四种改进PSO算法至少下降了83.2%,在求解质量上具有明显优势。     

A genetic algorithm for permutation flow shop scheduling under make to stock production system

The permutation flow shop scheduling is a well-known combinatorial optimization problem that arises in many manufacturing systems. Over the last few decades, permutation flow shop problems have widely been studied and solved as a static problem. However, in many practical systems, permutation flow shop problems are not really static, but rather dynamic, where the challenge is to schedule n different products that must be produced on a permutation shop floor in a cyclical pattern. In this paper, we have considered a make-to-stock production system, where three related issues must be considered: the length of a production cycle, the batch size of each product, and the order of the products in each cycle. To deal with these tasks, we have proposed a genetic algorithm based lot scheduling approach with an objective of minimizing the sum of the setup and holding costs. The proposed algorithm has been tested using scenarios from a real-world sanitaryware production system, and the experimental results illustrates that the proposed algorithm can obtain better results in comparison to traditional reactive approaches.     

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.     

A hybrid harmony search algorithm for the blocking permutation flow shop scheduling problem

This paper proposes a hybrid modified global-best harmony search (hmgHS) algorithm for solving the blocking permutation flow shop scheduling problem with the makespan criterion. First of all, the largest position value (LPV) rule is proposed to convert continuous harmony vectors into job permutations. Second, an efficient initialization scheme based on the Nawaz-Enscore-Ham (NEH) heuristic is presented to construct the initial harmony memory with a certain level of quality and diversity. Third, harmony search is employed to evolve harmony vectors in the harmony memory to perform exploration, whereas a local search algorithm based on the insert neighborhood is embedded to enhance the local exploitation ability. Moreover, a new pitch adjustment rule is developed to well inherit good structures from the global-best harmony vector. Computational simulations and comparisons demonstrated the superiority of the proposed hybrid harmony search algorithm in terms of solution quality.     

求解置换流水车间调度问题的混合蚁群算法

针对最大—最小蚂蚁系统在解决置换流水车间调度问题时易陷入局部最优的问题,引入最好—最差蚂蚁系统中的信息素变异和重置规则,提出了一种混合蚁群算法。使信息素矩阵变异并在搜索过程停滞时重置信息素矩阵以在搜索过程中引入多样性。在基准问题集上的对比实验表明,该算法比传统的蚁群算法具有更好的搜索全局最优解的能力。     

A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem

This paper proposes a hybrid variable neighborhood search (HVNS) algorithm that combines the chemical-reaction optimization (CRO) and the estimation of distribution (EDA), for solving the hybrid flow shop (HFS) scheduling problems. The objective is to minimize the maximum completion time. In the proposed algorithm, a well-designed decoding mechanism is presented to schedule jobs with more flexibility. Meanwhile, considering the problem structure, eight neighborhood structures are developed. A kinetic energy sensitive neighborhood change approach is proposed to extract global information and avoid being stuck at the local optima. In addition, contrary to the fixed neighborhood set in traditional VNS, a dynamic neighborhood set update mechanism is utilized to exploit the potential search space. Finally, for the population of local optima solutions, an effective EDA-based global search approach is investigated to direct the search process to promising regions. The proposed algorithm is tested on sets of well-known benchmark instances. Through the analysis of experimental results, the high performance of the proposed HVNS algorithm is shown in comparison with four efficient algorithms from the literature.     

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.     

面向多目标流水车间调度的多种群多目标遗传算法

针对制造型企业普遍存在的流水车间调度问题,建立了以最小化最迟完成时间和总延迟时间为目标的多目标调度模型,并提出一种基于分解方法的多种群多目标遗传算法进行求解.该算法将多目标流水车间调度问题分解为多个单目标子问题,并分阶段地将这些子问题引入到算法迭代过程进行求解.算法在每次迭代时,依据种群的分布情况选择各子问题的最好解及与其相似的个体分别为当前求解的子问题构造子种群,通过多种群的进化完成对多个子问题最优解的并行搜索.通过对标准测试算例进行仿真实验,结果表明所提出的算法在求解该问题上能够获得较好的非支配解集.     

Minimizing total completion time for re-entrant flow shop scheduling problems

In this paper, we study re-entrant flow shop scheduling problems with the objective of minimizing total completion time. In a re-entrant scheduling problem, jobs may visit some machines more than once for processing. The problem is NP-hard even for machine number m=2. A heuristic algorithm is presented to solve the problem, in which an effective k-insertion technique is introduced as the improvement strategy in iterations. Computational experiments and analyses are performed to give guidelines of choosing parameters in the algorithm. We also provide a lower bound for the total completion time of the optimal solution when there are only two machines. Objective function values of the heuristic solutions are compared with the lower bounds to evaluate the efficiency of the algorithm. For randomly generated instances, the results show that the given heuristic algorithm generates solutions with total completion times within 1.2 times of the lower bounds in most of the cases.     

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 estimation of distribution algorithm for minimizing the total flowtime in permutation flowshop scheduling problems

In this work we propose an estimation of distribution algorithm (EDA) as a new tool aiming at minimizing the total flowtime in permutation flowshop scheduling problems. A variable neighbourhood search is added to the algorithm as an improvement procedure after creating a new offspring. The experiments show that our approach outperforms all existing techniques employed for the problem and can provide new upper bounds.     

求解置换流水车间调度问题的改进遗传算法

目前求解置换流水车间调度问题的遗传算法中,加工顺序编码方法导致交叉、变异算子复杂,且子代与父代不相似,算法易陷入局部最优。为解决以上问题,提出了一种基于优先权值编码并含有限优算子的改进遗传算法。利用各工件的优先权值进行编码,避免遗传算子中不合法编码的出现;加入限优算子限制种群中最优个体的繁殖数量,防止种群陷入局部最优点,改善寻优质量。实验结果表明,该算法中的编码方法可行且易于应用于求解紧急工件优先加工的实际问题;同时用基准算例验证了具有限优算子的改进算法求解结果相对误差小且求解稳定性高。     

A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time

A variety of metaheuristics have been developed to solve the permutation flow shop problem minimizing total flow time. Iterated local search (ILS) is a simple but powerful metaheuristic used to solve this problem. Fundamentally, ILS is a procedure that needs to be restarted from another solution when it is trapped in a local optimum. A new solution is often generated by only slightly perturbing the best known solution, narrowing the search space and leading to a stagnant state. In this paper, a strategy is proposed to allow the restart solution to be generated from a group of solutions drawn from local optima. This allows an extension of the search space, while maintaining the quality of the restart solution. A multi-restart ILS (MRSILS) is proposed, with the performance evaluated on a set of benchmark instances and compared with six state of the art metaheuristics. The results show that the easily implementable MRSILS is significantly better than five of the other metaheuristics and comparable to or slightly better than the remaining one.     

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.     

求解零空闲流水线调度问题的改进蚁群算法*

在研究蚁群算法的基础上,解决零空闲流水线调度问题的最大完工时间。改进了蚁群算法中信息素密度的初始化方法和更新规则,结合快速邻域搜索算法,解决算法易陷入局部收敛的缺点,提出了该算法解决零空闲调度问题的最佳求解策略。仿真实验表明,该算法具有高效性和优越性。     

Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling

Factory management plays an important role in improving the productivity and quality of service in the production process. In particular, the distributed permutation flow shop scheduling problem with multiple factories is considered a priority factor in the factory automation. This study proposes a novel model of the developed distributed scheduling by supplementing the reentrant characteristic into the model of distributed reentrant permutation flow shop (DRPFS) scheduling. This problem is described as a given set of jobs with a number of reentrant layers is processed in the factories, which compromises a set of machines, with the same properties. The aim of the study is to determine the number of factory needs to be used, jobs assignment to certain factory and sequence of job assigned to the factory in order to simultaneously satisfy three objectives of minimizing makespan, total cost and average tardiness. To do this, a novel multi-objective adaptive large neighborhood search (MOALNS) algorithm is developed for finding the near optimal solutions based on the Pareto front. Various destroy and repair operators are presented to balance between intensification and diversification of searching process. The numerical examples of computational experiments are carried out to validate the proposed model. The analytical results on the performance of proposed algorithm are checked and compared with the existing methods to validate the effectiveness and robustness of the proposed potential algorithm in handling the DRPFS problem.     

Flow shop问题的嵌套分区优化调度方法

介绍了嵌套分区算法(NP)的基本思想, 并用于求解流水作业优化调度问题. 算法用嵌套分区树来描述流水作业调度问题, 对可行域进行系统性分区, 然后集中搜索有优良解的区域. 在每一步迭代中, 算法跟踪最有希望的分区, 并结合启发式算法和邻域搜索来实现分区转移. 仿真实验表明, 该算法比单纯的启发式算法和邻域搜索有较好的寻优能力.