基于群智能优化算法的流水车间调度问题若干研究

发布时间：2018-04-29 14:19

本文选题：生产调度 + 流水车间　；参考：《华东理工大学》2014年博士论文

【摘要】：生产调度问题存在于大量实际制造业与服务业中,如石化业、烟草业、纺织业、造纸业、制药业以及食品业等,并在其中发挥着非常重要的作用。简单来说,生产调度问题就是如何在给定的时间约束内合理地安排分配有限的资源,使得一个或多个目标达到最优。从本质上来说它是一个决策过程。同时,生产调度问题也是一类非常典型的组合优化问题,当中很多类型的子问题都是NP-hard问题。使用传统的方法进行求解很难得到令人满意的结果,特别是对一些极为复杂的问题,甚至根本得不到有效的解。因此,无论在实际工业生产方面,还是在理论学术研究方面,对生产调度问题的研究都有着非常重要的意义。本文深入研究了四种典型的流水车间调度问题：带阻塞流水车间调度问题、中间存储有限流水车间调度问题、混合流水车间调度问题和机器故障情况下混合流水车间调度问题,建立了相应的数学模型,提出了几种群智能优化算法并成功应用到这些问题中。本文的主要研究成果如下： (1)针对带阻塞流水车间调度问题(Blocking Flowshop Scheduling Problem, BFSP),提出了一种离散群搜索优化算法(Discrete Group Search Optimizer, DGSO)用来最小化它的总流水时间。在DGSO算法中,种群初始化阶段使用了随机初始化与两种启发式算法(NEH和NEH-WPT)相结合的方法,保证了初始种群既具有一定的质量,又兼备多样性；接着将基于插入操作的邻域搜索、离散差分进化策略以及破坏重建过程嵌入到算法中,提高了算法的性能；最后使用了一种正交实验设计的方法选取了合适的算法参数值。基于标准算例的大量仿真测试结果表明,提出的DGSO算法具有明显的可行性和有效性。 (2)针对中间存储有限流水车间调度问题(Flowshop Scheduling Problem with Limited Buffers, LBFSP),提出了一种混合离散和声搜索算法(Hybrid Discrete Harmony Search, HDHS)对其进行求解。此算法基于工件排列的编码方式,设计了一种构造离散和声的新方法以及离散差分进化策略；同时将此离散和声搜索策略与基于插入操作的局部搜索操作相结合,很好地平衡了算法的全局搜索能力与局部搜索能力;并使用正交实验的方法确定HDHS算法的参数值。基于Taillard标准算例的仿真实验表明提出的HDHS算法具有明显的优越性。 (3)针对混合流水车间调度问题(Hybrid Flowshop Scheduling, HFS),使用向量表述的方式进行数学建模,并提出了一种改进离散人工蜂群算法(Improved Discrete Artificial Bee Colony, IDABC)来最小化其最大完工时间makespan。IDABC算法在引领蜂和跟随蜂阶段分别使用了一种全新设计的差分进化策略和改进变邻域搜索策略,实现了个体的更新；在侦察蜂阶段使用破坏重建操作提高了算法的全局搜索能力。此外也使用了正交设计的方法,仅仅通过少量次数的实验就获得了很好的算法参数值。大量的仿真实验表明,在求解相同的标准算例时,提出的IDABC算法的求解效果明显优于参与比较的当前其他几种高性能算法。 (4)在以往对生产调度问题的研究中,常常假设所有的机器一直可用,不会出现故障。然而在实际生产中,加工机器由于各种原因不可避免地会发生故障。针对机器发生故障情况下的混合流水车间调度问题(Hybrid Flowshop Scheduling with Random Breakdown, RBHFS),分析了机器发生故障后的两种加工情况：preempt-resume情况和preempt-repeat'隋况,并提出了一种改进离散群搜索优化算法(Improved Discrete Group Search Optimizer, IDGSO)来求解。IDGSO算法采用向量表述方式来描述问题,并使用一些离散操作进行迭代进化,包括分布在发现者、追随者和游荡者阶段中的插入操作、交换操作、差分进化操作以及破坏重建操作等。仿真计算结果表明,在preempt-resume和preempt-repeat两种情况下,提出的IDGSO算法比其他高性能算法具有更好的效果。
[Abstract]:Production scheduling problems exist in a large number of actual manufacturing and service industries, such as petrochemical industry, tobacco industry, textile industry, paper industry, pharmaceutical industry and food industry, and play a very important role in it. In simple terms, the problem of scheduling is how to allocate limited resources in a given time constraint, so that a Or multiple objectives are optimal. In essence, it is a decision-making process. At the same time, production scheduling problem is also a kind of very typical combinatorial optimization problem. Many of the types of sub problems are NP-hard problems. It is difficult to obtain satisfactory results by using traditional methods, especially for some extremely complex problems, The research on production scheduling problem is very important in both practical industrial production and theoretical academic research. Four typical flow shop scheduling problems are studied in this paper: the problem of traffic shop scheduling with blocking and the limited flow shop in the middle of this paper. Scheduling problem, mixed flow shop scheduling problem and hybrid flow shop scheduling problem under machine fault conditions, a corresponding mathematical model is established, and several swarm intelligence optimization algorithms are proposed and applied to these problems successfully. The main research results of this paper are as follows:
(1) a discrete group search optimization algorithm (Discrete Group Search Optimizer, DGSO) is proposed to minimize its total flow time for the Blocking Flowshop Scheduling Problem (BFSP). In the DGSO algorithm, the initialization phase of the population uses random initialization and two heuristic algorithms (NEH and heuristics). EH-WPT) the combination method ensures the quality and diversity of the initial population. Then, the neighborhood search, the discrete differential evolution strategy and the failure reconstruction process are embedded into the algorithm to improve the performance of the algorithm. Finally, an orthogonal experimental design method is used to select the appropriate calculation. A large number of simulation tests based on standard examples show that the proposed DGSO algorithm is feasible and effective.
(2) a new hybrid discrete harmonic search algorithm (Hybrid Discrete Harmony Search, HDHS) is proposed to solve the problem of Flowshop Scheduling Problem with Limited Buffers (LBFSP) in the middle storage. A new method for constructing discrete harmony is designed based on the coding method of the work-piece scheduling. As well as the discrete differential evolution strategy, combining the discrete harmony search strategy with the local search operation based on the insertion operation, the global search capability and the local search ability of the algorithm are well balanced. The parameter values of the HDHS algorithm are determined by the orthogonal experiment. The simulation experiments based on the Taillard standard example show that the algorithm is proposed. The HDHS algorithm has obvious superiority.
(3) for the mixed flow shop scheduling problem (Hybrid Flowshop Scheduling, HFS), a mathematical model is used by vector expression, and an improved discrete artificial bee colony algorithm (Improved Discrete Artificial Bee Colony, IDABC) is proposed to minimize the maximum completion time makespan.IDABC algorithm in the leading and following wasps stage. A new design of differential evolution strategy and an improved variable neighborhood search strategy are used respectively to update the individual and improve the global search ability of the algorithm in the reconnaissance bee stage. In addition, the orthogonal design method is used to obtain good algorithm parameters by only a small number of experiments. A large number of simulation experiments show that the proposed IDABC algorithm is better than the other high performance algorithms that participate in the comparison when solving the same standard example.
(4) in the previous research on production scheduling problems, it is often assumed that all machines are always available and will not fail. However, in actual production, processing machines will inevitably fail for a variety of reasons. Hybrid Flowshop Scheduling with Random Br Eakdown, RBHFS), analysis of the two processing conditions after the failure of the machine: the preempt-resume situation and the preempt-repeat'Sui state, and proposed an improved discrete group search optimization algorithm (Improved Discrete Group Search Optimizer, IDGSO) to solve the.IDGSO algorithm using vector expression to describe the problem, and use some discrete. The operation is iterative evolution, including the insertion operation in the discoverer, the followers and the wanderer stage, the switching operation, the differential evolution operation and the destruction reconstruction operation. The simulation results show that the proposed IDGSO algorithm has better effect than the other high performance algorithms in the two cases of preempt-resume and preempt-repeat.

【学位授予单位】：华东理工大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TB497;TP18

【参考文献】