【作者】 崔喆；

【导师】 顾幸生；

【作者基本信息】 华东理工大学 ， 控制科学与工程， 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 problem is a decision-making process that plays a crucial role in manufacturing and service industries and widely exists in practical environments, such as chemical, oil, tobacco, textile, paper, pharmaceutical and food industries. It concerns how to allocate available production resources to tasks over given time periods, aiming at optimizing one or more objectives. At the same time, this problem is categorized as a very typical combinatorial optimization problem, and many kinds of subproblems are NP-hard. When we solve these subproblems, the traditional methods are difficult to obtain satisfactory results, especially for some complex problems, it can not even get feasible solutions. Therefore, the production scheduling problem has great significance in both engineering and theoretical fields, and it is meaningful to develop effective and efficient approaches for this problem. This dissertation analyses four typical flow shop scheduling problems:the blocking flow shop scheduling problem, the flow shop scheduling problem with limited buffers, the hybrid flowshop scheduling problem, and the hybrid flowshop scheduling problem with random breakdown, establishes the corresponding models, and proposes some swarm intelligence optimization algorithms for solving these problems. The main content of this dissertation can be summarized as follows:(1) For the blocking flow shop scheduling problem (BFSP), a discrete group search optimizer (DGSO) algorithm is proposed to minimize the total flow time. In the proposed DGSO algorithm, an efficient population initialization based on the NEH heuristic and NEH-WPT heuristic is incorporated into the random initialization to generate an initial population with certain quality and diversity; moreover, the insert neighborhood search, the discrete differential evolution scheme and the destruction and construction procedures are hybridized to improve the algorithm performance; in addition, an orthogonal experiment design is employed to provide a receipt for turning the adjustable parameters of the DGSO algorithm. The simulation results on benchmarks demonstrate the effectiveness and efficiency of the proposed DGSO algorithm.(2) A hybrid discrete harmony search (HDHS) algorithm is proposed for the flow shop scheduling problem with limited buffers (LBFSP). The HDHS algorithm presents a novel discrete improvisation and a differential evolution scheme with the job-permutation-based representation. Moreover, the discrete harmony search is hybridized with the problem-dependent local search based on insert neighborhood to balance the global exploration and local exploitation. In addition, an orthogonal test is applied to configure the adjustable parameters in the HDHS algorithm. Comparisons based on the Taillard benchmark instances indicate the superiority of the proposed HDHS algorithm in terms of effectiveness and efficiency.(3) The hybrid flowshop scheduling (HFS) problem is modeled by vector representation, and then an improved discrete artificial bee colony (IDABC) algorithm is proposed for this problem to minimize the makespan. The proposed IDABC algorithm combines a novel differential evolution and a modified variable neighborhood search to generate new solutions for the employed and onlooker bees, and the destruction and construction procedures are used to enhance the ability of global search for the scout bees. Moreover, an orthogonal test is applied to efficiently configure the system parameters, after a small number of training trials. The simulation results demonstrate that the proposed IDABC algorithm is effective and efficient comparing with several state-of-the-art algorithms on the same benchmark instances.(4) The production scheduling problems have been discussed in the literature extensively under the assumption that the machines are permanently available without any breakdown. However, in the real manufacturing environments, the machines could be unavailable inevitably for many reasons. Here the authors introduce the hybrid flowshop scheduling problem with random breakdown (RBHFS) together with an improved discrete group search optimizer algorithm (IDGSO). In particular, two different working cases:preempt-resume case and preempt-repeat case are considered under random breakdown. The proposed IDGSO algorithm adopts the vector representation and several discrete operators, such as insert, swap, differential evolution, destruction and construction in the producers, scroungers, and rangers phases. The computational results in both cases indicate that the proposed algorithm significantly improves the performances compared with other high performing algorithms in the literature.更多还原