（管理科学与工程专业论文）模糊环境下的flexible+jobshop调度问题的研究.pdf

。中圈斜爹投京大孥博：i ：学位论文 模糊环境下的f l e x i b | c i 。b s h o p 训度问题的研究 摘要 模糊环境下的柔性作业车l 、自j 调度( f l e x i b l ej o b s h o ps c h e d u l i n g ，f j s s ) 问题是实际生产系统中的核心问题之一，它是由古典作业车间调度( j o b s h o p s c h e d u l i n g ，j s s ) 问题逐渐引申、发展而来的。古典j s s 问题是一个经典问题， 至今还是一个研究热点，由于j s s 问题对机器加工路线做了限定，因此难以适用 于柔性制造系统。f j s s 问题对古典j s s 问题进行了扩展，允许操作可以在多台 机器上进行加工，从而更加接近实际工作环境，具有重要的理论价值和工程意义。 现有的针对f j s s 问题的研究大都建立在对调度环境进行严格限制的基础 上，强调各类限制条件和生产信息预先明确，然而在实际生产环境中，存在人力、 机器、环境等因素的影响，致使包括时间参数和约束条件在内的相关信息无法准 确预知，存在模糊不确定性。本文将f j s s 问题从严格限定的理想环境拓展到逼 近现实的模糊环境中，使其具有更强的灵活性和实用性。 首先，本论文研究了以最小化制造跨度为目标的，具有模糊加工时间与模糊 操作延迟的t o t a lf l e x i b l ej o b s h o ps c h e d u l i n g ( t f j s s ) 问题本文引入模 糊理论和可能性理论，针对该问题的子问题，分别采用区间数有符号距离测度、 可信性测度等方法，进行了系统的阐述，最后分别通过遗传算法进行有效求解。 其次，本论文研究了以最小化制造跨度为目标的，具有模糊加工时间的 p a r t i a lf l e x i b l ej o b s h o ps c h e d u l i n g ( p f j s s ) 问题。针对该问题，本文采 用三角模糊数来表征时间参数，并研究了预处理算法将p f j s s 问题转化为更容易 处理的t f j s s 问题，最后通过遗传算法进行有效求解。 最后，本论文研究了以最小化提h l f 拖期惩罚为目标的，具有模糊加工时间 与模糊交货期的f j s s 问题。针对该问题，本文结合有符号距离测度和区间数距 离测度方法，构造出一种具有更高计算精度的提前拖期惩罚函数，最后通过遗 传算法进行有效求解。 关键词：柔性作业车间调度；模糊理论：模糊交货期；遗传算法 q 哼圈斜季拽意大学博：i j 学位论文 模糊环境下的f i e 。i b i ej 。b s h 。p 调度问题的硐究 a b s t r a c t f l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m ( f j s s ) i nf u z z ye n v i r o n m e n ti so n eo ft h e m o s ti m p o r t a n ti s s u e si np r a c t i c a lf l e x i b l em a n u f a c t u r i n gs y s t e m s ，c h i c he x t e n d sa n d d e v e l o p e sf r o mc l a s s i c a lj o b s h o ps c h e d u l i n g ( j s s ) p r o b l e m j s sp r o b l e mi sac l a s s i c p r o b l e ma n di ss t i l lah o t s p o t ，h o w e v e r ，r e s t r i c t e db yf i x e dm a c h i n er o u t e ，j s sm o d e l d o e sn o ta c c o m m o d a t et of l e x i b l em a n u f a c t u r i n ge n v i r o n m e n t f j s se x t e n d st h ej s s b ya l l o w i n ga no p e r a t i o nt ob ep e r f o r m e do nm o r et h a no n em a c h i n e ，w h i c hc o n s i d e r s t h ef l e x i b i l i t yo fp r a t i c a lm a n u f a c t u r i n gs y s t e ma n di tp r e s sc l o s et or e a le n v i r o n m e n t ，w h i c hh a sv e r yi m p o r t a n tv a u l ei nt h e o r ya n de n g i n e e r i n gm e a n i n g m o s tr e s e a r c h e sa b o u tf j ssp r o b l e m sa r el i m i t e di ns t r i c tr e s t r i c t e de n v i r o m e n t s i nw h i c ha l lk i n d so fi n f o r m a t i o na n dr e s t r i c t i o n sa r ep r e d e f i n e d h o w e v e r , a f f e c t e d b yh u m e n ，m a c h i n e sa n de n v i r m e n t a lf a c t o r s ，t h ec o r r e s p o n d i n gi n f o r m a t i o ns u c ha s r e s t r i c t i o n sa n dt e m p o r a lp a r a m e t e r sa r eu n c e r t a i n a n dc a i ln o tb ep r e d e f l n e dp r e c i s e l y t h i sd i s s e r t a t i o ne x t e n df j ssp r o b l e mf o r mi d e a le n v i r o n m e n tt op r a c t i c a lf u z z y e n v i r o n m e n tw h i c ha r em o r ef l e x i b l ea n dp r a c t i c a l f i r s t ，t h i sd i s s e t a t i o ns t u d i e st h et o t a lf l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m a i m i n ga tm i n i m i z e dm a k e s p a nw h i c hh a sf u z z yo p e r a t i o nt i m ea n df u z z yo p e r a t i o n s i n t e r v a l s i n t r o d u c i n gf u z z yt h e o r ya n dp o s s i b l et h e o r y ，i tu s et h et h es i g n e dd i s t a n c e m e a s u r ea n dt h ec r e d i b i l i t ym e a s u r ea n do t h e rm e t h o d st oi l l u s t r a t ee a c hs u b - p r o b l e m o ft h i sp r o b l e ma n di tu s eg e n e t i ca l g o r i t h mt og e tp e r f e c ts c h e d u l i n gs c h e m e s r e s p e c t i v e l y t h e n ，t h i sd i s s e r t a t i o ns t u d i e st h ep a r t i a lf l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m w h i c hh a sf u z z yo p e r a t i o nt i m ea n dw h i c ha i m sa tm i n i m i z e dm a k e s p a n f o rt h i s p r o b l e m ，i ti n t r o d u c e st r i a n g l ef u z z yn u m b e rt od e n o t et i m ep a r a m e t e r s ，a n di ts t u d i e sa p r e t r e a t m e n ta l g o r i t h mt oc h a n g ep a r t i a lf l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e mi n t o t o t a lf l e x i b l ej o b s h o ps c h e d u l i n gp r o b l e m ，t h e na ni m p r o v e dg e n e t i ca l g o r i t h mi s g i v e nt og e tap e r f e c ts c h e d u l i n gs c h e m e f i n a l l y , t h i s d i s s e r t a t i o ns t u d i e st h ef l e x i b l ej o b s h o p s c h e d u l i n gp r o b l e m 。串圈甜营投赤大学博f j 学位论文 模糊王1 i 境下的f 1 e x b l 。j 。b s h o p 训度问题的i 卅究 a i m i n ga tm i n i m i z e de tp e n a l t yw h i c hh a sf u z z yo p e r a t i o nt i m ea n df u z z yd u ed a t e s f o rt h i sp r o b l e m ，i ti n t r o d u c et h et h es i g n e dd i s t a n c em e a s u r ea n dt h ei n t e r v a ln u m b e r d i s t a n c em e a s u r et oc o n s t r u c tae tp e n a l t yf u n c t i o nw h i c hh a sm o r ep r e c i s i o n ，t h e ni t u s eg e n e t i ca l g o r i t h mt og e tap e r f e c ts c h e d u l i n gs c h e m e k e y w o r d s ：f l e x i b l ej o b s h o ps c h e d u l i n g ；f u z z yt h e o r y ；f u z z yd u ed a t e ；g e n e t i c a l g o r i t h m 。中避裔季投瘁丈爹博士学位论文 模糊环境下的f l e x i b l ej 。b s h 叩调度问幽堕 第一章绪论 生产调度，即对生产过程进行作业计划，是整个先进生产制造系统实现管理 技术、运筹技术、优化技术、自动化技术和计算机技术发展的核心。有效的调度 方法和优化技术的研究和应用，是实现先进制造和提高生产效益的基础和关键。 改善生产调度方案，可以显著提高生产效益和资源利用率，进而提高企业竞争能 力。 1 1 调度问题概念 1 1 1j o b - s h o p 调度问题 调度问题是指作业或任务如何占用有限资源的决策过程。典型的车间调度问 题包括一个要完成的作业( j o b ) 集，每个作业由一个操作( o p e r a t i o n ) 集组成， 各操作的加工需要占用机器( m a c h i n e ) 或其它资源，并且必须按一些可行的工 艺次序进行加工；每台机器可加工作业的若干操作，并且在不同的机器上能加工 的操作集可以不同。调度的目标是将作业合理地安排到各机器，并合理地安排作 业的加工次序和加工开始时间，使约束条件被满足，同时优化一些性能指标。 在包含肌台机器( m a c h i n e ) 似，鸩，坂夕和门个作业( j o b ) ，以，以，的 调度问题中，通常一个作业j ，包含圪，个操作( o p e r a t i o n ) ，d ，一q 。q ，。记 操作0 ：! 的可用机器集为心彤，心，m 。，q 可以在心中的任何一台机器 上加工。通常熊仅对应一台机器或对应所有机器，前者称为专用机器( d e d e c a t e d m a c h i n e ) ，后者称为并行机( p a r a l l e lm a c h i n e ) 。在许多现实生产系统中，各 机器可以装备相同或不同的工具，操作可以在任何一台装备适合工具的机器上加 工，这就是生产系统的柔性，该调度称为多目的机器( m u l t i p u r p o s e m a c h i n e s ，m p m ) 调度，如果q ，的加工过程同时占有x 。i 中的全部机器，则该调度 固申瀚鹰季莰：l i ：太季博= 卜学位论文 模糊环境下的f l e x b l ej 。b s h 。p 调度问题的形i ：究 司题称为多处理机任务调度( m u l t i p r o c e s s o rt a s ks c h e d u l i n g ) 。对作业以， 其计划完成时间或交货期( d u ed a t e ) 表示为d ；。 如果同一机器上没有任意两个时间区间的重叠，也没有分配给同一个作业的 任何两个时间区间重叠，并且满足调度问题的一些特殊工艺要求，则称一个调度 为可行( f e a s i b l e ) 调度，使得调度准则或指标最优的可行调度为最优( o p t i m a l ) 调度。 作业车间调度( j o b s h o ps c h e d u l i n g ) 问题( 简称j s s ) 是许多实际生产 调度问题的简化模型，具有重要的理论意义和工程价值，也是目前研究最广泛的 一类典型调度问题。j s s 问题研究门个作业在m 台机器上的加工过程，第f 个作 业在第，台机器上的相应的加工时间p i 为已知，事先给定各作业在各机器上的加 工次序( 称为技术约束条件) ，要求确定与技术约束条件相容的各机器上的所有 作业的加工次序，使得加工性能指标达到最优。若各作业的技术约束条件相同， 一个j o b s h o p 调度问题就转化为较为简单的f l o w s h o p 调度问题。进而，若各 机器上各作业的加工次序也相同，则问题可迸一步转化为置换f l o ws h o p 调度问 题。 在典型的j o b s h o p 调度问题中，除技术约束条件外，通常还做出以下假设： 1 ) 每一时刻每台机器只能加工一个作业，且每个作业只能被一台机器加工，加工 过程不问断，整个加工过程中机器均有效； 2 ) 整个加工工程中，每个作业不能在同一台机器上加工多次： 3 ) 各作业必须按照工艺路线以制定的次序在机器上加工； 4 ) 不考虑作业加工的优先权； 5 ) 操作允许等待，即一个操作未完成时，后面的操作需要等待； 6 ) 作业的加工时间事先给定，且在整个加工过程中保持不变。 下面给出一个n m g c , ，。调度问题的数学描述 m i n m a x m a x c j k ， ( 1 ) l k m l f 门 s t g p i k + m ( 1 一a i h 女) i = 1 ，2 ，门；h ，k = l ，2 ，聊 固串驾奢季投， ：失擎博二b 学位论文 模糊环境下的f l e x i b l ej 。b s h 。p 调度问题的研究 c _ 一g + m ( 一勃t ) p j k i ，= l ，2 ，职；七= l ，2 ，朋 q k 0 ，i2 1 ，2 ，2 ；h ，k2 1 ，2 ，聊 2 0 或1 ，i ，2 1 ，2 门；尼= l ，2 ，聊 ( 2 ) 式( 1 ) 表示目标函数制造跨度为m i n 聊锻砌甜c i k ，。式( 2 ) 表示工艺约束条件决 定的各作业的各操作的先后加工顺序以及加工各个作业的各机器的先后顺序。 c 瑭和最分别表示作业f 在机器尼上的完成时间和加工时间，m 是一个足够大的 正整数，a i h k 为指示系数，若机器h 先于机器七加工作, _ l k i 则。为1 ，否则为0 。 嘞为指示变量，若作业f 先于作业在机器尼上加工，则为l ，否则为0 。 1 1 2f i e x i b l ej o b s h o p 调度问题 在古典作业车间调度问题中，2 个作业在肌台机器上进行加工，每个作业包 含加个操作，按照己知的加工时间和次序进行，j s s 假定进行作业加工的机器路 线是固定的，因此难以适应柔性生产系统。柔性作业车间调度( f l e x i b l e j o b s h o ps c h e d u lin g ) 问题( 简称f j s s ) 对j s s 进行了扩展，允许一个操作可在 多台机器上加工，操作的加工时间随机器的性能不同而变化。f j s s 肫够充分发挥 调度系统的灵活性，比较符合生产的实际情况。 柔性作业车间调度问题可以被描述为： 生产系统内有，2 个相互独立的作业( j o b ) ，第个作业表示为弘6 ，j n ，zo 对某个作业j o b ，包含，2 ，个操作( o p e r a t i o n ) ，表示为一组有序操作 集合q ，f ( 1 甩，) ，这组操作序列用以表示。生产系统内有m 台机器 ( m a c h i n e ) ，第七台机器表示为心a 对每个操作q ，有一组机器可以用来加工， 这组机器表示为坞。操作q 在机器鸭上的开始时间为s j k ，完工时间记为， 加工时间已经预定义，用磁表示。加工时间随着机器的不而不同，这主要是由 机器的性能和加工能力决定的每个操作q 在加工期间不可以被中断。在任一时 。中蹿辞季辍j 弼, i 丈爹博：卜学位论文毽坚型f l 堂j 旦b - s h 9 卫塑望塑婴壅 刻，一台机器至多只能处理一个操作。目标是发现一种满足某种最优标准的调度 方案。 以最小化制造跨度为目标的f j s s m 题可以描述为： m i n m a x s n j j k + 瓦肿，( 1 以) s t e u k e 够 女毛k1 i ，女2 x 晒似2 1 ( 1 ) e e 醇一e 口k 2 t 噼 e j k t j k ， x 4 k 2x 噼21 ，r 孵。1 x j k 2 、 厂l ，q 和。品在m k 上执行，若q 先于0 曙 r 啦2 l 0 ， 其它 rl ，若q 在心上执行 x 驰2 l0 ，其它 ( 2 ) ( 3 ) 约束条件：( 1 ) 顺序约束工艺要求的同一作业相邻操作间的加工顺序。即 作业i 的第i 个操作必须在第i ，个操作完成后才能开始。( 2 ) 资源约束一同 一机器k 上一个加工任务完成后才能开始另一个任务的加工。即任一确定时刻， 机器k 不能同时加工任意两个不同的作业，也不能同时加工任意两道不同的操 作。( 3 ) 其它约束任何一道操作的完工时间不能小于其加工时间。 1 1 3 模糊环境下的f ie xibiej o b - s h o p 调度问题 f l e x i b l ej o b s h o p 调度( f j s s ) 问题是柔性生产系统计划和操作中的核心 问题之一，当前对f j s s 问题的研究大都局限在理想的确定性环境引，然而在现 实生产系统中，存在机器因素、人力因素和环境因素的影响，致使包括时间参数 在内的相关信息无法准确预知，存在模糊不确定性。例如作业的准确加工时间难 以预先确定，同一作业的相邻两个操作之间也往往存在模糊的时间延迟等等。随 着模糊数学的发展以及模糊规划思想在调度领域内的成功应用，有关模糊交货 期，模糊加工时间的模糊调度问题以及成为研究的热点。但当前对于模糊环境下 车问调度问题的研究，多限定于古典j s s 问题，对于模糊环境下的f j s s 问题的 4 母壤崭季莰# 大爹博：卜学位论文 模糊环境下的f l e x i b l ej o b - s h 。峭度阀塑幽 研究还鲜有文献报道。 1 2 研究问题 本论文主要研究以下三个问题： 1 ) 模糊环境下的t o t a lf l e x i b l ej o b s h o p 最小化制造跨度调度问题； 2 ) 模糊环境下的p a r t i a lf l e x i b l ej o b s h o p 最小化制造跨度调度问题； 3 ) 模糊环境下的f l e x i b l ej o b s h o p 的最小化e t 惩罚调度问题。 下面具体描述这三个问题。 。 1 2 1 模糊环境下的t o t a lf l e x i b l ej o b s h o p 最小化制造跨度调度问 题 针对该问题，本文着重研究以下三个子问题： 1 ) 有模糊加工时间的t o t a lf l e x i b l ej o b s h o p 最小化制造跨度调度问题 问题可以被定义为：有玎个相互独立的作业( j o b ) ，第个作业表示为0 ，( 1 n ) 。对某个作业j o b j ，包含，l ，个操作( o p e r a t i o n ) ，表示为一组有序 操作集合q ，i ( 1 ，z ，) ，这组操作序列用以表示。有m 台机器( m a c h i n e ) ， 第k 台机器表示为m k 。操作0 ：! 在系统中任何一台机器上加工，q 在机器m 上 的加工时间& 是不确定的，用模糊数表征，每个操作q 在加工期间不可以 被中断，并且在任一时刻，一台机器至多只能处理一个操作。目标是发现一种制 造跨度最小的调度方案。 2 ) 有模糊操作延迟的t o t a lf l e x i b l ej o b - s h o p 最小化制造跨度调度问题 问题可以被定义为：有，2 个相互独立的作业( j o b ) ，第个作业表示为0 ( 1 ，2 ) 。对某个作业弘乞，包含咒，个操作( o p e r a t i o n ) ，表示为一组有序操 作集合0 ：! ，i ( 1 _ ) ，这组操作序列用z 表示。有朋台机器( m a c h i n e ) ，第 中龋辩季段菇天誊博? ，l 二学位论文 模糊环境下的f i 。x i b l 。j o b s h 。p 调度问题的研究 k 台机器表示为m 。操作o u 在系统中任何一台机器上加工。操作q 和o i “，之 间存在模糊时间延迟0 ，0 用模糊数表征，每个操作q 在加工期间不可以被中 断，并且在任一时刻，一台机器至多只能处理一个操作。目标是发现一种制造跨 度最小的调度方案。 3 ) 有模糊加工时间和模糊操作延迟的t o t a lf l e x i b l ej o b s h o p 最小化制造跨度调 度问题 问题可以被定义为：有刀个相互独立的作业( j o b ) ，第个作业表示为j o b j ( 1 珂) 。对某个作业弘色，包含门。个操作( o p e r a t i o n ) ，表示为一组有序操作 集合q ，f ( 1 门，) ，这组操作序列用以表示。有朋台机器( m a c h i n e ) ，第ka 口 机器表示为心。操作q 在系统中任何一台机器上加工。操作q 在机器地上的 加工时间弓。是不确定的，q 和o i 之间也存在模糊时间延迟0 ，t j k 和勺分别用 模糊数表征，每个操作q 在加工期间不可以被中断，并且在任一时刻，一台机 器至多只能处理一个操作。目标是发现- - 椭 1 造跨度最小的调度方案。 1 2 2 模糊环境下的p a r tia lfie ibied o b - s h o p 最小化制造跨度调 度问题 在现实生产系统中，存在不同类型的机器，待加工的作业对机器的要求也不 同，造成某些操作只能在系统的机器集合中的部分机器上执行，此类问题称为 p a r t i a lf l e x i b l ej o b s h o p 调度( p f j s s ) 问题。在p f j s s 问题中，某些操作 只能选择系统机器集合中的部分机器来执行。 在现实生产系统中，由于人力介入等原因，存在着大量的不确定性因素 9 , 1 0 , t l 】，包括加工时间在内的诸多参数具有模糊性。在此类模糊环境下的p f j s s 问题被归为模糊环境下的p f j s s 问题。p f j s s 问题可以被定义为：有n 个相互独 立的作业( j o b ) ，第个作业表示为弘6 ，j ( 1 甩。对某个作业弘6 i ，包含 6 固寸避鸯爹辍球丈爹博：i ：学位论文模糊环骶监哆i 堕1 2 1 ：! ! ! 旦塑壁塑型! ! 塑 n j 个操作( o p e r a t i o n ) ，表示为一组有序操作集合q ，i ( 1 _ ) ，这组操作序 列用以表示。有m 台机器( m a c h i n e ) ，第k 台机器表示为坂。对每个操作q ， 有一组机器可以用来加工，这组机器表示为坞，l 坞l s 朋且i b l i i 己m 。 每个操作q 在加工期间不可以被中断，并且在任一时刻，一台机器至多只能处 理一个操作。目标是发现一种制造跨度最小的调度方案。 1 2 3 模糊环境下的f l e x i b l ej o b s h o p 最小化提前拖期惩罚调度问题 现实的生产系统中存在很多不确定因素，如机器故障、工人劳动能力变化、 原材料的差异和环境参数变化等。顾客对交货期的要求也是一个变化范围，在某 一时刻交货顾客的满意度最高，偏离这一时刻满意度变小。这样，用模糊数表示加 工时间和交货期更加符合实际。现代准时生产制( j i t ) 要求作业按时加工，准时 交货，因此提前拖期( e a r l i n e s s t a r d i n e s s ，e t ) 问题已经成为受到广泛关注的 热点问题提前拖期调度问题规定不论任务的完成时间早于还是晚于交货期都 将受到惩罚。 具有模糊加工时间和模糊交货期的柔性作业车间的最小化提前拖期惩罚调 度问题可以描述为：有玎个待加工的的作业( j o b ) ，作业弘6 ，包含，z ，个操作， 表示为一组有序操作集合q ，( 1 n ) ，i ( 1 玎，) 。系统有m 台机器 ( m a c h i n e ) 每个操作q ，有一组机器可以用来加工。操作d j ，在机器鸭上的加 工时间为乙，乙为模糊数。没个操作。： 在加工期间不可以被中断，并且在任 一时刻，一台机器至多只能处理一个操作。作业的完成时间为c i ，交货期为 q ，提i z l _ f j x u _ a 、jl 、a - - 易2 m a x o ，q q ) ，拖期时间弓= m a x o ，q q ) 。提前拖 期指标通常为r a i ne t , ，。= 加饿一弓+ q 乃，。如果作业的完工时间c ，和交货期d ， 不相符，就会受到提前拖期惩罚。要求获得具有最小提前拖期惩罚的调度方案。 q 中鹤磷誊投，l ：大擎博：卜学位论文模糊环境下的! l e x i b 堡坐| ；! 型型鐾! 型_ | _ i ! 堕 1 3 研究现状 1 3 1 具有模糊a n t 时间的调度问题 在制造业进入后大量生产( p o s tm a s sp r o d u c t i o n ) 时期，客户的需求更加多 样化和个性化，产品的种类不断增加，导致产品的生命周期逐渐下降，而产品的结 构越来越复杂，开发的难度也越来越高对于一些新产品，特别是单件加工的新 产品，在生产调度时，无法确切得到其加工时间，只能通过对以往曾经加工的类似 作业的加工时间的分析，结合现场的实际经验，将作业的加工估计为在一定区间 变化的模糊变量例如，某小型电器常随着客户的个人喜好进行改变，则作业 的成型周期( 加工时间) 变为一个模糊变量关于加工时间不确定的调度问题， 一般认为加工时间是随机的，但是，像上述加进人类主观因素的估计，理解 为模糊的变量更接近于实际，并且运用模糊模型可以方便地计算模糊变量迭加 的联合隶属函数，而随机变量迭加的联合随机函数，只有随机变量服从均匀分布 时容易计算得到，其它分布时几乎无法计算i z j 随着模糊数学的发展，模糊数学规划【3 ，4 】的思想被运用到调度领域，形成非 确定性调度的一个重要分支模糊调度1 5 j 目前，关于模糊调度问题的研究， 主要集中在模糊数的操作问题上，主要包括模糊数的求和，取大，以及模糊数之 间的比较等方面的研究。 针对调度问题中的模糊加工时间的研究已经取得了一定的进展，m i t s u r u k u r o d a 和f e n g _ - t s el i n l 6 1 等用三角模糊数对j o b s h o ps c h e d u l i n g 模糊加工时 间等问题进行了分析，t z u n g p e ih o n g 等【7 】用三角模糊数对双机f l o w - s h o p 中的 时间参数进行了分析。o m a ra g h r a y e b 8 1 采用三角模糊数来处理j o b - s h o p 中的 多目标优化问题。p a u im s t a n f i e l d 等【9 】用通用l r 模糊数和梯形模糊数来解决 单机调度中的模糊加工时间问题。f e n g t s e 等【1 0 】用( 入，1 ) 区间值模糊数来表 征模糊作业车间调度中的模糊加工时间，j i n g - s h i n gy a o 等【l l 】用( 入，p ) 三角 区间值模糊数和有符号距离来处理f l o w s h o p 中的加工时间问题j u i t ew a n g 1 2 】 用六角梯形来表征项目调度中的模糊时间间隔问题。 然而对于模糊加工时间问题的探讨大都集中在古典j s s 问题和f l o w s h o p 调 度问题中，对更加复杂的f j s s 问题的探讨尚未发现相关文献。 固审鹤辞孥段菇失擘博= t ：学位论文 模糊环境下的f 1 。x i b l 。j 。b s h o p 调度问题的研究 1 3 2 具有模糊交货期的调度问题 模糊生产环境下单独模糊加工时间与模糊交货期综合问题的研究是当今全 球性竞争机制带来的必然趋势，具有极其广泛的应用价值和实际背景。1 9 9 2 年， i s hi i 【5 】提出了关于模糊交货期的调度问题，首次提出应将交货期视为模糊数， 并对开环车间的双机调度问题作了研究。随后学者们相继就模糊交货期下的具有 不同目标函数的调度问题进行了研究，i s h i b u c h ih 等l l 驯对模糊f l o w s h o p 调度中 的模糊加工时间进行了描述，h a r ts 等【1 4 j 研究了单机模糊交货期的调度问题， a d a m o p u l o u sg i 等【1 5 】用基于邻域搜索的混合方法研究了具有模糊交货期和可变 加工时间的单机调度问题；t s u j i m u r ay 等【l6 j 运用遗传算法求解了模糊调度中的 模糊加工时间问题；s a k a w am 、m o i lt 【1 7 j 就模糊加工时间与模糊交货期下的单 件作业车间调度问题进行了研究，设计了一个有效的遗传算法；i t o ht 等【1 8 】将 m o o r e ( 1 9 6 8 ) 的调度模型磨合化，并正面了这种模糊化的可能性；c h a n a ss 等【l 9 】 研究了单机模糊调度问题；m u r a t at 等【2 2 j 研究了模糊交货期下的多目标调度问 题；s a k a w am ，k u b o t a 【2 3 】就单件作业的多目标模糊规划问题做了研究。 在对模糊交货期问题的时间参数表征上，j u i t ew a n g 眩】用六角梯形来表征 项目调度中的模糊交货期，s s l a m 等【2 0 j 用l - r 模糊数和来表示单机调度中的模 糊加工时间和模糊交货期，并定义了一种基于期望距离的拖期惩罚函数。h i s a o i s h i b u c h i 等【2 l j 用梯形模糊数来表征模糊加工时间，用三角模糊数、梯形模糊数 来表示不同要求下的模糊交货期，t a d a h i k om u r a t a 等【2 2 】用三角模糊数、梯形模 糊数、单调递减模糊数来表征不同情况下的作业完成时间，解决一类基于不同交 货期要求的多目标模糊调度问题。m a s a t o s h is a k a w a 等【2 3 】分别用三角模糊数和 梯形模糊数来表征模糊加工时间和模糊交货期。s l o b o d a nr i b a r i c 等乜郇采取基 于模糊交集面积的方法来度量和比较用三角模糊数和梯形模糊数表征的时间参 数。 针对古典j s s 问题中的模糊加工时间和模糊交货期问题的研究已经取得了 一定的进展。m a s a t o s h is a k a w a 2 3 1 等提出了基于模糊数交集面积的交货期满意度 函数，试验表明，该方法存在判别条件繁琐、计算量大等问题，难以适用于复杂 的模糊数模型。s sl a i l 【2 0 1 等提出了一种适于用单机调度的基于模糊数距离的交 9 q 串壤裔誊较亦丈擎博：l 学位论文 模糊环境下的f l e x i b l ej o b s h 叩调度问题的研究 货期惩罚函数，l i e mt r a n 5 0 1 用区间数距离来测量两个模糊数的距离，测量的准 确度较高，但存在测度公式过于冗长等问题。p r z e m y s l a wg r z e g o r z e w s k i s 1 采用 了最近区间模拟的方法，然而模糊数之间先后次序区分困难。在现实生产系统中， 每个待加工作业的调度标准往往存在差别，不同作业的交货要求也有所不同。 j i n g s h i n gy a o 4 0 , 4 9 1 采用有符号距离来测量和比较模糊参数，可以较好的估算模糊 时间参数之间的距离和先后次序。 1 3 3j o b s h o p 调度问题求解算法 j s s 属于n p - - h a r d 类【25 l ，因此开发求解j s s 的有效算法一直是调度和优化 领域的重要课题。迄今，研究j s s 的方法包括传统运筹学方法、启发式规则、分 枝定界法、人工智能、仿真方法、神经网络、l a g r a n g i a n 松弛法、模拟退火s a 、 遗传算法g a 、禁忌搜索t s 、蚁群系统和混合算法等【5 2 】。k a n e t 等2 6 1 提出了一种解 决单机生产调度问题的遗传算法：f a l k e n u e r 等旧提出了一种健壮性遗传算法处 理具有优先权限制的j o b - s h o p 调度问题；s i t t i s a t h a n c h a i 等【2 8 】提出了一种遗 传算法，在确定的生产系统中产生j o b s h o p 调度；在柔性作业车间调度方面， n a ji b m n a jid 等【2 9 】提出了一种面nf j s s 口 题的模拟退火算法；i m e dk a c e m 等【3 2 】 用遗传算法来解决f j s s j h 题：h a o x u nc h e n 等【3 6 1 提出了一种双染色体双循环的遗 传算法来解决f j s s i s 7 题；y a z i dm a t i 等3 0 1 用启发式贪心算法来解决f j s s f 口 题； t i e n t eh s u 等川用进化算法解决多目标f j s s i 口 题； 对于j s s 问题目前的若干求解方法，大量研究标明： 1 ) 枚举方法，如分支定界策略，计算量和存储量巨大，难以应用于大规模调度 问题。 2 ) 基于优先规则的构造性方法和启发式方法；能快速构造解，但优化质量一般 较差 3 ) 模拟退火方法，禁忌搜索方法能够取得比较满意的优化质量，但其性能对算 法参数有比较强的依赖性，而且优化时间通常较长。 4 ) 神经网络和蚁群系统等方法优化时间性能比较差，而优化质量严重依赖于网 络参数，甚至可能产生非法调度。 5 ) l a g r a n g i a n 松弛法可以通过松弛和分解的策略降低问题的求解复杂性，但需 1 0 。聿渤辩季：投太学博：l 学位论义 模糊环境下的f l e x i b l ej o b s h 。p 趔度问幽f 壅 要适合选取或调整相应的算法参数，同时大多数情况下需要对所得到的解进行再 加工，才能够得到可行的比较满意的调度。 经过研究发现，在多数情况下，遗传算法比古典的启发式算法具有更好的性 能【5 2 1 ，同时遗传算法比传统的搜索技术具有更强的鲁棒性，因为它不仅能解决 某一特定问题，而且可以适应不同的问题形式。遗传算法的优越性归功于它与传 统搜索方法不同的特定结构：首先，g a 的作业问题是编码，对搜索问题的限制 极少，对函数的一些约束条件象连续性、可导性等不作要求，减少了要解决的问 题的复杂性。其次，g a 是同时搜索解空间内的许多点，因而可以有效地防止搜 索过程中收敛到局部最优解，并获得全局最优解，与其它单点搜索的方法相比， 在计算时间上也有较大的优势。同时，g a 使用遗传操作时是按概率在解空间进 行搜索，因而既不同于随机查找，也不同于枚举查找那样盲目的穷举，而是一种 有目标、有方向的启发式搜索。 1 4 本文的研究动机、研究结果、结构 1 4 1 研究动机和结果 由上节可知，学者们针对古典j s s 问题，进行了深入细致的研究，取得了丰 硕的成果，在针对f j s s 方面的研究则相对较少。在模糊环境下的作业车间调度 问题方面进行的研究，也多集中在简单模糊模型的构建上，而且局限在古典j s s 问题。本文将f j s s 问题从理想的确定环境扩展到更加接近实际生产系统的模糊 环境中，并采用了灵活性、适应性更强的模糊模型和更加精确便捷的模糊测量方 法来表征模糊参数，构建调度目标函数。 本文分别对具有模糊加工时间和模糊操作延迟的t o t a lf l e x i b l ej o b s h o p 调 度问题、具有模糊加工时间的p a r t i a lf l e x i b l ej o b s h o p 调度问题、具有模糊加工 时间和模糊交货期的f l e x i b l ej o b s h o p 最小化e t 惩罚调度问题进行了研究，在 模糊参数建模、模糊模型测量、调度算法改进方面取得了较为理想的研究成果。 1 4 2 论文结构 第二章研究了有模糊加工时间和模糊操作延迟时间的t o t a lf l e x i b l ej o b s h o p 弩瀚麟孽辍球太爹l g - 1 ：学位论文 模糊环境下的f l e x i b l 。j o b 。h 。p 调度问题的研究 调度中的最小化制造跨度问题。首先针对模糊加工时间问题，分别采取基于区间 值模糊数和基于可信性测度的方法进行研究，以满足不同的调度要求。然后对具 有模糊操作延迟的调度问题，以及同时具有模糊加工时间和模糊操作延迟的调度 问题进行了研究。 第三章研究了有模糊加工时间的p a r t i a lf l e x i b l ej o b s h o p 调度中的最小化制 造跨度问题。 第四章研究了具有模糊加工时间和模糊交货期的f l e x i b l ej o b s h o p 调度中的 最小化提前拖期惩罚问题。 1 2 哼圈斜爹投，# 大擎博i i j 学位论义 模糊环境下的f l e 。i b i ej 。b s h 。p 调度问题的删究 第二章模糊环境下的t o t a lf l e x i b l e j o b s h o p 最小化制造跨度调度问题 f l e x i b l ej o b s h o p 调度( f j s s ) 问题是柔性生产系统计划和操作中的典型问 题。根据操作可以选用的机器集合范围，f j s s 问题可以细分为t o t a lf l e x i b l e j o b s h o ps c h e d u l i n g ( t f j s s ) 问题和p a r t i a lf l e x i b l ej o b s h o ps c h e d u l i n g ( p f j s s ) 问题。在t f j s s 问题中，每个操作可以在生产系统中的任意一台机器上加工。现 有的针对f j s s