排序论基本概念综述

1、2012年7月重庆师范大学学报(自然科学版( J o u r n a l o fC h o n i n o r m a lU n i v e r s i t N a t u r a l S c i e n c e g q g N y第29卷第4期V o l . 29N o . 4J u l . 2012运筹学与控制论:/D O I C N K I 50-1165N. 20120704. 1115. 001排序论基本概念综述唐国春*( 上海第二工业大学经济管理学院, 上海201209摘要:第二次世界大战期间运筹学(兴起, 首次把运作(作为研究对象 研究运作的时O e r a t i o n s

2、r e s e a r c h O e r a t i o n p p 这是学科正在成熟的标志, 也是学术交流的需要 王元院士等于2数学大辞典“ 是一部综合010年8月编辑出版的 性的数学大辞典, 目前正在修订出版第2版 中国运筹学会排序专业委员会(排序分会 组织34位专家执笔和审阅了3供入选 数学大辞典“ 第2版用 本文综述了这3旨在征求9条排序论最基本的概念, 9条排序论最基本的概念, 意见, 为以后编辑出版完整的 排序论辞典“ 奠定基础 关键词:运筹学; 排序; 综述中图分类号:O 221. 7文献标志码:A( 文章编号:1672-6693201204-0001-11间安排又促成排序(概

3、念的建立和研究的开展 经过5国内排序术语正在逐步走向统一, S c h e d u l i n 0多年的发展, g1背景介绍 尽管排序似的解法 面向应用的或者基于理论的 论取得了进展, 但是在这个令人兴奋并且值得研究3 经过5的领域, 许多挑战仍然存在 0多年的发概念的建立和研究的开展 在2l i n 0世纪中叶运g筹学奠基时期, 排序论的先驱工作已经在离散优化领域占有重要地位 此后, 排序论始终保持蓬勃发展的势态兴起, 首次把运作(作为研究对s e a r c h O e r a t i o n p 象 其间, 研究运作的时间安排促成排序(S c h e d u -第二次世界大战期间运筹学(

4、O e r a t i o n sr e p -展, 国内排序(调度 术语正在逐步走向统一 这是学科正在成熟的标志, 也是学术交流的需要 在最优化理论和应用中把 排s c h e d u l i n g 序 调度 这三者视为涵义完全相同, 完全可以相互替代的3个中英文词汇, 只不过是这三者使用的4 这时, 场合(英语 运筹学 自动化 不同而已不20世纪60年代越民义就注意到排序(S c h e d u - 问题的重要性和在理论上的难度 1l i n 960年他g编写国内第一本排序理论讲义 70年代初他和韩继业研究同顺序流水作业排序问题, 开创中国研究1 在他们两位的倡导和带动下国内排序论的先河

5、, , 要把 排序 理解为 安排次序 不是 s e u e n c i n q g 类似地, 而要理解为 也不要把 调度 s c h e d u l i n g 因此, 可以把 译成 安s c h e d u l i n s e u e n c i n g q g 但是, 排次序 这并不意味着 排序 就是 s e u e n q -, , 间表 或者 排时 也是可以的; 还有把 s c h e d u - 也尊重自动化学科从上个世纪8译成 排序 0年代就在使用 调度 的译法 所以, 提倡用 排序 和, 理解为 调整速度 或者 调剂力度 而要理解为排序的理论研究和应用研究有较大的发展 国内最早把

6、s c h e d u l i n 983年2 正如国g 译为调度是在1际上著名s 排序论的c h e d u l i n o t t s 等指出:g 专家P 进展是巨大的 这些进展得益于研究人员从不同的学科(例如, 数学 运筹学 管理科学 计算机科学 工程学和经济学 所做出的贡献 排序论已经成熟, 有(例如, 有确定性或者随机性的模型 精确的或者近许多理论和方法可以处理问题; 排序论也是丰富的 作为英语 的动名词, c i n s c h e d u l i n s c h e d u l e g g是包含 动作 的, 所以, 把 译成 安排时s c h e d u l i n g5 考虑到

7、在数学和运译成 排程 或者其他l i n g筹学中5赞同把 0多年来使用的习惯, s c h e d u l i n g调度 作为 的中文译名 苏步青院士s c h e d u l i n g*收稿日期:2012-03-06 网络出版时间:2012-07-04 11:15:00 资助项目:国家自然科学基金(N o . 70731160015; N o . 20710015作者简介:唐国春, 男, 教授, 博士生导师, 研究方向为排序论:/_0网络出版地址:h t t w w w. c n k i . n e t k c m s d e t a i l 50. 1165. N. 20120704

8、. 1115. 201204. 101. h t m l p2:/重庆师范大学学报(自然科学版 h t t w w w. c n u . c n 第29卷p q j曾为排序专业委员会(排序分会 题签 排序通讯 和排序论学报1974年B a , k 激励大家学习和研究排序论6e r 定义: S c h e d u l i n g i s t h ea l t l o c a -o i f o t no a s f k s r e s 7o u , r c 即e so s c h v e e d r u t l i i n m g e 是为完成若干项t o p e r f o r mac o l

9、l 任e c 务t i o 而n对资源(指包括行分配 接着, B m a a k c e h r i n e 在内的各种资源按时间进指出: S c h e d u l i n g i sad e c i -l s i 1e o ma n m m a o k u i n n t g s f t u o n c a t n i s o w n e . r i S n o g l v t i w n g ok as i n c d h s e o d f u l q i u n e gp s t i o r o n b s -:e a .W c h t h a i s c k hr ? 2e s .

10、W o u r h c e e nw s w i i l l l lb e a c ea h t l l a o s c kb a t e e dt p e o r f o p r e m r f e o dr ? mr P i i S t n h e c h m d o 在著名的 e s d u , l a i n n dS g d y e s t e m s “ S 一书中提出几乎相同的定义c h e d u l i n g :T h e o r y , A l g o - p s o u r c e s t o t a s k s a l o sw v e r i t t ht i m

11、h e ea . I t l l i o s c a ad t i o e no c i s f i o s n c a m r c a e k i r n e g -js e r c c o c e s sw h t i e v d e i 8t h t h 因e g 而o a , l 按o f 时o p t 间i m i 分z i n 配g o 任n e 务o rm 和资o r e 源o b 是-制造业推动下发展起来的B u s a l i k n e g 很本质的特征r 指出: 排序领域内许多早期的工作是在, 所以在描述排序问题时会很自然地使用制造业的术语 虽然排序问题在许多非制造业的领

12、域内取得了相当有意义的成果, 但是制造业的术语仍然经常在使用 因而, 往往把资源(先后次序约T a s R k e s s o 称为工件u r c e s 称束相互(J 为联o b 系s 机 着 器的有时工(M a c h 基本任件i n 务可e s (能, 是把由任几务个t E l e m e n t a r yt i a s k s 问题o n s 也 所描例如组成述成, 对这为门种 工诊件病基 人本在到任 医务机疗称器诊为 上所工 看序加病(O 工的p 排e r a 的序-过程 6制造业中的 排序论中的 车床 和 机器车床加工的螺丝 和 工件 已经不是机器, 已经从 车床 和 螺丝 等具

13、体事物中抽象出来, 是抽象的代表性概念 正好比 水果 是从 香蕉 苹果 等具体事物中抽象出来, 是抽象的代表性概念一样 排序论中的 机器 可以是数控机床 计算机处理器 医生 机场跑道等, 工件 可以是零件C P U (中 央计算机终端 病人 降落的飞机等 例如, 计算机科学中并行计算机的出现, 促进排序论中对平行机(a 的深入研究; 反过来, P a r -行机可以应用到具体的计算机科学的并行计算机中l l e lm a c h i n e排序论中的平去, 平行机排序的成果在一定程度上推动并行计算机的发展42010年 8月王元院士等编辑出版数学大辞典“ 这是一部综合性的数学大辞典, 涵盖数理逻

14、辑与数学基础 数论 代数学 分析学 复分析 常微分方程 动力系统 偏微分方程 泛函分析 组合数学 图论 几何学 拓扑学 微分几何 概率论 数理统计 计算数学 控制论 信息论 运筹学等学科, 以常用 基础和重要的名词术语为基本内容, 提供简短扼要的定义或概念解释, 并有适度展开 最近 数学大辞典“ 运筹学部分主编章祥荪教授提出: 数学大辞典目前正在进行修改, 以便在一年后出版第1版中对排序的确反映不够,可以考虑在新2版 第版中加以改进 其他有些分支也有同样的问题, 正在改进 辞典的定位是大学本科的读者, 因此条目的选择要有普遍性, 不要太细的学术展开 为此, 中国运筹学会排序专业委员会(排序分会

15、 组织和审阅“ 第39条排序论最基本的条目, 3供入选4位专家执笔 数学大辞典论最基本概念2版用 笔者在此文中综述了这, 旨在公开征求意见, 为以后编辑出版39条排序完整的 排序论辞典“ 奠定基础在 数学大辞典“ 和 排序论辞典“ 中 排序 默认的涵义是 c 在h i n e 排序s c h 论e d s c h e d u 辞u l i 典n g “ l 也 i n , s g , 而且是指 机器安排次序排序(M a - 介e q 绍u e n 项c i n 目g 是译成排序 中最基础的条目, 但是不会涉及计算机科学中关于 数据排序(t D a -和a s o 排序论辞典r t i n g,

16、 如冒泡排序等条目“ 中把所有的 度 都改为 排序 同样, 以s 后c h 在e d u 在 数学大辞典 l 自i n g 动 化涵义的辞典“ 调“ 和 调度论辞典化理论和应用中完全可以相互替代排序 都改为“ 中 调度, 可以把所有的 , 因为 排序 s c h 与e d u 调度l i n g 涵义的在最优2排序论基本概念条目排序(完成若干项S c 任h e 务d u l (i c T n a gs k 是为加工若干个工件或者 而对资源(包括机器(M a -时间进行高效率的分配h i n e 或者处理机(P r o c ; e 在自动化学科中称为调度s s o r在内的各种资源 按; 在最优

17、化理论和应用中是指机器排序(s c h e d u l i n g , 以区别项目排M a c h i n e和数据排序(序和现代排序D a t as o r t i n g 序排(P 序r o j 问e c 题t s 分c h 为e d 经u l i 典n g 排(执笔:唐国春 校阅:韩继业排序三参数表示(l i n g 1967年C o n w a yT , h r M e a e -x f i w e l e dn l l o 和t a t M i o i no l l e r f s 提c h 出e d u 用-第4期 唐国春:排序论基本概念综述34个参数表示排序问题 和K i n n

18、 o o a n 改用三参数197年G r 来表示a h a m , L , 其中a w l e r 表示机器环境y K (单台机器, bc P 表M 示a c 同h i 型n e 机e n , v i r o n m e n t , 比如1表示h a r a c t e r i s t i c s Q 表示同类机; 表示工件特性(J o , 比如r j 表示工件的就绪时间可以不相同, o 表示目标函数n l i n e 表示在线排序, p t n 表示加工允许中断; -m , 比如C m a x 表示最大完工时间(M a k e s a n , C w p j C j表示带权总完工时间

19、40; j 表示总完工时间,ð 例如:P m p m t n , r jð C j表示m 台同型机工件的就绪时间可以不相同 加工允许中断 优化的目标是使总完工时间为最小的排序问题(执笔:张玉忠 校阅:唐国春机器(所需要的资源M a c ; h i 也有称为处理机n e 是加工工件或者是完成任务(可以分成两大类:通用平行(P a r a l l P e r lo c 机和专用串联e s s o r 机器(在D e m d i c 台平行机上的加工是只需要在这a t e d机 对于加工不允许中断的情况m 台机器中, 工件的任何一台机器上加工一次; 工件在m 台串联机上的加工是需

20、要在这m 台机器中的每一台机器上都加工一次 平行机分成; 串联机也分为3类3类:同型机 同类机和非同类机:流水作业 自由作业和异序作业(执笔:张玉忠 校阅:唐国春工件(任务 对于J o n b 个 是被加工的对象, 或者是要完成的工件在m 台串联机上加工不允许中断的情况, 工件J j 在机器M i 上的一次加工称为一个工序(i e n c g u t t i i o m O n e t i p m e 服务时间r a t i o n , e 是指工件(记S e r 为O i j 加J v i c e t i m e 工或执行时间时间(P r o c (e s s -需E x j 在机器M i

21、上加工所的-(时间非负的(A r r i 时间v a l t , i m 可以用e 准备时间p i j 来表示 就绪时间 到达(放行 时间(R e l e a s e t i m e 是指工件(R e a d y J ti m e 或释放j 可以开始加工的时间, 可以用r j 来表示 如果所有的工件都同时就绪, 可以认为r j d a t e d =0(j =1, , n 交货期(D u e j 表示工件J j 的所有工序的加工都应该结束的时刻 权(机器和工件W 的e i 一g h 种t w j 表示工件J j 的重要性 在安排下, 对应于一张时间表t (i S m c e h e C d u

22、 l e 的输出数据有完工时间(j , 是工 件J C o m pl e t i o n j 的最后一道工序实际结束加工的时刻; 运行时间(F l o wt i m e F j =C j -r j ;延迟L L a t e n e s s L j =C j -d j ;延误(T a r d i n e s s T j =ma x j , 0; 提前(E a r l i n e s (s 执笔 E j =m:张玉忠a x - L j 校阅, 0:等唐国春 误工计数(C U n i t j 大于该工件的交货期p e n a l t y 如果工件J j 的完工时间d j 误工的; 否则, 称为不误工

23、 通常, 那么该工件称为是用U j 表示误工计数 如果C j U d j , 那么U j =0; 如果C j >d j ,那么j =N 1 从而ð U, 误工的工件的个数(简称为误工工件数T =j 在赋予工件的权w j 适当的物理量纲后w j U j 可以看成是一次误工(不管误工时间的长短 造成的损失; ð w j U j 又可以称为带权误工工件数(执笔:沈灏 校阅:唐国春经典排序(e C l a s s i c a l s c h e d u l i n g 1993年L a w l -q r p u , e n L c e i n n s t r a n , d

24、R s i c n h n e o d o u y l i n K a :n 和A l o S r h i t m h o m y s s 等在 a n d c o S m e -源的类型l e x i t yg 一文中提出经典排序有a g g 机器是加工工件所需要的一种资源4个基本假设:1 资-经典排序假设, 一台机器在任何时刻最多只能加工一个工件; 同时还假设, 一个工件在任何时刻至多在一台机器上加工 问题的一个实例的所有2 确定性(输入 经典排序假设决定排序 参数都是事先知道的和完全确定的 算的层面上研究排序问题3 可运算性, 而不去顾及诸如如何确 经典排序是在可以运定工件的交货期, 如

25、何购置机器和配备设备等技术上可能发生的问题 假设排序的目的是使衡量排序好坏的单个目标函数4 单目标和正则性 经典排序的函数值为最小, 而且这个目标函数是工件完工时间的非降函数 这就是所谓正则目标(执笔:唐国春 校阅:韩继业现代排序(新型排序(N e wc M l o a d s e s r e so ns f c h s e c d h u e l d i n u l g i n gp 现代排序或r o b l e m s 是l B o i r n u c k e r r 和o b l e m K s n u s (t 在 见h C o m :/p /l e x i t y r e s u l

26、 t s o f s c h e d u -相对于经典排序而言s n gp a b r u e c k . d e /r e s e a r t t c p , h 其特征是突破经典排序的基/O w R w /c w. l a s m s/a t h 中e m 提a t 出i k 的. u , n i 是-本假设 作为经典排序关于资源的类型基本假设的突破, 有成组分批排序 同时加工排序 不同时开工排序和资源受限排序等 作为经典排序确定性基本4:/重庆师范大学学报(自然科学版 h t t w w w. c n u . c n 第29卷p q j假设的突破, 有可控排序 随机排序 模糊排序和在线排

27、序等 作为经典排序可运算性基本假设的突破, 考虑实际应用中有关的情况和因素, 就是应用排序(l p i l o y A e e p p s l c i h e ds e d u c l i h n e d u l 和i n 智g 能问排题序 (I 如n t e 人l l i 员排序(E m -的突破n g 等, 有多目标排序作为经g 典排序g e n t s c h e d u - 准时排序和窗时排序等单目标和正则性基本假 设这10种经过推广的排序(可控排序 成组分批排序 在线排序 同时加工排序 准时排序和窗时排序 不同时开工排序 资源受限排序 随机排序 模糊排序 多目标排序等 构成现代排序论

28、的主要内容 新型排序还有c S m a t 序u i l o t 等i n p r d c e l h a e y d s u l (i n 带g 有w i o c e s s o r j o b s (传t ht 多输r 台时a n 机间s p 器的o r t a t i o n 同排时序加 工 (S c c o mm u n i -工h e 件d u 的l i n 排g(执笔:唐国春 校阅:韩继业多代理竞争排序(u C o m e t i t i v em u l t i a e 个类l i n g, 在多代理竞争排序问题中p , 全部工件分为-g n t s c h e d K -每一类

29、由一个代理(竞争公共的资源(即利用相A g 同e n t 的 机负器责集 合这些加代工理工件 , 某代理负责的工件的约束条件和使用的目标函数可以与其他代理负责的工件的约束条件和使用的目标函数不同 假设f j 是代理j 的目标函数, 优化的目标有求问题的帕3类:累托1 (同时优化所有代理的目标函数(寻题 ; 2优化带权求和型的目标函数P a r e t o 最优解, 属多目标优化问jfj束优化, 排序的目标函数为j e c t t o (l 1l sm i n (f j 1ð f ; 3f , , j k s u b 约s , 其中Q -给定的目标函数值 Q 1, f , k +Q s

30、 = s 是对代理s 事先K 例如, 考虑在m 台平行机上对n 个工件进行加工, 这n 个工件可以分为两类, 由代理别负责n 1和n 2个工件(n =n 1理+n 2 1和代理代理1(2分或代记为2 w 负责的工件j 的加工时间记为p 1j 1w (或p 2j , 其权j j j d 1(2 , 就绪时间和交货期记为r 1(或r 2j 和j 的目标函(或d 2j , 完工时间记为C 1j 数可以不同, 例如代(或C 2j 理L11的 目这标两函个代数理是m a x, 而代理问题的最优排序中2的目标函数是, 可能是先加工代理ð w 2j C 2j Q 在这个件, 再加工代理1的部分工如

31、此等等2的部分工件, 然后加工代理 利用排序三参数表示, 1的另一部分工件, 这个排序问题可以表示为:P m |r 1j , d 1j :r 2j |L 1m a x :ð w 2j C 2j Q (执笔:万国华 校阅:涂菶生随机排序(排序问S t 题o c h a s 在t i cs 确定c h 性e d 排u l i 序n g 场合下的(s D 处理随机e t e r m i n i s t i c都是已知常数c h e d u l i n g问题中 一旦这些参数不能事前完全, 各个参数如加工时间 交货期等知道, 随机排序方法提供一种解决方案, 其机理为:虽然问题的参数事先未知,

32、 但是如果同样或类似排序问题大量使用(即概率理论中的重复性 , 这些参数可以被当作随机变量 此时, 需要优化的目标(比如说总完工时间 也是随机变量, 需要在概率意义下求其最优解 目前采用较多的方法是优化其数学期望 由于在随机排序中所涉及的参数是随机变量, 它们的值在未实现之前都是未知的, 因此, 当一部分随机变量实现或者部分实现之后, 决策者对未实现或者未完全实现之随机变量的分布(亦即条件分布 会有新的认识(也就是信息更新 如果技术允许, 原有策略应该基于被更新的信息进行合理修正, 因而使得随机排序的策略带有动态特征在随机排序中, 根据技术条件的不同, 策略有静态(而后者又可以分为完全动态S

33、t a t i c p o l i c i e s 与动态(D y (n U a n m r e i c s t r p i o c l t i e c i dd e s yn 之a m 分i c , p c o l i c i e s 和不完全动态(R e s t r i c t e dd n a m i c p o l i 序最本质的部分应该是在动态策略类中研究一定意i e s 虽然静态策略的寻找也非易事y , 但是随机排-义下的最优解问题 在动态策略研究方面目前最好的方法是离散时间和连续时间上的随机动态规划方法(点(S t o c h a s t i c d n a m i c p r

34、o r , 在每个决策便最大化利益或者最小化成本D e c i s i o ne p o y c h s , 决定下一个该处理的工作g a mm i n g , 以(执笔:吴贤毅 校阅:蔡小强平行机(机器, 每个工件只需要在这些机器中的任何一台上P a r a l l e lm a c h i n e 是功能基本相同的加工一次 依据工件在机器上加工的情况, 平行机分为同型机 同类机和非同类机作为复杂机器环境的组成部分 3类 平行机还可例如, 流水作业中某道工序的加工机器可以是多台平行机, 称为混合流水作业(H y b r i d f l o ws (执笔h o p:谈之奕 校阅:刘康生同型机(

35、I d e n t i c a lm a c h i n e 是对加工工件完第4期 唐国春:排序论基本概念综述5全相同的(同的 因而I d , e 一个工件在不同的同型机上的加n t i c a l 平行机, 亦即机器的型号是工相时间都相同, 也即所有的同型机加工同一个工件的速度都相同 默认的平行机通常是指同型机在同型机排序中, 常用的优化目标是最大完工时间 对于使最大完工时间为最小的同型机排序, 即使只有两台机器时也是常用的近似N 算P 困难的,因此通常研究其近似解 法有列表算法(s 算法c h e d u l i 列表算法是把工件排成一个序列n g , L S 和L P T (L o n

36、g e s t p r o c e s s L i s t, i n 任何g t i 时m e 候 是加工排在最前面的工件, 如果这个工件需要加工并且可以加工(机器有空闲 的话, 直到所有工件都加工 列表算法不需要知道还没有加工工件的信息, 所以这种算法对于在线排序也可以采用 如果工件是按照加工时间非增的次序排列, 那么相应的列表算法就称为L P T 算法(执笔:王振波 校阅:邢文训同类机(工件在不同机器上的加工时间可以不同U n i f o r m m a c h i n e 是这样的平行机, 但却是成比例的 这个比例因子就是机器加工工件的 速度 , 即机器对不同工件的 适应程度 是一致的(

37、n U -件都比较快i f o r m 当机器的型号比较新时 这时机器的型号可能不同, 其加工所有的工, 但是类型是相同的 更确切地定义, m 台平行机称为是同类机, 如果工件j 的加工时间是p (j =1, 2, , n 在其中一台机器上 , j m , 存在s ,那么对所有的机器i (i =1, 2, i , 件j 在机器i 上(的称为是机器i 的加工速度 使得工加工时间是p i j 有的s p /s i 如果所i =1在同类机排序中, 此时的平行机就是同型机=, 常用的优化目标 j 是最大完工时间 由同型机可知, 对于使最大完工时间为最小的同类机排序是N P 困难的 借助L P T 算法

38、, 改进的L P T 算法和线性规划松弛算法可以得到此问题的常数因子的近似算法(执笔:康丽英 校阅:鲁习文非同类机(U n r e l a t e dm a c h i n e 是这样的平行机, 工件在不同机器上的加工时间可以不同, 也不成比例, 与机器加工工件的 速度 无关(这时机器i 加工工件的速度与工件j 有关U n r e , l 应a t e 该d 表 示为s i j 如果s i j 平行机就是同类机=s i 对所有的i , j 都成立, 此时的在非同类机排序中, 常用的优化目标是最大完工时间和总完工时间 由同型机可知, 对于使最大完工时间为最小的非同类机排序是, 利用线性规划松弛算

39、法可N P 困难的 对于机器台数为固定值时以得到此问题的最小的非同类机2排-近似算法 对于使总完工时间为序, 可以转化为具有偶图(二部图 匹配结构的0-1整数规划, 可以给出此问题的多项式时间算法(执笔:康丽英 校阅:鲁习文流水作业(件以相同的特定的机器次序在两台及两台以上机器F l o ws h o p 是两个及两个以上工上加工的排序问题, 用三参数表示为F m 表示流水作业, m 为机器的台数 不失一般性,其中, 流水作业工件集J :J 1按照机器集M :M , J 2, , , J n 的中机器的下标次每个工件J j 都件的工序1, 2, m 个数都在这1m , M 2台机器上依次加工,

40、 M m 序 , 每个工是m 流水作业大多是N P 困难的, 只有少数特殊情形是多项式可解的(执笔:王雄志 校阅:王国庆自由作业(件依次在机器次序并不指定的两台及两台以上机器O p e ns h o p 是两个及两个以上工上加工的排序问题, 用三参数表示为O m 表示自由作业, m 为机器的台数 每台机器,其中上加工所有工件的次序和每个工件被所有机器加工的次序都是自由作业要决策的 自由作业大多都是困难的, 只有少数情形是多项式可解的N P (执笔:陈荣军 校阅:张峰异序作业(以各自特定的机器次序在两台及两台以上机器上加J o b s h o p是两个及两个以上工件工的排序问题, 用三参数表示为

41、J m m 示异序作业, 为机器的台数 异序作业中每个工, 其中J 表件以各自特定的机器次序加工, 而且工序的数目可以不相同, 可以小于m 主要通过近似算法或启发式算法求解 异序作业大多是强 N P 困难的, 流水作业是一种特殊的异序作业 自由作业可以理解成松弛 的异序作业(执笔:王雄志 校阅:王国庆在线排序(前, 已经知道工O 件n l i 的n e 全s c 部h e 信d u 息l i n , g这种 如果在排序之排序称为离线F O6:/重庆师范大学学报(自然科学版 h t t w w w. c n u . c n 第29卷p q j(决定当前工件的加工时对其后面就绪工件的信息一O f

42、f -l i n e 排序; 如果工件的信息是逐步释放的, 在无所知, 并且一旦决定工件的安排后就不允许改变, 这种排序称为在线排序 在线排序分为两种:按序(按序在线排序中O v e r l i s t 在线排序和按时, 工件排成一个序列逐个出现(O v e r t i m e在线排序, 只有 当一个工件前面的工件全部安排后, 才知道这个工件的信息 按时在线排序中, 每个工件都有一个就绪时间, 只有当工件就绪后才可以知道这个工件的信息 另外, 如果当一个工件就绪后, 就知道其加工信息, 那么这种在线排序称为可预测的(C l a i r v o y -加工n t 信如果一个工件直到加工结束时才可

43、以知道其息, 那么这种在线排序称为不可预测的(的有限性N o n -c l a i r , v 在线排序的困难在于信息的匮乏o y a n t 离线排序的困难在于计算资源 在线排序研究的主要手段是算法竞争比(a t i o分析 C o m pe t i t i v e (执笔:王振波 校阅:邢文训半在线排序(于在线排序和离线排序之间的排序问题S e m io n -l i n es c h e d u l i n g 在线排序 是介有两个重要条件:工件的信息是逐步释放的; 不允许改变已安排工件的决策 若上述两类条件部分满足则称为半在线排序 一般来讲, 半在线模型分为两类, 一是提前预知工件的部

44、分信息, 二是部分地调整已经安排的工件 第一类模型主要包括:已知所有工件加工时间的总和; 已知工件的最大加工时间; 已知最后到达工件的信息; 已知问题的最优值; 工件按照某种已知的特定次序到达(如按照加工时间从小到大或者从大到小的次序到达等 工件的加工时间属于某个给定的区间; 预先知道即将出现的若干工件的信息; 带缓冲器(模型主要有:可调整最后一个安排的工件B u f f e r 的排序等等; 可重排任第二类意k 个工件; 改变工件的决策有相应的费用等等 半在线模型还可以是上述模型的组合, 即同时已知或者满足两个或者两个以上的条件 与在线排序一样, 衡量半在线排序算法的优劣往往采用竞争比分析

45、与在线排序相比, 半在线排序一般有较好的竞争比(执笔:叶德仕 校阅:谈之奕批处理排序(同时加工一批多至B a B t c (B hs c 1h e ,d 称为机器的容量u l i n g 是机器可以 个工件; 又称为分批排序或者同时加工排序; 产生于世纪90年代初大规模的流水作业生产线, 如半导体20生产 航空工业 钢铁铸造 制鞋业等等 同一批中的工件具有相同的开工时间和相同的完工时间, 而批的就绪时间就是该批中所有工件的最大就绪时间 在继列分批(个固定的安装(于该批中所有工件的加工时间之和S e S t -e u r i p a l 时b a t 间c h , i 并n g 且 中批, ;

46、的每一批都有一而在平行分批加工时间等(有工件的最大加工时间P a r a l l e l b a t c h i n g中, 批的加工时间等于该批中所 分批排序就是确定工件的批划分, 并安排批的加工使得目标最优(执笔:张玉忠 校阅:原晋江可控排序(, 包括加工时间C o n 交货期t r o l l a b l e 就绪时间或权等可以通过s c h e d u l i n 工件的参数g 改变资源控制其大小的排序问题称为可控排序 记工件集合J =次序J 1J , J , 工件的加工(=x 1期 , x 2就绪时间或权等, , (x (1n ( 其中, (2x , , , 2, (n , n 控制

47、参数x =j 是工件J j 的加工时间交货 可控排序考虑两个目标, 一个是工件的完工费用, 即为通常的排序问题目标, 记为F 1费用, (x 记为, F , 另一个是控制工件参数x 所需的控制2(x 完工费用F 1(x , 和控制费用2(x 次序, X 的总和称为总费用表示控制参数全 体记取是工件的所有加工值 4种可控排序如下所述:(m P (P i 12n F 使总费用最小在限的+完F :1(x , 工2(x 费 用|x ÎX , Î m i n F 2(x F 1(x , , , x 下ÎX 使控制费用最小:是给定的常数, Î, 其中m i n (F

48、 P 3 在有的控制费用下ÎX 使完工费用最小:1是给定的常数(x , F 2(x , x , Î, 其中m i n (F P 14(x , 两 个, F 目标的帕累托(2(x |P a r e t o 有效解:(x ÎX 执笔:, Î张峰 校阅 :刘朝晖 多目标排序(究多个目标的排序问题M u l t i - c r i 由于多个目标之间常常是t e r i as c h e d u l i n g 是研相互 冲突 的, 一般不存在使多个目标同时达到最优的 绝对 最优解 多目标排序分成是寻找约束解和多重解(H i e r a r c h i c a l

49、 s 3类 第o l u t i o n1类 对a r F 第4期 唐国春:排序论基本概念综述7两个目标函数1和2来讲, 如果是在第数1满足一定的约束条件下, 使第2个目标函数1个目标函2为最优, 这样得到的解称为约束解 特别, 如果是在第1个目标函数1为最优的条件下, 使第函数2为最优, 这样得到的解称为多重解2个目标 第是寻找帕累托(又称为非支配解P a r e t 排o 序 有效解称为(E 是f f i 两c i e 个n t 2类目s 标o l u 函t i o 数n , 1和12为最小的有效解, 如果使得i ( i (i =号成立的这种排序, 2, 并且在这两个不等式中至少有一个严格

50、不等不存在的话 第权函数(3类是用构造化为单目标排序W e i g h t e dc 这种方法得到的多目标排序的解r i t e r i a 的方法把多目标排序转称为权函数解, 其中最重要的权函数是线性加权函数 对两个目标函数1和2来讲, 就是1关于两个目标函数的大部分结果可以直接推广到1+22 个或者更多个目标函数的情况 对多台机器不论是3平行机还是串联机, 也都可以研究相应的多目标排序问题(执笔:张峰 校阅:刘朝晖准时排序与窗时排序(a J u s t -i n -t i m es c h e d u l i n g 之前完工和之后完工都要支付费用的排序问题称为n dd u ew i n

51、d o ws c h e d u l i n g 对于工件在交货期准时排序 准时排序的重要研究方向是工件具有共同交货期的情况, 分为两类问题, 一类是共同交货期为给定的参数; 另一类是共同交货期为决策变量准时排序主要研究两类目标函数:总费用函数f =数f =ðm ja (j E j x +j T j j j j j E j , +C +j d j j T j , 其中j , 与最大费用函j 交货期的单位费用, j , j 分别表示提前 延误 完工时间如果把工件J j 的交货期d j 改为时间区间d 1j d 2,j 不需要支付费用, 即工件在时间区间, 在时间d 1j d 1, d

52、2j 内完工没有 惩罚 , j 之前完工(提前 , 或在时间之后d 2j 完工(延误 都要支付费用 这样的排序问题称为窗时排序, 窗时排序是准时排序的推广(执笔:张峰 校阅:刘朝晖正则排序(R e g u l a rs c h e d u l , i n 则称为正则目标函g 如果优化目标是工件完工时间的非减函数数 具有正则目标函数的排序问题称为正则排序问题 经典排序问题仅考虑正则目标, 如最大完工时间C m a x 带权总完工时间j 最大延迟L m a x 误工工件数n T 等 对正则排序问题ð w j C,最优排序只需在半活动排序中求解 半活动排序是指在不改变工件在机器上的加工次序

53、前提下, 不可能提前任何一个工件的完工时间 半活动排序的全体又称为优势集(寻找最优解D o m i n a n t s 构造尽可能小的优势集e t 因此, 正则排序只, 要对求解在优势正集则排序问题有特殊的意义 对于半活动排序, 机器对工件的加工次序一旦确定, 则机器对工件的开工时间也就唯一确定 这时, 最优排序由其机器对工件的加工次序唯一确定 因此, 此时求最优排序便转化为仅求机器对工件的加工次序问题 准时排序是典型的非正则排序(执笔:陈秋双 校阅:涂菶生鲁棒排序(确定性的一类排序问题R o b u s t s c h 鲁棒排序通过事先考虑环e d u l i n g是作为解决不境中一定程度

54、的不确定性, 使得产生的预排序(P r e -关注的焦点是预排序在不确定环境下的稳定性i c t i v e s c h e d u l e具有抵御可预测的扰动的能力, 其目前, 在鲁棒排序中考虑的不确定性主要是工件加工时间的不确定性和机器故障 鲁棒排序的概念针对不同的研究问题和要求, 有不同的含义 如:扰动发生后, 次序和开始加工时间可以维持不变1 预排序仍为一个可行排序 ; 行排序的概率不低于某一水平; 2 预排序为可(工件加工调整可限定在某一局部范围之内3 对预排序的实时常用鲁棒排序方法有时间冗余法 鲁棒优化 多目标优化等 鲁棒排序方法通常应用于不希望频繁调整预排序的场合鲁棒排序的概念应

55、用非常广泛, 除上述鲁棒机器排序外, 还有鲁棒项目排序 鲁棒航班排序等, 在这些领域, 多数称为鲁棒调度(执笔:陈秋双 校阅:涂菶生混合流水作业(作业包含s 个加工阶H 段y b (r i 工d f 序l o ws , 每h 个o p 加 混合流水工阶段i 有i 1台平行机,但至少有一个加工阶段的平行机数m i 2同类机或非(i =1同类, , s 机 每 这些平行机可以是同型机个待加工的工件 , n 流程是单一方向的依次经过这j 个加工阶段, 且工件在作业中的(j =1s , 在每个阶段, 每个工件只能在一台机器上加工, 而一台机器一次至多加工一个工件 混合流水作业问题的目标是在决定每一阶段

56、处理工件的机器分配及该机器上工件的加工次序和开始加工时间, 使得给定的目标函数最小d m8:/重庆师范大学学报(自然科学版 h t t w w w. c n u . c n 第29卷p q j如果s =1且m i =11且m , 则是单机排序; 如果s =i >1, 则是平行机排序; 如果s >1且m i =1则是流水作业, 混合流水作业是流水作业排序和平行机排序的扩展, 又称为具有多台平行机的流水作业或柔性流水线问题, 是一类复杂的作业排序问题 与经典流水作业相比, 混合流水作业的某些加工工序上存在平行机, 因此混合流水作业具有平行机排序问题的特征, 其求解较经典流水作业排序问题更为困难 这类问题在流程工业中如钢铁 化工等工业中比较常见(执笔:唐立新 校阅:万国华半连续型批处理排序(s S e m i -c o n t i n u o u sb a t c h 同时加工多个工件c h e d u l i n g半连续型批处理排序问题中机器可以 我们把在同一机器中按照同一加工模式(如加热炉中的加热制度 进行加工的相邻工件称为一个批 与传统间隙型批处理机排序问题属于同批的工件批进批出的方式不同,