代表机器空闲状态   代表工件1的加工状态 代表工件2的加工状态

  代表工件3的加工状态 代表工件4的加工状态 代表阻塞状态

图2-1 测试数据甘特图

如图2-1所示，灰色区域代表阻塞状态，机器m1在2至4的区域内属于阻塞情况。出现的原因主要是因为此时工件1正在机器m2上加工，因此即使工件2完成了第一部分的加工，他还需要停留在机器m1上，这样就导致了该机器的堵塞。而白色区域表示此时机器上没有可加工工件，如机器m3的5至6区域由于此时工件1已完成，同时机器m2上的工件2还未加工完成，因此m3只能处于空闲状态。

阻塞流水车间问题的研究目标可以分为最小化最大完工时间和总流水时间。针对这两种不同的目标可以提出不同的方案。本文所针对的是最小化最大完工时间，即最后一个工件离开最后一台机器的时间。文献综述

本文多级提到该类问题属于NP类问题，而NP是指非确定性多项式（non-deterministic polynomial，缩写NP）。所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可解决的问题。NP 问题通俗来说是其解的正确性能够被“很容易检查”的问题，这里“很容易检查”指的是存在一个多项式检查算法。NP完全问题（NP-Complet或NPC）和NP难题（NP-Hard或NPH）：问题中不能找出一个有效算法，该问题不能用精确算法求解，必须寻求该问题的有效近似算法。

2。3 车间调度问题的研究现状与方法

车间调度问题是一个比较传统的问题，最早的研究可以追溯到上个世纪50年代。由于我们一直车间调度问题属于NP类问题，所以我们无法求出一个最优解，因此我们都致力于有效和快速的求出一个较优解。

本文所提到的群体智能算法在该问题上的应用已经有许多学者在该方面做出努力。例如，又提出解决该问题的离散粒子群优化算法，有基于候鸟优化算法的流水车间调度问题[[[4]谢展鹏，贾艳。 基于候鸟优化算法的阻塞流水车间调度问题[J]。华中科技大学，计算机集成制造系统,2015,21(8):2099-2107。]]，还有基于新型的人工蜂群算法[[[5]王慧颖,刘建军,王全洲。 改进的人工蜂群算法在函数优化问题中的应用[J]。 计算机工程与应用,2012,19:36-39。]]的研究。上面所提到说该问题是NP难问题，因此任何算法在该问题上都存在理论解，因此本文选取人工蜂群算法作为研究该问题的突破口。

一般车间调度问题都是针对具体情况下的动态问题的一种简化过程。因此，对这个过程我们可以提供许多不同的方法。起初，我们集中在整数规划和一些简单的规则方面，但是这些方法很显然没能达到我们想要的效果。随着科技的发展和一些新兴技术的提出，许多新的优化方法在车间调度问题上也能够适用。比如：模拟退火算法，遗传算法等等。

（1）基于启发式规则的调度方法：调度规则因为其易于实现，计算简易等优点，

因此一直活跃在许多学者的研究范围中。学者研究可以将他们分为三类：复合规则，简单规则以及启发式规则。我们可以利用一些有效的操作来提高机器的平均利用率，总的加工时间，或者总流程时间等。来.自^优+尔-论,文:网www.youerw.com +QQ752018766-

（2）仿真调度方法：由于该问题的复杂性，我们很难在实践中验证某个方法的正确性，因此我们可以利用仿真模型来收集数据，这样就能对实际系统进行各方面的分析，从而采取适当措施提高效率。之前有学者研究一种基于纯仿真模型的调度方法。即完全利用仿真模型来仿真一个规则集，以适应系统状态的变化。虽然基于纯仿真可以包含我们在现实生活中无法描述的因素，同时实验者也可以对其进行性能测试，但是它的缺点也很明显。比如因为它是纯仿真，因此缺乏实际意义，同时它的准确性也欠缺验证。