Xpress-MP在生产运作与调度中的研究与应用(5)
（2）流水车间调度问题（Flow Shop Scheduling Problem,FSSP）
流水车间调度问题，也称为同序作业调度问题，是许多实际流水线生产调度问题的简化模型。流水车间调度问题一般可以描述为n个工件要在m 台机器上加工．每个工件需要经过m道工序，每道工序要求不同的机器。n个工件在m 台机器上的加工顺序相同。工件i在机器j上的加工时间是给定的，设为t(I．j)。问题的目标是求n个工件在每台机器上最优的加工顺序，使最大流程时间达到最小。对该问题常常作如下假设。
(1)每个工件在机器上的加工顺序是1，2．⋯ ，m；
(2)每台机器同时只能加工一个工件；
(3)一个工件不能同时在不同的机器上加工；
(4)工序不能预定：
(5)工序的准备时间与顺序无关，且包含在加工时间中；
(6)工件在每台机器上的加工顺序相同，且是确定的。
流程性加工业的车间调度问题是典型的流水车间调度例子。不同的产品，尽管材料规格不同，但加工工序是相同的。这实际上是作业车间调度问题的一个特例：统一了工件加工路线的作业车间调度问题。
（3）开放式车间调度问题（Open Shop Scheduling Problem,OSSP）
开放式车间调度问题是典型的NP难题，相对于作业车间调度问题，该问题具有更广阔的搜索空间。问题一般描述如下:n个工件在m台机器上加工，每个工件包含m道工序，每道工序均有确定的加工时间。在给定的时间内每台机器只能加工一个工件，且每个工件只能由一台机器处理。同一台机器上工件的加工顺序任意，每个工件的工序处理顺序也无限制。在加工过程中工序不允许中断。调度的目的是在满足上述约束的同时，确定所有工件和机器的顺序组合，以达到一定的性能指标。
由于没有加工技术路线的约束，可行的调度方案种类大大增加，在大规模的调度方案中寻找最优解也同样不是一件简单的事情。
在实际的生产调度问题中往往存在着混合型的车间调度问题，即以上三种调度问题的混合。
上面介绍的集中车间调度问题都很难通过简单的数学运算或调度经验获得最优解，这就从一个侧面反映了车间调度问题的高度复杂性。当今车间生产运作规模越来越大，导致车间调度问题的规模也越来越大，计算机技术和信息化的发展为管理者提供了解决这些问题的工具，合理运用调度软件解决这些问题势在必行。
2．2 车间生产运作与调度问题的特点
(1)复杂性：车间中的制造过程是一个复杂的系统工程，调度问题是一个复杂的NP难问题，包括建模的复杂性和计算的复杂性。用系统的观点来看，既要考虑系统整体目标的实现，又要注意针对子系统的具体特性及其具有的局部目标的实现，加以协调和平衡，才能实现整个系统的最优调度。任何一个看似简单的车间调度问题实际上都是若干等式和不等式约束的组合优化问题。这是车间调度问题最显著的一个特点，也是我们需要引进Xpress-MP软件解决调度问题的原因。
(2)多约束：在研究调度问题时，不仅要考虑机器约束和加工过程的时间约束，同时好要考虑其他约束如员工设备的工作能力等,约束条件的复杂性是导致生产运作与调度问题复杂性的主要原因。
(3)多目标：调度的目标多种多样，在实际的调度中需要综合考虑各种目标。一次调度往往具有多个目标，如加工时间最短、利润最大、生产成本最低等，而且这多个目标之间有时互相冲突，需要对不同目标加以协调；再次调度时，目标可能变化，因此，需要动态调整目标。这种多目标性导致生产运作与调度的复杂性和计算量急剧增加。