车间作业调度问题及多种目标函数分析

1.调度

调度（scheduling）就是为了实现某种目的而对共同使用的资源实行时间分配。例如，车间作业调度问题（JSSP，job shop scheduling problem）就是为处理多项作业而分配机器设备（共同资源）的工作顺序及时间，使总的作业时间最少。一般认为，这种JSSP是NP-完全问题中最困难的问题。即使是JSSP中比较简单的流动车间调度问题（FSSP，flow shop scheduling problem），也是与TSP问题的难度相当的同一类型的问题。

2.车间作业调度问题的描述

1）标准的车间作业调度问题

设在车间的m台设备上处理n项作业（n个不同的零件），各台设备处理不同作业的时间是预先给定的。如果每个作业均用到m台设备（即有m个操作，或m个工序），则可有（n！）m种不同的调度方式在实际工作中，通常还有一些约束条件。最一般的约束条件是：每台设备不能同时处理两项以上的作业，每项作业也不能同时在两台设备上被处理。另一个较普通的约束条件是：每项作业都规定一种技术顺序，即该项作业所需设备的使用顺序（不同操作的次序）。所以标准的车间作业调度（即流动车间调度）问题就是在满足任务配置和技术顺序两个约束条件下，为给定的作业求最佳的设备工作次序和时间分配，使完成全部作业所需的时间最少。

2）约束条件不同的车间作业调度问题

有时，有的作业不需要给定技术顺序，即该作业没有操作顺序的要求，可以在不同的设备上以不同的次序工作。这种车间就称为开放式车间，显然这种车间调度的灵活性要大于上述标准车间作业调度的灵活性。(www.xing528.com)

对设备、作业、操作的数量、时间、次序、优先级等有不同的要求便构成不同的约束条件，例如：不同作业使用的设备种类和数量不相等；各作业的数量不相等；有的设备上可以同时完成不同的作业和操作；允许作业中断或不允许作业中断；各作业的操作之间有优先级的要求；同种设备、作业和操作有不同数量；作业处理的时间全部相等或处理时间不限制，等等。

3）单资源、双资源及多资源调度问题

上述车间作业调度问题中，只规定使用机器设备一种资源，称为单资源调度问题。如果把操作工人也作为一种资源，那么就称为双资源调度问题。由于工人的技术熟练程度与工作能力的不同，不同工人操作设备的种类和数量也是不同的。这样，这种双资源的调度问题就更加复杂。两个以上资源的调度问题是多资源调度问题，目前处理这类复杂的调度问题还没有较好的数学方法。

4）不同目标函数的作业调度问题

通常用于作业调度问题的目标函数是总的作业时间。最佳化准则就是寻求总的作业时间最小的作业调度。还可以采用不同的目标函数作评定标准，例如，可以选择平均设备利用率，它是各设备利用率（设备工作时间/设备占用时间）的平均值。车间调度要求平均设备利用率最高。又如，在双资源问题中，选择平均工人生产率或作业总成本等作为目标函数。