緩冲区有限的两阶段置换流水车间调度问题性质分析.docVIP

缓冲区有限的两阶段置换流水车间调度问题性质分析 ［摘 要］ 本文针对缓冲区有限的两阶段置换流水车间调度问题的基本性质进行了分析，指出了缓冲区的大小对于问题最优解的影响并证明了该问题的复杂性。通过对原问题及其特例在目标函数之间关系方面的研究，为算法获得较好的初始解提供了依据。这些性质为设计求解算法提供了理论依据。 ［关键词］ 置换流水车间； 缓冲区有限； 复杂性分析 ０ 引 言 传统的流水车间调度模型通常假定各机器间的缓冲区无穷大，然而在许多实际生产过程中，由于受到缓冲区空间或存储设备的限制（如中间库存等），缓冲区的大小是有限的。缓冲区有限的流水车间调度问题（ｌｂｆｓｓ）广泛存在于钢铁、化工、制药等带有中间存储环节的生产系统中［1-2］。对于ｌｂｆｓｓ问题存在两种特殊情况：当缓冲区大小为零时，该问题转化为阻塞流水车间调度问题（ｂｌｏｃｋｉｎｇ ｆｓｓ，ｂｆｓｓ）；当缓冲区大小为无穷时，该问题转化为一般流水车间调度问题（ｆｓｓ）。 对于ｆｓｓ问题，当阶段数为２时，ｊｏｈｎｓｏｎ（１９５４）［3］提出了多项式优化算法，当阶段数为３及以上时，该问题是ｎｐ难问题［4］。作为另一特例的ｂｆｓｓ问题，已被证明当阶段数为３时是ｎｐ难问题［5-6］，并且算法多为启发式算法。目前对缓冲区有限的流水车间调度问题的研究较少。文献［7］对缓冲区有限的两阶段流水车间调度问题的复杂性进行了分析，并给出了该问题与两阶段无等待流水车间调度ｍａｋｅｓｐａｎ之间的关系：c0* / cb* = （2b + 1） / （b + 1），文献［8］针对多阶段的混合流水车间调度问题得到了相似的结论。文献［9］提出了一种多有哪些信誉好的足球投注网站模式遗传算法，算法使用多个交叉和变异操作进行解空间的探索和改良，并采用基于有向图的邻域结构来增强局部有哪些信誉好的足球投注网站。文献［10］针对随机有限缓冲区流水线调度问题提出了混合差分进化算法，其中差分进化用于执行全局有哪些信誉好的足球投注网站和局部有哪些信誉好的足球投注网站，最优计算量分配用于对有限计算量进行合理分配，从而保证优质解得到较多仿真计算量，并提高了在噪声环境下获得优质解的置信度。 从已有研究来看，对具有缓冲区限制的流水车间调度问题的基本性质的研究还不够充分，其算法设计的理论基础尚待完善。为此，本文针对该问题的基本情况——两阶段置换流水车间调度问题，在理论上探讨了缓冲区的大小对问题最优解的影响；是否存在基于排列排序的最优解；该问题及其两种特殊情况在目标函数之间的关系等基础问题，旨在为进一步研究此类问题提供理论依据。 １ 问题模型 1.１ 问题描述 缓冲区有限的两阶段置换流水线调度问题可描述为：n个工件｛j1，j2，…，jn｝依次经过２个阶段的加工，其中每个阶段只有１台机器。两阶段间存在缓冲区，缓冲区内工件的个数不能超过上限，本文假定缓冲区上限为b。在每台机器上，工件的加工顺序均相同，即工件在缓冲区中均服从先进先出规则（ｆｉｆｏ），本文研究的调度问题以最小化最大完成时间（ｍａｋｅｓｐａｎ）为目标函数。应用ｇｒａｈａｍ［11］提出的三元组表示法，此问题可表示为：f2 | bi ≤ b|cmax。 1.２ 数学模型 为便于描述，定义符号和变量如下： i ——工件序号，ji表示第i个工件； i ——所有工件序号的集合，i∈i = ｛1，2，…｝； j ——阶段序号，mj表示第j阶段的机器，j = 1 ，2； pij ——工件ji在机器mj上的加工时间； sij ——工件ji在机器mj上的开工时间； cij ——工件ji在机器mj上的完工时间； bi ——工件ji在两阶段间的缓冲区的大小； b ——缓冲区上限； π = ｛π（1），π（2），…，π（n）｝ —— 可行加工顺序。 缓冲区有限的两阶段置换流水线调度问题的数学模型如下： 其中，式（１）表示目标函数：最小化最大完成时间；式（３）表示工件在加工时不允许中断； 式（４）、式（５）表示不同情况下工件的开工时间；式（６）表示变量的取值约束。 ２ 问题复杂性 在流水车间调度问题中，当每台机器上加工工件顺序相同时，称为排列排序。在一般流水车间调度问题中，我们已经知道当阶段数为２时，可以通过基于排列排序的ｊｏｈｎｓｏｎ规则在多项式时间得到最优解。但是当两阶段间缓冲区的大小变为有限时，问题的性质将发生根本性改变。 定理１ 对于f2 | bi ≤ b | cmax问题，当b = 1时，在任一可行调度中，两台机器上工件的加工顺序必然相同。 证明（反证法）：不失一般性，设在任一可行调度中m1上工件i在工件j之前加工，在m2上工件j在工件i之前加工，由于工件j必须要在m1上完成加工之后才能进入m2加工，并且工件i在工件j之前加工，因此工件i和工件j均需进入缓冲区，与b = 1的条件相矛盾。因此，两台机器上工件的加工顺序必然相同。 根据定理１