西北工业大学明德学院本科毕业设计论文
同的速度，称之为同速机(identical processors );如果处理机的速度不同，但每个处理机的速度都是常数，不依赖被加工的任务，称它们为恒速机(uniform processors);如果处理机的速度依赖被加工的任务，它们被称为变速机(unrelated processors)。
多处理机的另一种情况是多类型机(dedicated processors)。多类型机指的是m个处理机具有不同的功能。在多处理机环境中，被加工的任务需要在不同的处理机上加工.在这种情况下，把任务(task )称为作业(job)。设有作业集 J={,,?,}
每个作业,有，道工序(operation) ，，?，}.工序指的是作业在某处理机上被加工的这部分任务。
如果每个作业需要在每个处理机上加工，即=m ,j二1，2，?，n.而且每个作业的工序也相同，即在处理机上加工的顺序相同，把这种多类机的环境称为同顺序作业或流水作业(flow shop)。
如果每个作业需要在每个处理机上加工，每个作业有自己的加工顺序，称之为异顺序作业(job shop)。
如果每个作业需要在每个处理机上加工，每个作业可按任意顺序加工，把它称为自由顺序作业或开放作业(open shop ) 。
在多处理机中，还有一种更复杂的情况，这就是柔性流水作业(flexible flow shop)，它是流水作业和平行机的推广。在柔性流水作业中，有，类处理机，第J类有个平行机，每个作业有s道工序，每道工序需要在每类平行机中的一个处理机上加工，且每个作业的加工顺序相同。
为方便起见，以后我们把同顺序作业、异顺序作业、开放作业、柔性流水作 业通称为车间作业。
处理机的各种类型和环境总结如下:
·· 单处理机
同速机 同类机（平行机） 恒速机
· 自由顺序作业（开放作业）
柔性流水作业
8
西北工业大学明德学院本科毕业设计论文
任务和作业排序问题中的约束条件，主要指的是任务或作业的性质以及它们在加工过程中的要求和限制。下边的数据描述了任务的一些性质 (1)加工时间向量 任务的加工时间向量是
=(,,?,)
其中是任务 在处理机，上所需要的加工时间，对同速机有=，i=1,2，?，m，对恒速机有,= /，i=1,2，?,m。其中 是标准的加工时间(一般是速度最慢的处理机的加工时间)，是处理机的速度因子，在车间作业的排序问题中，作业的加工时间向量是
=(,,?,)
其中,是工序。在对应的处理机上的加工时间。 (2)到达时间
到达时间( arrival time)或准备时间(ready time) 是任务已经准备好可以被加工的时间如果所有的任务的准备时间相同，取=0 ;j=1,2, ?,n。
(3)工期和截止期限
工期(due date)表示对任务限定的完工时间.如果不按期完工，应受到一定的惩罚。绝对不准许延误的工期称为截止期限(deadline) 。
(4)优先因子
优先因子玛是一个权，它表示任务相对于其他任务的重要程度.为了叙述方便起见，我们假设以上参数，，和都是整数.实际上这等价于它们可以是任意的有理数。
我们经常用向量和矩阵的列给出这些数据。例如用
r=(,,?,) d=(,,?,) w=(,,?,)
分别表示n个任务的到达时间、工期和优先因子。用
的第i行(,, ?,)表示n个任务在第i个处理机上的加工时间。
9
相关推荐：
loading