（运筹学与控制论专业论文）成组技术下的现代排序问题.pdf

大连理工大学硕士学位论文 摘要 排序问题是一类重要的组合优化问题。现代排序问题突破经典排序问题的种种假 设，有着越来越广阔的应用前景。为适应订货式、多品种、小批量生产的需要，引进了 成组技术的概念。在成组技术假设下，可以避免或大大减少安装时间和安装费用。因 此，研究成组技术下的现代排序问题算法很有必要。本文主要研究成组技术下的加工时 间可变的某些现代排序问题，通过推理和分析，对不同的问题分别给出了最优算法。 第二章研究工件加工时间是开工时间线性增加函数的单机成组排序问题。分两种情 况：增长率与基本加工时间无关以及增长率与基本加工时间相关。在第一种情况下，对 目标函数为极小化最大完工时间、完工时间和以及在权与基本加工时间成比例情况下的 加权完工时间和问题分别给出了最优算法。在第二种情况下，给出了目标函数为极小化 最大完工时间以及加权完工时间和问题的最优算法。 第三章研究工件加工时间是开工时间线性减少函数的单机成组排序问题。在递减率 与基本加工时间无关以及递减率与基本加工时间相关的两种情况下，对目标函数为极小 化最大完工时间与完工时间和问题分别给出了最优算法。 第四章研究具有学习效应的单机成组排序问题。在此类问题中，工件的加工时间与 工件所排的位置有关。对工件加工时间是线性型和指数型两种形式分别进行了讨论，在 两种情况下，分别给出了目标函数为极小化最大完工时间与完工时间和问题的最优算 法。 关键词：排序；单机；成组技术：最优算法 成组技术下的现代排序问题 m o d e r n s c h e d u f i n g p r o b l e m su n d e r g r o u pt e c h n o l o g ya s s u m p t i o n a b s t r a c t s c h e d u l i n gi sa ni m p o r t a n tc o m b i n a t o f i a lo p t i m i z a t i o np r o b l e m t h em o d e r ns c h e d u l i n g p r o b l e m st h a tb r e a kt h r o u g ht h ev a r i o u sa s s u m p t i o n so f t h ec l a s s i c a lo n e sh o l do u tm o r ea n d m o r eb r o a dp m s p e c t s i no r d e rt os a t i s f yt h ed e m a n do f o r d e rg o o d s ，v a r i o u sk i n d s ，s m a l ll o t - s i z i n gp r o d u c t i o n ，t h ec o n c e p t i o no fg r o u pt e c h n o l o g yi si n t r o d u c e d u n d e rt h ea s s u m p t i o no f g r o u pt e c h n o l o g y , b o t ht h es e t u pt i m e sa n ds e t u pc o s t sa r cg r e a t l yd e c r e a s e do re v e na v o i d e d t h e r e f o r e , i t i s n e c e s s a r y t o s t u d yt h ea l g o r i t h m so ft h em o d e mp r o b l e m sw i t hg r o u p t e c h n o l o g ya s s u m p t i o n u n d e rg r o u pt e c h n o l o g ya s s u m p t i o n , t h i sp a p e rc o n s i d e r ss o m em o d e m s c h e d u l i n gp r o b l e m s w i t h v a r y i n gp r o c e s s i n gt i m e s t h r o u g hi n f e m n c ea n da n a l y s i s ，t h e o p t i m a la l g o r i t h m s t od i f f e r e n t p r o b l e m s a r e p m s e n t e dr e s p e c t i v e l y i nc h a p t e r 2 ，u n d e rg r o u pt e c h n o l o g ya s s u m p t i o n ，s i n g l em a c h i n es c h e d u l i n gp r o b l e m si n w h i c h j o bp r o c e s s i n gt i m e sa r el i n e a r l yi n c r e a s i n gf u n c t i o n so f t h es t a r t i n gt i m e sa r es t u d i e d t h e r ea r et w os i t u a t i o n s ：t h eb a s i cp r o c , c s s i n gt i m e sa r ei n d e p e n d e n to f t h e i n c r e a s i n g r a t e sa n d t h eb a s i cp r o c e s s i n gl i m e sa r er e l a t e dt ot h ei n c r e a s i n gm t e s ht h ef i r s ts i t u a t i o n , t h eo p t i m a l a l g o r i t h m sa r ep r e s e n t e dr e s p e c t i v e l yf o rt h ep r o b l e m so fm i n i m i z i n gt h em a k e s p a n , s l i mo f c o m p l e t i o nt i m e sa n dw e i g h t e ds u m - o fc o m p l e t i o nt i m e su n d e r t h ec o n d i t i o nt h a tw e i g h t sa r e r e l a t e dt ot h eb a s i cp r o c e s s i n gt i m e s i nt h es e c o n ds i t u a t i o n t h eo p t i m a la l g o r i t h m sa 佗a l s o p r e s e n t e dr e s p e c t i v e l yf o rt h ep m b l e m so fm i n i m i z i n gt h em a k e s p a na n d t h ew e i g h t e ds u mo f c o m p l e t i o n t i m e s i nc h a p t e r 3 ，s i n 萌e m a c h i n e s c h e d u l i n gp m b l e m sw i t hj o bp m c e s s i n gt i m e sb e i n g d e c r e a s i n gf u n c t i o n so f t h es t a r t i n gt i m e sa r es t u d i e du n d e rt h eg r o u pt e c h n o l o g ya s s u m p t i o n f o rt w oc a s e st h a tt h eb a s i cp r o c e s s i n gt i m e sa r ei n d e p e n d e n to ft h ed e c r e a s i n gr o t e sa n dt h e b a s i cp r o c e s s i n gt i m e sa r er e l a t e dt ot h ed e c r e a s i n gr a t e s t h eo p t i m a la l g o r i t h m sa m p r e s e m e d r e s p e c t i v e l yf o rt h ep r o b l e m so f m i n i m i z i n g t h em a k e s p a na n dt h es u m o f c o m p l e t i o nt i m e s i nc h a p t e r4 ，s i n g l em a c h i n es c h e d u l i n gp r o b l e m sw i t ha l e a r n i n ge f f e c tu n d e rt h eg r o u p t e c h n o l o g ya s s u m p t i o na r cs t u d i e d i ns u c hk i n dp r o b l e m , j o bp r o c e s s i n gt i m e s a r ed e p e n d e n t o nt h e i r p o s i t i o m p r o b l e m s a r ed i s c u s s e df o rl i n e a r p r o c e s s i n g t i m e sa n de x p o n e n t i a l p r o c e s s i n gt i m e sr e s p e c t i v e l y a n dt h eo p t i m a la l g o r i t h m sa r cp r e s e n t e df o rt h ep r o b l e m so f m i n i m i z i n g t h em a k e s p a na n dt h es t l r no f c o m p l e t i o nt i m e sf o rb o t hs i t u a t i o n s r e s p e c t i v e l y k e yw o r d s ：s c h e d u l i n g ；s i n g l em a c h i n e ；g r o u pt e c h n o l o g y ；o p t i m a la l g o r i t h m 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表蓼撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：日期： 大连理工大学硕士学位论文 1 绪论 排序问题( s c h e d u l i i 玛p r o b l e m s ) 是一类重要的组合最优化问题，也是运筹学研究的一 个非常活跃的分支。排序问题产生的背景主要是机器制造，后来它广泛应用子管理科 学、计算机科学和工程技术等很多领域，从普通的生产部门的计划安排、人员调度，学 校课程表的制定，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论与算法。 1 1 排序问题 1 1 1 排序问题的定义 排序问题是一类重要的组合最优化问题，它是利用一些处理机、机器( m a c h i n e s ) 或 资源( r e s o u r c e s ) ，最优的完成一批给定的任务或作业。在执行这些任务或作业时需要满 足某些限制条件，如任务的到达时间、完工的限定时间、任务的加工顺序、资源对加工 时间的影响等。最优的完成指的是使目标函数达到最小，而目标函数通常是对加工时间 的长短、处理机的利用率的描述。在这里把任务称为工件( j o b s ) 。通常是用如下的方式 来描述排序问题： 给定以个工件的工件集 j = v i ，j 2 ，以j 埘台机器的机器集 m = m 1 ，肘2 ，肘。j 和s 种资源的资源集 r = 怛l ，r 2 ，r ，j 排序问题指的是在定条件下，为了完成各项任务，把m 中的机器和r 中的资源 分配给，中的任务，使目标函数达到最优。 排序问题基本上是由机器的数量、种类与环境，以及工件的性质和目标函数所组 成。 机器 只有一台处理机的排序问题称为单机( s i n g l er n a c h i n e ) 排序问题，否则称为多机排序 问题。 在多机排序问题中，如果所有的机器都具有相同的功能，则称它们为平行机 ( p a r a l l e lm a c h i n e s ) 。平行机按加工速度又分为三种类型。如果所有的机器都具有相同的 成组技术下的现代排序问题 速度，称之为同速机( i d e n t i c a lm a c h i n e s ) 。如果机器的速度不同，但每台机器的速度都是 常数，不依赖被加工的工件，则称为恒速机( 1 1 1 1 i f o r mm a c h i n e s ) 。如果机器的加工速度依 赖于被加工的工件，则称为鲻i l ( u n r e l a t e d m a c b _ i n e s ) 。 多机问题的另一种情况是多类型机( d e d i c a t e dm a c h i n e s ) 。多类型机指的是机器具有 不同的功能。在多类型机环境中，被加工的工件需要在不同的机器上加工。通常情况 下，每个工件有多道工序，每道工序需要在不同的机器上加工。 如果每个工件需要在各个机器上加工，且各个工件在各台机器上的加工顺序都相 同，则称为流水作业( 也称为同顺序作业或f l o w s h o p ) 。 如果每个工件需要在各个机器上加工，但各个工件有自己的加工顺序，则称为异顺 序作业( 也称j o bs h o p ) 。 如果每个工件需要在各个机器上加工，但各个工件的加工顺序任意，则称为开放作 业( 也称o p e ns h o p ) 。 工件 排序问题中的约束条件，主要指的是工件的性质以及它们在加工过程中的要求和限 制。下边的数据描述了工件的一些性质。 ( 1 ) 加工时间 工件的加工时间向量为p j = ( p p ：p ，p 。) ，其中p v 是工件在机器j 嵋上所需 要的加工时间( p r o c e s s i n gt i m e ) 。 ( 2 ) 到达时间 到达时间或准备时间( r e a d yt i r n e ) 0 是工件，已经准备好可以被加工的时间a 如果所 有的工件的准备时间相同，取，= 0 ，= l ，2 ，n 。 ( 3 ) 工期和截止期限 工期( c l u ed a t e ) d j 表示对工件，；限定的完工时间。如果不按期完工，应受到一定的 惩罚。绝对不准许延误的工期称为截止期限( d e a d l i n e ) 。 ( 4 ) 权 权( w e i g h t ) w j 表示工件，相对于其它工件的重要程度。 目标函数 对于给定的一个排序石，我们用c ，( 厅) 表示任务的完工时间，要极小化的目标函数 总是完工时间的函数。在排序问题中，目标函数主要有下面几种。 ( 1 ) 最大完工时间 2 大连理工大学硕士学位论文 率。 最大完工时间( m a k e s p a n ) ( 也称为时间表长) 定义为 c 。= m a x c j ) 。 它等于最后一个被加工完工件的完工时间，小的时间表长意味着机器有较高的利用 q ) 加权完工时间和 加权完工时间和( w e i g h t e d s u m o f c o m p l e t i o nt i m e s ) 定义为 一q = m q a 硝 当权相同时，加权完工时间和变为完工时间和( s 啪o f c o m p l e t i o n 血坨s ) c j = c j - p l ( 3 ) 最大延误 最大延误( m a x i m u mt a r d i n e s s ) 定义为 上。= m a x ( l j ， 其中0 = q d j 是工件的延误时间。 1 1 2 排序问题的表示方法 机器、工件和目标函数三要素组成了排序问题。机器的数量、类型和环境有近十种 情况，工件和资源的约束条件更是错综复杂，再加上度量不同指标的目标函数，形成了 种类繁多的排序类型。目前通常使用三参数表示法来表示排序问题。 三参数表示法由三个域组成：口i i ，。它们分别具有下面的含义。 口域表示机器的数量、类型和环境。 1 ：单机 3 成组技术下的现代排序问题 p m ：历台同速平行机。 q m ：m 台恒速平行机。 r m ：m 台变速平行机。 f m ：所台机器，流水作业。 j m ：m 台机器，异序作业。 o m ：m 台机器，自由作业。 口域表示工件的性质、加工要求和限制，资源的种类、数量和对加工的影响等约束 条件。它可以同时包括多项，可能的项主要有： 7 ，：工件有不同的准备时间。如果域中不出现7 ，说明r j = o ，( ，= 1 , 2 ，”) 。 p n 即：工件加工时允许中断。如果域中不出现p r m p ，表示工件加工时不允许 中断。 p r e c ，c h a i n s ，t r e e ：表示工件的相关性，分别表示一般优先约束，平行链优先约束 和树型优先约束。如果夕域中不出现这些约束，表示工件是无关的。 p r m u ：这个约束只可能出现在流水作业环境中，表示工件按通过第一台机器的顺 序始终不变的通过所有的机器。 y 域表示要优化的目标函数。 这些函数可以是： c 。：最大完工时间。 q ，w j c j ：完工时间和，加权完工时间和a 。：最大延误t 1 1 3 排序问题的求解 排序问题是一类组合最优化问题。由于排序问题中的机器、工件都是有限的，绝大 部分排序问题都是从有限个可行解中找出一个最优解，使目标函数达到最小。在排序问 题中把可行解称为可行排序( f e a s i b l es c h e d u l e ) ，最优解称为最优排序( o 叩m a is c h e d u l e ) 。 一个可行排序是一个顺序( s e q t m a e e ) 或排列( p e r m u t a t i o n ) ，按照这个顺序，在给定的机器 上加工所有的工件，满足问题所要求的各种条件和限制。 最优排序是可行排序中使给定可行排序中目标函数达到最小的排序。 由于绝大多数排序问题是n p 难问题，其最优解往往很“难”找到，而且在实际应 用中只需要找到满足一定要求的启发式解和近似解。因此排序问题的研究主要有两个方 4 大连理工大学硕士学位论文 向。一个是对可解的p 问题，寻求多项式时间最优算法( 又称为有效算法，简称多项式 算法或最优算法) 来得到问题的最优解。或者对n p 难问题在特殊情况下寻求有效算 法，也就是研究n p 难问题的可解情况。二是设计性能优良的启发式算法和近似算法， 当然无论是启发式算法还是近似算法都应该是多项式算法。实际上n p - 难问题可解情况 的多项式算法往往可以作为m ，- 难问题本身的启发式算法和近似算法。 1 2 现代排序问题 如果按数学分为理论数学和应用数学，那么排序论可以分为排序的理论部分和排序 的应用部分。排序的理论部分又可分为经典排序和现代排序。现代排序问题是相对经典 排序而言，是非经典的，其特征是突破经典排序的基本假设经典排序有四个基本假 设。 ( 1 ) 资源的类型。机器是加工工件所需要的一种资源。经典排序假设，一台机器在 任何时刻最多只能加工一个工件；同时还假设，一个工件在任何时刻至多在一台机器上 加工。作为这个假设的突破，有成组分批排序、同时加工排序、不同时开工排序和资源 受限排序等。 ( 2 ) 确定性。经典排序假设排序问题的一个实例的所有( 输入) 参数都是事先知道 的和完全确定的。作为这个假设的突破，有可控排序、随机排序、模糊排序和在线排序 等。 ( 3 ) 可运算性。经典排序是在可以运算、可以计算的程度上研究排序问越，而不去 顾及诸如如何确定工件的交货期，如何购置机器和配备设备等技术上可自b 发生的问题。 如果考虑实际应用中有关的情况和因素，就是应用排序问题。如人员排序和智能排序 等。 ( 4 ) 单目标和正则性。经典排序假设排序的目的是使衡量排法好坏的一个一维目标 函数的函数值为最小，而且这个目标函数是工件完工时间的非降函数。这就是所谓正则 暑标。作为这个假设的突破，有多目标排序、准时排序和窗时排序等。 相对于经典排序问题，现代排序问题是指突破经典排序问题某一假设的问题。唐国 春等最近出版的专著删介绍了发展较为完备的十种现代排序闯题。随着实际问题的研 究，现代排序问题层出不穷。由于现代排序问题往往具有更广泛的实际背景，因此研究 现代排序阃题更有意义。 5 成组技术下的现代排序问题 1 3 排序问题的研究概况 排序领域内许多早期的工作是在制造业推动下发展起来的。普遍认为1 9 5 4 年 j o h n s o n 的论文 3 4 】是排序问题的第一篇。从这篇文章问世以来的半个多世纪中，全世界 已经发表排序问题的文献2 千余篇，其中包括专著和教材4 0 余种。早期的工作，主要 围绕着整数规划、动态规划和分枝定界等数学方法研究一系列有代表性的问题。随着复 杂性理论和n p - 完全问题的兴起，人们开始注重排序问题的复杂性研究，证明了许多排 序问题是n p 难问题。对于这种问题，通常认为不存在多项式算法。由于实际问题的需 要，对不同的问题建立了大量的有效的启发式算法。近年来，随着计算机科学的发展， 许多现代优化计算方法，如遗传算法、模拟退火算法、禁忌搜索算法和人工神经网络算 法等，被用来求解排序问题。 在排序问题的研究过程中，一方面是求解方法的多样性发展，另一方面是现代问题 模型的不断产生。由于许多实际问题的出现，经典排序问题的基本假设不断被突破，产 生了大量的现代排序问题。在2 0 世纪8 0 年代以前，对于排序问题的研究主要集中在一 些经典模型上。近十多年来，出现了许多新模型。这两者的差异主要表现在加工方式和 目标函数上，从而也表现在用来解决问题的方法上。 在各类现代排序问题中，工件加工时间为变量的问题是一类重要的问题，这一问题 突破了经典排序问题的确定性假设。在这一问题中，通常分为三类情况：一类问题是工 件的加工时间与工件的开工时间有关的排序问题：另一类问题是工件的加工时间与所用 资源有关的可控排序问题；第三类问题是工件的加工时间与工件所排位置有关的排序问 题。关于工件加工时间与开工时间有关的排序问题方面的综述可参见文献【2 】【2 3 】；关于 可控排序方面的专著可参见【6 0 】；文献【8 】【2 5 】【3 7 】 4 2 】- 4 3 】【4 5 】都是关于第三类排序问题方 面的研究。 1 4 成组技术 成组技术( g r o u pt e c h n o l o g y ) 是利用任务的某种性质将任务分成若干组再进行加工， 以提高生产效率的一种原理和方法。根据成组技术理论，工件可以分成“类似”工件的 工件组。同组的工件连续加工时，不需要或者需要较少的安装时间：不同组的工件接连 加工时，则需要一定的或者需要较多的安装时间。随着柔性制造系统的发展，数控机床 的高度柔性可以适用于加工越来越多的不同种类的工件，从而可以避免和大大减少工件 的安装时间和安装费用，适用订货式、多品种、小批量生产的需要。研究工件的分类， 6 大连理工大学硕士学位论文 研究数控机床在某种状态下可以加工的工件类别，研究数控机床在不同状态下所需要的 安装时间和安装费用，这是成组技术加工排序的任务。 近年来，国内外不仅重视成组技术的研究，更重视分组后组内工件的排序和组与组 之间的排序。这种考虑成组技术，考虑安装时间和安装费用的排序问题就是成组排序问 题。研究这类排序问题对提高成组技术的效率，提高柔性制造系统的生产能力具有重大 的意义。 n 个工件的单机成组加工问题描述为： 工件分为m 组，第f 组记为g 。，g i 中的工件为山，以：，厶，i = 1 , 2 ，m ， 啊+ 挖：+ + 玎。= 疗。当这九个工件在机器上加工时，只有加工完一组工件后，才能加 工另一组工件，并且从加工一组工件转向加工另一组工件需要独立的调整时间，即当机 器转向加工某组工件时，其所需调整时间仅与该组工件有关，而与前面的是何组工件无 关。 成组加工问题不仅包括确定各工件组之间的顺序，而且需要确定同组中每个工件之 间的加t 顺序，使目标函数达到最优。 用三参数表示法，成组加工问题可记为 l l r ，s ，g t f ( c ) 其中r 是工件的准备时间向量，s 为机器的调整时间向量。第f 组g 的调整时间记 为置，g t 指同组工件顺序加工，f ( c ) 为某个给定的目标函数。 1 5 本文的研究内容 本论文讨论了成组技术下的现代排序问题，对某些工件加工时间可变的单机成组排 序问题分别给出了多项式算法。本论文共分四章。第二章研究了工件加工时间是开工时 间线性增加函数的单机成组排序问题。先研究增长率与基本加工时间无关的成组问题 l ip 。+ b i t ，s ，g ti ，( c ) ，对目标函数为极小化最大完工时间、完工时间和以及权与基本 加工时问成比例情况下的刍e 权完工时间和闷题分另日给出了多项式算法。又对增长率与基 本加工时间相关的成组问题1 i p 。，( 口+ b t ) ，s ，g t i ，( c ) 进行研究，对目标函数为极小化 最大完工时间与加权完工时间和问题分别给出了多项式最优算法。第三章研究了工件加 工时间是开工时间线性减少函数的单机成组排序问题，使用类似于第二章的研究方法分 - 7 成组技术下的现代排序问题 别对问题1 i p f b i t ，s ，g r l 厂( c ) 与问题1 l p f ( a - b t ) ，s ，g r l ，( c ) 进行了研究，对目标 函数为极小化最大完工时间、( 加权) 完工时间和问题分别给出了多项式最优算法。第 四章主要研究具有学习效应的单机成组排序问题。对加工时间为线性型和指数型两种形 式下的问题l i p , j ( a 一打) ，s ，o t i ，( c ) 与问题l l 功矿，s ，g r l ，( c ) 分别进行了讨论，对 目标函数为极小化最大完工时间与完工时间和问题分别给出了多项式最优算法。 8 大连理工大学硕士学位论文 27 - 件加工时间是开工时间线性增加函数的单机成组排序问题 2 1 引言 在经典排序问题中，工件的加工时间通常是一个常数，与工件的开工时间无关。但 在某些具有较强实际背景的排序问题中，工件的加工时间可能与开工时间有着某种联 系。这类问题在钢铁工业，塑料工业，军事以及医疗等方面有着广泛的应用。如在军事 方面当天气渐渐变坏或者天色渐渐变黑时，探测目标开始的时间越晚则所花费的时间 就越长 4 1 】；在消防工程中，救火的开始时间一旦被耽搁，火势就会越难控制，这样救 火的时间将会变长，所付出的代价也会变大【3 6 】。所有的这些问题都是完成一项工作所 需要的时间将会随着开始加工时间的增加而变长，这类问题通常称为加工时间依赖开工 时间的排序问题。在这类问题中，工件的实际加工时间通过基本加工时间，增长率和开 工时间函数来描述。由于具有广泛的应用背景，此类问题近年来越来越受到研究者的关 注。 加工时间依赖开工时间的排序问题首先由g 叩诅和o u p t a 2 7 提出，文献【2 7 】中研究 了非线性加工时间极小化最大完工时间的单机排序问题，给出了启发式算法并对算法进 行了数值仿真，对线性加工时间极小化最大完工时间的单机排序问题，给出了多项式算 法。b r o w n e 和y e c h i a l i 在文献【1 1 】中对涉及到随机变量的单机排序问题进行了研究，对 目标函数为极小化最大完工时间期望和极小化最大完工时间方差两类问题，给出了多项 式算法。m o s h e i o v 3 9 讨论了工件j - r 时间为开工时间的简单线性函数的情况，对一些 经典目标函数分别给出了多项式时间算法。m o s h e i o v 4 0 研究了基本加工时间相同增长 率不同的线性加工时间单机排序问题，证明了极小化完工时间和问题的最优排序具有v 型性质。m o s h e i o v 在文献 4 1 】中研究了极小化加权完工时间和问题，对于权和基本加工 时间成比例的情况，证明了最优排序具有a 型性。w a n g 等【4 9 】研究了加工时间是开工 时间的分段函数，对目标为极小化最大完工时间问题，给出了一些结论。关于这方面的 综述可以参考文献 2 】【2 3 】。 在成组排序问题中，工件可以分成“类似”工件的工件组。同组的工件连续加工时 不需要安装时间，不同组的工件连续加工时，需要一定的安装时间。对于经典排序问 题，p o t t s 和v a nw a s s e n h o v e 4 7 讨论了满足成组技术的单机成组问题，对极小化加权完 工时间和问题与极小化最大延误问题分别给出了最优算法。张峰d 6 2 对工件的加工时间 是其开工时间简单线性函数的成组问题作了讨论，对满足成组技术限制极小化关于完工 时间函数的问题给出了多项式算法。 9 成组技术下的现代排序问题 本章着重讨论工件的加工时间是其开工时间线性增加函数的单机成组排序问题。本 章第二节给出了此类问题的描述。第三节讨论了增长率与基本加工时间无关的线性加工 时间排序问题，对目标函数为极小化最大完工时间、完工时间和以及当权与基本加工时 间成比例情况下的加权完工时间和的单机成组排序问题，分别给出了多项式最优算法。 第四节则讨论了增长率与基本加工时间相关的单机成组排序问题，对目标函数为极小化 最大完工时间以及( 加权) 完工时间和问题分别给出了多项式最优算法。这些结论都是 文献中已有结果的推广。 2 2 问题的描述 设有”个工件，以，以，若工件，的开工时间为t ，其实际加工时间为 p ，+ 6 ，r ，= 1 , 2 ，玎，其中p j 称为，的基本加工时间，b i 为大于零的常数，称为工 件j ，的增长率。同时假设所有工件的到达时间为t 。0 。在成组技术假设下，z 个工件 分别属于研g f t g ，g 2 ，g 。，第i 组g 包含吩个工件： ， 2 ，厶。这时工件山的 基本加工时间记为p 。，增长率记为b 。同组工件必须接连放在一起加工。加工第i 组工 件时需要安装时间蜀。由于加工时间为一般线性函数p ，+ b j r 情况下的大部分问题为开 放问题或n p 难问题，因此本章只考虑下面的两种特殊情况： ( 1 ) 各组增长率相同，即b f l - - b ，2 = = b ，= 岛； ( 2 ) 增长率与基本加工时间相关，即b o = 印。 在第一种情况下，工件j o 的 j n - r 时间变为p + b ；在第二种情况下，工件山的 加工时间变为p 。( 1 + b t ) 。对第二种情况将考虑工件加工时间是更一般的增加函数 ( i n c r e a s i n gf u n c t i o n ) p d ( f ) = p g ( a + b t ) 的情况。这样增长率与基本加工时间无关以及增 长率与基本加工时间相关的线性加工时间的单机成组排序问题分别记为 1j p f + 6 。r ，s ，g t l f ( c ) ， 1 i p g + b t ) ，s ，g t l ，( c ) 。 对于上述两问题，既要考虑各个组内工件之间的加工顺序，又要考虑工件组之间的 加工顺序。对于同一组的工件，需要确定工件的加工顺序使该组工件的最大完工时间、 - 1 0 - 大连理工大学硕士学位论文 ( 加权) 完工时间和最小，此时这一问题又相当于无成组技术限制的线性加工时间单机 排序问题，下面对各种情况分别进行讨论。 2 3 增长率与基本加工时间无关的问题1jp 。+ 6 f ，s ，g tj 厂( c ) 2 3 1 问题1 i p “+ 岛f ，s ，g t f c ，。 首先给出下面的定理。 定理2 1 对于问题1 lp + b t f ，s ，g t lc 一，第i 组工件以1 ，j i 2 ，按聊不减的 顺序排列得到最优排序( 1 i m ，l _ ，z 。) 。 证明设第f 组工件的最优排序为万。在万中，若工件的加工顺序不满足按基本加工 时间岛不减的顺序排列，则至少有两个相邻工件，f 和以“+ 1 ) ，有关系式岛 p + 1 ) a 交 换工件j v 和一( 川的位置，得到另一排序，记为矛，则 c 。( ，r ) 一c 。( 石) = p f ( 1 + 6 ，) 嘶一+ p ，( + 1 ) ( 1 + 6 f ) 嘶7 一- - p i ( j + i ) ( 1 + 岛) 吗一7 + p 口( 1 + 6 ，) 】 = 饥( 1 + 岛) “一。“( p 口一p f ( ，“) ) 因此，若p f p 划+ ”，则有c 一( 石) 一c 。( 石) o 成立，这与石是最优排序矛盾。 定理得证。 下面考虑工件组之间的加工顺序。一旦每个工件组内的工件加工顺序确定后，该组 工件可以看成是一个复合工件，每个复合工件具有与加工顺序无关的安装时间。 先考虑两组的情况。 设有两工件组g l ：以，i t ：，氐，g 2 ：厶，以：，正。，。由定理2 1 ，在最优排序中， 第一组工件应按a ，不减排列，第二组工件应按见，不减排列。为讨论方便，设两组工件 按上述要求排列后的顺序为g i ：，：， ，g 2 ：以。，以：， 。对于两组的情况，有 下面的结论。 定理2 2 对于问题1 f 既+ 6 f ，s ，g t i c , 。, ，若尸( g i ) p ( g 0 ，则组g l 排在组g 2 前 可使最大完工时间最小， 其中 成组技术下的现代排序问题 p ( g 。) = n 。 s ，( 1 + 6 i ) “一p 口( 1 + 玩) “一。 p ( g ，) 称为第f 组的优先因子。 ( 1 + 6 f ) “一1 ，f = l 2 ， 证明若工件的加工顺序为g l ，g 2 ，则各个工件的完工时间分别为 对g 1 组： c i l = t o + s l + p i l + b i ( f o + s 1 ) = p l l + ( t o + q ) ( 1 + b 1 ) ， c 1 2 = p i l + ( t o + s 1 ) ( 1 + b 1 ) + p 1 2 + b t ( p 1 1 + ( t o + j i ) ( 1 + b 1 ) = p 1 2 + p l l ( 1 + 岛) + o o + j 1 ) ( 1 + 岛) 2 ， h c j = ( f 0 + ) ( 1 + 6 1 ) 一。+ p 1 ，( 1 + 耵h ， j - 1 对g 组： c 2 i = p 2 i + ( c i 。+ 5 2 ) ( 1 + b 2 ) ， c 2 2 = p 2 2 + p 2 l ( 1 + 6 2 ) + ( c t 。+ j 2 ) ( 1 + 6 2 ) 2 ， c 2 h = ( c i + s 2 ) ( 1 + 6 2 ) + 芝p 2 月+ 6 2 ) 叫， j l 此时最大完工时间为 h c 一( g l ，g 2 ) = ( t o + q ) ( 1 + 6 1 ) ( 1 + 6 2 ) h + ( 1 + 6 2 ) p 1 j ( 1 + 6 1 ) 叫 l + j ： l + 6 ：) ”：+ 兰p ：( 1 + 6 2 ) 州 严l 若工件的加工顺序为g 2 ，g 1 ，则各个工件的完工时间分别为 对g 2 组： c 2 j = o + j 2 + p 2 1 + b 2 ( t o + j 2 ) = p 2 l + ( + s 2 ) ( 1 + b 2 ) ， c 2 2 = p 2 i + ( t o + 5 2 ) ( 1 + 6 2 ) + p 2 2 + b 2 ( p 2 1 + ( f o + s 2 ) 0 + 6 2 ) ) = p 2 2 + p 2 i ( 1 + 6 2 ) + 0 0 + j 2 ) ( 1 + 6 j ) 2 ， 1 2 ( 2 1 ) 大连理工大学硕士学位论文 c 2 。，= ( t o + s 2 ) ( 1 + 6 2 ) + 芝p 2 月+ 6 2 ) 。， - 1 对g i 组： c l l = p l 】+ ( c 2 。，+ 置) ( 1 + b 1 ) ， c 1 2 = p 1 2 + p l l ( 1 + 6 i ) + ( c 2 。，+ 黾) ( 1 + 6 1 ) 2 ， c = ( c 2 + 毛) ( 1 + 6 i ) 1 + p l ，( 1 + 6 1 ) 一7 ， j - l 此时最大完工时间为 c 。( g 2 ，g 1 ) = ( f o + s 2 ) ( 1 + 6 1 ) “( 1 + 6 2 ) 1 + ( 1 + 6 1 ) 1 芝p 2 ，( 1 + 6 2 ) ”z 1 一l + s l ( 1 + 耵1 + a 月+ 6 1 ) 州 1 式( 2 1 ) 与式( 2 2 ) 相减，得 c 。( g l ，g 2 ) 一c 。( g 2 ，g 】) h = ( ( 1 + 6 2 ) “一1 ) p l ( 1 + 6 i ) 1 + 2 p l i ( 1 + 抚) 1 】 一l 一“1 + 6 1 ) “- 1 ) s 2 ( 1 + 6 2 ) + 芝p 2 j ( 1 + 6 2 ) “t 一7 】， j - t 若 毛( 1 + 6 1 ) 1 - x 1 + 6 1 ) ” 。! ：! 一 p w + 1 ) ，则有q ( 石) 一q ( 矛) 0 成立，这与石是最优排序矛 盾。定理得证。 类似于上面的讨论，下面考虑工件组之间的加工顺序，先考虑两组的情况。 由定理2 3 ，在最优排序中，第一组工件应按a 不减排列，第二组工件按乜不 减排列。同样假设两组工件按上述要求排列后的顺序为 g l ：以。，：， ，g 2 ：j 2 一，以：，也。对于两组的情况，有下面的结论。 定理2 4 对于问题1 l 既+ 6 f r ，最g 丁i 。q ，若p ( g 1 ) p ( g 2 ) ，则组g 1 排在组g 2 之前加工可使完工时间和最小， 其中 ( t o + 丑) ( 1 + 6 j ) 1 + 功( 1 + 包) 州- t o p ( g f ) = 1 _ 上l 一，i = 1 , 2 艺( 1 + 岛) 证明若工件的加工顺序为g 1 ，g 2 ，则各个工件的完工时间分别为 对g 1 组： c l 。= f o + + p 1 】+ 6 l ( f 。+ 置) = p l l + ( r o + ) ( 1 + 6 1 ) ， c 1 2 = p 1 1 + ( f o + ) ( 1 + b 1 ) + p 1 2 + b l ( p l l + ( t o + q ) ( 1 + b 1 ) ) = p 1 2 + p l i ( 1 + 6 i ) + ( f o + ) ( 1 + 6 1 ) 2 ， c h = ( f 。+ 量) ( 1 + 6 1 ) “+ 艺p k ( 1 + 6 1 ) 1 ， k - ! 对g 组： c 2 1 = p 2 i 4 - ( c 1 月+ 5 2 ) ( 1 + b 2 ) ， c 2 2 = p 2 2 + p 2 l ( 1 + 6 2 ) + ( c j + s 2 ) ( 1 + 6 2 ) 2 ， - 1 5 成组技术下的现代排序问题 c 2 凡= ( c l + s 2 ) ( 1 + 6 2 ) n + p 2 ( 1 + 6 2 ) _ ， k - i 此时完工时间和为 主宝q ( g l ，6 2 ) ：( t o - b s i ) 艺( 1 + 岛) ，+ 兰圭p u ( 1 + 6 1 ) h + i f f i l