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.     

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.     

A hybrid discrete artificial bee colony algorithm for permutation flowshop scheduling problem

To minimize the makespan in permutation flowshop scheduling problems, a hybrid discrete artificial bee colony (HDABC) algorithm is presented. In the HDABC, each solution to the problem is called a food source and represented by a discrete job permutation. First, the initial population with certain quality and diversity is generated from Greedy Randomized Adaptive Search Procedure (GRASP) based on Nawaz–Enscore–Ham (NEH) heuristics. Second, the discrete operators and algorithm, such as insert, swap, path relinking and GRASP are applied to generate new solution for the employed bees, onlookers and scouts. Moreover, local search is applied to the best one. The presented algorithm is tested on scheduling problem benchmarks. Experimental results show its efficiency.     

A smart algorithm for multi-criteria optimization of model sequencing problem in assembly lines

Assembly Lines (ALs) are used for mass production as they offer lots of advantages over other production systems in terms of lead time and cost. The advent of mass customization has forced the manufacturing industries to update to Mixed-Model Assembly Lines (MMALs) but at the cost of increased complexity. In the real world, industries need to determine the sequence of models based on various conflicting performance measures/criteria. This paper investigates the Multi-Criteria Model Sequencing Problem (MC-MSP) using a modified simulation integrated Smart Multi-Criteria Nawaz, Enscore, and Ham (SMC-NEH) algorithm. To address the multiple criteria, a modified simulation integrated Smart Multi-Criteria Nawaz, Enscore, and Ham (SMC-NEH) algorithm was developed by integrating a priori approach with NEH algorithm. Discrete Event Simulation (DES) was used to evaluate each solution. A mathematical model was developed for three criteria: flow time, makespan and idle time. Further, to validate the effectiveness of the proposed SMC-NEH a case study and Taillard's benchmark instances were solved and a Multi-Criteria Decision-Making (MCDM) analysis was performed to compare the performance of the proposed SMC-NEH algorithm with the traditional NEH algorithm and its variants. The results showed that the proposed SMC-NEH algorithm outperformed the others in optimizing the conflicting multi-criteria problem.     

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 effective discrete invasive weed optimization algorithm for lot-streaming flowshop scheduling problems

Lot-streaming scheduling problem has been an active area of research due to its important applications in modern industries. This paper deals with the lot-streaming flowshop problem with sequence-dependent setup times with makespan criterion. An effective discrete invasive weed optimization (DIWO) algorithm is presented with new characteristics. A job permutation representation is utilized and an adapted Nawaz–Enscore–Ham heuristic is employed to ensure an initial weed colony with a certain level of quality. A new spatial dispersal model is designed based on the normal distribution and the property of tangent function to enhance global search. A local search procedure based on the insertion neighborhood is employed to perform local exploitation. The presented DIWO is calibrated by means of the design of experiments approach. A comparative evaluation is carried out with several best performing algorithms based on a total of 280 randomly generated instances. The numerical experiments show that the presented DIWO algorithm produces significantly better results than the competing algorithms and it constitutes a new state-of-the-art solution for the lot-streaming flowshop problem with sequence-dependent setup times with makespan criterion.     

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.     

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.     

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

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

A discrete differential evolution algorithm for the permutation flowshop scheduling problem

Very recently, Pan et al. [Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO07, pp. 126–33] presented a new and novel discrete differential evolution algorithm for the permutation flowshop scheduling problem with the makespan criterion. On the other hand, the iterated greedy algorithm is proposed by [Ruiz, R., & Stützle, T. (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177(3), 2033–49] for the permutation flowshop scheduling problem with the makespan criterion. However, both algorithms are not applied to the permutation flowshop scheduling problem with the total flowtime criterion. Based on their excellent performance with the makespan criterion, we extend both algorithms in this paper to the total flowtime objective. Furthermore, we propose a new and novel referenced local search procedure hybridized with both algorithms to further improve the solution quality. The referenced local search exploits the space based on reference positions taken from a reference solution in the hope of finding better positions for jobs when performing insertion operation. Computational results show that both algorithms with the referenced local search are either better or highly competitive to all the existing approaches in the literature for both objectives of makespan and total flowtime. Especially for the total flowtime criterion, their performance is superior to the particle swarm optimization algorithms proposed by [Tasgetiren, M. F., Liang, Y. -C., Sevkli, M., Gencyilmaz, G. (2007). Particle swarm optimization algorithm for makespan and total flowtime minimization in permutation flowshop sequencing problem. European Journal of Operational Research, 177(3), 1930–47] and [Jarboui, B., Ibrahim, S., Siarry, P., Rebai, A. (2007). A combinatorial particle swarm optimisation for solving permutation flowshop problems. Computers & Industrial Engineering, doi:10.1016/j.cie.2007.09.006]. Ultimately, for Taillard’s benchmark suite, four best known solutions for the makespan criterion as well as 40 out of the 90 best known solutions for the total flowtime criterion are further improved by either one of the algorithms presented in this paper.     

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.     

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.     

A combinatorial particle swarm optimisation for solving permutation flowshop problems

The m-machine permutation flowshop problem PFSP with the objectives of minimizing the makespan and the total flowtime is a common scheduling problem, which is known to be NP-complete in the strong sense, when m ? 3. This work proposes a new algorithm for solving the permutation FSP, namely combinatorial Particle Swarm Optimization. Furthermore, we incorporate in this heuristic an improvement procedure based on the simulated annealing approach. The proposed algorithm was applied to well-known benchmark problems and compared with several competing metaheuristics.     

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.     

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.     

A Constructive Genetic Algorithm for permutation flowshop scheduling

The general flowshop scheduling problem is a production problem where a set of n jobs have to be processed with identical flow pattern on m machines. In permutation flowshops the sequence of jobs is the same on all machines. A significant research effort has been devoted for sequencing jobs in a flowshop minimizing the makespan. This paper describes the application of a Constructive Genetic Algorithm (CGA) to makespan minimization on flowshop scheduling. The CGA was proposed recently as an alternative to traditional GA approaches, particularly, for evaluating schemata directly. The population initially formed only by schemata, evolves controlled by recombination to a population of well-adapted structures (schemata instantiation). The CGA implemented is based on the NEH classic heuristic and a local search heuristic used to define the fitness functions. The parameters of the CGA are calibrated using a Design of Experiments (DOE) approach. The computational results are compared against some other successful algorithms from the literature on Taillard’s well-known standard benchmark. The computational experience shows that this innovative CGA approach provides competitive results for flowshop scheduling problems.     

Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects

In this paper, we study the problem of minimizing the weighted sum of makespan and total completion time in a permutation flowshop where the processing times are supposed to vary according to learning effects. The processing time of a job is a function of the sum of the logarithms of the processing times of the jobs already processed and its position in the sequence. We present heuristic algorithms, which are modified from the optimal schedules for the corresponding single machine scheduling problem and analyze their worst-case error bound. We also adopt an existing algorithm as well as a branch-and-bound algorithm for the general m-machine permutation flowshop problem. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems.     

瓶颈指向的启发式算法求解混合流水车间调度问题

针对以最小化时间表长为目标的复杂混合流水车间调度问题,提出了一种将机器布局和工件加工时间特征紧密结合的启发式算法.首先,充分利用各阶段平均机器负荷一般不相等的特点确定瓶颈阶段,构建初始工件排序.其次,针对在瓶颈阶段前加工时间较短而瓶颈阶段后加工时间相对较长的工件,在第1阶段优先开始加工.同时,在瓶颈阶段前的每一个阶段,每当有工件等待加工或同时完工时,优先选择瓶颈阶段前剩余加工时间最短的工件加工;在瓶颈阶段以及瓶颈阶段之后,则优先选择这台机器后剩余加工时间最长的工件加工.最后,采用工件交换和插入操作改进初始调度.用Carlier和Neron的Benchmark算例测试提出的启发式算法.将计算结果与NEH启发式算法进行了比较,平均偏差降低了0.0555%,表明这个启发式算法是有效的.     

An efficient stochastic hybrid heuristic for flowshop scheduling

The paper addresses the problem of flowshop scheduling in order to minimize the makespan objective. Three probabilistic hybrid heuristics are presented for solving permutation flowshop scheduling problem. The proposed methodology combines elements from both constructive heuristic search and a stochastic improvement technique. The stochastic method used in this paper is simulated annealing (SA). Experiments have been run on a large number of randomly generated test problems of varying jobs and machine sizes. Our approach is shown to outperform best-known existing heuristics, including the classical NEH technique (OMEGA, 1983) and the SA based on (OMEGA, 1989) of Osman and Potts . Statistical tests of significance are performed to substantiate the claims of improvement.     

An effective L-MONG algorithm for solving multi-objective flow-shop inverse scheduling problems

Generally, in handling traditional scheduling problems, ideal manufacturing system environments are assumed before determining effective scheduling. Unfortunately, “ideal environments” are not always possible. Real systems often encounter some uncertainties which will change the status of manufacturing systems. These may cause the original schedule to no longer to be optimal or even feasible. Traditional scheduling methods are not effective in coping with these cases. Therefore, a new scheduling strategy called “inverse scheduling” has been proposed to handle these problems. To the best of our knowledge, this research is the first to provide a comprehensive mathematical model for multi-objective permutation flow-shop inverse scheduling problem (PFISP). In this paper, first, a PFISP mathematical model is devised and an effective hybrid multi-objective evolutionary algorithm is proposed to handle uncertain processing parameters (uncertainties) and multiple objectives at the same time. In the proposed algorithm, we take an insert method NEH-based (Nawaz–Enscore–Ham) as a local improving procedure and propose several adaptations including efficient initialization, decimal system encoding, elitism and population diversity. Finally, 119 public problem instances with different scales and statistical performance comparisons are provided for the proposed algorithm. The results show that the proposed algorithm performs better than the traditional multi-objective evolution algorithm (MOEA) in terms of searching quality, diversity level and efficiency. This paper is the first to propose a mathematical model and develop a hybrid MOEA algorithm to solve PFISP in inverse scheduling domain.