SOLVING THE OPEN SHOP SCHEDULING PROBLEM VIA A HYBRID GENETIC-VARIABLE NEIGHBORHOOD SEARCH ALGORITHM

In this article, a hybrid metaheuristic method for solving the open shop scheduling problem (OSSP) is proposed. The optimization criterion is the minimization of makespan and the solution method consists of four components: a randomized initial population generation, a heuristic solution included in the initial population acquired by a Nawaz-Enscore-Ham (NEH)-based heuristic for the flow shop scheduling problem, and two interconnected metaheuristic algorithms: a variable neighborhood search and a genetic algorithm. To our knowledge, this is the first hybrid application of genetic algorithm (GA) and variable neighborhood search (VNS) for the open shop scheduling problem. Computational experiments on benchmark data sets demonstrate that the proposed hybrid metaheuristic reaches a high quality solution in short computational times. Moreover, 12 new hard, large-scale open shop benchmark instances are proposed that simulate realistic industrial cases.     

Parallel-machine scheduling problems with sequence-dependent setup times using an ACO,SA and VNS hybrid algorithm

This paper proposes a hybrid metaheuristic for the minimization of makespan in scheduling problems with parallel machines and sequence-dependent setup times. The solution approach is robust, fast, and simply structured, and comprises three components: an initial population generation method based on an ant colony optimization (ACO), a simulated annealing (SA) for solution evolution, and a variable neighborhood search (VNS) which involves three local search procedures to improve the population. The hybridization of an ACO, SA with VNS, combining the advantages of these three individual components, is the key innovative aspect of the approach. Two algorithms of a hybrid VNS-based algorithm, SA/VNS and ACO/VNS, and the VNS algorithm presented previously are used to compare with the proposed hybrid algorithm to highlight its advantages in terms of generality and quality for large instances.     

A Neurogenetic approach for the resource-constrained project scheduling problem

A variety of metaheuristic approaches have emerged in recent years for solving the resource-constrained project scheduling problem (RCPSP), a well-known NP-hard problem in scheduling. In this paper, we propose a Neurogenetic approach which is a hybrid of genetic algorithms (GA) and neural-network (NN) approaches. In this hybrid approach the search process relies on GA iterations for global search and on NN iterations for local search. The GA and NN search iterations are interleaved in a manner that allows NN to pick the best solution thus far from the GA pool and perform an intensification search in the solution's local neighborhood. Similarly, good solutions obtained by NN search are included in the GA population for further search using the GA iterations. Although both GA and NN approaches, independently give good solutions, we found that the hybrid approach gives better solutions than either approach independently for the same number of shared iterations. We demonstrate the effectiveness of this approach empirically on the standard benchmark problems of size J30, J60, J90 and J120 from PSPLIB.     

Bi-objective parallel machines scheduling with sequence-dependent setup times using hybrid metaheuristics and weighted min–max technique

In the literature of multi-objective problem, there are different algorithms to solve different optimization problems. This paper presents a min–max multi-objective procedure for a dual-objective, namely make span, and sum of the earliness and tardiness of jobs in due window machine scheduling problems, simultaneously. In formulation of min–max method when this method is combined with the weighting method, the decision maker can have the flexibility of mixed use of weights and distance parameter to yield a set of Pareto-efficient solutions. This research extends the new hybrid metaheuristic (HMH) to solve parallel machines scheduling problems with sequence-dependent setup time that comprises three components: an initial population generation method based on an ant colony optimization (ACO), a simulated annealing (SA) as an evolutionary algorithm employs certain probability to avoid becoming trapped in a local optimum, and a variable neighborhood search (VNS) which involves three local search procedures to improve the population. In addition, two VNS-based HMHs, which are a combination of two methods, SA/VNS and ACO/VNS, are also proposed to solve the addressed scheduling problems. A design of experiments approach is employed to calibrate the parameters. The non-dominated sets obtained from HMH and two best existing bi-criteria scheduling algorithms are compared in terms of various indices and the computational results show that the proposed algorithm is capable of producing a number of high-quality Pareto optimal scheduling plans. Aside, an extensive computational experience is carried out to analyze the different parameters of the algorithm.     

Elucidating multiprocessors flow shop scheduling with dependent setup times using a twin particle swarm optimization

Particle swarm optimization (PSO) is a novel metaheuristic, which has been applied in a wide variety of production scheduling problems. Two basic characteristics of this algorithm are its efficiency and effectiveness in providing high-quality solutions. In order to improve the traditional PSO, this study proposes the incorporation of a local search heuristic into the basic PSO algorithm. The new, hybrid, metaheuristic is called “twin particle swarm optimization (TPSO)”. The proposed metaheuristic scheme is applied to a flow shop with multiprocessors scheduling problem, which can be considered a real world case regarding the production line. This study, as far as the multiprocessors flow shop production system is concerned, utilizes sequence dependent setup times as constraints. Finally, simulated data confirm the effectiveness and robustness of the proposed algorithm. The data test results indicate that TPSO has potential to replace PSO and become a significant heuristic algorithm for similar 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.     

基于混合遗传算法的车间调度问题的研究

提出了在柔性生产环境下基于遗传算法与模拟退火算法混合的动态调度算法,充分发挥遗传算法良好的全局搜索能力和模拟退火算法有效避免陷入局部极小的特性,有很好的收敛精度,并且能够在扰动发生后提供新的调度计划;通过交叉,变异等遗传操作、得到目标的最佳或次优解,最后对算法进行了仿真研究,仿真结果表明该算法是可行的,与传统的调度算法相比,其优越性是明显的。     

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.     

Evolutionary algorithms for scheduling m-machine flow shop with lot streaming

This paper addresses the problem of making sequencing and scheduling decisions for n jobs–m-machines flow shops under lot sizing environment. Lot streaming (Lot sizing) is the process of creating sub lots to move the completed portion of a production sub lots to down stream machines. There is a scope for efficient algorithms for scheduling problems in m-machine flow shop with lot streaming. In recent years, much attention is given to heuristics and search techniques. Evolutionary algorithms that belong to search heuristics find more applications in recent research. Genetic algorithm (GA) and hybrid genetic algorithm (HEA) also known as hybrid evolutionary algorithm fall under evolutionary heuristics. On this concern this paper proposes two evolutionary algorithms namely, GA and HEA to evolve best sequence for makespan/total flow time criterion for m-machine flow shop involved with lot streaming and set-up time. The following two algorithms are used to evaluate the performance of the proposed GA and HEA: (i) Baker's algorithm (BA), an optimal solution procedure for two-machine flow shop problem with lot streaming and makespan objective criterion and (ii) simulated annealing algorithm (SA) for m-machine flow shop problem with lot streaming and makespan and total flow time criteria.     

Solving the flow shop problem by parallel programming

The matter of using scheduling algorithms in parallel computing environments is discussed in this paper. There are proposed methods of parallelizing the criterion function calculations for a single solution and a group of concentrated solutions (local neighborhood) dedicated to being used in metaheuristic approaches. Also a parallel scatter-search metaheuristic is proposed as a multiple-thread approach. Computational experiments are done for the flow shop, the classic NP-hard problem of the combinatorial optimization.     

Scheduling jobs with ready times and precedence constraints on parallel batch machines using metaheuristics

In this paper, we discuss a scheduling problem for parallel batch machines where the jobs have ready times. Problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). In addition, we consider precedence constraints among the jobs. Such constraints arise, for example, in scheduling subproblems of the shifting bottleneck heuristic when complex job shop scheduling problems are tackled. We use the total weighted tardiness as the performance measure to be optimized. Hence, the problem is NP-hard and we have to rely on heuristic solution approaches. We consider a variable neighborhood search (VNS) scheme and a greedy randomized adaptive search procedure (GRASP) to compute efficient solutions. We assess the performance of the two metaheuristics based on a large set of randomly generated problem instances and based on instances from the literature. The obtained computational results demonstrate that VNS is a very fast heuristic that quickly leads to high-quality solutions, whereas the GRASP is slightly outperformed by the VNS approach. However, the GRASP approach has the advantage that it can be parallelized in a more natural manner compared to VNS.     

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.     

Genetic algorithms applied to the continuous flow shop problem

This research develops an approach for applying Genetic Algorithms (GA) to scheduling problems. We generate a GA based heuristic for continuous flow shop problems with total flow time as the criterion. The effects of several crucial factors of GA on the performance of the heuristic for the problem are explored in detail. The computational experience of heuristic provides several observations of the application of GA, and strongly supports that the applications of GA are problem specific. The computational experience also shows that GA can be good techniques for scheduling problems.     

A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system

Effective task scheduling, which is essential for achieving high performance in a heterogeneous multiprocessor system, remains a challenging problem despite extensive studies. In this article, a heuristic-based hybrid genetic-variable neighborhood search algorithm is proposed for the minimization of makespan in the heterogeneous multiprocessor scheduling problem. The proposed algorithm distinguishes itself from many existing genetic algorithm (GA) approaches in three aspects. First, it incorporates GA with the variable neighborhood search (VNS) algorithm, a local search metaheuristic, to exploit the intrinsic structure of the solutions for guiding the exploration process of GA. Second, two novel neighborhood structures are proposed, in which problem-specific knowledge concerned with load balancing and communication reduction is utilized respectively, to improve both the search quality and efficiency of VNS. Third, the proposed algorithm restricts the use of GA to evolve the task-processor mapping solutions, while taking advantage of an upward-ranking heuristic mostly used by traditional list scheduling approaches to determine the task sequence assignment in each processor. Empirical results on benchmark task graphs of several well-known parallel applications, which have been validated by the use of non-parametric statistical tests, show that the proposed algorithm significantly outperforms several related algorithms in terms of the schedule quality. Further experiments are carried out to reveal that the proposed algorithm is able to maintain high performance within a wide range of parameter settings.     

Neural network and genetic algorithm-based hybrid approach to expanded job-shop scheduling

The expanded job-shop scheduling problem (EJSSP) is a practical production scheduling problem with processing constraints that are more restrictive and a scheduling objective that is more general than those of the standard job-shop scheduling problem (JSSP). A hybrid approach involving neural networks and genetic algorithm (GA) is presented to solve the problem in this paper. The GA is used for optimization of sequence and a neural network (NN) is used for optimization of operation start times with a fixed sequence.

After detailed analysis of an expanded job shop, new types of neurons are defined to construct a constraint neural network (CNN). The neurons can represent processing restrictions and resolve constraint conflicts. CNN with a gradient search algorithm, gradient CNN in short, is applied to the optimization of operation start times with a fixed processing sequence. It is shown that CNN is a general framework representing scheduling problems and gradient CNN can work in parallel for optimization of operation start times of the expanded job shop.

Combining gradient CNN with a GA for sequence optimization, a hybrid approach is put forward. The approach has been tested by a large number of simulation cases and practical applications. It has been shown that the hybrid approach is powerful for complex EJSSP.     

A HYBRID METAHEURISTIC FOR THE SINGLE-MACHINE TOTAL WEIGHTED TARDINESS PROBLEM

This article presents a new hybrid algorithm for combinatorial optimization that combines differential evolution (DE) with variable neighborhood search (VNS). DE (a population heuristic for optimization over continuous search spaces) is used as global optimizer for solution evolution guiding the search toward the optimal regions of the search space; VNS (a random local search heuristic based on the systematic change of neighborhood) is used as a local optimizer performing a sequence of local changes on individual DE solutions until a local optimum is found. The effectiveness of a DE-VNS approach is demonstrated on the solution of the single-machine total weighted tardiness scheduling problem. The concepts of Lamarckian and Baldwinian learning are also investigated and discussed. Experiments on known benchmark data sets show that DE-VNS with Lamarckian learning can produce high-quality schedules in a rather short computation time. DE-VNS uses a self-adapted mechanism for tuning the required control parameters, a critical feature rendering it applicable to real-life scheduling problems.     

A new evolutionary clustering search for a no-wait flow shop problem with set-up times

This paper addresses the m-machine no-wait flow shop problem where the set-up time of a job is separated from its processing time. The performance measure considered is the total flowtime. A new hybrid metaheuristic Genetic Algorithm–Cluster Search is proposed to solve the scheduling problem. The performance of the proposed method is evaluated and the results are compared with the best method reported in the literature. Experimental tests show superiority of the new method for the test problems set, regarding the solution quality.     

Variable neighborhood search for two-agent flow shop scheduling problem

Multi-agent scheduling in flow shop environment is seldom considered. In this paper flow shop scheduling problem with two agents is studied and its feasibility model is considered, in which the goal is to minimize the makespan of the first agent and the total tardiness of the second agent simultaneously under the given upper bounds. A simple variable neighborhood search (VNS) algorithm is proposed, in which a learning neighborhood structure is constructed to produce new solutions and a new principle is applied to decide if the current solution can be replaced with the new one. VNS is tested on a number of instances and the computational results show the promising advantage of VNS when compared to other algorithms of the problem.     

一种多目标置换流水车间调度问题的优化算法

针对最大完工时间最小和总流经时间最小的多目标置换流水车间调度问题(permutation flow shopscheduling problem, PFSP), 提出一种粒子群优化算法与变邻域搜索算法结合的混合粒子群优化(hybrid particleswarm optimization algorithm, HPSO)算法, 并使算法在集中搜索和分散搜索之间达到合理的平衡. 在该混合算法中,采用NEH 启发式算法进行种群初始化, 以提高初始解质量;运用随机键表示法设计基于升序排列规则(ranked-order-value, ROV), 将连续PSO 算法应用于置换流水车间调度问题;引入外部档案集存贮Pareto 解, 并采用强支配关系和聚集距离相结合的混合策略保证解集的分布性;采用Sigma 法和基于聚集距离的轮盘赌法进行全局最优解的选择;提出变邻域搜索算法, 对外部集中的Pareto 解作进一步地局部搜索. 最后, 运用提出的混合算法求解Taillard 基准测试集, 并将测试结果与SPEA2 算法进行比较, 验证该调度算法的有效性.     

Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence-dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on-time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches.