Modeling realistic hybrid flexible flowshop scheduling problems

This paper aims to contribute to the recent research efforts to bridge the gap between the theory and the practice of scheduling by modelizing a realistic manufacturing environment and analyzing the effect of the inclusion of several characteristics in the problem formulation. There are several constraints and characteristics that affect the scheduling operations at companies. While these constraints are many times tackled in the literature, they are seldom considered together inside the same problem formulation. We propose a formulation along with a mixed integer modelization and some heuristics for the problem of scheduling n jobs on m stages where at each stage we have a known number of unrelated machines. The jobs might skip stages and, therefore, we have what we call a hybrid flexible flowshop problem. We also consider per machine sequence-dependent setup times which can be anticipatory and non-anticipatory along with machine lags, release dates for machines, machine eligibility and precedence relationships among jobs. Manufacturing environments like this appear in sectors like food processing, ceramic tile manufacturing and several others. The optimization criterion considered is the minimization of the makespan. The MIP model and the heuristics proposed are tested against a comprehensive benchmark and the results evaluated by advanced statistical tools that make use of decision trees and experimental designs. The results allow us to identify the constraints that increase the difficulty.     

A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems

This paper addresses the flexible job shop scheduling problem (fJSP) with three objectives: min makespan, min maximal machine workload and min total workload. We developed a hybrid genetic algorithm (GA) for the problem. The GA uses two vectors to represent solutions. Advanced crossover and mutation operators are used to adapt to the special chromosome structure and the characteristics of the problem. In order to strengthen the search ability, individuals of GA are first improved by a variable neighborhood descent (VND), which involves two local search procedures: local search of moving one operation and local search of moving two operations. Moving an operation is to delete the operation, find an assignable time interval for it, and allocate it in the assignable interval. We developed an efficient method to find assignable time intervals for the deleted operations based on the concept of earliest and latest event time. The local optima of moving one operation are further improved by moving two operations simultaneously. An extensive computational study on 181 benchmark problems shows the performance of our approach.     

A hybrid genetic algorithm for no-wait job shop scheduling problems

A no-wait job shop (NWJS) describes a situation where every job has its own processing sequence with the constraint that no waiting time is allowed between operations within any job. A NWJS problem with the objective of minimizing total completion time is a NP-hard problem and this paper proposes a hybrid genetic algorithm (HGA) to solve this complex problem. A genetic operation is defined by cutting out a section of genes from a chromosome and treated as a subproblem. This subproblem is then transformed into an asymmetric traveling salesman problem (ATSP) and solved with a heuristic algorithm. Subsequently, this section with new sequence is put back to replace the original section of chromosome. The incorporation of this problem-specific genetic operator is responsible for the hybrid adjective. By doing so, the course of the search of the proposed genetic algorithm is set to more profitable regions in the solution space. The experimental results show that this hybrid genetic algorithm can accelerate the convergence and improve solution quality as well.     

A hybrid genetic algorithm for the job shop scheduling problems

The Job Shop Scheduling Problem (JSSP) is one of the most general and difficult of all traditional scheduling problems. The goal of this research is to develop an efficient scheduling method based on genetic algorithm to address JSSP. We design a scheduling method based on Single Genetic Algorithm (SGA) and Parallel Genetic Algorithm (PGA). In the scheduling method, the representation, which encodes the job number, is made to be always feasible, the initial population is generated through integrating representation and G&T algorithm, the new genetic operators and selection method are designed to better transmit the temporal relationships in the chromosome, and island model PGA are proposed. The scheduling methods based on genetic algorithm are tested on five standard benchmark JSSP. The results are compared with other proposed approaches. Compared to traditional genetic algorithm, the proposed approach yields significant improvement in solution quality. The superior results indicate the successful incorporation of a method to generate initial population into the genetic operators.     

A hybrid quantum-inspired genetic algorithm for multiobjective flow shop scheduling.

This paper proposes a hybrid quantum-inspired genetic algorithm (HQGA) for the multiobjective flow shop scheduling problem (FSSP), which is a typical NP-hard combinatorial optimization problem with strong engineering backgrounds. On the one hand, a quantum-inspired GA (QGA) based on Q-bit representation is applied for exploration in the discrete 0-1 hyperspace by using the updating operator of quantum gate and genetic operators of Q-bit. Moreover, random-key representation is used to convert the Q-bit representation to job permutation for evaluating the objective values of the schedule solution. On the other hand, permutation-based GA (PGA) is applied for both performing exploration in permutation-based scheduling space and stressing exploitation for good schedule solutions. To evaluate solutions in multiobjective sense, a randomly weighted linear-sum function is used in QGA, and a nondominated sorting technique including classification of Pareto fronts and fitness assignment is applied in PGA with regard to both proximity and diversity of solutions. To maintain the diversity of the population, two trimming techniques for population are proposed. The proposed HQGA is tested based on some multiobjective FSSPs. Simulation results and comparisons based on several performance metrics demonstrate the effectiveness of the proposed HQGA.     

最优子种群遗传算法求解柔性流水车间调度问题

为了验证最优子种群遗传算法在解决柔性流水车间调度问题时相比于传统遗传算法的优越性,分析了柔性流水车间调度问题的特点,并运用一种新的编码方法和新的遗传算法求解了该问题。考虑到最优个体保护策略法对复杂问题容易使种群收敛陷入局部最优解,为了提高精度、加快较优个体的产生并避免陷入局部最优解,首先提出了一种合理、全面的编码方法,并运用最优子种群遗传算法来求解柔性流水车间调度问题。最后运用实例验证了最优子种群遗传算法的有效性、优越性和编码方式的合理性。     

A memetic algorithm for the flexible flow line scheduling problem with processor blocking

This paper introduces an efficient memetic algorithm (MA) combined with a novel local search engine, namely, nested variable neighbourhood search (NVNS), to solve the flexible flow line scheduling problem with processor blocking (FFLB) and without intermediate buffers. A flexible flow line consists of several processing stages in series, with or without intermediate buffers, with each stage having one or more identical parallel processors. The line produces a number of different products, and each product must be processed by at most one processor in each stage. To obtain an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches and optimization tools is extremely difficult. Our proposed MA employs a new representation, operators, and local search method to solve the above-mentioned problem. The computational results obtained in experiments demonstrate the efficiency of the proposed MA, which is significantly superior to the classical genetic algorithm (CGA) under the same conditions when the population size is increased in the CGA.     

An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems

This paper proposes an effective hybrid tabu search algorithm (HTSA) to solve the flexible job-shop scheduling problem. Three minimization objectives – the maximum completion time (makespan), the total workload of machines and the workload of the critical machine are considered simultaneously. In this study, a tabu search (TS) algorithm with an effective neighborhood structure combining two adaptive rules is developed, which constructs improved local search in the machine assignment module. Then, a well-designed left-shift decoding function is defined to transform a solution to an active schedule. In addition, a variable neighborhood search (VNS) algorithm integrating three insert and swap neighborhood structures based on public critical block theory is presented to perform local search in the operation scheduling component. The proposed HTSA is tested on sets of the well-known benchmark instances. The statistical analysis of performance comparisons shows that the proposed HTSA is superior to four existing algorithms including the AL + CGA algorithm by Kacem, Hammadi, and Borne (2002b), the PSO + SA algorithm by Xia and Wu (2005), the PSO + TS algorithm by Zhang, Shao, Li, and Gao (2009), and the Xing’s algorithm by Xing, Chen, and Yang (2009a) in terms of both solution quality and efficiency.     

Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm

This paper deals with a scheduling problem for reentrant hybrid flowshop with serial stages where each stage consists of identical parallel machines. In a reentrant flowshop, a job may revisit any stage several times. Local-search based Pareto genetic algorithms with Minkowski distance-based crossover operator is proposed to approximate the Pareto optimal solutions for the minimization of makespan and total tardiness in a reentrant hybrid flowshop. The Pareto genetic algorithms are compared with existing multi-objective genetic algorithm, NSGA-II in terms of the convergence to optimal solution, the diversity of solution and the dominance of solution. Experimental results show that the proposed crossover operator and local search are effective and the proposed algorithm outperforms NSGA-II by statistical analysis.     

可重入混合流水车间调度的拉格朗日松弛算法

为了有效提升多重入车间的生产效率,考虑了实际生产中检查和修复过程对于逐层制造的可重入生产系统的重要性,提出了基于拉格朗日松弛算法的可重入混合流水车间的调度方法.首先进行了问题域的描述,并在此基础上以最小化加权完成时间为调度目标,建立数学规划模型.针对该调度问题提出了基于松弛机器能力约束的拉格朗日松弛算法,使松弛问题分解成工件级子问题,并使用动态规划方法建立递归公式,求解工件级子问题.随后,使用次梯度算法求解拉格朗日对偶问题.最后,对各种不同问题规模进行了仿真实验,结果表明,所提出的调度算法能够在合理的时间内获得满意的近优解.     

A modified genetic algorithm for distributed scheduling problems

Genetic algorithms (GAs) have been widely applied to the scheduling and sequencing problems due to its applicability to different domains and the capability in obtaining near-optimal results. Many investigated GAs are mainly concentrated on the traditional single factory or single job-shop scheduling problems. However, with the increasing popularity of distributed, or globalized production, the previously used GAs are required to be further explored in order to deal with the newly emerged distributed scheduling problems. In this paper, a modified GA is presented, which is capable of solving traditional scheduling problems as well as distributed scheduling problems. Various scheduling objectives can be achieved including minimizing makespan, cost and weighted multiple criteria. The proposed algorithm has been evaluated with satisfactory results through several classical scheduling benchmarks. Furthermore, the capability of the modified GA was also tested for handling the distributed scheduling problems.     

双种群混合遗传算法求解具有预防性维护的分布式柔性作业车间调度问题

在实际生产过程中,生产调度和设备维护相互影响,因此两者应该统筹优化.为研究具有预防性维护的分布式柔性作业车间调度问题,以最小化最大完工时间为目标,提出一种双种群混合遗传算法.结合问题特性,设计三维编码以及对应的机器解码方案,采用不同的策略初始化种群以均衡一部分工厂负载,为双种群设计不同的交叉变异算子提高算法的多样性,并利用交换精英解的方法实现两个种群的协作优化,同时针对关键工厂和预防性维护操作设计相应的局部搜索.最后对比现有算法,在同构和异构工厂的算例上进行实验,使用正交试验法优化算法参数设置.实验结果验证了局部搜索以及种群协作的有效性和双种群混合遗传算法求解具有预防性维护的分布式柔性作业车间调度问题的优越性.     

Embedding ant system in genetic algorithm for re-entrant hybrid flow shop scheduling problems with time window constraints

This paper focuses on minimizing the makespan for a reentrant hybrid flow shop scheduling problem with time window constraints (RHFSTW), which is often found in manufacturing systems producing the slider part of hard-disk drive products, in which production needs to be monitored to ensure high quality. For this reason, production time control is required from the starting-time-window stage to the ending-time-window stage. Because of the complexity of the RHFSTW problem, in this paper, genetic algorithm hybridized ant colony optimization (GACO) is proposed to be used as a support tool for scheduling. The results show that the GACO can solve problems optimally with reasonable computational effort.     

A genetic algorithm for integrating lot-sizing and sequencing in scheduling a capacitated flow line

In this paper we present a genetic algorithm for solving an important but difficult scheduling problem: that of integrating the lot-sizing and sequencing decisions in scheduling a flow line involving sequence dependent setup times, capacity constraints, limited buffer capacity between machines, and due dates. The problem is based on a real world manufacturing facility that is also described. Novel crossover and mutation operators are presented for both the lot-sizing and sequencing parts of the scheduling problem and the performance of the genetic algorithm is compared to a heuristic approach of integration previously shown to have been effective.     

An effective hybrid genetic algorithm for flow shop scheduling with limited buffers

As a typical manufacturing and scheduling problem with strong industrial background, flow shop scheduling with limited buffers has gained wide attention both in academic and engineering fields. With the objective to minimize the total completion time (or makespan), such an issue is very hard to solve effectively due to the NP-hardness and the constraint on the intermediate buffer. In this paper, an effective hybrid genetic algorithm (HGA) is proposed for permutation flow shop scheduling with limited buffers. In the HGA, not only multiple genetic operators based on evolutionary mechanism are used simultaneously in hybrid sense, but also a neighborhood structure based on graph model is employed to enhance the local search, so that the exploration and exploitation abilities can be well balanced. Moreover, a decision probability is used to control the utilization of genetic mutation operation and local search based on problem-specific information so as to prevent the premature convergence and concentrate computing effort on promising neighbor solutions. Simulation results and comparisons based on benchmarks demonstrate the effectiveness of the HGA. Meanwhile, the effects of buffer size and decision probability on optimization performances are discussed.     

柔性作业车间调度中的组合遗传优化研究

针对柔性作业车间调度问题,提出一种组合遗传算法。该算法在种群初始化、选择、交叉、变异各阶段,组合使用各种不同的策略。针对机器编码部分的交叉,提出一种基于工件的机器交叉算子,用以改进机器分配部分随机交叉引起的对父代优秀基因继承不足的缺陷。通过对典型算例的计算以及与其他文献的研究成果比较,证明该算法的优良性能。     

生物地理学算法求解柔性车间作业调度问题

针对加工设备和操作工人双资源约束的柔性作业车间调度问题,建立以生产时间和生产成本为目标函数的柔性作业车间调度模型,提出基于模糊Pareto支配的生物地理学算法,采用模糊Pareto支配的方法计算解之间的支配关系并对Pareto解集排序,进行全局最优值的更新,并采用余弦迁移模型来改善生物地理学算法的收敛速度。将该方法应用于某模具车间的柔性作业车间调度中,仿真结果验证了该方法的可行性和有效性。     

A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems

This paper proposes a genetic algorithm \(GA\_JS\) for solving distributed and flexible job-shop scheduling (DFJS) problems. A DFJS problem involves three scheduling decisions: (1) job-to-cell assignment, (2) operation-sequencing, and (3) operation-to-machine assignment. Therefore, solving a DFJS problem is essentially a 3-dimensional solution space search problem; each dimension represents a type of decision. The \(GA\_JS\) algorithm is developed by proposing a new and concise chromosome representation \({\varvec{S}}_{{\varvec{JOB}}}\), which models a 3-dimensional scheduling solution by a 1-dimensional scheme (i.e., a sequence of all jobs to be scheduled). That is, the chromosome space is 1-dimensional (1D) and the solution space is 3-dimensional (3D). In \(GA\_JS\), we develop a 1D-to-3D decoding method to convert a 1D chromosome into a 3D solution. In addition, given a 3D solution, we use a refinement method to improve the scheduling performance and subsequently use a 3D-to-1D encoding method to convert the refined 3D solution into a 1D chromosome. The 1D-to-3D decoding method is designed to obtain a “good” 3D solution which tends to be load-balanced. In contrast, the refinement and 3D-to-1D encoding methods of a 3D solution provides a novel way (rather than by genetic operators) to generate new chromosomes, which are herein called shadow chromosomes. Numerical experiments indicate that \(GA\_JS\) outperforms the IGA developed by De Giovanni and Pezzella (Eur J Oper Res 200:395–408, 2010), which is the up-to-date best-performing genetic algorithm in solving DFJS problems.