（计算机应用技术专业论文）基于剩余函数的jobshop调度算法的研究.pdf

呈尘堡耋三銮兰三茎至占耋堡鎏三 基于剩余函数的j o b s h o p 调度算法的研究 摘要 生产调度问题是自动化管理领域中一个十分重要的问题，而单件车间 ( j o b s h o p ) 调度问题是一个实际的生产调度问题。单件车间调度算法是当前 调度理论的重要研究内容之一，此项研究既可以促进调度理论的发展及其相 关问题的研究，又可以使企业实现生产计划的动态调整。 j o b s h o p 调度问题是一类具有次序约束和资源约束的组合优化问题， 是一个典型的n p 难题，而非标准j o b s h o p 调度问题，由于放宽了资源约 束的条件，因而具有更大的寻优空间，从而增加了问题的难度。理论上已经 汪明要在多项式时间复杂度内对这一类问题找到全局最优解是不可能的。本 文通过对j o b s h o p 调度问题和非标准j o b s h o p 调度问题的深入分析和研 究，根据问题的特点，提出了两种适用于工程实际的算法基于剩余函数 的j o b s h o p 调度算法和非标准j o b s h o p 调度的效率算法，它们均可以在多 项式时间复杂度内寻得较优解。论文分别从以下几方面进行论述。 首先，论文对调度问题及其研究现状进行全面综述，阐述基于剩余函数 的j o b s h o p 调度算法以及非标准j o b s h o p 调度的效率算法的优越性。 其次，论文给出基于剩余函数的j o b s h o p 调度算法以及非标准j o b s h o p 调度的效率算法的详细描述，包括j o b s h o p 调度问题和非标准j o b s h o p 调度问题在数学上的描述、目标函数、算法描述和调度实例。 最后，论文根据生产中的实际情况，提出一类更实际的调度问题多 部套相关工件的j o b s h o p 调度问题，并给出求解算法。 关键词单件车间调度；目标函数；调节算法；启发式算法 竺尘堡型三查兰三兰丝三兰竺兰兰 r e s e a r c ho nj o b s h o ps c h e d u u n g a l g o r i t h mb a s e do n r e m a i nf u n c t i o n a b s t r a c t t h ep r o d u c t i o ns c h e d u l i n gp r o b l e mi sv e r yi m p o r t a n ti nt h ed o m a i no f a u t o m a t i cm a n a g e m e n t ，a n dj o b - s h o p s c h e d u l i n gp r o b l e m i sa p r a c t i c a l p r o d u c t i o ns c h e d u l i n gp r o b l e m j o b s h o ps c h e d u l i n ga l g o r i t h mi so n eo ft h e i m p o r t a n tp r o b l e mo fs c h e d u l i n gt h e o r y ，w h i c hc a nn o to n l yp r o m o t et h es t u d yo f s c h e d u l i n gt h e o r y b u ta l s om a k et h ep r o d u c t i o np l a n so fe n t e r p r i s er e a s o n a b l e j o b - s h o ps c h e d u l i n gp r o b l e mi s ac l a s s o fl a r g ec o m b i n a t o r i a lo p t i m u m p r o b l e mw i t hs e q u e n c ea n dr e s o u r c e sc o n s t r a i n t s ，w h i c hi sac l a s s i c a ln p - h a r d n o n s t a n d a r dj o b s h o ps c h e d u l i n gp r o b l e ms l a c k st h er e s o u r c e sc o n s t r a i n t s ，a n d g e t sl a r g e rs e a r c hs p a c e t h ef a c tt h a ti ti si m p o s s i b l et of i n dt h eg l o b a lo p t i m u m i np o l y n o m i a lc o m p l e x i t yh a sb e e np r o v e d i nt h i s p a p e r ，t h r o u g ht h ea n a l y s i s a n d s t u d y o f j o b s h o ps c h e d u l i n g p r o b l e ma n dn o n s t a n d a r d j o b - s h o p s c h e d u l i n gp r o b l e m ，j o b - s h o ps c h e d u l i n ga l g o r i t h mb a s e do nr e m a i nf u n c t i o n a n dn o n s t a n d a r dj o b s h o ps c h e d u l i n ge f f i c i e n c ya l g o r i t h ma r ep r o p o s e d t h i s a l g o r i t h ma d a p t st h ee n g i n e e r i n gp r a c t i c e ，a n di tc a nf i n dt h eb e t t e rs o l u t i o ni n p o l y n o m i a lc o m p l e x i t y t h em a i ni d e ao ft h i sp a p e ri sd e s c r i b e da sf o l l o w s f i r s t ，t h ea u t h o rb r i e f l yi n t r o d u c e st h es t u d y i n gl e v e lo fs c h e d u l i n gp r o b l e m a n dt h ea d v a n t a g eo fj o b - s h o ps c h e d u l i n ga l g o r i t h mb a s e do nr e m a i nf u n c t i o n a n dn o n s t a n d a r dj o b s h o ps c h e d u l i n ge f f i c i e n c ya l g o r i t h m s e c o n d ，t h cd e t a i l e dd e s c r i p t i o no fj s s a b r fa n dn j s s e aa r ep r e s e n t e d ， i n c l u d i n gt h ed e s c r i p t i o no fj s s pa n dn j s s p , c o s tf u n c t i o n ，d e t a i l e ds t e p so ft h e a l g o r i t h ma n dt h ei n s t a n c eo fs c h e d u l i n g a tl a s t ，ac l a s so fm o r ep r a c t i c a ls e q u e n c ep r o b l e mi so f f e r e d ，w h i c hi st h e n j s s pw i t hr e l a t e d o p e r a t i o n s m u l t i - c l a s s r e l a t e dj o b s h o p s c h e d u l i n g i i 堕尘堡些三查兰三兰竺兰些耋兰 p r o b l e m t h es o l v i n ga l g o r i t h mi sa l s op r e s e n t e d k e y w o r d sj o b - s h o ps c h e d u l i n g ；c o s tf u n c t i o n ；a d j u s t i n ga l g o r i t h m ；h e u r i s t i c s i i i 兰玺堡矍三奎兰三兰堡圭耋堡竺圣 1 1 课题的研究意义 第1 章绪论 在单件、多品种、小批量制造企业中，由于生产的产品品种多、批量小， 致使生产组织工作复杂，尤其是生产计划编排工作难度很大。生产计划的编制 往往凭借主观经验手工进行，致使计划编制时间长，计划的及时性、应变性 差，导致产品生产周期长，资金占用量大，机器利用率低，不能保证交货期， 从而影响了企业的经济效益及社会效益。 在生产计划编制中，j o b - s h o p 调度问题是一个重要的问题。对于这一类问 题的研究和解决，既具有理论意义又具有实用价值。对j o b s h o p 调度问题的最 初研究是寻找最优解【1 1 ，但遇到了很大的困难，而实际上，好的次优解也可以 满足问题要求，会达到理想效果。 本课题研究的目的是针对求解车间调度问题存在的问题，通过深入研究该 类问题的特性，设计并实现求解车间调度问题的算法基于剩余函数的j o b s h o p 调度算法( j o b s h o ps c h e d u l i n ga l g o r i t h mb a s e do nr e m a i nf u n c t i o n ，缩写 j s s a b r f ) 平i i 非标准j o b s h o p 调度的效率算法( n o n s t a n d a r dj o b s h o ps c h e d u l i n g e f f i c i e n c ya l g o r i t h m ，缩写n j s s e a ) 。 1 2 调度问题及其研究现状 先进的制造技术是一个国家、一个民族赖以繁荣昌盛的最根本技术，其研 究开发正以国家目标的高度在全球各主要工业国家蓬勃展开。制造业的发展经 历了2 0 世纪2 0 年代以前的手工制作、5 0 年代的柔性自动化、8 0 年代的及时 生产到今天的并行规划设计等阶段。 随着制造技术的发展，带来了许多的生产管理问题，其中最重要的是生产 的组织与计划问题。随着企业规模的扩大和全球更为激烈的市场竞争的形成， 经常发生由于计划不周、组织不当及多变化的市场和客户需求造成生产脱节等 现象，从而影晌生产进度，加长生产周期，劳动生产率下降，使企业的经营与 计划系统难以适应。然而，在竞争激烈的市场中，客户需求的多变是必然的和 f 常的，为了满足客户多变的需求，必然会引起生产计划的多变1 2 j 。在这种情 彗堡鎏型三奎兰三耋堡圭兰堡篁圣 况下，如何利用现有的资源( 加工能力) ，满足被加工任务所需的各种约束( 加工 次序、所需机器) ，使所有的任务能尽量如期完成( 性能指标最小) ，就成为十分 现实和迫切的问题，这就是生产调度问题。 生产调度，即对生产过程进行作业计划，作为一个关键模块，是整个先进 生产制造系统实现管理技术、运筹技术、优化技术、自动化与计算机技术发展 的核心。有效的调度方法和优化技术的研究与应用，是实现先进制造和提高生 产效益的基础和关键。改善生产调度方案，可大大提高生产效益和资源利用 率，进而增强企业的竞争能力。生产调度的研究主要可分为建模和调度算法设 计两方面，它是一个交叉性研究领域，涉及运筹学、数学、计算机工程、控制 工程、工业工程等多个学科。 车间调度问题( 也称工件排序问题) 是一个实际的生产调度问题。自从2 0 世 纪5 0 年代车间调度问题被开始广泛研究以来，经历了5 0 多年，产生了许多车 洲调度的类型3 卜【8 1 和求解方法 9 1 f 】3 i 。 1 9 5 4 年s m j o h n s o n 提出了m = 2 ( 2 台机器，_ 2 个工件) 时的算法【l ”，揭 开了研究工件排序问题的序幕，从此人们针对m 3 时的情况加以研究。1 9 7 5 年，越民义、韩继业在中国科学发表了“f 个零件在m 台机床上加工顺序 问题”【l5 】一文，从此推动了我国对工件排序问题的研究。1 9 7 9 年g a r e y 证明 了m 3 的车间调度问题是一个n p c ( n o - p o l y n o m i a l c o m p l e t e ) i h “。 对于求解车间调度问题，使用启发式方法【1 7 1 【1 9 1 和元启发式方法忙0 1 【2 1 1 均有 一些调度效果不同的结果。下面简单介绍应用这两类方法求解车间调度问题的 一些研究成果。 1 启发式方法包括数学规划法、组合优化方法、规则调度，人工智能 方法等。 ( 1 ) 数学规划法：包括线性规划( l i n e a rp r o g r a m m i n g ) j y 法( 2 2 1 、非线性规划 m o d l i n e a rp r o g r a m m i n g ) 法、动态规戈l j ( d y n a m i c a lp r o g r a m m i n g ) 法等，在这些 算法中，线性规划法作为一种精确调度方法，是较成熟的方法之一，但很多问 题不能以简单的线性关系精确表达，且变量多为整数，因此它的使用具有很大 的局限性。 ( 2 ) 组合优化方法：包括分支定界法( b r a n c ha n db o u n d ) 田l 、割平面法等， 其中较常用的是分支定界法。s a r i ns c 【2 4 】和p o t t s c n 1 2 5 提出了改进的分支定 界法，这类方法虽然从理论上能求得最优解，但由于其计算复杂性高以及搜索 效率低，难以解决大规模的调度问题。 ( 3 1 规则调度1 2 6 l ：p a n w a l ks se ta l 2 7 】总结了1 1 3 条规则，并将它们分为三 竺兰堡塞三查兰三耋堡圭兰堡芝兰 类：简单规则、复合规则、启发式规则。这一方法可以大大缩短寻优过程，具 有很强的使用价值。 ( 4 ) 人工智能方法【2 8 】【2 9 1 ：人工智能方法如专家系统的研制，为调度问题指 明了一条通向应用的途径，但其具有知识难于表达和难于获取等缺点。 2 元启发式方法包括模拟退火法、禁忌搜索法 3 1 】、神经网络方法、 遗传算法和蚁群算法等。 模拟退火法( s i m u l a t e da n n e a l i n g ) t 3 2 l 将组合优化问题与传统力学问题的热平 衡问题类比，它模仿了晶体结晶的冷却过程。 t a i l a n de 【j 驯提出了求解f l o w - s h o p 调度问题的禁忌搜索( t a b us e a r c h ) 算 法，l a g t m am 1 3 4 j 最早将禁忌搜索策略应用于j o b s h o p 调度问题中，为了更有 效地搜索解空间。 张长水、沈刚、王凌、郜庆路、李小平等用神经网络方法( n e u r a l n e t w o r k ) 3 5 】1 3 6 】、遗传算法( g e n e t i ca l g o r i t h m ) 3 7 1 4 6 】和蚁群算法( a n tc o l o n y a l g o r i t h m ) 4 7 卜侧等算法求解车间调度问题均能高效地求得较优解。 1 3 调度算法的优越性 理论上已经证明在多项式时间复杂度内对j o b s h o p 调度问题找到全局最 优解是不可能的，为了得到在工程上可行的、有效的算法，构造了两种调度算 法一基于剩余函数的j o b s h o p 调度算法和非标准j o b s h o p 调度的效率算 法，分别用来求解j s s p 和n j s s p ，其主要思想是通过追求各工件的均衡推进 和各机器的均衡使用来达到使生产周期尽可能短的目的。 调度算法有以下几方面的优点： 1 算法直接使用工时工序表的原始数据，而无需对数据进行额外加工； 2 算法得到的结果都是可行解，因而无需判断结果的有效性； 3 算法具有多项式时间复杂度，效率高，适于工程上使用。 哈尔滨理工大学工学硕士学位论文 第2 章调度问题描述 2 1 调度问题及其描述 调度问题通常是指对生产过程的作业计划，比如工件在机器上的加工顺 序、生产批量的划分等。就生产方式而言，调度问题可分为开环( o p e ns h o p ) 车 间型和闭环( c l o s e ds h o p ) 车间型。开环调度问题，也称加工排序问题，它本质 上只研究工件的加工顺序。闭环调度问题，除研究工件的加工顺序外，还涉及 各产品批量大小的设置。显然，闭环调度问题较开环调度问题要复杂。 调度问题中，通常一个工件z 包含n i 个操作( d j 。，0 f ：，瓯， ，每个操作0 。 的加工时间或需求为“。若碍= 1 ，则工件以仅包含一个操作q ，简记其加工 时间为只。称工件z 的第1 个操作可执行的时刻为释放时间或准备时间 ( r e l e a s ed a t e ) ，记为。记加工操作0 “的机器集为。 m l ，m 2 ，m 。) ，0 可以在。中任何一台机器上加工。 若同一机器上既没有任何两个时间区间重叠，也没有分配给同一个工件的 任意两个时间区间重叠，并且满足调度问题的一些特殊工艺约束，则称一个调 度为可行( f e a s i b l e ) 调度。进而，称使得调度准则或指标最优的可行调度为最优 ( o p t i m a l ) 调度。 通常，工件加工特性可用六元组= ( 届，屈，屈，局，屈，屈) 来表示，其中 1 届用来表示加工方式，包括抢占式( p r e e m p t i o n ) 或非抢占式( n o n p r e e m p t i o n ) 。其中，抢占式加工中操作在加工过程中可以被打断，再在原机器 或别的机器上重新开始：非抢占式加工则一旦操作开始，直到加工完毕，不能 被其他加工打断。通常，记抢占式加工为届= p m t n ，而非抢占式加工则不在 中出现届。 2 晟用来表示工件间的加工优先关系( p r e c e d e n c er e l a t i o n ) 。该优先关系可 以用非循环有向图g = 来表示，其中v = l 2 ，n ) 表示工件， e ，当且仅当，必须在以开始加工之前完成。若g = 为任意非 循环有向图，则记历= p r e c 。若g = 对应树，则记反= t r e e ，若 g = 对应链，则记屈= c h a i n ，若g = 对应的图具有系列一并行 ( s e r i e s p a r a l l e l ) 特性，则记屈= s p g r a p h 。若调度问题不考虑工件加工的优先 权，则中不出现廖。 哈尔滨理工大学工学硕士学位论文 3 屈用来表示工件的准备加工时间。若t 0 ，则记肛= ；若所有 r = 0 ，则卢中不出现从。 4 屈表示加工时间或操作数量的限制。若鼠记作p ，= l 或p , j = 1 ，则每个 工件( 或操作) 有1 次操作需求( 如加工时间为1 ) 。有时屈也可为一些具有明显 意义的别的值，如p i 1 ，2 ) ，4 = d 。 5 屈用来表示交货期信息。屈= z 表示工件有交货期要求，否则中不 出现屈。 6 成用来表示批量信息，即工件是否成批联合进行加工。批量调度中， 同批的各工件的完成时间等于该批量的完成时间，假定各批量的加工设置时间 相同且与加工顺序无关。成= p b a t c h 或成= s b a t c h 分别表示批量长度等于 该批量中所有工件的加工时间的最大值或加工时间之和。若不考虑批量调度， 则中不出现成。 j o b s h o p 调度闯题是具有特殊工件特性和加工环境的摄典型和最重要的调 度问题，通常是特殊的开环调度问题。 2 2 j o b s h o p 调度问题的一般描述 2 2 1 j o b s h o p 调度问题的一般描述 假设有n 个工件以，：，以要经过埘台机器m ，鸠，帆加工。一个工件 在一台机器上的加工称为一道工序。加工顺序要求表示工件在技术上的约束， 即工件的加工工艺过程，这是事先给定的。用加工顺序表示各台机器上工件加 工的先后次序，即次序约束。加工顺序是排序要解决的问题。当每个工件都有 其独特的加工路线时，要确定工件的加工顺序，这属于单件车间调度问题，即 j o b s h o p 调度问题( j o b s h o ps c h e d u l i n gp r o b l e m ，简称j s s p ) 。 为了便于对调度问题进行分析，建立数学模型，有必要作出一些一般的假 设条件，一般地说，j o b s h o p 调度问题满足以下八项假设： i 一个工件不能同时在不同的机器上加工，尽管一个工件有时可能包括 多个相同的零件，也不能将其分成几部分，同时在不同机器上加工； 2 不允许中断，当一个工序一旦开始加工，必须一直进行到完工，不允 许中断下来，插入其他工件； 3 每台机器同时只能加工一个工件； 4 每道工序只能在一台机器上完成： 哈尔浜理工大学工学硕士学位论文 5 对整个工件来说，在整个加工过程中采取平行移动方式，即当上一道 工序完工后，立即送下一道工序加工； 6 允许工件在工序间等待，允许机器在工件未到达前闲置； 7 工件数、机器数、加工时间已知，且加工时间与加工顺序无关： 8 工件加工技术上的约束事先给定。 2 2 2 非标准j o b - s h o p 调度问题 j o b s h o p 调度问题是类具有约束满足的调度问题，它要求在一定的机器 集上完成一批工件的调度加工，每个工件由若干道具有次序约束的不重叠的工 序组成，每道工序又有一定的加工时间和唯一的机器需求。 而在实际中广泛存在的平行加工问题，能够加工同一道工序的机器不唯 一，即存在一机器子集，其中的任意一台机器都能够加工该道工序。显然，此 类调度问题放宽了资源( 机器) 约束，从而扩大了寻优空间，因而增加了问题的 难度。 为了将问题理论化，将j o b s h o p 调度问题的八项基本假设做适当调整， 将4 改为： 4 + 每道工序可以在一台或多台机器上加工，即能够加工这道工序的机器 不唯一。 我们将此类j o b s h o p 调度问题称为非标准j o b s h o p 调度问题( n o n s t a n d a r d j o b s h o ps c h e d u l i n gp r o b l e m ，简称n j s s p ) 。 2 3 目标函数 衡量加工顺序优劣的标准应该是总费用最低。与调度有关的费用主要有三 项：工序等待费用、设备闲置费用和延误交货损失费用。g u p t a l 5 l j 曾提出这些 费用的计算方法。 用总费用最低为调度问题的目标函数是合理的。但是，这会使调度问题大 大复杂化，而且，事实上几乎不可能找到最优解。即使对于非常简单的目标函 数【5 2 】，求调度问题的最优解都是十分困难的，更何况象总费用这样复杂的目标 函数。因此只能把影响总费用的主要因素作为目标函数。按这样处理，可以提 出三类目标函数： 1 以工序的完工时间为尺度的目标函数。这类目标函数主要有最长完工 时间、最长流程时间、平均完工时间和平均流程时间； 哈匀 滨理工大学工学硕士学位论文 2 以完工期限为尺度的目标函数。这类目标函数主要有平均延误时间和 最大延误时间： 3 以设备利用程度为尺度的目标函数。若要充分利用设备，则要求正在 加工的工序的平均数最大或设备的平均空闲时间最小。 在研究调度问题时，经常要用到常规目标函数。常规目标函数是指那些为 工序完工时间的非减函数的目标函数。假设有两个加工顺序，其中一个顺序中 每道工序的完工时间都不迟于第二个顺序中每道工序的完工时间，则按常规目 标函数，第一个顺序一定不劣于第二个顺序。调度问题所追求的是常规目标函 数值最小。 定理2 1 若以工序最长完工时间为目标函数，则它是常规目标函数。 证明：设工件以( f - 1 ，2 ，n ) 的完工时间为c f ，r 是c l ，c 2 ，e 的函数， 工序最长完工时间为c m 。，c m 。= r ( c i ，c 2 ，c n ) = m a x c 1 ，c 2 ，c o ) 。当 c i c i ，c 2 c 2 ，e c o 时， r ( c 1 ，c 2 ，c o ) = m a x c i ，c 2 ，q m a x ( c l ，c 2 ，e1 = r ( c 1 ，c 2 ，q 因此，g 。是常规目标函数。 本论文中所讨论的目标函数仅限于常规目标函数。 2 4 本章小结 调度问题可分为开环( o p e ns h o p ) 车间型和闭环( c l o s e ds h o p ) 车间型。开环调 度问题，它本质上只研究工件的加工顺序。j o b s h o p 调度问题是具有特殊工件 特性和加工环境的最典型和最重要的调度问题，通常是特殊的开环调度问题。 本章首先对调度问题及其特性进行了描述，然后为便于对调度问题进行分 析，建立数学模型，而作出了八项一般的假设条件，接下来阐述了j o b s h o p 调度问题与非标准j o b - s h o p 调度问题的本质区别，同时给出了目标函数的描 述。 堕尘堡矍三奎兰三茎罂圭兰堡兰圣 第3 章j o b s h o p 调度算法 3 1 j o b s h o p 调度问题的数学描述 设有机器集m e c h i n e s = ( m ，鸠，m m ) 和工件集弘b s = “，j 2 ，以) 。其中 工件以有9 f 个具有次序约束的加工工序为厶，z ：，( 厶p 正：p p ) ， 工件z 第，道工序厶在机器巴( 0 m e c h i n e s ) 上加工，其加工时间为，设 s l 和用：，分别为工序z ，的开始时间和结束时间。则约束条件为： 1 每个工件的各道工序的加工顺序预先确定； 2 每道工序指定在唯一的机器上加工； 3 一个工件不能同时在不同的机器上加工； 4 一台机器仅能加工一个工件的一道工序； 5 允许工件在工序间等待，允许机器在工件未到达前闲置； 6 每个工件的第一道工序的实际开始时间大于等于0 ，即 s f l o ( i = 1 ，2 ，”) ； 7 任何一个工件的前一道工序加工完成后方能进行后一道工序的加工， 即s z + l 踢+ t , j ( i = l ，2 ，n ；j = 1 ，2 ，q j 1 ) ； 8 在同一台机器上，一个加工任务完成之后方能开始另一个加工任务， 即当= 0 时，田_ s 巧十五或蹋田i + 。 调度目标是确定各加工工序的开始时间和结束时间，使各工件尽早加工完 成。 3 2 目标函数 3 2 1 剩余函数 设工件以第1 ，道工序毛在机器0 上加工，其加工时间为乃，则工件z 的 ， 前，道工序的总加工时间为：t o t o l , _ l = ( f = l ，2 ，n ；l = 1 ，2 ，q j ) 。 h = l ：一： 堕垒堡垩三奎兰三兰堡圭兰堡丝兰 工件的总加工时问为：t o t o l = 毛( f = l ，2 ，h ) 。 引入剩余函数( r e m a i nf u n c t i o n ) r ( i ，) ：用实数，( f ，_ ，) ( o r ( i ，) 1 ) 作为度 量工件，的加工剩余率： t o t o l ( 7 ，) 2 1 一斋( k 1 厶棚舻j l ，2 ，q ) ( 3 - 1 ) 对加工剩余率做如下解释： 假设r ( i l ，j 1 ) 为工件t 在加工工序z l f l 时的加工剩余率，r ( i 2 ，j 2 ) 为工件 以z 在加工工序以：，2 时的加工剩余率，( 1 s i l , i 2 _ r ( i 2 ，j 2 ) ，则表明工件厶在加工完工序厶n 后剩余的部分比工件_ ：在 加工完工序z ，后剩余的部分多。 因此为了降低总体加工剩余，从而提高加工速度，应优先安排加工剩余多 的工件，先加工，安排加工剩余少的工件z ，后加工。因而，从总体上来说， 应优先加工满足m a x r ( i ，朋的工件。 为了尽快地完成总体加工任务，应选用式( 3 2 ) 作为工件加工的目标。 r a i nm a x r ( ，) ( 3 2 ) 3 2 2 最长加工路径 设伟为机器坂( = l ，2 ，m ) 加工的工件数，为机器峨上最后一个加 工工件的结束时间，则m a x e k ) 为最长加工路径。 为了保证加工周期最短，应选用式( 3 3 ) 作为目标。 m i n m a x e _ m ) ( 3 3 ) 3 2 3 目标函数 综上所述，选用式( 3 4 ) 作为目标函数： m i n an ：l _ a x r ( i ) ) + ( 1 - a ) m a x ( 3 4 ) 这里口= 1 或0 。由此，基于剩余函数的j o b s h o p 调度算法包括初排算法和 调节算法两部分。 令口= 1 ，为初排算法，式( 3 4 ) 变为r a i n m a x r ( ，j ) ，以此为目标能够保证 各工件在各机器上按工件的工序要求均衡加工。 令口= 0 ，为调解算法，式( 3 4 ) 变为m i n m a x 民 ，以此为目标能够保证 哈尔滨理工_ 人学工学硕士学位论文 加工周期最短。 3 3 基于剩余函数的j o b - s h o p 调度算法 3 3 1 建立队列 由3 1 节所描述的问题可知，存在两个队列： 第一为工件队列。将每个工件的各加工工序按其次序约束排列为队列 l i s t j , ( i = 1 ，2 ，n ) 。在这个队列中，各工序的加工时间互不重叠，即前一道工 序加工完成后方能进行后一道工序的加工。 第二为机器队列。将每台机器上加工的工件按实际加工顺序排列为队列 l i s t m 。( k = 1 2 ，m ) 。在这个队列中，各工序的加工时间互不重叠，即在同一 台机器上，一个加工任务完成之后方能开始另一个加工任务。 所出，在计算各工序的实际开始时间和结束时间时，必须严格地保证这两 个队列的完整性，不能破坏其中的任意一个队列。这样，调度问题就变成了如 何把l i s t j 中的各工序插入到 中，并保证目标函数的值最优或近似最,listmk 优。 3 3 2 初始化 步骤a ) 建立工件队列：根据各工件的各道工序的次序约束，为每个工件建 立一个工件队列上f s “( f _ l 2 ，n ) 。 步骤b ) 根据式( 3 1 ) 计算每道工序的，( f ，) ，则对于各工件以( i = l 2 ， ) 满 足m a x r ( i ，) 的工序必在队首。 步骤c ) 为每个工件队列工捃以( i = l 2 ，”) 设置一个可移动的指针 p o i n t ( i 1 ，其初值指向z i j t j 的队首。, 在排序的过程中，每安排一道工序，p o i n t ( i ) 就后移一次，指向下一道 工序。在某一时刻，对于各工件( i = 1 ，2 ，n ) ，没有被安排的各工序中 满足m a x ( r ( i ，肼的工序必为p o i n t ( i ) 指向的工序。所以，p o i n t ( i ) 总是指向工 件，的下一个要安排的工序。 步骤d ) 建立机器队列：由于初始状态各机器均未被分配，因此所有机器队 列l i s t m k ( k = l ，2 ，m ) 均置空n u l l ，而且各机器眠加工的工件数n k 均置0 ， e 。甥置0 。 哈尔滨理丁大学工学硕士学位论文 3 3 3j s s a b r f 的初排算法 口= 1 时，为初排算法。 算法3 1 j s s a b r f 初排算法 步骤a ) 根据式( 3 2 ) ，在指针p o i n t ( i ) ( f _ 1 2 ， ) 所指的各工序中选择满足 m a x r ( ，j ) 的工序，。若这样的以不唯一，则在其中选择满足m a x t o t o l , 的 工序，胪并移动指针p o i n t ( i ) ，使其指向下一道工序山+ 。 步骤b ) 若p ，= m k ，则将工序山插入到机器队列l i s t m k 的队尾。 步骤c ) 分别依据式( 3 - 5 ) 、( 3 - 6 ) 和( 3 7 ) 计算工序一，的开始时间s 巧、结束时 间f z ，和等待时间啊，。 s 毛= m a x 。瓦。) ( 3 5 ) f z ，= s z + z ， ( 3 - 6 ) 阡乃= 蹋一。 ( 3 7 ) 步骤d ) n k = n k + 1 ，并= f 巧。 步骤e ) 判断是否所有p o i n t ( i ) ( i = 1 ，2 ，h ) 指向工件队列队尾n u l l ，若 是，则算法结束，否则，转步骤a ) 。 3 3 4j s s a b r f 的调节算法 盘= 0 ，为调节算法。 设为机器m 完成第l - 1 次加工也后要进行第f 次加工正，的等待时 间，即：= 啊，( 七= 1 2 ，m ；l = 1 2 ，仇) ，则 ：艺( + 巩) ：n k + n kz7(3-8) i = 11 = 1 1 = 1 设g i n i = m a x ) ，则 民，= ( 彬f + ) = + ( 3 _ 9 ) 因为7 ：，为定数，所以 m i n e , ，) = m i n 窆形，十艺 = m i n 彬一h ( 3 _ 1 0 ) 从而m m e 。) m i n 彬，) ( 3 _ 1 1 ) 哈尔滨理工大学工学硕士学位论文 即 r a i n m a x e k , r a i n m a x ( 3 - 1 2 ) i = 1 在调解算法中以式f 3 1 3 ) 为目标。 生 m i n m a x ) ( 3 1 3 ) i = 1 算法3 2 j s s a b r f 调节算法 步骤a ) 求l = 毛。= m a x e 矗 。这里f 存在，但不一定唯。 步骤b ) 对某一i ，遍历机器队列l i s t m 。若彬，= o u = 1 ，2 ，_ ) ，则排序结 果最优，不可调解，转步骤h ) 。 步骤c ) 求= r a i n ) 但0 的工序，。 步骤d ) 设机器m 上第次加工的工序为j 。，第，+ 1 次加工的工序为 j 内，若工序j p v 的前一道工序以v 一，的结束时间s t , v 一， s ，则交换j m 与 ，。在机器m 。上的加工次序。 步骤e ) 重新计算机器队列l i s t m j 中工序，m 及其以后各工序的开始时间、 结束时间和等待时间，并更新，l = 。 步骤f ) 求巨。，= m a x 。 。 步骤g ) 若e l , 。l ，则l = 毛，转步骤b ) ，否则不再调解。 步骤h ) 算法结束。 3 3 5 算法时问复杂性分析 由j o b s h o p 调度问题描述中约束条件( 4 ) 知，m 2 q ( i = 1 ，2 ，, ) 。 在初始化中，步骤a ) 和步骤b ) 均需0 即肌) 时间，步骤c ) 需0 ( ) 时矧，步 骤d ) 需o ( m ) 时间，因此，初始化所需要的总时间为o ( n m ) 。 在j s s a b r f 初排算法中，步骤a ) 需o ( n ) 时间，步骤b ) 、步骤c ) 和步骤d ) 均需d ( 1 ) 时间，而且步骤a ) 、b ) 、c ) 、d ) 均需重复d ( m ) 次，因此，初排算法所 需要的总时间为o ( n x m ) 。 在j s s a b r f 调节算法中，步骤a ) 需0 ( 肌) 时间，步骤b ) 和步骤c ) 均需 d ( ”) 时间，步骤d ) 均需o ( 1 ) 时间，步骤e ) 需d ( 玎) 时间，步骤f ) 需o ( m ) 时间， 而且步骤b ) 、c ) 、d ) 、e ) 、f ) 均需重复o ( m ) 次，因此，调节算法所需要的总时 间为o ( n x m + m x m ) 。 由此，j s s a b r f 算法的时间复杂性为o ( n m + m x m ) 。 在实际生产中，加工能力是有限的，即m c 。，而且m r ( i ，j + 1 ) ，所以保证了工序，在z 。之前加工，这样就保证了 每个工件加工工序的偏序关系，符合加工工艺的要求。 2 具有均衡性。 在初排时使用剩余函数r ( f ，j ) ，使得所有工件能够相对均衡加工，使最长 加工路径较短。 3 加工周期较短。 在调解算法中以m i n m a x ) 为目标，保证了最长加工路径最短，从而进 一步缩短加工周期。 第4 章非标准j o b s h o p 调度算法 4 1 非标准j o b s h o p 调度问题的描述 设有机器集m e c h i n e s = m i ，鸠，坂) 和工件集j o b s = j i ，j 2 ，以) 。其中 工件z 有q 个具有次序约束的加工工序为一。，以：，如，( z 。pz ：p p 以。) ， 工件t 第，道工序以，具有加工时间i ，和机器需求子集 d ( 厶) ( d ( 以，) m e c h i n e s ) ，设工序，的开始时问和结束时间分别为s l ，和 f l ，加工机器为p 。则约束条件为： 1 每个工件的各道工序的顺序预先确定。 2 每道工序可在机器需求子集的任一台上加工。 3 一个工件不能同时在不同的机器上加工。 4 一台机器一次仅能加工一道工序。 5 允许工件在工序间等待，允许机器在工件未到达前闲置。 6 每个工件的第一道工序的实际开始时间大于等于0 ，即 s t , 。o ( i = 1 ，2 ，”) 。 7 任何一个工件的前一道工序加工完成后方能进行后一道工序的加工， b 口s l 一s 瓦一瓦o ( i = 1 2 ，嘣j = 1 ，2 ，q 一1 ) 。 8 在同一台机器上，一个加工任务完成之后方能开始另一个加工任务， 即，当= 0 时，一s r o 一乃0 或踢一s 一0 。 调度目标是确定各加工工序，。，的机器只，并求解其开始时间s 互，和结束时 问啊，使各工件尽早加工完成。 对于非标准j o b s h o p 调度问题，除了考虑j o b s h o p 调度问题的因素外， 特别应注意的是，必须使得能够完成相同操作的几台机器上所承担的任务量具 有“均衡性”，即在任一时刻，不能出现下面的情况：一台机器上有工件等 待，而能够完成同一操作的另一台机器空闲。 哈尔滨理工大学工学硕士学位论文 4 2 目标函数 4 2 1 以各机器均衡利用为目标 由于在非标准j o b s h o p 调度问题中，能够) j nn - 同一道工序的机器不唯 一，因此必须使得能够完成相同操作的几台机器所承担的任务具有均衡性，为 此引入机器的调度效率： 为每台机器设一个调度指针厶( k = l ，2 ，m ) ，它始终记录着 以上最后一 道工序的结束时间。 用厶( f ，) 表示按照式( 3 2 ) 选择加工厶时，机器 以上最后一道工序的结束 时间。 令k 。( f ，) = m a x & ( i ，朋，定义机器坂上的调度效率函( s c h e d u l i n g e f f i c i e n c yf u n c t i o n ) e k ( f ，) ： 牝舻l 一瓦z k ( 而i , j ) ( 4 - i ) j i 。 可见，e j 。( f ，) 反映了能够加工工序以的机器峨承担任务的能力，则为了 使能够加工工序一，的几台机器上的任务具有均衡性，应优先选取承担任务的能 力最大( 即满足m a x e k ( i ，肼) 的机器来加工以。 若使承担任务的能力最大的机器的承担任务的能力最小，则可保证各台机 器上的任务量尽可能均衡。因此选用式( 4 2 ) 作为目标函数。 m i nm a x e k ( i ，肼 ( 4 - 2 ) 4 2 2 以最长加工路径最短为目标 设怫为机器帆( 七= l ，2 ，肌) 加工的工件数，为机器坂上最后一个加 工工件的结束时间，则m a x e 厶) 为最长加工路径。 若使最长加工路径最短，则可保证加工周期最短，应选用式( 4 3 ) 作为目 标。 m i n m a x 女) ( 4 - 3 ) 4 2 3 目标函数 令( f