（机械制造及其自动化专业论文）多重资源约束下的作业车间优化调度研究.pdf

摘要 摘要 作业车间调度是制造系统的一个研究热点，也是理论研究中最为困难的问 题之一。有效的调度方法与优化技术的研究和应用，对于制造企业提高生产效率、 降低生产成本等方面起着重要作用，因而越来越受到学者们的关注。 通常经典作业车间调度是假设加工工件只需要机器一种资源，但实际问题 中，在工件加工的过程中往往除了需要机器以外，还需要另外的附加资源。另一 方面，由于车间资源的有限性使得这些作业在调度时受到多重资源的制约。因此 具有多重资源约束下的车间调度问题比经典作业车间调度问题更复杂，都属于 n p - h a r d ( n o n d e t e r m i n i s t i cp o l y n o m i a l h a r d ，非确定性多项式) 问题。解决问题 的核心是模型和算法，有效的调度算法，可以大大提高资源的利用率和生产效益。 因此，研究具有多重资源约束下的车间调度问题具有重要的理论意义和现实意 义。 首先，本文论述多重资源约束下的作业车间调度研究内容的目的和意义，介 绍了国内外作业车间调度研究的方法和发展现状；研究了有关作业车间调度的基 本理论，并在经典作业车间调度的基础上，增加了资源约束条件，对多重资源以 及多重资源约束下的作业车间调度问题进行了描述。 接着，以机器和模具为多重资源实例建立了多重资源约束下的作业车间调度 模型。在该研究领域里，它属于非标准型的的作业车间调度问题。本文就此模型 设计了作业级、设备级和优化级的三级优化的启发式求解算法，并运用算例对它 进行可行性、有效性验证。结果表明该算法具有良好的目标优化性能和较高的运 算速度。 最后，在本文所研究的理论基础上，设计了多重资源约束下的作业车间调度 系统，它包括帐号及权限管理、基础数据管理、作业调度和车间信息显示四大功 能模块，并给出了系统中的一些应用实例。 关键词：多重资源；资源约束；作业车间调度；启发式算法 广东工业大学工学硕士学位论文 a bs t r a c t a sap o p u l a rr e s e a r c hr e a l mi nm a n u f a c t u r es y s t e m ，j o bs h o ps c h e d u l i n gi so n e o ft h em o s td i f f i c u l tp r o b l e m si nt h e o r e t i c t h em a i nt a s ki ns c h e d u l i n g ，i nt e r m so f p r o d u c et a r g e ta n dc o n s t r a i n t s ，i st od e t e r m i n et h ep r e c i s ep r o c e s s ，t i m e ，e q u i p m e n t a n do p e r a t i o nf o re v e r yp r o c e s so b j e c t a ne m i n e n ts c h e d u l i n gs t r a t e g yc a l li m p r o v e t h eo p t i m i z a t i o na n de c o n o m i ce f f i c i e n c yo fp r o d u c es y s t e m u s u a l l y , c l a s s i c a lj o bs h o ps c h e d u l i n gh y p o t h e s i st on e e do n l ym a c h i n er e s o u r c e t op r o c e s sw o r k p i e c e h o w e v e r , n o to n l ym a c h i n ei sn e e d e dt op r o c e s sw o r k p i e c e ，b u t a l s oa d d i t i o n a lr e s o u r c e sa r en e e d e di nt h ea c t u a lp r o b l e m o nt h eo t h e rh a n d ，t h e r ei s m u t i l r e s o u r c ec o n s t r a i n e dw h e nj o b sa r es c h e d u l i n gb e c a u s eo ft h el i m i t a t i o no f w o r k s h o pr e s o u r c e s s oi t i sm o r ec o m p l i c a t e df o rm u t i l r e s o u r c ec o n s t r a i n e dj o b s h o ps c h e d u l i n gp r o b l e mt h a nf o rc l a s s i c a lj o bs h o ps c h e d u l i n gp r o b l e m b o t h c l a s s i c a lj o bs h o ps c h e d u l i n gp r o b l e ma n dm u t i l - r e s o u r c ec o n s t r a i n e dj o bs h o p s c h e d u l i n gp r o b l e ma r eb e l o n gt on o n d e t e r m i n i s t i cp o l y n o m i a lh a r dp r o b l e m t h ek e y o fs o l v i n gp r o b l e mi sm o d e la n da l g o r i t h m i tc a np r o m o t eg r e a t l yt h eu t i l i z a t i o nr a t i o o fr e s o u r c e sa n dt h ep r o d u c t i o ne f f i c i e n c y 、) l ，i t he f f e c t i v es c h e d u l i n ga l g o r i t h m t h e r e f o r e ，i th a si m p o r t a n tt h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c et o r e s e a r c h m u t i l - r e s o u r c ec o n s t r a i n e dj o bs h o ps c h e d u l i n gp r o b l e m f i r s to fa l l ，t h i sp a p e rd i s c u s s e dt h er e s e a r c hp u r p o s ea n ds i g n i f i c a n c eo f m u t i l r e s o u r c ec o n s t r a i n e dj o bs h o ps c h e d u l i n g t h et r e n do ft h ed o m e s t i ca n d o v e r s e a sr e s e a r c ho f j o bs h o ps c h e d u l i n ga n dt h er e s e a r c hm e t h o d si nt h i sd o m a i na r e a n a l y z e d t h eb a s i ct h e o r i e sa b o u tj o bs h o ps c h e d u l i n ga r es t u d i e d m u t i l r e s o u r c e a n dm u t i l r e s o u r c ec o n s t r a i n e djo bs h o ps c h e d u l i n go nt h eb a s i so fc l a s s i c a ls h o p s c h e d u l i n ga n di n c r e a s i n gc o n d i t i o na b o u tr e s o u r c ec o n s t r a i n t sa r ed e s c r i b e d s e c o n d l bw et o o km a c h i n ea n dm o u l da sm u t i l - r e s o u r c ee x a m p l ea n db u i l tt h e m o d e lo fm u t i l r e s o u r c ec o n s 仃a i n e dj o bs h o ps c h e d u l i n g i nt h i sr e s e a r c hf i e l d ，i ti sa n o n e - s t a n d a r dj o bs h o ps c h e d u l i n gp r o b l e m a nt h r e e - l e v e lo p t i m i z i n ga l g o r i t h m c a l l e dj o bl e v e l ，e q u i p m e n tl e v e la n do p t i m i z a t i o nl e v e lh e u r i s t i ca r i t h m e t i ci s d e s i g n e df o rs e t t l i n gt h i sp r o b l e mi nt h i sa r t i c l e s o m ee x a m p l e sa r eu s e dt ot e s tt h e f e a s i b i l i t ya n dt h ev a l i d i t yo ft h i sa l g o r i t h m t h er e s u l t si n d i c a t et h a tt h ea l g o r i t h m i t a b s t r a c t h a s g o o dp e r f o r m a n c eo fo b j e c to p t i m i z i n ga n dc a l c u l a t i n gs p e e d f i l l a l l v o nt h eb a s i so fr e s e a r c ht h e o r i e s ，am u t i l - r e s o u r c ec o n s t r a i n e dj o bs h o p s c h e d u l i n gs o f t w a r es y s t e mi sd e v e l o p e d t h e r ea r e f o u rf u n c t i o nm o d u l e si nt h i s s y s t e m ，w h i c h i n c l u d e s m a n a g e m e n t f o ra c c o u n tn u m b e ra n dp e r m i s s i o n , m a n a g e m e n tf o rb a s i cd a t a , j o bs c h e d u l i n ga n di n f o r m a t i o nd i s p l a yi nw o r k s h o p a t t h es a m et i m es o m ee x a m p l e sf o ra p p l i c a t i o no fs y s t e ma r ea l s og i v e n k e y w o r d s ：m u t i l r e s o u r c e ；r e s o u r c ec o n s t r a i n t ；j o bs h o ps c h e d u l i n g ；h e u r i s t i c a r i t h m e t i c i i i 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 7 4 驰1 1 论文作者签字：弓蛤三乏 2 0 0 8 年5 月2 0 日 第一章绪论 1 1 研究背景及意义 第一章绪论 随着现代制造技术、信息技术和自动化技术的迅速发展，全球性的竞争给制 造业企业提出了新的挑战：产品生命周期日益缩短，顾客需求日益多样化和对时 间的敏感性日益增强，变化和不确定性是新的竞争环境的标志。而且目前，在我 国多数制造企业中，存在设备利用率低、交货期长、生产准备周期长、费用高、 自动化水平和柔性水平较低，质量不稳定，资金周期慢，库存大等问题。企业要 想在激烈的竞争中立于不败之地，必须以最快的速度、最好的质量、最低的成本 和最优的服务来响应市场的快速应变能力。这就要求企业除了在转变现有的经营 机制外，最重要的是运用先进的制造技术及好的生产与运作管理方案，以提高企 业的生产、经营和管理效率，从而提高企业的核心竞争优势。而生产与运作管理 的核心是生产作业调度问题能否高效的获得最优解，因此，研究生产调度问题具 有很大的理论意义和现实价值。 目前，企业中车间一级的生产调度控制依然处于传统管理方式，这种管理方 式不能综合考虑整个生产过程，导致等待时间长、在制品占用量大、信息反馈慢、 资源浪费、生产不均衡。因此，在车间作业控制中及时准确地进行调度，对于生 产系统的高效运行有着重要影响。研究生产车间调度问题，合理地安排工件和工 序的加工顺序、高效地分配企业资源，对提高生产率，促进企业生产管理的现代 化，提高企业的竞争力具有重要的意义【l 矧。 在实际车间调度过程中都涉及到有效分配有限的资源、合理安排活动或作业 的顺序和活动的开始加工时间，这些资源包括机器、模具、夹具、刀具、人员等。 在作业任务的实施过程中，不仅仅是一个作业任务安排在一台机器上就可以开始 加工的，而往往需要一些附加资源和机器一起才能完成加工这个任务。例如当车 间作业调度时，车间的机器数量相对充足，但夹具或模具等这种辅助设备不足， 由于这些资源的数量有限，而任何两个需要相同资源因互相冲突不能同时进行， 所以各个作业相互之间就存在着对这些辅助设备资源的竞争、工期冲突等多种联 系，这样在受到资源约束的情况下要进行比较合理地安排各个作业就比较困难。 因此车间作业调度问题不单单只考虑机器这一种资源，而往往要考虑多重资源之 广东工业大学工学硕士学位论文 间及多重资源与生产任务之间的约束关系，而现有的对多重资源约束下的调度问 题的研究却十分有限。 如何改进此类问题的调度方式和调度算法，将极大提高相关系统的运行性 能，因此对该类调度问题的研究具有重要的实际意义和理论意义。 1 2 需求分析 随着科技的进步和经济的发展，机械零部件加工行业已从传统的、较为落后 的生产方式，向着强调现代化管理的生产方式迈进。为了满足准时制生产模式， 提高车间生产效率，降低生产成本等目标，机械零部件加工企业对于生产调度也 提出了更高的要求。下面从该行业的调度特点和调度需求两方面进行企业对于生 产调度的需求分析。 1 机械零件加工行业调度特点分析 ( 1 ) 生产类型 从实现j i t ( j u s ti nt i m e ) 生产的角度看，由于准时制生产需要企业在合 适的时间点或时间段，生产出合适的产品。因此如何做好静态的计划编制和动态 的实时调度，以满足j i t 的生产方式，这对车间的调度提出了要求。 从任务接收的角度来看，机械零部件加工企业主要从事多品种、小批量的 生产，大部分企业按订单组织生产，订单类型主要有常规订单、急件订单等， 订单的到达有很大的随机性，对生产车间的计划与车间的实时调度就提出了较高 的要求。 ( 2 ) 产品特点 从产品种类来说，一般的机械零部件加工企业都生产相关和不相关的较多 品种和系列的产品或零件。每种产品或零件都有着自身的加工及工艺要求，如何 为这些具有不同工艺技术条件的不同种类的零件进行调度分配，对车间的调度能 力提出了较高要求。 从产品的工艺特性上看，每个零件的工艺流程简单明了，但工艺路线灵活， 每道工序又已有多种可供选择的加工设备，且每台加工设备的加工时间和加工效 率都不尽相同，为调度的合理性和科学性提出了要求。 ( 3 ) 生产环境特点 加工过程中生产车间的环境复杂性，主要体现在以下几点：各种类型的产品 2 第一章绪论 或零件同时处于加工或等待过程中；机械零部件加工企业生产过程是由不同零部 件) j n - r 子过程或并联或串连组成的复杂的过程，其过程中包含着更多的变化和不 确定因素，譬如生产设备的故障、订单交货期的变更、人员的旷工等。如此多的 不确定性和复杂性，使得机械零部件企业对于车间实时动态调度的要求非常高， 不仅要对已经下达生产计划进行实时的跟踪，及时纠正实际生产情况与生产计划 之间的偏差，还要对各种动态的不确定性和复杂性有着及时地调度措施。 ( 4 ) 制造资源特点 从设备的组成及类型上看，大部分机械零部件加工企业中普通加工设备和数 控加工设备共存，每个工件都有若干台加工设备可供选择，因此如何为工件分配 合适的加工设备以及如何进行各种加工设备之间的协调，使车间的整体加工生产 效率达到最高，成了需要解决的主要问题。 2 调度需求分析 根据以上对机械零部件加工行业车间调度特点的分析，得出此种类型的车间 对于调度的主要需求如下： ( 1 ) 静态调度的需求 针对零件加工的特点，具有满足柔性加工的静态调度能力。 具有多资源、多约束条件下的静态调度能力。 根据企业不同部门对生产的需求，具有相应的静态调度能力。 ( 2 ) 动态调度的需求 在普通订单和急件订单并存条件下，具有常规的动态调度与协调能力。 针对车间生产复杂性和动态性的特点，具有处理异常事件和随机事件的动 态调度能力。 1 3 相关领域的国内外研究概况 车间调度问题是一个比较古老而又传统的问题，对它的研究始于2 0 世纪5 0 年代，早在1 9 5 4 年j o h n s o n 对两台机床f l o w - s h o p 型调度问题进行了研究后， 提出了解决n 2 f c m a x 和部分特殊i l 3 f c m a x 问题的优化算法，这代表调度理 论研究的开始，以后他便开始对调度问题进行了广泛研究，经过几十年的发展， 产生了许多车间调度问题的类型【7 】和求解方法1 8 1 。对于车间调度问题，根据加工 系统的复杂性，可分为单机、多台并行机、f l o w s h o p 问题和j o b s h o p 问题，并 广东工业大学t 学硕士学位论文 且工件的加工路线不同为单件车间( j o b s h o p ) 调度的基本特征；而所有工件的 加工路线相同为流水车间( f l o w - s h o p ) 调度的基本特征【9 】。本文所研究的基本 类型为单件车间作业调度( j o b s h o ps c h e d u l i n g ) ，而具体研究的模型为非标准的 作业车间调度问题，它与典型的、标准的作业车间调度问题主要区别在于，标准 作业车间调度中每道工序排序前均指定机器，而非标准作业车间调度中每道工序 在排序前并不指定机器，只指定所属的工作单元，具体的加工机器将在运算中智 能地选择；根据性能指标，可分为基于调度费用和调度性能的指标两大类。根据 生产环境的特点，也可以将调度问题分为确定性调度和随机性调度问题。根据作 业的加工特点，也可以将调度问题分为静态调度和动态调度。实际中，车间调度 的类型往往是j o b s h o p 型，且是动态的。目前研究比较多的是作业车间调度问 题1 0 圳1 和流水车间调度问题1 2 1 ，并随着对各类调度问题研究的深入及各种交叉学 科的发展，出现了许多新的车间调度理论【1 3 1 5 1 和方法【1 6 1 。研究人员经过多年的研 究，提出了上百种调度算法，这些调度算法大致可以划分为如图卜1 所示的不同 类别【l7 1 。 图1 - 1 调度算法的划分 f i g 1 一ls c h e d u l i n ga r i t l 珈e t i cp a r t i t i o n 在当前对单件车间作业调度的研究中，主要集中对标准作业车间调度问题的 4 第一章绪论 研究。它主要研究n 个工件在m 台机器上的加工组合排序问题，它是一种特殊 的组合优化问题，它在学术界上被证明是n p 完全问题【1 8 之o 】，早在2 0 世纪6 0 年 代，人们就开始了解决这一问题的研究。目前国内外的很多学者对该问题都作了 深入的理论研究，大致产生了两类研究方法：一类是为了得到问题的精确解而进 行的定性研究，它可以得到全局最优解，但所能求解的问题规模比较小，而且速 度慢；另一类则利用近似算法来寻求该问题的近似解，即近似求解方法。 车间调度问题的精确求解主要集中在分支定界法的研究，它是主要的枚举方 法之一。用动态结构分支来描述所有的可行排序的解空间。在对最优解的搜索过 程中，它允许把大部分的非最优点分支从搜索过程中去掉，从而避免完全枚举。 但它只能解决小规模的车间调度问题，与车间实际调度应用还有较大的差距。目 前，对该方法的研究重点放在如何改进分枝定界策略，以便在搜索的最初阶段排 除更多的非最优点，从而大幅度减少运算时间【1 9 】。 车间调度问题的各种近似算法，诸如基于规则的调度算法，是指系统运行时， 根据一定的规则和策略来决定下一步操作的调度方法。它是动态调度的典型代 表，它的优点是直观、简单实用，而且花费的求解时间较少、易于实现，在实际 生产中获得了广泛的应用，但其往往不能对所得解的次优性进行评估。p a n w a l k e 等【2 l 】总结了1 1 3 个调度，将调度规则分为三大类，即简单规则、复合规则、启发 式规则。拉氏松弛法具有独到的优越性，在可行的时间里能对复杂的规划问题提 供好的次优解，并能对解的次优性进行定量评估，近年来已成为解决复杂车间调 度问题的一种重要方法。已经用拉氏松弛法解决了单机调度和多台并行机调度问 题。但是解的震荡与收敛问题直是该方法应用的一个巨大障碍。启发式图搜索 算法主要有宽度优先、深度优先、b e a m 搜索、f i l t e r e db e a m 搜索以及a 或者爿+ 算 法等。么。算法将分支定界算法和动态规划相结合，常用于图的路径搜索中。理 论上，彳算法一定能够找到最优解。这些方法原理上都能找到可行解，但受到 搜索时间和存储空间的限制。近年来，随着研究的深入，将生物学、物理学、人 工智能以及计算机科学等多种技术引入到生产调度领域，提出了解决调度问题的 新方法，各种智能算法的提出丰富了解决问题的途径，成为了一个热门课题。 ( 1 ) 进化算法 进化算法是基于生物界“物尽天择，适者生存”的进化思想基础之上而发展 起来的一种随机搜索技术。主要包括了遗传算法( g a ，g e n e t i ca l g o r i t h m ) ，进化 广东 业大学工学硕上学位论文 规则( e p ，e v o l u t i o np r o g r a m m i n g ) 、进化策略( e s ，e v o l u t i o ns t r a t e g y ) 等。它通过 模拟群体的进化过程，使得群体中的个体不断朝着好的方向发展，由于算法不苛 求待求解问题的具体表达形式以及动力学特性( 如：连续、可微等) ，因而具有较 强的鲁棒性和适应性。遗传算法的特点在于模仿自然界生物的竞争生存机制，通 过将问题的解映射为遗传种群中的个体，再运用适当的遗传操作和选择机制，对 具有一定规模的种群实施世代更替的遗传演化，最终找出整个过程中性能最佳的 个体，即求得所需问题的最优解【2 2 】。遗传算法在求解众多标准作业车间调度问题 均能得到最优解。 ( 2 ) 模拟退火算法 模拟退火( 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 等人提出， k i r k p a t r i c k 等首先将其引入组合优化问题的求解过程。其出发点是基于物理中固 体物质的退火过程与一般组合优化问题之间的相似性，通过设定一初温和初态， 伴随着温度的不断下降，结合概率接收特性，在解的空间中通过邻域函数进行随 机搜索，可以在多项式时间内找到近似最优解。迄今，s a 算法得到广泛应用， 但在提高优化效率方面还待进步的研究【2 3 1 。 ( 3 ) 人工神经网络 人工神经网络( a n n s ) 是一种模拟人脑神经系统的结构和功能，运用大量的 处理部件经广泛互连而组成的网络系统。h o p f i e l d 应用神经网络方法求解旅行商 问题获得成功，从而为组合优化问题求解开辟了新的途径。c h e u n gj y 【2 4 】描述 了一些主要的用于求解调度问题的神经网络结构：搜索网络( h o p f i e l d 网络) ， 纠错网络( 多层感知器) ，随机网络( b o l t z m a n 机) ，竞争网络和自组织网络。 然而，对于求解j o b s h o p 调度问题来说，上述的神经网络模型归纳起来主要还是 两种。 一种是h o p f i e l d 神经网络模型。f o o y se t a 1 首先提出用h o p f i e l d 网络求解 j o b - s h o p 调度问题，同时为避免网络陷入局部极小，又提出了一种随机h o p f i e l d 网络。为了改进早期的方法，f o o y se t a 1 等皿5 1 后来又提出一种整数线性规划神 经网络( i l p n n ) 来解决j o b s h o p 调度问题。但f o o 等提出的计算能量函数没有包 含j s p 的全部约束条件，不能保证得到合法解，且收敛速度较慢，因此，王万良， 徐新黎等【2 6 】提出了用h o p f i e l d = 0 经网络求解调度问题的新方法，保证神经网络的 输出为j s p 的全局最优解；同时又将混沌搜索方法取代模拟退火算法，不仅使算 6 第一章绪论 法具有全局搜索能力，而且提高了收敛速度，取得了较好的结果。 除了h o p f i e l d 神经网络模型，另# b b p 神经网络模型也用来求解j o b - s h o p 调度 问题。r e m u sw 【2 7 】是最早研究用b p 神经网络求解j o b s h o p 调度问题的人之一， 他通过比较线性衰减规则改进了几个b p 网络模型。d a g l ic h e t a l 【2 8 】提出了结合 遗传算法的b p 神经网络模型。近来，j a i na s e ta 1 【2 9 】提出的改进的b p 神经网络 模型克服了传统的b p 网络模型在处理包含复杂的输入输出映像的问题时会训练 不成功并收敛于局部极小解的不足。 ( 4 ) 禁忌搜索算法 禁忌搜索( t a b us e a r c h ) 算法是局部邻域搜索算法的推广，是人工智能在组 合优化算法中的一个成功应用。由g l o v e r 等人首先提出，其核心在于借助禁忌 表的使用，实现某种形式的短期记忆机制。禁忌表标记已搜索到的局部最优解的 对象，在进一步的搜索中尽量避开这些对象，从而阻止搜索过程在等于禁忌表长 度的有限步搜索移动内重返搜索空间中近期访问的状态点，避免迂回搜索。这样， 搜索过程既可通过接受恶化解而跳出局部最优点，又能够防止可能由此造成的局 部循环 2 2 d o 】【3 1 1 。禁忌搜索算法在作业车间问题求解中，取得了较为满意的结果。 对于非标准的作业车间调度问题，它也属于n p 问题。g o n z a l e z 和s a h n i 及 c h o 和s a h n i 对这类问题的特殊问题的复杂性进行了研究【1 9 】。c h u n g h s i n gy e h 提出了基于操作块的快速限定装填算法，解决了多机分配问题【3 2 1 。国内也有一些 文献【3 3 】 3 4 1 提出了解决该问题的多项式算法。总的来说，这类问题的研究文献很 少，能引起学术界关注的研究成果几乎没有。然而，该类问题更接近实际生产， 解决这一问题将具有更大的现实意义。 在有资源约束的车间作业调度方面，文献【35 】提出一种基于神经网络的有约 束的资源调度方法，它是首先将问题分解成一系列多维背包模型并且为背包模型 建立了一个等价的h o p f i e l d 神经网络，然后通过扩展h o p f i e l d 网络，给出了一种 求解有约束的资源调度问题的方法。文献【3 6 】提出一种有约束资源调度的新方法， 它是利用神经网络与模拟退火方法来解决问题的，有约束的资源调度被分解为一 系列时间间隔的调度，这些时间间隔的调度由事件驱动，随着这些时间间隔的调 度的完成，整个调度过程结束。e l m a r a g h y 、p a t e l 、g a r g e y a 、n e l s o n 和d e a h p 7 j 根据机床、工人、辅助工具约束资源的情况把车间作业调度进行了分类。t r e l e v e n 和e l v e r s 3 7 】研究了受工人和机床限制的调度问题，认为当工人与机床设备的比 7 广东工业大学工学硕士学位论文 率在5 0 一7 5 之间时，系统的生产率最高。 1 4 研究的主要内容 本课题研究的目的将针对机械零件制造行业，主要研究面向该制造业车间辅 助加工设备等资源短缺情况下制约着生产的作业车间调度，并以机器和模具辅助 设备为资源约束实例建立多重资源约束下的作业车间调度模型和对此模型设计 了三级优化的启发式算法求解。同时并对这类调度问题为研究重点进行深入的探 讨。 本文的研究工作以姜莉莉教授主持的广州市科技计划项目“全柔性化 c a d c a p p c a p p s 集成系统推广应用( 2 0 0 7 c 1 3 g 0 0 2 1 ) ”为基础，以广东一家 大型的机械制造企业为企业背景，研究该背景下车间多重资源制约情况下的作业 车间调度的优化方法，并在本课题组原有对车间作业调度系统的研究的基础上， 开发一套具有多重资源约束下的作业车间调度的软件系统。 本文研究的主要内容如下： ( 1 ) 系统地研究了作业车间调度问题的基本理论，对作业车间调度问题和多 重资源进行了描述，总结了作业车间调度的优化方法及其特点，并着重 就车间调度问题的调度优先规则进行研究； ( 2 ) 在经典作业车间调度的基础上，增加了资源约束条件，对多重资源约束 下的作业车间调度问题进行了描述，并具体以机器和模具设备资源约束 为多重资源约束实例，建立多重资源约束下的作业车间调度问题的数学 模型； ( 3 ) 在多重资源约束下的作业车间调度问题研究的基础上，针对已建立的调 度模型设计了解决该调度问题的三级优化启发式调度算法，并运用实例 验证了算法的可行性和有效性，结果证明了算法具有较好的目标优化性 能和较高的运算速度； ( 4 ) 结合本课题组原有的研究成果，针对广东某家机械制造企业，开发了机 器和模具资源受到制约下的多重资源约束的作业车间调度系统。 8 第一章绪论 1 5 本文结构 本文论文结构如下： 第一章：在对机械加工行业的调度特点和调度需求以及相关领域的国内外研 究现状进行了详细分析的基础上，结合课题研究背景提出了本文所要研究的目的 和研究内容。 第二章：研究作业车间调度问题的基本理论以及对多重资源进行了概述，并 着重就作业车间调度问题的调度优先规则进行阐述； 第三章：以机器和模具资源约束为多重资源约束实例，建立了多重资源约束 下的作业车间调度问题的数学模型，设计了解决多重资源约束下的作业车间调度 问题的三级优化启发式算法，并对算法的可行性、有效性进行验证； 第四章：介绍系统的设计与实现，并对系统的有关功能进行详细的阐述； 最后对本文的研究工作进行全面总结和对该方向做了下一步的研究展望。 9 广东工业大学工学硕士学位论文 第二章多重资源约束及作业车间调度问题的基本理 2 1 多重资源概述 论 作业车间调度问题( j o bs h o ps c h e d u l i n gp r o b l e m ，简称j s s p ) 是许多实际生 产调度问题的简化模型，是一个典型的n p 难题【2 0 】。j s s p 研究二个作业在各台 机器上的加工，己知各操作的加工时间和各作业在各机器上的加工次序约束，要 求确定与工艺约束条件相容的各机器上所有工件的加工开始时间或完成时间或 加工次序，使加工性能指标达到最优。在j s s p 问题中，通常只考虑机器设备受 到制约的情况，而往往忽视了在生产中处理作业时除需要机器外还需要其他的附 加资源。在实际的生产过程中，机器设备和这些附加资源作为生产资源都是缺一 不可的。我们可以将机器和附加资源同时受到制约的车间系统，称作多重资源受 制约车间( m u l t i r e s o u r c ec o n s t r a i n e ds h o p ( m r c s ) ) ，也就成了我们所研究的多重 资源约束下的作业车间调度( m u l t i r e s o u r c ec o n s t r a i n e dj o bs h o ps c h e d u l i n g ，简 称m r c j s s ) 问题。这样的一种车间生产系统，其表现性能就受到这些机器、附 加资源的数量以及它们的分配效果的影响。 车间调度的本质是为了达到某种生产指标的最优，而合理的分配生产资源。 随着对作业车间调度问题的深入研究，学者们逐渐意识到生产车间的有效调度管 理，不仅与直接加工零件的机器设备有关联：而且与其他生产资源，如人力资源 和辅助生产资源等等，也是紧密相关的。 辅助生产资源不仅包括生产加工过程所需的模具、刀具、夹具等加工附件； 而且还包括支持生产系统正常运转的车间运输附件，如叉车、吊车、自动物料运 输小车、货盘等。在m r c j s s 问题中，附加资源有很多种，如模具、夹具、刀 具等辅助设备资源及人力资源等等。 一般根据资源的性质，可以把资源分为不同的种类( t y p e s ) 和不同的类型 ( c a t e g o r i e s ) 。 首先，如果只考虑资源在工件的加工过程中的功能，那么可以把资源分为 不同的种类( t y p e s ) 。把具有相同功能的资源称为同一种类的资源。其次，如果考 1 0 第二章多重资源约束及作业车间调度问题的基本理论 虑资源的可用性约束( r e s o u r c ec o n s t r a i n t s ) 和资源的可分性( r e s o u r c ed i v i s i b i l i t y ) ， 又可以把资源分为不同的类型( c a t e g o r i e s ) 1 3 引。 从资源的可用性约束的角度来划分，可以把资源分为可再生的( r e n e w a b l e ) 、 不可再生的( n o n r e n e w a b l e ) 和双重约束( d o u b l yc o n s t r a i n e d ) 的资源三个类型。可 再生资源( r e n e w a b l er e s o u r c e s ) 是指它在任意时刻的临时可用性( t e m p o r a r y a v a i l a b i l i t y ) 受到约束，其获取和使用以阶段为基础，某个阶段获得的数量有限， 但使用之后被释放可以再生，可以再次被使用，如人力资源和机器设备等。不可 再生资源( n o n r e n e w a b l er e s o u r c e s ) 是指它的一次可用性受到约束，即这类资源 被分配给某个工件使用后，它在任意时刻都不能分配给其它任务，一旦消耗完就 不能再生，如能源、原材料等资源。双重约束资源( d o u b l yc o n s t r a i n e dr e s o u r c e ) 是指它的临时可用性和一次可用性都受到约束的资源，每一个时间段内受到约 束，这类资源一般可以通过不可再生资源约束和可再生资源约束来代替。 从资源的可分性的角度，资源又分为离散( 可分) ( d i s c r e t e l y d i v i s i b l e ) 和连续 ( 不可分) ( c o n t i n u o u s d i v i s i b l e ) 资源。离散资源能够从有限个可能的分配量中选 择一种量分配给工件，通常离散资源是指工件在加工过程中需要资源不会被消 耗，如模具、刀具、盛器、工具等夹、存储设备等，一旦工件加工完毕，该工件 所占有的附加资源就会得到释放和恢复。在整个加工过程中，资源的数量不会发 生变化。而连续资源能以任意小于或等于某个给定的量分配给工件，连续资源是 不可再生的，它在工件的加工过程中会受到消耗，如生产辅料、生产费用、化工 生产中的添加剂等。随着工件的加工，附加在其上的资源逐渐被消耗，并且工件 加工完毕后被消耗的资源不会再释放和恢复。在整个加工过程中，不可恢复资源 的数量将会逐渐减少。 本文所研究的多重资源属于车间的离散的、可再生的制造资源。并在后面章 节中以机器和模具资源约束为多重资源约束实例建立多重资源约束下的作业车 间调度模型以及求解算法。 广东_ 亡业大学工学硕七学位论文 2 2 作业车间调度问题描述 2 2 1 作业车间调度概述 1 9 5 4 年，j o h n s o n 研究了两台机床的流水车间调度问题【3 9 】。这标志着调度理 论研究的开始。此后调度问题得到了理论界和工程界研究人员的广泛关注和研 究，尤其是在运筹学、工业工程和计算机科学等领域。调度问题通常涉及到四个 基本要素：任务、资源、时间和性能指标，针对这四个要素，调度的目的可简明 地描述为：将任务在资源和时间上进行合理的分派。其中，“合理”程度的评价 是以一个或一组性能指标为依据的。调度问题所涉及的实际问题域非常广泛，如 运输调度、电力调度、水资源调度、操作系统运行调度、人员调度、项目调度、 制造系统生产调度等。由于制造业在经济发展中所占的举足轻重的地位，使得制 造系统的生产调度问题一直是最为引人关注的研究热点之一。 作业车间调度( j o bs h o ps c h e d u l i n g ) 就是对一个可用的加工机器集在时间 上进行加工任务集分配，以满足一个性能指标集。典型的作业车间调度问题包括 一个要完成的作业集合，每个作业由一个操作集组成，包含一个工序集合，各操 作工序的完成需要占用机器或其它资源，并且必须按一些可行的工艺路线、工艺 次序进行加工，每台机床可加工零件的若干操作，并且在不同机器上能加工的操 作集可以不同。研究的目的是确定一个调度，在约束条件下，该调度将每个工序 分配到对应机器的某个时间段形成最佳的生产加工顺序，同时实现设备集和任务 集的合理最优化结合，如图2 1 所示。1 4 0 图2 1 作业车间调度优化组合 f i g 2 1j o bs h o ps c h e d u l i n go p t i m i z ec o m b i n a t i o n 1 2 第二章多重资源约束及作业车间调度问题的基本理论 2 2 2 作业车间调度问题描述 作业车间调度问题一般可以描述为：n 个工作在m 台机器上加工，一个工件 分为k 道工序，每道工序可以在若干台机器上加工。每一台机器在每个时刻只能 加工某个工件的某道工序，只能在上道工序加工完成后才能开始下一道工序的加 工，前者称为占用约束，后者称为顺序约束。 作业车间调度问题的决策内容包括分配决策( 工件的加工顺序) 和时间决策 ( 工件各工序的加工时间) 以及路径决策( 工件工序的加工设备的分配) 。多个工件 在有限的机器上加工，每台机器在切换不同工件生产时需要一定的准备时间。切 换加工次数增加有利于减少工件的库存，但导致生产率下降。因此，需要在库存 成本和工件切换加工频率之间获得平衡。生产的柔性体现在设备使用和设备安排 两个方面，设备使用的柔性指可用于多个零件的多个工序的加工；设备安排的柔 性是指工件的设备加工路径不是固定和预先确定的，具有可选的路径，可以通过 将若干设备组作为一条或者多条生产线加工一种工件，使得该工件生产率最大。 作业车间调度问题可得另一类研究集中于柔性制造系统( f m s ) ，f m s 由一 系列n c 数控设备组成，n c 是固定和预先确定的，具有可选的路径，可以通过 将若干个设备组作为一条或者多条生产加工一种工件，使得该工件生产率最大。 n c 能够单独加工多个工件，在选择了待加工工件后，所需刀具必须分配到该设 备的工具集中。f m s 问题包括：工件选择分配、设备分组、生产率确定和设备负 荷、工具分配等问题，它的约束包括设备工具集的容量限制、设备可用时间和设 备负荷等。【4 1 】 2 2 3 作业车间调度的目标 作业车间调度问题的目标是对企业资源进行优化配置，提高企业的经济效 益。具体在评价调度方案好坏时，评价指标的确定可以根据影响企业成本费用的 主要因素来确定，常用的指标有：总流程时间( m a k e s p a n ) 、平均流程时间、最大交 货误期、平均交货误期、交货误期的工件数、平均在制品库存量和费用指标等。 一个好的调度方案，一般应能做到： (