（机械电子工程专业论文）模具车间交互反应式调度系统的研究与开发.pdf

m o u l d - - m a k i n ge n t e r p r i s e s c a n d i d a t e ：y uh a i f e n g s u p e r v i s o r ：p r o f z h a n gp i n g j u n e2 0 1 0 s c h o o lo fe l e c t r o m e c h a n i c a le n g i n e e r i n g g u a n g d o n gu n i v e r s i t yo ft e c h n o l o g y g u a n g z h o u ，g u a n g d o n g ，p r c h i n a ，5 10 0 9 0 摘要 摘要 模具企业是典型的依单制造的小批量多品种生产企业，由于订单的随 机性和生产过程中设备的不稳定性，使得模具企业的生产过程的有效控制 非常困难，从而经常造成交货期延迟和质量无法保证等一系列问题。 针对此种现状，本文采用了一种基于最大前瞻性的交互反应式的集成 解决方案。在工艺规划开始时，调度员和车间工程师通过系统可视化得知 工序在不同的设备上的加工成本和已经规划好的工件在设备上的加工累 积时间，从中凭经验知识决定工件的某道工序在某一设备上加工，从而避 免了系统盲目生成多种可选的工艺路线，从一定程度上减弱了n - p c o m p l e t e 问题，减少了“组合爆炸问题的影响。交互反应式的调度方法 通过对系统做出局部的最小的调整以对不可预知的扰动做出反应，从而提 高了系统对实际生产的扰动的敏捷性，更加适合中小型模具企业。 本文对基于交互反应式的模具车间调度方案，进行了较为深入地研究， 取得了一些有益的成果。具体工作如下： 1 对现有智能调度文献进行了综述，研究了各种调度规则，如s p t ( 最 短过程时间) 、e d d ( 最早交货期) 、c r ( 关键比例) ，分析了车间调度研究的 现状以及存在的问题。 2 提出了一个基于最大前瞻性( m a x i m u mf o r w a r dv i s i o n ) 的交互反应式 的集成解决方案，并建立了系统模型。该方案将车间的实时动态信息以可 视化的方式直接呈现给工艺师，工艺师根据c a d 的信息和来自车间的制 造资源信息来实时制定工艺规划和生产调度，从根本上避免了“盲目地 ( b l i n d l y ) ”生成多种可选的工艺规划，从而从根本上避免了n - pc o m p l e t e 难 题。通过为工程技术人员提供最大前瞻性的信息，不仅可解决系统的集成 问题，而且可对动态的，不可预知的突发事件等不确定性扰动性、误差渐 进累积性的问题进行快速的监视、跟踪和决策。 3 使用j a v a 编程语言和m y s q l 数据库开发了一个交互反应式调度系 统，进行了仿真实验。由于获得真实数据非常困难，因此本系统所用数据 是仿真数据，仿真数据是在对模具企业所处的环境的特点以及模具企业生 广东工业大学硕士学位论文 产管理现状进行了调查案例( c a s es t u d y ) 的基础上模拟生成的，但能反映 模具企业的真实性，具有代表性。 4 最后，对交互反应式的模具车间调度系统与没有实现交互反应功能 的调度的实验结果进行了对比，对比结果显示：交互反应式的调度系统输 出的结果的各项性能指标均优于纯智能调度方法。 关键词：车间动态调度、交互反应、调度规则 a b s t r a c t a bs t r a c t p r o d u c t i o ni nm o u l d - m a k i n ge n t e r p r i s e si sat y p i c a lm a k e - t o o r d e ra n d o n e o f - a - k i n do fm a n u f a c t u r i n gp a t t e r n t h ep r o d u c t i o np r o c e d u r ef o rm o u l d i sh a r dt ob ec o n t r o l l e db e c a u s et h ec u s t o m e r s o r d e ri su n p r e d i c t a b l ea n dt h e m a n u f a c t u r i n gp r o c e s si sn o ts t a b l e ，s u c ha sd e l a yo fm o u l d s d e l i v e r yt i m e a n di n f e r i o rq u a l i t yo fm o u l d s i nr e s p o n s et ot h e s ei s s u e s ，ar e a c t i v ea n di n t e r a c t i v es c h e d u l i n gb a s e d o nm a x i m u mf o r w a r dv i s i o nw a sp r o p o s e d f r o mt h eb e g i n n i n go ft h ep r o c e s s p l a n n i n g ，d is p a t c h e ra n dp r o c e s s o rc h o o s et h em a c h i n et op r o c e s s i n gt h ep a r t t o g e t h e rb yv i s u a l i z a t i o ns y s t e m t h u sr e a c t i v es c h e d u l i n gs y s t e ma d j u s t e d m i n i m u mp a r t i a lo fs c h e d u l i n gr e s u l tt oa d j u s tt ot h eu n k n o w nd i s t u r b a n c e i t w a sm o r es u i t a b l ef o rs m a l l t o - m e d i u ms i z e dm o u l de n t e r p r i s e s i n t h i sd i s s e r t a t i o n ，ar e a c t i v ea n di n t e r a c t i v es c h e d u l i n gs y s t e mf o r s m a l l - t o m e d i u mm o u l d m a k i n ge n t e r p r i s e sh a sb e e ns t u d i e di nd e p t h s o m e g o o dr e s u l t sh a v eb e e no b t a i n e d t h er e l a t i v er e s e a r c hw o r k sa r ef o l l o w i n g ： 1 t h el a t e s tl i t e r a t u r e sw e r er e v i e w e d ，a l lk i n d so fs c h e d u l i n g d i s p a t c h i n gr u l e s ，f o re x a m p l es p t ( s h o r t e s tp r o c e s s i n gt i m e ) ，e d d ( e a r l i e s t d u ed a t e ) ，c r ( c r i t i c a lr a t i o ) w a si n v e s t i g a t e da n da n a l y s e d t h ei n v e s t i g a t i o n s h o wt h a tt h o s ei n t e l l i g e n ts c h e d u l i n ga l g o r i t h m sa r en o ts u i t a b l ef o rm t o s s m e s 2 ar e a c t i v ea n di n t e r a c t i v es c h e d u l i n gs y s t e mb a s e do nm a x i m u m f o r w a r dv i s i o nw a sp u tf o r w a r d ，a n dt h es y s t e mm o d e lw a se s t a b l i s h e d i nt h e p r o p o s a l ，t h er e a l t i m ed y n a m i cd a t ai nj o bs h o p sa r ep r e s e n t e dt ot h ed e s i g n e r o rp l a n n i n g ，w h od r a wu pt e c h n o l o g yp l a n n i n ga n dp r o d u c t i o ns c h e d u l i n g a c c o r d i n gt ot h ec a dd a t aa n dt h em a n u f a c t u r i n gr e s o u r c e sd a t af o r mt h ejo b s h o p ，a v o i db l i n d l yg e n e r a t i n gv a r i o u sk i n d so ft e c h n o l o g yp l a n n i n g ，s on - p c o m p l e t ec a nb ea v o i d e df u n d a m e n t a l l y 3 t h em o u l dj o bs h o ps c h e d u l i n gs y s t e mw a se s t a b l i s h e dw i t hj a v aa n d i i i 广东工业大学硕士学位论文 m y s q l ，s i m u l a t i o ne x p e r i m e n t sw e r ed o n e b e c a u s ei ti sv e r yd i f f i c u l tt o o b t a i nr e a ld a t af r o me n t e r p r i s e s ，t h ed a t au s e di nt h es y s t e mw e r es i m u l a t e d d a t a 4 f i n a l l y , as i m u l a t i o nc o n c l u s i o nh a ss h o w nt h a tt h er e a c t i v ea n d i n t e r a c t i v ea p p r o a c hc a ni m p r o v et h es y s t e mp e r f o r m a n c ec o m p a r i n gw i t h c o n v e n t i o n a li n t e l l i g e n ta p p r o a c hf o rm a k e - t o - o r d e ri nt h es m a l l - t o m e d i u m e n t e r p r i s e s k e yw or d s ：jo bs h o pd y n a m i cs c h e d u l i n g ，i n t e r a c t i v e a n d r e a c t i v e ， s c h e d u l i n gr u l e s i v 目录 目录 摘要嬖。i a b s t r a c t i i i l ；i 录一1 r c o n t e n t v i i i 第一章绪论。1 1 1 引言1 1 2 课题背景意义1 1 3 车间生产调度2 1 3 1 车间调度问题描述2 1 3 2 车间调度问题的分类7 1 3 3 车间调度的假设7 1 3 4 车间调度的相关参数8 1 3 5 车间调度方法研究现状8 1 3 6 研究现状分析1 3 1 4 课题来源1 4 1 5 论文的研究内容1 4 1 6 论文的框架结构1 5 第二章动态车间调度方法的研究1 6 2 1 动态调度问题概述1 6 2 1 1 动态调度问题描述一1 6 2 1 2 动态车间调度的特点1 8 2 1 3 车间动态调度研究方法的现状2 0 2 1 4 车间调度的调度策略2 1 2 2 车间调度的分解方法2 2 2 2 1 基于时间的分解方法2 2 v 广东工业大学硕士学住论文 2 2 2 基于空间的分解方法2 3 2 3 车间生产调度系统流程2 4 2 4 本章小结2 5 第三章交互反应式调度系统的建立2 7 3 1 建立模具车间交互反应式调度系统的理由2 7 3 1 1 模具企业生产特点一2 7 3 1 2 模具企业生产管理现状2 8 3 1 3 交互反应式调度方案的提出3 0 3 2 基于交互反应式的模具企业业务模型3 0 3 3 交互反应式模具车间调度系统的功能模块组成3 2 3 4i 艺规划与车间调度计划集成3 3 3 5 交互反应式模具车间调度系统的系统框架3 4 3 6 交互反应式调度的优点3 6 3 7 本章小结一3 7 第四章交互反应式模具车间调度系统算法的研究3 8 4 1 交互反应车间调度的数学模型3 8 4 1 1 以最大完工时间最短为目标函数3 8 4 1 2 以交货期约束为目标函数3 9 4 2 交互反应车间调度的调度规则一3 9 4 3 交互反应的调度算法一4 0 4 3 1 交互反应调度算法的必要性4 0 4 3 2 交互反应调度方法4 1 4 4 算法试验计算及结果分析4 3 4 5 本章小结4 8 第五章模具车间交互反应式调度系统的实现。5 0 5 1 系统开发环境5 0 5 2 系统实现的主界面5 0 5 3 仿真实验5 5 v 广东工业大学硕士学位论文 c o n t e n t a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h i i i c o n t e n t si nc h i n e s e v c o n t e n t si ne n g l i s h 。v i i i c h a p t e r1i n t r o d u c t i o n 二1 1 1i n t r o d u c t i o n 1 1 2t h em e a n i n ga n db a c k g r o u n do ft h es u b j e c t 1 1 3j o bs h o ps c h e d u l i n g 2 1 3 1t h ed e s c r i p t i o no f j o bs h o ps c h e d u l i n g 2 1 3 2t h ec l a s s i f i c a t i o no f j o bs h o ps c h e d u l i n g 7 1 3 3t h eh y p o t h e s i so f j o bs h o ps c h e d u l i n g 7 1 3 4t h er e l a t i v ep a r a m e t e r so f j o bs h o ps c h e d u l i n g 8 1 3 5t h er e s e a r c hs t a t u so f j o bs h o ps c h e d u l i n gm e t h o d 8 1 3 6t h ea n a l y s i so ft h er e s e a r c hs t a t u s 13 1 4t h eo r i g i no ft h es u b j e c t ! 1 4 1 5t h ec o n t e n to ft h et h e s i s 1 4 1 6t h ef r a m eo ft h et h e s i s 1 5 c h a p t e r 2r e s e a r c ho fd y n a m i cjo bs h o ps c h e d u l i n gm e t h o d 16 2 1t h es u m m a r yo fd y n a m i cj o bs h o ps c h e d u l i n g 16 2 1 1t h ed e s c r i p t i o no fd y n a m i cs c h e d u l i n g 16 2 12t h ec h a r a c t e r i s t i c so f j o bs h o pd y n a m i cs c h e d u l i n g 18 2 13t h es t a t u so f j o bs h o pd y n a m i cs c h e d u l i n gr e s e a r c hm e t h o d 一2 0 2 14t h es c h e d u l i n gs t r a t e g i e so f j o bs h o ps c h e d u l i n g 2 1 2 2t h ed e c o m p o s em e t h o do f j o bs h o ps c h e d u l i n g 2 2 2 2 1t h ed e c o m p o s em e t h o db a s e do nt i m e 2 2 c o n t e n t 2 2 2t h ed e c o m p o s em e t h o db a s e do ns p a c e 2 3 2 3t h ep r o c e d u r eo f j o bs h o pd y n a m i cs c h e d u l i n g 2 4 2 4s u m m a r yo ft h i sc h a p t e r 2 5 c h a p t e r3t h ee s t a b l i s h m e n to fr e a c t i v ea n di n t e r a c t i v es c h e d u l i n g s y s t e m 。”2 7 3 1t h er e a s o no fr e a c t i v ea n di n t e r a c t i v es c h e d u l i n gs y s t e mf o rm o u l djo b s h o p 2 7 3 1 1t h ep r o d u c t i o nc h a r a c t e r i s t i co fm o u l de n t e r p r i s e s 2 7 3 i 2t h es t a t u so fm o u l de n t e r p r i s e sm a n u f a c t u r i n gm a n a g e m e n t 2 8 3 1 3t h ep r o p o s a lo fr e a c t i v ea n di n t e r a c t i v es c h e d u l i n gs c h e m e 3 0 3 2t h eb u s i n e s sm o d e lo fm o u l de n t e r p r i s e sb a s e do nr e a c t i v ea n d i n t e r a c t i v e 3 0 3 3t h ef u n c t i o nm o d u l e so fr e a c t i v ea n di n t e r a c t i v es c h e d u l i n gs y s t e mf o r m o u l dj o bs h o p 3 2 3 4i n t e g r a t i o no fp r o c e s sp l a n n i n ga n ds c h e d u l i n g 3 3 3 5t h es y s t e mf r a m e w o r ko fr e a c t i v ea n di n t e r a c t i v es c h e d u l i n gs y s t e mf o r m o u l dj o bs h o p 3 4 3 6t h ea d v a n t a g eo fr e a c t i v ea n di n t e r a c t i v es c h e d u l i n g 3 6 3 7s u m m a r yo ft h i sc h a p t e r ：3 7 c h a p t e r4r e s e a r c ho fr e a c t i v ea n d i n t e r a c t i v es c h e d u l i n gs y s t e m a l g o r i t h mf o rm o u l dj o bs h o p 3 8 4 1t h em a t h e m a t i c a lm o d e l so fr e a c t i v ea n di n t e r a c t i v ej o bs h o p s c h e d u l i n g 3 8 4 1 1w i t ht h es h o r t e s tm a k e s p a na st h eo b j e c tf u n c t i o n 3 8 4 1 2w i t ht h ed e l i v e r yt i m ec o n s t r a i n ta st h eo b j e c tf u n c t i o n 39 4 2t h es c h e d u l i n gr u l e so fr e a c t i v ea n di n t e r a c t i v ej o bs h o ps c h e d u l i n g 3 9 4 3t h ea l g o r i t h mo fr e a c t i v ea n di n t e r a c t i v es c h e d u l i n g 4 0 4 3 1t h en e c e s s i t yo fr e a c t i v ea n di n t e r a c t i v es c h e d u l i n ga l g o r i t h m 4 0 4 3 2t h em e t h o do fr e a c t i v ea n di n t e r a c t i v es c h e d u l i n g 4 1 4 4t h ec a l c u l a t i o na n de x p e r i m e n to fa l g o r i t h ma n dt h ea n a l y s i so fr e s u l t 4 3 z i 5s u m m a r yo ft h i sc h a p t e r 4 8 c h a p t e r5r e a l i z a t i o no fm o u l dj o bs h o ps c h e d u l i n gs y s t e m 5 0 5 1t h ed e v e l o p m e n te n v i r o n m e n to ft h es y s t e m 5 0 5 2t h em a i ng u io ft h es y s t e m 5 0 5 3s i m u l a t i o ne x p e r i m e n t s 5 5 5 4s u m m a r yo ft h i sc h a p t e r 5 8 c o n c l u s i o na n df u t u r er e s e a r c h 5 9 1c o n c l u s i o n 5 9 2f u t u r er e s e a r c h 6 0 r e f e r e n c e 61 p a p e rp u b l i s h e d 6 6 s t a t e m e n t 6 7 a c k n o w l e d g e m e n t ，6 8 第一章绪论 第一章绪论弟一早三百了匕 1 1 引言 制造业是国民经济的基础，是国家经济实力的重要体现。制造业的水 平先进与否，既是国家科技实力的体现，也是科学技术发展的强大动力。 而科技的进步既为制造业的发展带来了机遇，也加剧了制造业的竞争，企 业必须在竞争中求生存、在竞争中求发展。企业要在现时的环境中立于不 败之地，缩短产品上市的时间、提高产品质量以及降低产品的成本无疑是 企业的必由之路，要实现这些目的，不仅要提高企业以及车间的管理水平， 同时也要提高生产过程中计划、调度以及决策的水平。 生产调度是制造系统生产管理的核心，生产管理任务顺利实施与完 成，最终要靠合理的车间调度来保证。生产调度研究的如何合理配置加工 过程的各种资源，减少零件的加工准备、等待与传送时间，从而提高设备 利用率与生产效率，降低生产成本。车间调度对任务的交货时间、各项生 产任务的生产周期、设备利用率和在制品占有率都有影响。因此，及时准 确的车间调度对生产系统的高效运行有着重要的影响，主要表现在：生产 计划的有效实施，高效低耗地使用生产资源，均衡生产及准时生产，减少 在制品的资金占用。所以，车间调度是制造业生产中最活跃和生产系统研 究的前沿问题之一。 1 。2 课题背景意义 随着世界经济的高速发展和人们生活水平的提高，市场结构发生了巨 大变化。一方面，交通和通讯技术的发展以及各国贸易限制的减少使得生 产竞争全球；另一方面，消费者的需求日趋个性化和多元化，市场结构已 由过去的“推 型市场转变为“牵拉”型市场。在此情况下，制造业面临 着一个由消费者占主导地位、变化迅速且无法预测的市场。传统的大批大 量生产模式对此难以适应，于是多品种、单件小批生产逐渐成为当今大多 数企业的主要生产模式。 广东工业大学硕士学位论文 车间作为敏捷化制造执行系统的物化中心，它是加工制造的具体执行 者，随着市场全球化趋势的加剧，车间生产环境越来越充满了不确定性， 因此要求车间面对任何不可预测的外部变化和内部扰动能够及时地、高质 量地、低成本地生产出满足客户要求的产品以适应敏捷制造的要求。 车间资源的合理配置、生产优化调度和控制是实现现代化生产管理的 核心，作为其核心之一的生产优化调度，其实现的关键就是要建立合理、 优化的作业车间模型并设计出恰当的算法。在目前的车间调度与控制决策 中，一般采用纯数学化、模型化、计算机化的决策方法，即先建立方程式、 不等式、逻辑式或分布函数等数学模型来反映决策问题，然后直接用数学 手段( 如：数学规划、排队论、网络图论等) 或启发式算法求解以提供优化 方案。然而，在敏捷制造环境下，上述作业车间的调度决策机制越来越不 适应车间动态变化和充满不确定性的制造环境，甚至成为制约车间生产敏 捷化的瓶颈，因此必须发展新的作业车间调度理论，建立新的作业车间调 度模型和算法。 面对这些已经存在生产调度上的问题，本文提出了一种基于交互反映 式的敏捷车间调度系统，在计算机自动排产的前提下，遇到突发事件时加 入生产调度人员和车间工程师的即时生产经验，降低各种不稳定因素对生 产系统造成的干扰，以提高系统的稳定性，增加企业的经济效益。 1 3 车间生产调度 1 3 1 车间调度问题描述 车间调度问题一般可以描述为：胛个工件在m 台机器上加工，一个工 件分为k 道工序，每道工序可以在若干台机器上加工。每一台机器在每个 时刻只能加工某个工件的某个工序，只能在上道工序加工完成后才能开始 下一道工序的加工，前者称为占用约束，后者称为顺序约束。 一个调度问题用三元组口i 卢iy 来描述。a 域描述机器环境并包含单一 一项；卢域提供加工特征和约束的细节，可能根本不包含任何一项，也可 能有多个选项。，域描述最小化的目标，常常包含唯一一项【l 】。 在a 域中可规定的机器环境有： 2 最简单的，是其他复杂 机器环境的特例。 ( 2 ) 并行同速机( p m ) ，并行的脚个速度相同的机器。工作_ ，需要单一操 作，可能在朋个机器的任何一台上加工，也可能在属于某个给定子集的任 何一台机器上进行加工。如果不允许工作7 f 仅简单地在任何一台机器上加 工，而必须在属于某个特定子集m ，的一台机器上进行加工，那么项m ，出 现在口域中。 ( 3 ) 并行异速机( q m ) 有m 台并行的具有不同速度的机器。机器f 的速 度记作v 。工作消耗在机器j 上的时间p , j = p j v ，( 假设工作_ ，所有的加工 都在机器i 上进行) 。这种环境称为一致机器。如果所有的机器具有相同的 速度( 即对所有的，有v = 1 以及p , j = p j ) ，那么这种环境和前一种相同。 ( 4 ) 并行的无关联的机器( r m ) 这种环境是前一种的一般化。有m 台不 同的并行机器。机器i 可以速度加- 1 - - 1 - 作。工作消耗在机器，上的时 间p , j = p j v , ( 假设工作歹所有的加工都在机器f 上进行) 。如果机器的速度独 立于工作( 即对所有的，和，有= v ) ，那么这种环境和前一种相同。 ( 5 ) 流水车间( f m ) 有串行的m 台机器。每项工作都必须经过每台机器 加工。所有工作都必须遵循相同的加工路径( 即它们必须首先在第一台机器 上加工，然后是第二台，以此类推) 。在一台机器上完成加工后，工作加入 到下一台机器的队列中。通常，假设所有的队列都遵循先入先出( f i r s ti n f i r s to u t ，f i f o ) 的规则一一也就是说，在队列中等待的时候，一项工作不能 “跳过”另一项。如果f i f o 规则有效，则这种流水车间称为流水车间，p 域包含项p r m u 。 ( 6 ) 柔性流水车间( f f e ) 柔性流水车间是流水车间和并行机环境的一 般化。代替m 台串行机器的是c 个串行工位，每个工位有许多并行同速机。 每项工作必须先在工位1 上加工，然后工位2 ，工位3 ，如此等等。每个 工位起到并行机器组的作用。在每个工位上，工作，只需要在一台机器上 加工，而每一台机器都可以完成这项工作。一个工位的队列可以遵循也可 以不遵循先来先服务( f i r s tc o m ef i r s ts e r v e d ，f c f s ) 的规则。 ( 7 ) 加工车间( j m ) 在有聊台机器的加工车间里，每项工作都有它自己 预先确定的加工路径。有所区别的是，在每项工作最多访问一台机器一次 广东工业大学硕士学位论文 的加工车间和一项工作可能访问一台机器多次的加工车间。在后一种情形 中，卢域包含表示再循环的项r e c t o 。 ( 8 ) 柔性加工车间( f j c ) 柔性加工车间是加工车间和并行机环境的一 般化。代替m 台机器的是c 个工作中心，每个工作中心有许多并行同速机。 每项工作遵循它自己的加工路径通过车间，工作，只需要在每个工作中心 的一台机器上加工，而每一台机器都可以完成该工作。如果一项工作需要 在它自己通过车间的加工路径访问一个工作中心多次，那么3 域包含表示 再循环的项r e c r c 。 ( 9 ) 开发车间( 0 m ) 有m 台机器。每项工作在每台机器上都进行多次加 工。但有些加工时间可以是零。对每项工作的加工路径没有任何限制。允 许调度者为每项工作确定加工路径，而不同的工作可以有不同的加工路 径。 口域中说明的加工约束和特定限制可能包括多项。3 域中可能的项有： ( 1 ) 提交日期( ，) 如果这个符号出现在p 域中，工作，不可能在它的 提交日期厂j 前开始加工。如果，没有出现在3 域中，工作，的加工可以在 任何时候开始。与提交日期不同，工期不再该域中规定。目标函数的类型 给出了是否有工期的要求。 ( 2 ) 顺序决定的准备时f a q ( s 肚) s 肺代表工作和工作k 之间的加工顺 序决定的准备时间。如果工作k 是第1 个，则。表示工作k 的准备时间； 如果工作是最后一个，则s ，。表示工作之后的清理时间( 当然，& 。和s ，。可 能是零) 。如果工作，和工作k 之间的准备时间依赖于机器，那么将包含下 标f ( 即) 。如果j 6 i 域中没有出现s 庸，所有的准备时间都假设为零或者与 顺序无关，在这种情况下，它们包含在加工时间中。 ( 3 ) 中断( p r m p ) 中断意味着不必将一项工作在其加工完成之前一直 保留在机器上。它允许调度者在任何时间中断一项工作的加工( 中断) ，而 把另一项工作放在该机器上。一项中断的工作已经进行的加工不会丢失。 当一项中断的工作重新返回到机器上时，它只需要加工完剩下的工作即 可。当允许中断时，p r m p 包含在卢域中；当p r m p 不在卢域中时，不允许 中断。 ( 4 ) 优先约束( p r e c ) 优先约束可能出现在单机或并行机环境中，在一 第一章绪论 项工作开始加工前，另一项或多项工作必须先完成。有几种优先约束的特 殊形式；如果每项工作最多有一个前驱，最多有一个后继，约束称为链式； 如果每项工作最多有一个后继，该约束称为入树；如果每项工作最多有一 个前驱，那么该约束称为出树。如果卢域中没有出现p r e c ，则工作不受优 先限制。 ( 5 ) 故障( b r k d w n ) 机器故障意味着机器不能连续使用。如果有许多相 同的并行机器，在任何时间点可用机器的数量是时间的函数( 即r e ( t ) ) 。 ( 6 ) 机器适用限制( m ，) 当加工环境是t n 台并行机器( p m ) 的时候，符 号m ，会出现在卢域中。当m ，出现时，意味着并不是所有m 台机器都有能 力加工工作，。集合m ，表示可以加工工作，的机器集合。如果j b 域中不包 含m ，则工作，可以在任何一台机器上加工。 ( 7 ) 排列( p r m u ) 在流水车间环境中可能出现的约束是每台机器前的 队列遵循f i f o 规则。这意味着所有工作经过第l 台机器的顺序( 或者排列) 与系统中其他机器上的加工顺序是一致的。 ( 8 ) 阻塞( b io e k ) 阻塞是可能出现在流水车间中的现象。如果一个流 水车间在两天连续的机器之间只有有限的缓冲区，那么可能出现当缓冲区 满的时候，上游的机器不允许释放已经加工好的工作。这种现象就是人们 所熟知的阻塞，即加工完的工作不得不保留在上游机器上，从而阻止或阻 塞那台机器上加工别的工作。阻塞发生的最普通的情况是在任何两台连续 的机器间缓冲为零。在这种情况系，如果前一项工作在下一台机器上还没 有完成它的加工，那么在一台给定的机器上完成加工的工作就不能离开那 台机器。因此，阻塞的工作也阻止或阻塞下一项工作在这台机器上开始加 工。在后面章节中考虑的带阻塞的模型中，假设机器遵循f i f o 规则。也 就是说，阻塞意味着p r m u 。 ( 9 ) 无等待( n w t ) 无等待需求是可能发生在流水车间中的另一种现 象。工作不允许在两台连续的机器间等待。这意味着一项工作在第l 台机 器上的开始时间不得不推迟，以保证该工作可以不必等待任何机器而通过 流水车间。这种操作的一个例子是在轧钢厂中，不允许钢板等待，因为在 等待过程中它会冷却。很明显，在无等待条件下，机器仍然在f i f o 规则 下运行。 广东工业大学硕士学位论文 ( 1 0 ) 再循环( r e c r c ) 在加工车间或柔性加工车间中，当一项工作可能 访问一台机器或加工中心超过一次的时候，发生再循环。 最小化的目标是所有工作完成时间的