（应用数学专业论文）若干单机在线排序问题研究.pdf

摘要 排序问题是一类重要的组合优化问题它是利用一些处理机、机器或资源 最优的完成一批给定的任务或作业经过近半个世纪的努力，排序理论已经发 展成一门相当重要的学科，并且应用非常广泛 在做决策之前，所有任务的信息都是已知的情况下做出的排序称为静态离 线最优排序在做决策的时间点上，只知道当前可排任务的信息而做出的最优 排序称为在线最优排序 本文选择单机排序问题为研究对象，并且研究单机排序问题的动态在线情 况首先建立了一般化中断模型，然后在此基础上研究了几类单机排序问题的 动态在线最优排序问题本文所做的工作如下： 首先，我们一般化了任务中断模型讨论了定义在更一般意义下的可中断 动态单机排序问题，即任务被中断后不能简单的恢复加工，而是需要有一定的 时间延迟，延迟是由任务的安装时间和任务在中断后恢复加工时其一部分( 或 全部) 需要返工的时间两部分共同造成的情况通过刻化上述条件，给出了两 种中断一安装重复模型一般化了任务可中断的概念同时我们研究并给出了并 行机排序问题最l 叩lc 。在中断一重复模型下的静态调度算法 其次，我们研究了总加权最小完工时间的在线调度问题用建立起来的两 个中断一安装重复模型来研究具有任意的和未知的任务到达时间的最小化总加 权完工时间问题，和最小化时间表长这两类单机动态排序问题，给出了只考虑 当前可用信息的在线调度规则 第三，我们研究了排序问题1 i o ，胛i w ( 1 一e 一叼) 的动态在线调度问 题考虑该问题在中断一重复和中断一安装重复模型下的动态在线排序问题， 西北工业大学硕士论文摘要 第四，我们研究了一般费用函数问题l f ，p r m p i 厶。的动态在线排序问 题考虑该问题在中断恢复和两种中断安装重复模型下的单机动态排序问题， 给出了在这几种模型下的只考虑当前可用信息的在线调度规则 第五，我们研究了具有前后相继约束关系的排序问题 l j ，p r e c ，p r m p i w j ( 1 - e 一) 的动态在线调度问题，同样给出了在中断一恢复 和两种中断安装重复模型下的只考虑当前可用信息的在线调度规则 最后，总结了本文的研究结果，展望了进一步研究动态在线排序问题的一 些方向 关键词：运筹学，排序，单机动态排序问题，在线最优排序，中断 a b s t r a c t s c h e d u l i n gi s o n ek i n do fi m p o r t a n tc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ， w h i c hu s es o m e p r o c e s s o r s ，m a c h i n e so rr e s o u r c e st oa c c o m p l i s ho p t i m a l l yab a t c h o fg i v e nt a s k so rj o b s t h et h e o r yo fs c h e d u l i n gh a sb e c o m eav e r yi m p o r t a n t s u b j e c ta f t e rh a l f ac e n t u r y jd e v e l o p m e n t ，a n di t sa p p l i c a t i o ni sv e r ye x t e n s i v e i na n o n - p r e e m p t i v e s t a t i c s c h e d u l i n gp r o b l e m ， a l lj o bp a r a m e t e r sa r e k n o w n s c h e d u l i n gd e c i s i o n s ，w h i c ho n l yt h ec h a r a c t e r i s t i c so f j o b sk n o w n t ob ei n t h es y s t e ma ta g i v e np o i n to r ec a l l e d0 7 l l i n eo p t i m a ls c h e d u l i n g s e e i n gt h ei m p o r t a n c eo f s i n g l em a c h i n es c h e d u l i n gp r o b l e m ，w et a k ei t a s o u ro b j e c ta n d s t u d yt h ed y n a m i cc o n d i t i o no f s i n g l em a c h i n ep r o b l e m s w e 秘s t g e n e r a l i z e t h ep r e e m p t i o nm o d e l sa n dt h e ns t u d ys o m es i n g l em a c h i n ed y n a m i c s c h e d u l i n g p r o b l e m s w ed o t h e f o l l o w i n g j o b s f i r s t l y ， w es t u d yp r o b l e m sw h e r ej o bp r e e m p t i o ni sa l l o w e du n d e rt h e g e n e r a l i z e d d e l a yc o n d i t i o n ，i e d e t 卿i s c a u s e d b y b o t hs e t u p t i m e a n d t i m eo f s o m e f r a c t i o no f w o r km u s tb er e p e a t e di f p r e e m p t i o no c c u r s w eg e n e r a l i z et h e n o t i o n o fj o bp r e e m p t i o nb yu s i n gt w ok i n d so fp r e e m p t - s e t u p - r e p e a tm o d e l s r e p r e s e n t i n g t h e s ec o n d i t i o n s t h i si st h e f u n d a m e n t a l f o ，l a t t e r s t u d y a c c o r d i n g t o t h e p r e e m p t - r e s u m em o d e l ，a s t a t i s t i ca l g o r i t h m f o r 只i p r m p c 。西g i v e n s e c o n d l y ， w eu s et h et w om o d e l sl o s t u 方t h ed y n a m i cs i n g l e m a c h i n e s c h e d u l i n gp r o b l e m so fm i n i m i z i n g t o t a l f l o w t i m ea n do fm i n i m i z i n gt o t a l t i m e t a b l e - l e n g t ha n dd e v e l o po n l i n eo p t i m a ld i s p a t c h i n gr u l e s ，w h i c hc o n s i d e r o n l ya v a i l a b l ei n f o r m a t i o n t h i r d l y ， w eu s et h et w om o d e l st o s t u d y t h e d y n a m i cs i n g l e m a c h i n e i i i s c h e d u l i n gp r o b l e m 1h p r m p l w j ( 1 一p ”7 ) a n dd e v e l o p o n l i n e o p t i m a l d i s p a t c h i n g r u l e s ，w h i c hc o n s i d e ro n l ya v a i l a b l ei n f o r m a t i o n f o u r t h l y ， w eu s et h et w om o d e l st o s t u d yt h ed y n a m i cs i n g l e - m a c h i n e s c h e d u l i n gp r o b l e m 1i - ，p r m p i 厂腑。a n dd e v e l o p o n l i n e o p t i m a ld i s p a t c h i n g r u l e s ，w h i c hc o n s i d e r o n l y a v a i l a b l e i n f o r m a t i o n ， f i f t h l y ，w e u s et h et w om o d e l st os t u d yt h ed y n a m i c s i n g l e m a c h i n es c h e d u l i n g p r o b l e m 1 fr j , c h a i n s ，p r m pi w j ( 1 - e 玛) a n dd e v e l o p o n l i n e o p t i m a l d i s p a t c h i n g r u l e s ，w h i c hc o n s i d e ro d ya v a i l a b l ei n f o r m a t i o n f i n a l 驴，a f t e rs u m m a r i z i n g t h ec o n t e n t si nt h et h e s i s ，w e p o i n to u tt h e f u r t h e r d i r e c t i o n st os t u d yt h e s i n g l em a c h i n ed y n a m i cs c h e d u l i n g p r o b l e m s k e y w o r d s ：o p e r a t i o n a lr e s e a r c h ，s c h e d u l i n g ，s i n g l e m a c h i n ed y n a m i c s c h e d u l i n g p r o b l e m s ，o n l i n eo p t i m a l s c h e d u l e ，p r e e m p t i o n i v 第一章绪论 1 1 引言 假如有几件事情放在眼前需要去做，人们便会比较轻重缓急排个工作顺序， 假如要从事一件较为复杂的工作，例如要建造一幢楼房，需要安排一些不同工 种的工人来做：有的挖地基，有的扎钢筋、注混凝土、砌砖、装修等等这就 需要给参与建筑的工人们安排一个顺序( 或时间表) 此等事物，何日无之，何 地无之过去处理此类问题，大多采用两种方式：一种是根据以往经验，必要 时做些修改；另种是事物并不复杂，做些考虑即可奏效，排序问题不成其为 门学问自从第二次世界大战后，各种大型企业逐渐兴起，规模庞大，结构 复杂，计算不周即可造成巨大损失依靠拍描脑袋已经不能解决问题：而且产 品更新很快，新产品的生产、销售等没有成法可资参考，此时各种新的组合优 化问题便涌现出来，排序问题便是其中之一 排序( s c h e d u l i n g ) i b 题产生的背景主要是机器弗9 造，后来被广泛应用于计算 机系统、运输调度、生产管理等领域从普通的生产部门的计划安排、人员调 度、学校课程表的制订，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的 理论和算法 经过近半个世纪的努力，排序的理论和应用已经发展成- - f l 相当重要的学 科一份题为美国国防部与数学科学研究的报告认为：2 0 世纪9 0 年代至 2 1 世纪数学发展的重点将从连续的对象转向离散的对象，并且组合最优化将有 很大的发展“因为在这个领域内存在着大量急需解决而又极端困难的问题其 中包括如何对各个部件进行分隔、布线和布局的问题”排序论是国际上发展最 迅速、研究最活跃、成果最丰富、前景最诱人的学科领域之一特别引人注目 的是：随着现代工业的发展，经典的排序模式已被突破，新的模式层出不穷， 吸引了越来越多的理论工作者和实际工作者在线排序、可控排序、多目标排 l 西北工业大学硕士论文第一章绪论 序、成组分批排序、同时加工顺序、窗时排序、资源受限排序、不同时开工排 序、随机排序、模糊排序、应用排序等，就是其中发展最为迅速的一些新方向 1 2 国内外排序问题研究概况 早在6 0 年代，中国科学院越民义先生就注意到排序问题的重要性和在理论 上的难度，他在1 9 6 6 年就编写了国内第一本排序理论的讲义7 0 年代初越民 义和韩继业开始研究同顺序流水作业f i p e r m i c 。问题，并且取得了杰出的成 就1 9 7 5 年发表在中国科学上的论文中，他们提出可行线和可行和的概念， 得到根据两个工件的工时来确定相邻加工次序的最佳条件国外1 9 7 6 年以后才 发表肌= 3 时的同样结果他们的成果受到国内外学术界的重视以后，他们提 出比s z w a r c 最优消去法准则更为广泛的消去准则和关于完工时间的下界表达 式以此为基础，他们设计出算法，并通过大量实例计算，表明此算法的效率 优于国外的算法他们的论文“排序问题中的一些数学问题”带动了国内对排 序问题的学习和研究近年来，越民义先生在国外讲学期间研究p8c 。排序问 题c o f f m a n 等人在1 9 7 8 年提出p | | c 。问题的m u l t i f i t 近似算法，证明最 坏情况下此算法的上界不会超过1 2 2 ，并猜测精确上界是2 0 1 7 - 1 1 7 6 1 9 8 4 年f r i e s e n 证明上界不会超过1 2 0 ，并给出上界是1 3 1 1 = 1 1 8 1 的实例越 民义证明此算法的精确上界就是1 3 1l ，从而结束了多年来对于m u l t i f i t 算法 的研究越民义和韩继业的研究成果接近和达到了国际先进水平 在越民义和韩继业的倡导和带动下，国内的排序研究有了较大的发展 林诒勋多年来研究排序的基本想法是寻找有效的工具他认为最基本的方 法是在文献 1 2 】中总结的置换法他在国内最早深入研究延误i - 1 题的文中0 3 1 也 是采用这种方法其次，他以序结构的观点来处理排序问题，也是很有特色的他 采用的第三个方法是把排序纳入数学规划的框架 2 罗守成，张峰，唐国春p 4 将圳w ，。问题表述成二次规划，并把单位权的 问题l | | 臼转化成指派问题张峰1 5 1 证明了工件加工时间简单线性增加的排序 问题( 1 l i c 。) 和加工时间一般线性增加的两种特殊情况是多项式时间可解的 赵玉芳1 3 ”给出了一类调整时间可分离的f l o ws h 叩排序问题e1 5 ic m 。的最 优算法 谈之弈，何勇m 研究了两台同类机系统两个半在线排序问题第一个为总 加工时间已知，第二个为最大任务加工时间已知对这两个问题，分别给出了 近似算法，证明了它们的最坏情况界分别为i 和3 2 时凌【3 3 】对具有延迟时间的自由作业排序问题作出了最坏性能比分析证明 在机器台数任意的情况下，一个简单的贪婪算法的最坏性能比不超过2 特别 的，当m = 2 时，证明了该算法的最坏性能比为3 2 ，其中研为机器台数 赵传立等【3 4 】研究了任务的加工不可中断的恒速机排序问题，证明了对于只 有2 台处理机的情况，如果2 台处理机的加工速度相差越大，则l p t 排序的界 越小 1 9 9 0 ，1 9 9 3 ，1 9 9 6 和1 9 9 9 年分别在上海、武汉、郑州和长沙召开了全国 第一、二、三和四届排序学术交流会与会者逐次增多，报告内容逐次扩大， 显示出了一种新兴景象可以相信，随着排序问题理论与应用的发展，必将为 我国的社会主义建设事业做出巨大的贡献 国际上，t c e d w i nc h e n g e ta 1 3 5 】研究了加工时间由于处理机具有 学习效率而逐渐减少的一类单机排序问题，即目标函数是最大化最大延迟的单 机排序问题他们证明了该问题在一般情况下是n p h a r d 的而在这两种特殊 情况下是多项式时间可解的他们给出了该问题的两个启发式算法，并分析了 这两个算法最坏情况的界 3 西北工业大学硕士论文第一章堵论 l u c i ob i a n c oe la 1 1 3 6 】研究了具有不同到达时间和序列相关的加工时间的最 小化总完工时间的单机排序问题他们证明了此闷题等价于具有附加时间约束 的累积旅行售货员问题他们通过动态规划的方法得到了该问题的下界，并给 出了两个启发式算法 n i c h o l a sg h a l le ta 1 3 7 1 研究了这样一类单机排序问题：到达的任务或者 被中断加工的任务在被加工之前存储在缓存器中，而缓存器的容量是有限的在 缓存器已满的情况下，再有任务到达或者有任务被中断，将会有一部分任务丢 失目标函数是使丢失的任务数最小 许多人己研究了多目标排序问题：文献 3 8 4 2 研究了最小化流时间和最大 延迟的问题文献 4 1 ，4 3 ，4 4 1 研究了最小化流时间和误工任务数问题，文献 4 6 】 研究了最小化流时间和总延迟的问题m u r a tk o k s a l a ne ta 1 【4 5 】研究了最小化流 时间和最大提前的问题 1 3 单机在线捧序问题 单机排序问题是最简单的一类排序问题，同时也是最重要的排序问题之 一首先单机排序问题比较容易求解这些方法对于研究比较复杂的排序问题 具有指导作用，可以为处理比较复杂排序问题提供近似算法：其次单机排序 问题大量存在于现实生活中，许多具有广泛背景的实际问题都可以归结为单机 排序闽题，因此，单机排序问题对于有效的利用资源，提高生产效率，具有十 分重要的指导意义 静态排序问题是指所有任务的参数，包括加工时间、工期和到达时间等都 是预先给定的这在我国还处于计划经济条件下是很普遍的政府部门每年年 初会为各生产单位制定全年计划，各生产单位按照给定的计划进行生产而在 市场经济条件下，实行政企分开，政府不再给企业下达指令性计划，而是企业 自主进行生产这时企业的生产完全是依靠经营销售部门的订货而进行安排的， 4 西北工业大学硕士论文第一章绪论 面销售部门能否定到货，什么时候订到货以及货物的各项指标，如交货期等全 部是未知的。企业的生产计划是在各时间点上，根据现有的任务数进行排序生 产，当有任务到达时，再及时的进行调整，以满足订货要求，这就是动态排序 不可中断问题是指，一旦开始加工项任务，那么只有当这项任务被加工 完毕才能接着加工下一项任务大部分不可中断静态问题都是极难求最优解的， 并且通常必须用诸如分枝定界法和动态规划法这类总目标技术通过使用当前可 排任务的数据来找到最优排序此类问题之所以难求解，是因为其最优排序未 必是无耽搁排序即在某些情况下，静态不可中断问题的最优解是需要在处理 机上插入一段空闲时间的这意味着虽然在某时刻有一项( 或几项) 任务已经到 达，但仍要使处理机空闲而不去加工此项( 或几项) 任务这样做的目的是由于 知道在很短的时间以后会有一项更为重要的任务到达，从而加入空闲时间以保 证这项更重要的任务- - n 达就能马上被加工只有在所有任务的性质和他们的 到达时间都是已知的情况下才会考虑插入空闲时间而且，在静态可中断问题 中要避免插入空闲时间 可中断排序问题是指，在一项任务的加工过程中，该任务可以被临时中断， 而后在该任务的中断点上继续开始加工如果任务被中断后。再加工时只是在 该任务的中断点上继续加工，我们也把此类问题称为中断一恢复问题中断一 恢复问题的解，对于给出与其相对应的不可中断问题解的下界是极其有用的这 是因为中断一恢复问题通常求解要容易得多，典型的是，在一个需要做出最优 排序的时间点上，只要知道该时阎点上系统中可排任务的信息就可以了，而不 需要知道所有任务的信息，我们把在做决策的时间点上，只知道当前可排任务 的信息而做出的最优排序称为在线最优排序 我们说静态问题的决策是离线的，这是因为所有任务的数据，即使是尚未 到达的任务，在做决策之前就已经被考虑进去了在动态问题里，任务的参数 往往是在任务到达的时候才知道，在此之前不知道该任务会不会到达，也不知 道该任务的参数这样，在任何时间点上，排序决策都必须与静态闯题中尚未 e 西北工业大学硬士论文第一章绪论 到达的任务无关当到达时间不确定的情况下以及其他任务的信息只有在任务 到达时才知道的情况下，排序问题提出了一个非常重要的要求：动态的重排的 能力b a k e r 【3 】定义了动态问题的在线决策结构调度：即在每一个决策点上( 任 务完工时间或任务到达时间) ，只是从当前可排任务的集合中获取信息，而不是 为将来事件做出预测根据已知信息，按时间顺序排列任务，得到排序决策 在线最优排序需要在两种时间点上做出决策：一是任务的到达时间，这时 需要考虑是否中断当前正在处理机上加工的任务，转而加工另一项任务；二是 任务的完工时间，这时需要考虑接下来要加工哪一项任务 1 4 本文主要工作概述 由于单机排序问题的重要性，本文选择单机排序问题为研究对象，并且研 究单机排序问题的动态在线情况首先建立了一般化中断模型，然后在此基础 上研究了几类单机动态在线最优排序问题 本文的结构如下： 第一章：绪论回顾了国内外对排序问题的研究情况，简要介绍了单机在 线排序问题 第二章：基础知识介绍了排序问题的一些基本知识，包括排序问题的定 义、分类、求解及算法复杂性等概念 第三章：一般化中断模型讨论了定义在更一般意义下的可中断动态单机 排序问题，即任务被中断后不能简单的恢复加工，而是需要有定的时间延迟， 而延迟是由任务的安装时间和任务在中断后恢复加工时其一部分( 或全部) 需 要返工的时间两部分共同造成的情况我们通过刻化上述条件，给出了两种中 断一安装重复模型一般化了任务可中断的概念为后面的研究打下了基础 第四章：总加权最小完工时间问题的在线调度本章用第三章建立起来的 i i 宣i i ；宣i ；i 昌；i i i i i i ；暑；暑昌墨昌昌昌暑昌宣暑暑昌昌置昌昌； 6 两个中断一安装重复模型来研究具有任意的和未知的任务到达时间的最小化总 加权完工时间问题和最小化时间表长这两类单机动态排序问题，给出了只考虑 当前可用信息在线调度规则 第五章：排序问题1 l o ，p r m p l w ，( 1 一p 一吁) 的动态在线调度本章考虑 单机排序问题l l o ，p 仰l w ，( 1 一p 一呜) 在中断一重复和中断一安装重复模型 下的动态在线排序问题，绘出了只考虑当前可用信息的在线调度规则 第六章：一般费用函数问题1 fr ，p r m p f 二的动态在线排序我们在第四章 和第五章研究的都是目标函数为某个函数的和的排序问题本章研究一般费用 函数问题1 1r ，p 唧i 丘在中断恢复和两种中断一安装重复模型下的单机动态 排序问题，给出了在这几种模型下的只考虑当前可用信息的在线调度规则 第七章：具有约束关系的排序问题1 l _ ，p r e c ，印1 m ( 1 一g 一。) 的动态在 线调度第五章讨论了排序问题l ir j ，p r m p i m ( 1 一p 一叶) 的动态在线调度在 第七章，我们讨论更为复杂任务之间具有前后相继关系的排序问题 l o ，p r e c ，p r m p f w ，( 1 一p 一) 的动态在线调度同样给出了在中断一恢复和两 种中断一安装重复模型下的只考虑当前可用信息的在线调度规则 最后，总结了本文的研究结果，展望了进一步研究动态在线排序问题的一 酋方向 第二章基础知识 本章介绍排序问题的一些基本知识，包括排序问题的定义、分类、求解及 算法复杂性等概念 2 1 排序问题的定义 排序问题是一类重要的组合优化问题，它是利用一些处理机( p r o c e s s o r ) 、机 i 器- ( m a c h i n e ) 或资源( r e s o u r c e ) 最优的完成一批给定的任务( i n k ) 或作q p ( j o b ) 在执 行这些任务或作业时需要满足某些限制条件，如任务的到达时间，完工的限制 时间，任务的加工顺序，资源对加工时间的影响等最优的完成指的是使目标 函数达到最优，而目标函数通常是指加工时间的长短、处理机的利用率 在排序问题中，处理机的数量和种类、任务或作业的顺序、到达时间、完 工限制、资源的种类和性能等情况是错综复杂的，很难用精确的数学描述给出 一般的排序定义本文按照文献【l 】中方式来描述排序问题： 给定含有n 个任务的任务集 卜( t l ，乃，矗 含有i t l 个处理机的处理机集 p = p 1 ，p 2 ，p m ， 和含有s 种资源的资源集 r = r 1 ，r 2 ，r ：l 排序问题指的是在一定条件下，为了完成各项任务，把p 中的处理机和r f 如 果有) 中的资源分配给f 中的任务，使目标函数达到最优 8 排序问题基本上是由处理机的数量、种类与环境以及任务或作业的性质和 目标函数所组成 一、处理机 只有一个处理机的排序问题称为单( 处理) 机( s i n g l ep r o c e s s o r ， s i n g l e m a c h i n e ) 排序问题，否则称为多( 处理) 机排序问题 在多处理机排序问题中，如果所有的处理机都具有相同的功能，称它们为 同类机或平行机( p a r a l l e lp r o c e s s o r s ) 同类机按处理的速度又分为三种类型：如果所有的处理机都具有相同的速 度，称之为i 砌( i d e n t i c a l p r o c e s s o r s ) ；如果处理机的速度不同，但每个处理机 的速度都是常数，不依赖被加工的任务，称它们为恒速机( u n i f o r mp r o c e s s o r s ) ； 如果处理机的速度依赖被加工的任务，它们被称为变速机( u n r e l a t e dp r o c e s s o r s ) 多处理机的另一种情况是多类型机( d e d i c a t e dp r o c e s s o r s ) 多类型机指的是 m 个处理机具有不同的功能在多处理机环境中，被加工的任务需要在不同的 处理机上加工在这种情况下，把任务( t a s k ) 称为作! i k ( j o b ) 设有作业集 j = u l ，j 2 j a 每个作业巧有吩道工序( o p e r a t i o n ) 正，疋，瓦，工序指的是作业在某处 理机上被加工的这部分任务 如果每个作业需要在每个处理机上加工，即”，= m ，= 1 , 2 ，r 而且每个 作业的工序也相同，即在处理机上被加工的顺序相同，把这种多类型机的环境 称为同顺序作业或流水作业( f l o ws h o p ) 如果每个作业需要在每个处理机上加工，每个作业可按任意顺序加工，把 它称为自由顺序作业或开放作q p ( o p e ns h o p ) 在多处理机中，还有一种更复杂的情况，这就是柔性流水作业( n e x i b l e f l o w q 西北工业大学硕士论文第二章基础知识 s h o p ) ，它是流水作业和平行机的推广在柔性流水作业中，有s 类处理机，第 j 类有s 个平行机，每个作业有s 道工序，每道工序需要在每类平行机中的一个 处理机上加工，且每个作业的加工顺序相同 同顺序作业、异顺序作业、开放作业、柔性流水作业通称为车间作业， 处理机的各种类型和环境总结如下： 处理机 单处理机 多处理机 二、约束 f 同速机 同类机( 平行机) 恒速机 变速机 f 同顺序作业( 流水作业) 多类机( 车间作业) 异顺序作业 i 自由顺序作业( 开放作业) 柔性流水作业 排序问题中的约束条件，主要指的是任务或作业的性质以及它们在加工过 程中的要求和限制下边的数据描述了任务的一些性质 ( 1 ) 加工时间向量 任务的加工时间向量是 p = ( p l j , p 2 ，一p w ) 其中p 。是任务t 在处理机p 上所需要的加工时1 5 对同速机有 p 。= 玛，i = 1 ，2 ，珑，对恒速机有p f = p j b ，i = 1 , 2 ，m ，其中p ，是标准的加 工时间( 般是速度最慢的处理机的加工时间) ，b 是处理机p ，的速度因子 1 0 在车间作业的排序阅题中，作业，的加工时间向量是 p ，2 ( a ，p 2 ，p ”，) 其中p ，：一t 。在对应的处理机上所需要的加工时间 ( 2 ) 到达时间 到达时间( a r r i v et i m e ) 或准备时间( r e a d yt i m e ) r j 是任务r 已经准备好可以被 加工的时间如果所有的任务的准备时间相同，取0 = 0 ，= 1 , 2 ，珂 ( 3 ) 工期和截止期限 工期( d u e d a t e ) d j 表示对任务t 限定的完工时间。如果不按期完工，将受到 一定的惩罚绝对不允许延误的工期称为截止期限( d e a d l i n c ) ( 4 ) 优先因子 优先因子是一个权，它表示任务l 相对于其他任务的重要程度 任务被加工时的一个重要约束是可中断( p r e e m p t i v e ) 或不可中断 ( n o n - p