（计算机应用技术专业论文）可动态生成具有优先级工序集的jobshop调度算法.pdf

哈尔滨理t 大学t 学硕l ：学位论文 可动态生成具有优先级工序集 的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 调度；虚拟加工树；备选集；动态调整；路径长度 哈尔演理t 大学t 学硕l ：学位论文 a na l g o r i t h mo fj o b s h o ps c h e d u l i n g p r o b l e mw i t hd y n a m i cc o l l e c t i o n o f o p e r a t i o nw i t hp i u o r i t y a b s t r a c t t o d a ym a n yr e s e a r c h e r sa t t e m p tt o s o l v ej o b s h o ps c h e d u l i n gp r o b l e m o s s p ) b yd i f f e r e n tm e t h o d s b u tb e c a u s et h ep r o b l e mi s s oc o m p l e xt h a te a c h m e t h o dh a si t so w ns h o r t a g e f o ri n s t a n c et h em e t h o di sm o r ec o m p l e xi t s e l fo r t h er e s u l ti sl e s so p t i m i z e d i nt h ed i s s e r t a t i o nan e wa l g o r i t h mf o rj s s pi sd e s i g n e dw h i c hi sm o d e l e d t h ea d v a n c e dt h e o r i e so fp r o c e s s ( t h r e a d ) s c h e d u l i n gi n o p e r a t i n gs y s t e m o p e r a t i o n si nj s s ph a v ec o n c u r r e n c ea n ds y n c h r o n i s m s t ot a k eg o o da d v a n t a g e o ft h ec h a r a c t e r so fo p e r a t i o n sa n dr e s o u r c e 血a c h i n e ) a r ea b l e t oi n c r e a s e m a n u f a c t u r i n ge f f i c i e n c y a n dm a k et h et o t a lm a n u f a c t u r i n gt i m el e s s f i r s t l ya m a n u f a c t u r i n gt r e ei s c o n s t m c t e da c c o r d i n gt oj o b t h e nt h e o r i e so fp r o c e s s ( t h r e a d ) s c h e d u l i n gi no p e r a t i n gs y s t e ma r em o d e l e da n dt h ep r i o r i t yo fo p e r a t i o n i ss e tb yo p e r a t i o n sl e v e l a l lo p e r a t i o n sa r es e p a r a t e di n t on o n s c h e d u l a b l e o p e r a t i o na n dp r e - s c h e d u l a b l eo p e r a t i o na n ds c h e d u l a b l eo p e r a t i o n a no p e r a t i o n c o l l e c t i o nf o rs c h e d u l i n gi sg e n e r a t e d e x c e p ti nt h ec o n d i t i o nt h a ts o m ew o r k i n g p r o c e d u r e sn e e dd y n a m i ca d j u s t i n g ，f r o mt h ev e r yb e g i n n i n gt ot h ee n do n e p r i n c i p l em u s tb ef o l l o w e dt h a ti st ok e e pt h em a c h i n eb u s y , w h i c hm e a n st h a t t h ej o bi sd i s p a t c h e dt ot h em a c h i n ei n c e s s a n t l ys ol o n ga st h em a c h i n ei si d l e w h e ns c h e d u l i n go p e r a t i o n ，s o m eo p e r a t i o ni ss e l e c t e df r o mo p e r a t i o nc o l l e c t i o n a n ds c h e d u l e dt oam a c h i n e w h e ns e l e c t i n go p e r a t i o n ，f o u rs t r a t e g i e sm u s tb e f o l l o w e d a f t e ra no p e r a t i o ni ss e l e c t e d ，t h en o d eo ft h eo p e r a t i o ni sd e l e t e df r o m m a n u f a c t u r i n gt r e ea n dt h e nan e wo p e r a t i o nc o l l e c t i o ni sg e n e r a t e da g a i n w h e n t h ec o l l e c t i o ni se m p t y , t h ej o bi sf i n i s h e d 1 i 堕堡堡矍三查兰三兰竺：兰竺篁塞 am e t h o do fc o n s t r u c t i n gv i r t u a lm a n u f a c t u r i n gt r e ef o rm u l t i - j o bj s s po r d y n a m i cj s s pi sd e s i g n e d a n dt h ep r o b l e mi ss i m p l i f i e d w h e ns c h e d u l i n g ， o p e r a t i o ni ss c h e d u l e df r o mv i r t u a lm a n u f a c t u r i n gt r e eb yt h ef o u rs t r a t e g i e s b y i n s t a n c ea n dc o m p a r i s o nt h ea l g o r i t h mh a ss a t i s f i e dc o m p l e xa n dc a ng e tg o o d r e s u l t s ot h ea l g o r i t h mh a si m p o r t a n tv a l u eb o t hi np r a c t i c ea n dt h e o r y k e y w o r d s j o b s h o ps c h e d u l i n g ；v i r t u a lm a n u f a c t u r i n gt r e e ；o p e r a t i o n c o l l e c t i o n ；d y n a m i c a d j u s t m e n t ；p a t hl e n g t h i n 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文可动态生成具有优先级工序集 的j o b s h o p 调度算法，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位 期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包 含他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均 已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：l 汤办日期：乃7 年多月厂口日 哈尔滨理工大学硕士学位论文使用授权书 可动态生成具有优先级工序集的j o b s h o p 调度算法系本人在哈尔滨理 工大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果 归哈尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完 全了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关 部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可 以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密日。 ( 请在以上相应方框内打) 作者签名：彳易办 日期：力d 7 年多月，。日 导师签名：啪盈孩开期：z 呻年；月o 同 堕玺堡矍三查兰二兰堡! ：兰堡丝三 第1 章绪论 1 。1 j o b s h o p 调度问题的背景 1 9 5 4 年，j o h n s o n 开始研究2 个和3 个工序的带准备时间的流水车间 ( f l o w - s h o p ) 调度问题，此后，对于生产调度问题的建模和求解，一直是理 论界的热点。随蓉对于调度问题的深入研究，人们发现可以将调度问题的理论 模型应用于许多领域，如计算机系统、生产管理、车辆管理、火车的时刻表制 定、物流、排课以及企业的人力资源管理。随着社会的不断向前发展，竞争的 加剧，制造业中普遍面i 临的问题不断地突现出来。如何在有限的生产资料条件 下，以最短的生产周期、最小的成本将产品制造出来以满足客户的需求是每一 个制造商不断追求的目标。如何运用有限的资源，降低产品的生产成本，缩短 产品的制造周期，保证按时交货，提高企业信誉，赢得更多的客户，成为制造 厂商在竞争生存的一个重要的条件。有效的利用现有的资源，合理的制定企业 和车间生产计划，是达到这个目标的关键。 1 2 j o b s h o p 调度问题概述 1 2 1 j o b s h o p 调度问题的含义 车间调度问题一般可以描述为：生产车间有m 台机器n 个作业，且每个 作业有多道工序，每道工序在某个机器上加工。问如何为这些作业分配机床， 使某个生产指标( 如生产周期) 最优。 每一台机器在某个时刻只能加工某个作业的某道工序，称为占用约束，同 时每个作业只能在上道工序加工完成后才能开始下一道工序的加工，称为顺序 约束“。车间调度问题的决策内容包括分配决策( 作业的加工顺序) 和时间决 策( 作业各工序的加工时间) 以及路径决策( 作业工序各加工设备的分配) 。 工厂中之所以会出现车间调度问题，主要是因为生产资源受到了制约而形 成的。设想，有n 个不同的作业，就至少有n 条不同的工艺加工路线，如果 有足够多的机床设备和其它生产资源分配给每条工艺加工路线，即每一道工序 独立占用一台机床设备和相应的生产资源，那么一切都会井然有序，也就不存 晴尔演理t 大学t 学硕i 。学位论文 在调度问题。但是，对于企业主来说，这样必定会造成资源浪费和制造成本的 增加，于是出现了工件和相应的工序数量多于机床设备和其它生产资源的情 况，车间调度问题也就自然而然的出现了。 总的说来，车间调度就是对一个可用的加工机床集在时间上进行加工任务 集分配，以满足一个性能指标集。从数学规划的角度看，车闻调度问题可表达 为在等式或不等式约束下，对目标函数的优化。典型的车间调度问题包括一个 要完成的作业集( 工件集) ，每个作业由一个操作集( 工序集) 组成，各操作 的加工需要占用机床或其它生产资源( 人员、刀具和辅助资源) ，并且必须按 一些可行的工艺次序进行加工。每台机床可加工工件的若干操作，并且在不同 的机床上能加工的操作集可以不同。调度的目标是将作业合理地安排到各机床 以及合理地使用其它生产资源，并合理安排作业的加工次序和加工时间，使约 束条件被满足，同时优化一些生产性能指标。 1 2 2 j o b s h o p 调度问题的特点 1 复杂性车间调度问题的复杂性主要表现在生产环境和调度的优化计算 两方面。首先，车间中工件、机器、操作人员和搬运系统之间相互影响、相互 制约。每个工件又要考虑它的加工时间、安装时间和操作顺序等因素，因而加 工环境相当复杂。其次，在各种条件的综合影响下，车自j 调度实质上是一个在 若干等式和不等式约束下的组合优化问题，从计算时间复杂度看是一个n p h a r d 问题，随着调度规模的增大，问题可行解的数量呈指数级增加，因而求解 非常困难。在现有计算条件下，一般优化方法对于车间调度问题是低效甚至是 无能为力的。 2 多约束性通常情况下车间调度受到工件工艺路线的约束，各道工序 的先后关系不能颠倒。同时，还受到各种资源的约束，如加工机床、操作工 人、运输小车、刀具以及其它辅助生产工具等。 3 离散性在生产车间中，工件的加工、储存和运输发生在不同的时间和 资源上，并且任务的到达、订单的更改、设备的增添和故障等都是离散事件。 因此，车间生产系统可以看作一个典型的离散系统，这样，就可以用数学规 划、离散系统建模与仿真的方式，通过排序理论研究车间调度问题。 4 动态随机性在真实的车白j 生产环境中有很多随机和不确定因素，如工 件到达时间的不确定性，实际工件的加工时间也有一定的随机性，而且系统中 常有突发偶然事件如紧急任务插入、交货期改变、订单被取消、设备故障或 哈尔滨理t 人学t 学硕l 学位论文 修复等。因此生产调度过程是一个动态的随机的过程。 5 多目标性实际的车间调度问题待优化的性能指标有很多，例如生产周 期、平均流通时间、平均延误率、设备利用率等，而且这些目标之间往往会发 生冲突。作者认为所有的性能指标最终都是为了减少成本，故一个可以适应不 同的任务类型和规模的通用调度系统，应该是基于成本目标的系统。遗憾的 是，迄今为止还没有一个通用并且实用的车间调度系统。 1 2 3 j o b s h o p 调度问题的分类 调度问题是一类重要的组合最优化问题，它是利用一些处理机( 机器或资 源) ，最优地完成一批给定的任务或作业。在执行这些任务或作业时需要满足 某些限制条件。最优地完成是指使目标函数达到最小“。调度问题一般可从以 下几个方面进行分类： 1 加工复杂度可分为单机、多台并行机、f l o w - s h o p 、j o b s h o p 和 o p e n - s h o p 。单机调度比较简单，所有的作业都在一个机器上加工。多台并行 机的调度问题更复杂，因而优化问题更突出。f l o w - s h o p 是指所有作业在处理 机上加工的顺序相同。j o b s h o p 是最一般、最复杂的问题，每个作业的加工顺 序不同。o p e n s h o p 是指每个作业可以按任意的顺序加工。 2 性能指标可分为基于调度费用和调度性能两大指标。 3 生产环境特点可分为确定性调度和随机性调度。 4 加工特点可分为静态调度和动态调度。静态调度是指所有待安排加工 的工作均处于待加工状态，因而进行一次调度后，各作业的加工被确定，在以 后的加工过程中就不再改变；动态调度是指作业依次进入待加工状态，各种作 业不断进入系统接受加工，同时完成加工的作业又不断离开，还要考虑作业环 境中不断出现的动态扰动，如作业的加工超时、设备的损坏等，因此动态调度 要根据系统中作业、设备等的状况，不断地进行调度。 1 3 j o b s h o p 调度问题的研究方法 一般的调度问题都是对具体生产环境中复杂的、动态的、多目标的调度问 题的一种抽象和简化，因而一个调度算法可以通过其如何表述这些复杂性进行 分类。由于实际中生产环境是千差万别的，所以一个调度算法就应该根据其是 否能适合对应的生产环境的重要特征进行评估。在对调度问题进行研究的方法 上，最初是集中在整数规划，仿真和简单的规则上“1 。运用这些方法，不是 哈尔滨理t 夫学t 学硕 学位论文 调度结果不理想就是难以解决复杂的问题。随着各种新的相关学科与优化技术 的建立与发展，在调度领域也出现了许多新的优化方法，比如神经网络、模 拟、退火法、遗传算法、禁忌搜索法等，这使得调度问题的研究方法向多元化 方向发展。以下是对调度算法的总结： 1 运筹学方法运筹学方法是将生产调度问题简化为数学规划模型，分枝 定界法或动态规划算法就是采用基于枚举思想解决调度最优化或近优化问题的 方法，属于精确方法”1 。但是，对于复杂的问题，这种纯数学方法具有模型抽 取困难、运算量大、算法难以实现的弱点，对于生产环境中的动态调度实现复 杂，解决不了动态及快速响应市场的问题。因此，尽管这类方法从理论上能求 得最优解，并不能使其获得真正的实用。 2 基于规则的方法对生产加工任务进行调度的最传统的方法是使用调度 规则。因其调度规则简单、易于实现、计算复杂度低等原因，能够应用于动态 实时调度系统中，许多年来一直受到学者们的广泛关注。许多学者在这方面已 进行了探索及大量研究工作，总结了1 1 3 条规则，并将它们按形式分为了三 类：简单规则、复合规则、启发式规则”1 。但是近十年的研究表明并不存在一 个全局最优的调度规则，它们的有效性依赖于对特殊性能需求的标准及生产条 件。它是局部优化方法，难以得到全局优化结果，并且不能对得到的结果进行 次优性的定量评估。而且寻找调度最优算法本身是一个n p 完全问题，这些使 得基于规则的调度思想己不能适合实际应用的要求。 3 控制理论方法它是一种比较适合定量地定义基本问题，但还没有形成 一套有效的调度模型表达、分析设计的技术。缺点是：模型描述能力有限，建 模时不得不对真实环境进行大量的简化，求得最优解的时自j 是随着问题规模增 大而呈指数规律增长”1 。因此也只适合对小规模的系统求解。 4 基于人工智能的方法人工智能( a r t i f i c i a li n t e l l i g e n c e ，a i ) 方法是通 过提高调度方法的智能而解决各类生产调度问题方法的总称。它主要利用启发 式规则来引导搜索并提供有效的搜索程序去寻求复杂问题的较优解。总的来 说，主要包括智能调度专家系统、基于智能搜索的方法及基于多代理系统 ( m u l t i a g e n ts y s t e m ，m a s ) 的合作求解的方法等。其中，智能调度专家系 统是人工智能应用的体现。由于专家系统中知识获取和推理速度这两个瓶颈， 使得神经网络逐渐被采用，但还存在训练速度慢、探索能力弱等缺点。基于多 代理技术的合作求解方法是较新的智能调度方法，它提供了一种动态、灵活、 快速响应市场的生产调度机制”。它以分布式人工智能( d i s t r i b u t e da r t i f i c i a l i n t e l l i g e n c e ，d a i ) 中的多代理机制作为新的生产组织与运行模式。通过代理 哈尔滨理t 人学t 学硕f 岸位论文 ( a g e n t ) 之间的合作以及m a s 协调来完成生产任务的调度，并达到预先规定 的生产目标及生产状态。在这种研究方法中，在a g e n t 内部也可采用基于规则 及智能推理相结合的混合方法，来构造基于m a s 的生产调度系统。 5 基于离散事件动态系统的解析模型方法离散事件动态系统( d i s c r e t e e v e n td y n a r n i es y s t e m ，d e d s ) 是指由离散事件按照一定的运行规则，相互作 用而导致系统状态演化的一类动态系统。离散事件驱动状态的演化，而状态演 化又导致新的事件的出现。这种离散事件的错综复杂的相互作用，构成了系统 的动态特性，此类动态特性难以用传统的微分方程或差分方程来描述。在八十 年代前后，随着计算机技术、信息技术、机器入技术等的发展完善以及广泛应 用，在通讯、制造、交通管理、军事指挥系统等领域相继出现了一些反映技术 发展方向的复杂人为系统，如大规模计算机网络、柔性制造系统、军事指挥系 统等。在这些系统中存在着大量的离散事件过程，它们无法由物理和其它自然 科学的定律描述，而是服从于人为的一些复杂规则，这些离散事件的相互作用 构成了系统的演化过程。由于制造系统是一类典型的离散事件系统，因此，可 以用研究离散事件系统的解析模型和方法去探讨车白j 调度问题。 6 系统仿真的方法基于仿真的方法不单纯追求系统的数学模型，侧重对 系统中运行的逻辑关系的描述，能够对生产调度方案进行比较评价，分析系统 的动态性能，并选择系统的动态结构参数。仿真方法用于调度的优点有：实验 时间短，不受时空限制；可以测试不同调度决策的性能，进而选择较优的调度 决策；能够对用分析方法解决的问题寻求可行解。其不足之处是：由于仿真具 有实验的特点，很难从特定的实验中提炼出一般的规律性；生产调度成本高； 仿真结果的价值和可信度严重依赖仿真模型、仿真方法及仿真实验输入数据； 仿真的准确性受程序员判断能力和技能的限制。 7 神经网络优化法用于车问调度主要有三类方式：一是利用其并行计算 能力。求解优化调度，以克服调度的n p 困难问题。二是利用其学习能力，从 优化轨迹中提取调度知识。三是来描述调度约束或调度策略，以实现对生产过 程的可行或次优调度”1 。 8 基于模糊数学理论的方法客观现象具有确定性与不确定性两个基本方 面，经典数学表达的是现象的确定性；不确定性一方面表现为随机性，另一方 面表现为模糊性。正是利用此特点，许多学者把它引入了调度领域。但与专家 系统相似，这种方法同样存在开发周期长、需要丰富的调度经验和知识等缺 点。 9 拉氏松弛法拉氏松弛法由于其在可行的时间里能对复杂的规划问题提 哈尔演理t 人学t 学硕十学位论文 供好的次优解，并能对解的次优性进行定量评估，近年来已成为解决复杂车间 调度问题的一种重要方法。但不可避免的是，存在拉氏松弛法其对偶问题存在 搜索效率低，可行调度的构造有待于进一步研究等问题。 l o 遗传算法遗传算法“”( g e n e t i ca l g o r i t h m s ，g a ) 是由美国m i c h i g a n 大学的j o i l i lh 。h o l l a n d 敦授创建的。遗传算法是以决策变量的编码作为运算 对象，在优化过程中借鉴生物学中染色体和基因等概念，模拟自然界中生物的 遗传和进化等机理，应用遗传操作，求解无数值概念或很难有数值概念的优化 问题：遗传算法直接以目标函数作为搜索信息，它仅使用由目标函数变换来的 适应度函数值就可确定进一步搜索的方向和范围，而不需要目标函数的导数值 等信息：遗传算法同时在多点进行信息搜索，具有天生的并行性，由多个个体 组成一个初始群体开始搜索，对群体进行选择、交叉、变异等运算，产生出新 一代的群体，继续搜索“”1 ；遗传算法使用概率搜索技术，它属于一种自适 应概率搜索技术，其选择、交叉、变异等运算都是以一定的概率进行的，增加 了其搜索过程的灵活性，实践和理论证明了在一定条件下遗传算法总是以概率 l 收敛于问题的最优解。除上述特点之外，遗传算法还有许多问题需要解决， 如算法本身的参数优化问题，如何避免过早收敛，如何改进操作手段或引入新 的操作来提高算法的效率，遗传算法与其它优化算法的结合问题等。 1 1 演化规划演化规划是本世纪6 0 年代提出的。主要用于数据诊断、模 式识别和分类以及控制系统的设计之中，并取得了良好的效果。后来，借助于 演化策略方法对演化规划进行了发展，并用到数值优化和神经网络训练等问题 之中。 1 2 禁忌搜索禁忌搜索“”“”( t a b o os e a r c h ，t s ) 最早是由g l o v e r 提出 的，它是一种“局部搜索”的修正方法，从一些初始解开始，试图找到更好的 解，然后从这个新的解开始，继续寻找好的解，这一过程不断重复，直到找到 的解不再改善为止。所谓禁忌就是禁止重复i j 面的工作，它避免了局部邻域搜 索陷入局部最优的主要不足，用一个禁忌表记录已经到达过的局部最优点。在 下一次搜索中，就利用禁忌表中的这些点，以跳出局部最优“。它的缺点是： 对于初始解具有较强的依赖性。 1 3 模拟退火模拟退火( s i m u l a t e da n n e a l i n g ，s a ) 的思想最早是由 m e t r o p o l i s 等提出的。其出发点是基于物理中固体物质的退火过程与一般的组 合优化问题之间的相似性，是一种通用的优化方法。物理退火过程包含三个部 分：( 1 ) 加温过程，其目的是增强粒子的热运动，使其偏离平衡位置。当温度 足够高时，固体将溶解为液体，从而消除系统原先可能存在的非均匀态，使随 6 后的冷却过程以某一平衡态为起点。溶解过程与系统的熵增过程相联系。系统 能量也随温度的升高而增大。( 2 ) 等温过程，对于与周围环境交换热量而温度 不变的封闭系统，系统的自发变化总是朝自由能减少的方向进行，当自由能达 到最小时，系统达到平衡态。( 3 ) 冷却过程，其目的是使粒子的热运动减弱并 渐渐趋于有序，系统能量逐渐下降，从而得到低能的晶体结构”。模拟退火算 法是模拟热力学中经典粒子系统的降温过程，来求解规划问题的极值。它能够 有效地解决大规模的组合优化问题，而且可以较好地避免局部最优，但算法的 收敛速度很慢，这成为s a 进一步应用的阻力。 1 4 人工蚁群算法人工蚁群算法“”是通过模拟自然界中蚁群觅食行为和 觅食策略来求解组合优化问题的一种崭新的方法。人工蚁群算法具有很强的发 现较好解的能力，由于算法本身采用了正反馈原理，加快了进化过程，且不易 陷入局部最优解；人工蚁群算法具有很强的并行性，个体之间不断进行信息交 流和传递，有利于发现较好解，单个个体容易收敛于局部最优，多个个体通过 合作，可以很快收敛于解空间的某一子集，有利于对解空间的进一步探索，从 而发现较好解”“。其存在的问题是该算法本身很复杂，一般需要较长的搜索 时间：容易出现停滞现象，即搜索进行到一定程度后，所有个体所发现的解完 全一致，不能对解空间进一步进行搜索，不利于发现更好的解。 1 5 数据挖掘技术数据挖掘( d a t am i n i n g ，d m ) 技术是一种从大量数据 中自动或者半自动地发现知识的方法。用以辅助人们进行科学有效的决策，已 成功应用于金融、销售等领域。由于车间调度问题相比其它领域的信息有自身 的特点和复杂性，目前国内外在这方面的研究刚刚起步，2 0 0 2 年，华中科技 大学的研究人员首次将数据挖掘技术应用于流程工业生产调度中，并在论文中 分析了生产调度与数据挖掘两者相结合的可行性”“。 1 4 j o b s h o p 调度问题的存在的问题和发展趋势 1 4 1 j o b s h o p 调度问题存在的问题 调度领域中的大部分问题都具有n p 问题，虽然对它的研究已有几十年的 历史，但至今未形成一套系统的方法和理论，理论研究与实际应用之问还存在 着很大差距。尤其随着j i t ( j u s t i n t i m e ) 思想的广泛采用，e i ( e a d i n e s s t a r d i n e s s ) 调度问题，即使得工件尽量按交货期完成，变得越来越 突出。实际应用中的调度方法能够响应系统的动态变化，但不能保证得到好的 哈尔演理t 大学t 学硕l 学位论文 调度：一些理论上的最优化方法能提供最优调度。但由于其计算的复杂性，并 且忽略了很多实际因素，离实际运用还有较大距离。基于最优化的方法，诸如 动态规划算法与分枝定界算法等等，由于其大多数是建立在对可能调度的部分 枚举上，因此只能解决小规模的调度问题，距离实用还有较大距离”5 “。 由于大多调度问题属于一类n p h a r d 组合问题，因此寻找具有多项式复杂 性的最优算法几乎是不可能的。但因其解的最优性，至今仍然激发学者们进行 不断地探索。各种近似启发式方法、诸如基于规则的算法等，由于能在合理的 时间内产生比较满意的调度，因此广泛应用于实际调度中，但其往往对所得的 调度解的次优性不能进行评估。在这方面有必要探索更好的近似最优调度算 法，可以考虑增加合理的计算时自j 代价，提高解的次优性。各种基于统计优化 的方法，诸如模拟退火法、遗传算法等，提供了一种解决调度优化问题的新途 径，但同其它的优化算法类似，其也存在着一定程度的不足。一般来说收敛到 最优解很慢，并且对于判断解的最优性也很困难，在这方面也需要做进一步的 研究。 在实际车间调度中，车白j 计划与车间调度往往是分层进行的，但这可能造 成计划在实际调度中的不可行问题，如何将计划与调度结合考虑，以求总体的 优化也是需要进一步研究的。另外，还有很多有待进一步研究的问题，比如实 际车间调度的多目标性等。调度理论、方法与应用的研究是一项非常艰巨的工 作，目前人们还在进行各种各样的探索性研究工作。 1 4 2 j o b s h o p 调度问题的发展趋势 车间调度问题本身源于实际生产需求，从车间生产的实际过程来看，不确 定性是调度的最大难点，也是任何现代化的企业所无法回避的，随时出现的任 何情况都有可能打乱原先所做出的零件排序和负荷均衡。目前所研究的调度问 题大多是将实际生产情况进行简化，把复杂问题转化为现有方法可以解决的简 单问题，绝大多数调度理论和算法都不能够对实际问题进行全面而有效的求 解，基于单件小批生产模式的车间调度方法研究和系统开发它们只对某种特定 或简单情况有效，却无法同样有效地解决动态环境下的其它问题。因此人们在 静态调度问题的研究基础上，不断增加问题的约束条件并提出面对意外事件的 处理方法，使所构建的系统尽量接近实际生产，做到可靠实用。随着各种特殊 调度问题的攻克和新方法、新设备的出现，车间调度研究正在向着动态、敏 捷、多重入、多资源、智能化的方向发展“”。另一方面，伴随着信息技术的广 竺尘堡堡三兰三兰竺! ：兰堡丝兰 泛使用，企业积累了大量的数据，并且在生产过程中不断地产生实时数据，这 些数据中蕴涵了大量的知识。如果能够对这些数据背后隐藏着的重要信息进行 更高层次的分析，从中得到有价值的规则和知识，就可以结合实际的生产状况 和生产数据来指导作业调度，进行科学有效的决策。数据挖掘技术作为一种知 识发现方法，正好迎合了这种趋势，引起了人们足够的重视和广泛的关注。 1 5 本文研究的意义和主要内容 1 5 1 课题来源 本课题来源于黑龙江省自然科学基金( f 0 3 0 9 ) 、黑龙江省教育厅重大科学 研究项目( 1 0 5 5 1 2 0 0 0 8 ) 、哈尔滨市科技攻关项目( 2 0 0 5a a l c g 0 6 1 1 1 ) 。 1 5 2 本文研究的意义 据国际生产与研究工程协会对欧美等工业国家的调查统计表明：在机械制 造中就产品的产量而言，多品种小批量( 约5 0 l o o o 件以下) 生产占5 0 左 右，就产值而占，占6 0 左右。进一步调查多品种小批量生产中的材料和工件 在车间总时白j 分配现状可知：制造过程9 5 的时间消耗在非加工过程中1 。可 见批量生产尤其是中小批量生产已成为当今生产车间中比较重要的一种生产方 式。 在生产计划编制中，j o b s h o p 调度问题是一个重要的问题。对于这一类问 题的研究和解决，既具有理论意义又具有实用价值。对于j o b - s h o p 调度问题 的最初研究是寻找最优解，但是遇到了很大的困难，而实际上好的次优解也可 以满足问题要求，会达到理想效果。 本课题研究的目的是针对求解车间调度问题存在的问题，通过深入研究该 类问题的特性，设计并实现求解车间调度问题的算法。 1 5 3 本文研究的主要内容 本课题研究的目的是针对求解n p h a r d 的车间调度存在的问题，通过深 入研究问题的性质，提出了一种新的求解j o b s h o p 调度问题的算法。该算法 借鉴了操作系统中进程( 线程) 调度的几种先进的调度算法，并且将这些先进 的调度思想与j o b s h o p 调度问题很好地相结合。 9 哈尔滨理t 人学t 学颀i 。学位论文 本文主要研究以下几项内容： 1 静态单作业j o b s h o p 调度问题包括将静态单作业j o b s h o p 调度问题 建模、借鉴操作系统中进程( 线程) 调度算法的思想为静态单作业j o b - s h o p 调度问题设计调度策略。 2 静态多作业j o b s h o p 调度问题包括将多作业建模，将多个作业对应 的加工树构造成为一个虚拟的加工树，从而化简多作业的j o b - s h o p 调度问 题。 3 动态j o b - s h o p 调度问题将初始时刻的作业构造成一个虚拟加工树； 并将不同时刻到来的作业所对应的加工树并入虚拟加工树，从而简化动态o h - s h o p 调度问题。 1 6 论文结构 第1 章介绍了j o b s h o p 调度问题的背景、含义、特点及分类，然后给出 了现有的研究j o b s h o p 调度问题方法、现状及发展趋势，最后说明了课题的 来源及论文主要研究内容。 第2 章介绍了计算机操作系统中有关进程和线程的单机和多机调度算法。 其中的一些先进的算法被借鉴到本论文的调度算法中。 第3 章对单个作业的j o b s h o p 调度问题进行了分析并且提出了四种调度 策略来调度工序。因为单作业同样具有一般j o b s h o p 调度问题的性质，所以 这四种调度策略可以作为研究更一般的j o b s h o p 调度问题的基础。 第4 章在前一章的基础上提出了一种以根对齐的构造方法来调度多作业的 j o b s h o p 调度问题并通过实例进行比较。 第5 章在前两章研究的基础上提出了一个完整的算法调度动态的j o b s h o p 调度问题并通过实例进行比较。 结论。对本文进行了总结，并对进一步的研究做出了展望。 0 哈尔演理t 人学t 学硕i 。学位论文 2 1 引言 第2 章操作系统中进程调度算法 操作系统作为最重要的计算机系统软件已经有3 0 多年的发展历史，在这 期间操作系统由简单到复杂，功能同臻完善，效率也不断提高。在操作系统的 发展过程中，出现了很多优秀的有关进程调度的算法。而进程调度与j o b s h o p 问题中作业调度有很多相似之处。本文所提出一些调度思想就是受到操作系统 中进程调度算法的启发，所以这里先来介绍在操作系统中的一些有关进程调度 的算法。 2 2 单机调度算法 2 2 1 先来先服务调度算法 先来先服务。1 ( f i r s tc o m ef i r s ts e r v i c e ，f c f s ) 调度算法是一种较简单的 调度算法，它可以用于作业调度，也可以用于进程调度。当在作业调度中采用 该算法时，每次调度都是从后备作业队列中，选择一个或多个最先进入该队列 的作业。在进程调度采用f c f s 算法时，则每次调度是从就绪队列中，选择一 个最先进入该队列的进程，为之分配处理机，使之投入运行。 f c f s 算法比较有利于长作业( 进程) ，而不利于短作业( 进程) 。表2 1 列出了a 、b 、c 、d 四个作业分别到达系统的时间、要求服务的时间、开始 执行的时间及各自的完成时间，并计算出各自的周转时间和带权周转时间。 从表2 1 中可以看出，其中短作业c 的带权周转时间竟高达1 0 0 ，而长作 业d 的带权周转时自j 仅为1 9 9 。据此可知，f c f s 调度算法有利于长作业。 2 2 2 短作业( 进程) 优先调度算法 短作业( 进程) 优先1 ( s h o r tj o b ( p r o c e s s ) f i r s t ，s j ( p ) f ) 调度算 法，是指对短作业或短进程优先调度的算法。s j f 是从后备队列中选择一个或 若干个估计运行时间最短的作业，将它们调入内存运行。s p f 是从就绪队列中 选出一个估计运行时间最短的进程，将处理机分配给它。 表2 i 四个进程的带权周转时间 开始执行 带全周转 进程名到达时间 服务时问完成时间周转时间 时间 时间 ao1ol ll b11 0 0 l1 0 11 0 0l c2i1 0 l1 0 2 l 1 0 0 d31 0 01 0 2 2 0 21 9 9】9 9 表2 - 2f c f s 和s j f 算法的比较 t a b l e2 - 2c o m p a r i s o no f a l g o r i t h r nf c f sa n ds j f 萨进程名 abcde平均 雳监 度情 到达时间 01234 雾摇 若 服务时间 43524 完成时间 471 21 41 8 f c f s周转时间 4 6 1 0 1 11 49 带权周转时间 1 2 2 2 5 5 5 2 8 完成时间 g91 861 3 s i f厕转时间 481 6 3 9 8 带权周转时间 l2 6 73 11 52 2 52 1 由表2 2 可以看出，采用s j ( p ) f 后不论是平均周转时间还是平均带 权周转时间，都有较明显地改善。但是s j ( p ) f 算法也有不容忽视的缺点： 该算法对长作业( 进程) 不利。 该算法完全末考虑作业( 进程) 的紧迫程度。 由于作业( 进程) 的长短只是根据用户所提供的估计执行时间而定而用 户有可能有意或无意地缩短期作业( 进程) 的估计运行时间，致使该算法不一 晴尔滨理t 大学t 学硕j 学位论文 定真正做到短作业( 进程) 优先调度。 2 2 3 高优先权优先调度算法 在操作系统中，为了照顾紧迫型作业，使之在进入系统后便获得优先处 理，引入了最高优先权优先( f p f ) 调度算法。当采用该算法时，系统将从后 备队列中选择若干优先权最高的作业，装入内存。当用于进程调度时，该算法 是把处理机分配给就绪队列中优先权最高的进程。优先权调度算法可以分为以 下两种类型：非抢占式和抢占式。 非抢占式和抢占式。在非抢占式方式下，系统一旦把处理机分配给就绪队 列中优先权最高的进程后，该进程便执行完成：或因发生某事件使该进程放弃 处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。在抢占方 式下，系统同样把处理机分配给优先权最高点进程，使之执行。但是在执行期 间，只要又出现了另一个优先权更高的进程，进程调度程序就立即停止当前的 进程，重新将处理机分配给新到的优先权最高的进程。对于最高优先权调度算 法，其关键在于：它是使用的是静态优先权还是动态优先权。静态优先权是在 创建进程时确定的，且在进程的整个运行期间保持不变。动态优先权是指在创 建进程时所赋予的优先权，可以随着进程的推进或随其等待时问的增加而改 变，以便获得更好的调度性能。 2 3 多机调度算法 在实际应用当中，多处理机有着很广泛的应用，因此，多处理机调度具有 相当重要实际意义。如果从多处理机之间耦合的紧密程度上分可以将其分为紧 密耦合和松弛耦合；如果按处理机是否相同分，可以将其分为对称多处理机系 统( s m p s ) 和非对称多处理机系统1 。 多处理机上的进程( 线程) 调度方式： 自调度机制：在多处理机系统中，自调度方式是最简单的一种调度方式。 它是直接由单处理机环境下的调度方式演变而来的。在系统中设置一个公共的 进程或线程就绪队列，所有的处理机在空闲时，都可以自己到该队列中取得一 进程( 线程) 来运行”。在自调度方式中，可采用在单处理机环境下所用的 调度算法，如先来先服务( f c f s ) 、最高优先权优先( f p f ) 调度算法和