An improved NEH heuristic to minimize makespan in permutation flow shops

For over 20 years the NEH heuristic of Nawaz, Enscore, and Ham [A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, The International Journal of Management Science 1983;11:91–5] has been commonly regarded as the best heuristic for solving the NP-hard problem of minimizing the makespan in permutation flow shops. The strength of NEH lies mainly in its priority order according to which jobs are selected to be scheduled during the insertion phase. Framinan et al. [Different initial sequences for the heuristic of Nawaz, Enscore and Ham to minimize makespan, idle time or flowtime in the static permutation flowshop problem. International Journal of Production Research 2003;41:121–48] presented the results of an extensive study to conclude that the NEH priority order is superior to 136 different orders examined. Based upon the concept of Johnson's algorithm, we propose a new priority order combined with a simple tie-breaking method that leads to a heuristic that outperforms NEH for all problem sizes.     

Production scheduling for blocking flowshop in distributed environment using effective heuristics and iterated greedy algorithm

Production scheduling plays an important role in the intelligent decision support system and intelligent optimization decision technology. In the context of the globalization trend, the current production and management may extend from a single factory to a distributed production network. In this paper, we study the distributed blocking flowshop scheduling problem (DBFSP) that is an important generalization of the traditional blocking flowshop scheduling problem in the distributed environment. Six constructive heuristics and an iterated greedy (IG) algorithm are proposed to minimize the makespan, which provides procedures for obtaining efficient and effective solutions to make decision-making sounder. The first five heuristics are developed based on the well-known NEH2 heuristic [B. Naderi, R. Ruiz, The distributed permutation flowshop scheduling problem, Computers & Operations Research, 37 (4) (2010) 754–768.] and the last heuristic is presented by extending the PW heuristic [Q.K. Pan, L. Wang, Effective heuristics for the blocking flowshop scheduling problem with makespan minimization, Omega, 40 (2) (2012) 218–229.] to DBFSP in an effective way. The composite heuristics that combining constructive heuristics and local searches are also studied. The proposed composite heuristics are chosen to generate an initial solution with a high level of quality. Keeping the simplicity of the IG algorithm, three local search procedures, two destruction procedures, an improved reconstruction procedure, and a simulated annealing-like acceptance criterion are well designed based on the problem-specific knowledge to enhance the IG algorithm. The computational experiments are carried out based on the 720 benchmark instances from the literature. The results show that the proposed heuristics are very effective for solving the problem under consideration and the presented IG algorithm performs significantly better than the other state-of-the-art metaheuristics from the literature.     

Comparing three-step heuristics for the permutation flow shop problem

In this paper a three steps heuristic for the permutation flow shop problem is proposed. The objective is to minimize the maximum time for completing the jobs, or the makespan. The first two steps are inspired by the NEH heuristic, to which a new tie breaking strategy has been incorporated in the insertion phase. Furthermore, the reversibility property of the problem dealt with is taken as a tool for improving the obtained solution. The third step consists of an iterated local search procedure with an embedded local search which is a variant of the non exhaustive descent algorithm. The statistical analysis of the results shows the effectiveness of the proposed procedures.     

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.     

An improved iterated greedy algorithm with a Tabu-based reconstruction strategy for the no-wait flowshop scheduling problem

This paper proposes a Tabu-mechanism improved iterated greedy (TMIIG) algorithm to solve the no-wait flowshop scheduling problem with a makespan criterion. The idea of seeking further improvement in the iterated greedy (IG) algorithm framework is based on the observation that the construction phase of the original IG algorithm may not achieve good performance in escaping from local minima when incorporating the insertion neighborhood search. To overcome this limitation, we have modified the IG algorithm by utilizing a Tabu-based reconstruction strategy to enhance its exploration ability. A powerful neighborhood search method that involves insert, swap, and double-insert moves is then applied to obtain better solutions from the reconstructed solution in the previous step. Empirical results on several benchmark problem instances and those generated randomly confirm the advantages of utilizing the new reconstruction scheme. In addition, our results also show that the proposed TMIIG algorithm is relatively more effective in minimizing the makespan than other existing well-performing heuristic algorithms.     

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.     

An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem

Permutation flowshop scheduling problems (PFSPs) and, in particular, the variant with the objective of minimizing makespan have received an enormous attention in scheduling research and combinatorial optimization. As a result, the algorithmic approaches to this PFSP variant have reached extremely high performance. Currently, one of the most effective algorithm for this problem is a structurally rather simple iterated greedy algorithm. In this paper, we explore the possibility of re-optimizing partial solutions obtained after the solution destruction step of the iterated greedy algorithm. We show that with this extension, the performance of the state-of-the-art algorithm for the PFSP under makespan criterion can be significantly improved and we give experimental evidence that the local search on partial solutions is the key component for the high performance of the algorithm.     

A generalized constructive algorithm using insertion-based heuristics

In this paper, a generalized constructive algorithm referred to as GCA is presented which makes it possible to select a wide variety of heuristics just by the selection of its arguments values. A general framework for generating permutations of integers is presented. This framework, referred to as PERMGEN, forms a link between the numbering of permutations and steps in the insertion-based heuristics. A number of arguments controlling the operation of GCA are identified. Features and benefits of the generalized algorithm are presented through the extension of the NEH heuristic, a successful heuristic solution approach of Nawaz, Enscore, and Ham for the permutation flowshop problem (PFSP). The goal of the experimental study is to improve the performance of the NEH heuristic on the PFSP. To achieve this goal, the space of algorithmic control arguments is searched for a combination of values that define an algorithm providing lower makespan solutions than NEH, in a linear increase of CPU time. Computational experiments on a set of 120 benchmark problem instances, originally proposed by Taillard, are performed to establish a more robust version of the original NEH constructive heuristic. The proposed procedures outperform NEH, preserving its efficiency and simplicity.     

求解批量流水线调度问题的蜂群算法

针对批量流水线调度问题,提出了一种改进的人工蜂群算法来优化最大完成时间。该算法运用NEH方法产生初始解,采用混沌遍历的方法生成新的邻域解。为了跳出局部最优,使用最优解的插入扰动来替换一些连续若干步不能改进的解来提高算法的全局搜索能力。采用自适应的局部搜索加强算法的局部搜索能力。仿真试验表明了所得算法的可行性和高效性。     

An artificial neural network based heuristic for flow shop scheduling problems

The objective of this paper is to find a sequence of jobs in the flow shop to minimize makespan. A feed forward back propagation neural network is used to solve the problem. The network is trained with the optimal sequences of completely enumerated five, six and seven jobs, ten machine problem and this trained network is then used to solve the problem with greater number of jobs. The sequence obtained using artificial neural network (ANN) is given as the initial sequence to a heuristic proposed by Suliman and also to genetic algorithm (GA) as one of the sequences of the population for further improvement. The approaches are referred as ANN-Suliman heuristic and ANN-GA heuristic respectively. Makespan of the sequences obtained by these heuristics are compared with the makespan of the sequences obtained using the heuristic proposed by Nawaz, Enscore and Ham (NEH) and Suliman Heuristic initialized with Campbell Dudek and Smith (CDS) heuristic called as CDS-Suliman approach. It is found that the ANN-GA and ANN-Suliman heuristic approaches perform better than NEH and CDS-Suliman heuristics for the problems considered.     

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.     

A hybrid algorithmic model for the minimum weight dominating set problem

Iterated greedy algorithms belong to the class of stochastic local search methods. They are based on the simple and effective principle of generating a sequence of solutions by iterating over a constructive greedy heuristic using destruction and construction phases. This paper, first, presents an efficient randomized iterated greedy approach for the minimum weight dominating set problem, where—given a vertex-weighted graph—the goal is to identify a subset of the graphs’ vertices with minimum total weight such that each vertex of the graph is either in the subset or has a neighbor in the subset. Our proposed approach works on a population of solutions rather than on a single one. Moreover, it is based on a fast randomized construction procedure making use of two different greedy heuristics. Secondly, we present a hybrid algorithmic model in which the proposed iterated greedy algorithm is combined with the mathematical programming solver CPLEX. In particular, we improve the best solution provided by the iterated greedy algorithm with the solution polishing feature of CPLEX. The simulation results obtained on a widely used set of benchmark instances shows that our proposed algorithms outperform current state-of-the-art approaches.     

离散和声求解带启动时间批量流水线调度问题

分别在有等待和无等待的情况下,深入分析了带有启动时间的批量调度问题,以最小化最大完成时间为目标,提出了两种离散和声搜索算法。针对算法本质连续而问题离散的矛盾,对和声搜索算法进行改进。首先提出了基于工序的编码方式,采用inver-over和重组两种离散算子产生候选解的进化机制;并利用改进的NEH(Nawaz-Enscore-Ham)方法进行初始化,产生的高质量和多样化的初始种群有效地指导了算法的进化方向,提高收敛速度;最后将一种简单而有效的局部邻域搜索方法嵌入到和声搜索算法中以增强其局部搜索能力。仿真实验和比较结果表明了所提算法的有效性。     

Scatter search for mixed blocking flowshop scheduling

Empty or limited storage capacities between machines introduce various types of blocking constraint in the industries with flowshop environment. While large applications demand flowshop scheduling with a mix of different types of blocking, research in this area mainly focuses on using only one kind of blocking in a given problem instance. In this paper, using makespan as a criterion, we study permutation flowshops with zero capacity buffers operating under mixed blocking conditions. We present a very effective scatter search (SS) algorithm for this. At the initialisation phase of SS, we use a modified version of the well-known Nawaz, Enscore and Ham (NEH) heuristic. For the improvement method in SS, we use an Iterated Local Search (ILS) algorithm that adopts a greedy job selection and a powerful NEH-based perturbation procedure. Moreover, in the reference set update phase of SS, with small probabilities, we accept worse solutions so as to increase the search diversity. On standard benchmark problems of varying sizes, our algorithm very significantly outperforms well-known existing algorithms in terms of both the solution quality and the computing time. Moreover, our algorithm has found new upper bounds for 314 out of 360 benchmark problem instances.     

An improved NEH-based heuristic for the permutation flowshop problem

NEH is an effective heuristic for solving the permutation flowshop problem with the objective of makespan. It includes two phases: generate an initial sequence and then construct a solution. The initial sequence is studied and a strategy is proposed to solve job insertion ties which may arise in the construct process. The initial sequence which is generated by combining the average processing time of jobs and their standard deviations shows better performance. The proposed strategy is based on the idea of balancing the utilization among all machines. Experiments show that using this strategy can improve the performance of NEH significantly. Based on the above ideas, a heuristic NEH-D (NEH based on Deviation) is proposed, whose time complexity is O(mn²), the same as that of NEH. Computational results on benchmarks show that the NEH-D is significantly better than the original NEH.     

An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem

In this work, we tackle the problem of scheduling a set of jobs on a set of unrelated parallel machines with minimising the total weighted completion times as performance criteria. The iterated greedy metaheuristic generates a sequence of solutions by iterating over a constructive heuristic using destruction and construction phases. In the last few years, iterated greedy has been employed to solve a considerable number of problems. This is because it is based on a very simple principle, it is easy to implement, and it often exhibits an excellent performance. Moreover, scalability for high-dimensional problems becomes an essential requirement for modern optimisation algorithms. This paper proposes an iterated greedy model for the above-mentioned scheduling problem to tackle large-size instances. The benefits of our proposal in comparison to existing metaheuristics proposed in the literature are experimentally shown.     

混合迭代贪婪算法求解准时生产分布式流水线调度问题

针对以最小化总延迟时间为优化目标的分布式置换流水线问题(distributed permutation flowshop scheduling problem,DPFSP),建立问题排序模型,并提出混合迭代贪婪算法(hybrid iterated greedy,HIG)进行求解.基于问题特点提出最小工期差值(smallest due date difference value,SDV)规则及3种工厂分配规则, 同时结合问题性质提出两种工件插入各工厂内部时问题目标值的下界估计方法.首先,通过实验确定使用分配规则1将工件向各工厂进行分配,同时结合下界估计方法的NEH作为改进启发式算法以生成较高质量初始解;其次,为了增加解的多样性,提出一种关键工厂的移除策略和适用于问题的模拟退火机制;然后,设计基于4种有效邻域操作的两阶段变邻域下降搜索策略,用于在HIG每代中对问题解空间的不同区域进行较深入和细致的搜索;最后,通过仿真实验和算法比较验证了采用HIG求解所提出问题的有效性.     

Total flow time minimization in no-wait job shop using a hybrid discrete group search optimizer

The no-wait job shop scheduling problem is a well-known NP-hard problem and it is typically decomposed into timetabling subproblem and sequencing subproblem. By adopting favorable features of the group search technique, a hybrid discrete group search optimizer is proposed for finding high quality schedules in the no-wait job shops with the total flow time criterion. In order to find more promising sequences, the producer operator is designed as a destruction and construction (DC) procedure and an insertion-based local search, the scrounger operator is implemented by differential evolution scheme, and the ranger operator is designed by hybridizing best insert moves. An efficient initialization scheme based on Nawaz–Enscore–Ham (NEH) heuristic is designed to construct the initial population with both quality and diversity. A speed-up method is developed to accelerate the evaluation of the insertion neighborhood. Computational results based on well-known benchmark instances show that the proposed algorithm clearly outperforms a hybrid differential evolution algorithm and an iterated greedy algorithm. In addition, the proposed algorithm is comparable to a local search method based on optimal job insertion, especially for large-size instances.     

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.     

Improving the quality of heuristic solutions for the capacitated vertex p-center problem through iterated greedy local search with variable neighborhood descent

The capacitated vertex p-center problem is a location problem that consists of placing p facilities and assigning customers to each of these facilities so as to minimize the largest distance between any customer and its assigned facility, subject to demand capacity constraints for each facility. In this work, a metaheuristic for this location problem that integrates several components such as greedy randomized construction with adaptive probabilistic sampling and iterated greedy local search with variable neighborhood descent is presented. Empirical evidence over a widely used set of benchmark data sets on location literature reveals the positive impact of each of the developed components. Furthermore, it is found empirically that the proposed heuristic outperforms the best existing heuristic for this problem in terms of solution quality, running time, and reliability on finding feasible solutions for hard instances.