管加工中两机器协调调度问题.ppt

管加工中两机器协调 调度问题 东北大学 关静 导师 唐立新 基金项目 国家杰出青年科学基金(70425003)； 国家自然科学基金项目 (70171030, 60274049)； 高等学校优秀青年教师教学科研奖励计划 (教育司2002383) . 摘 要 本文研究大型钢铁加工企业管加工厂生产作业中 存在的一种工件分解类型的生产调度问题，其特 点为一个工件（母件）经过切管机后被切成多个 子件，母件和子件分别在两个工序对应的设备上 （每个工序假设只有一个设备）进行加工，文中 考虑的机器环境是二机流水车间，目标函数是所 有工件最大完成时间最小。 摘 要 传统生产调度都是工件装配类型或者工件类型不 变，本文研究的调度问题与传统问题不同，属于 分解类型的调度，不仅需要确定母件在切管机上 的排序，同时要考虑母件在切管机上切出各个子 管的先后顺序。 摘 要 根据母件分解成子件的数目不同，把问题分成为 两类： 一类是所有母件分解成子件的数目相同； 一类是母件分解成子件的数目任意。 对于这两类问题又分别就下面的几种情况进行分 析： 子件同时产生； 子件不同时产生、母件的加工不可中断； 母件加工可中断、母件间的切换有一个常数 时间。 引言 本文研究的问题描述如下：考虑工件分解型的调 度问题，机器环境是二机流水车间，一个工件(母 件)在经过第一台机器时裂变出多个工件(子件)， 考虑的目标函数是所有工件的最大完成时间最小 。调度需要确定每个工件(母件)在切管机上的加 工顺序，以及母件的每个子件产生的顺序。 引言 本文研究的问题是以钢铁加工企业钢管厂为背景 ，研究套管加工流程中切管机和下游机器的协调 调度，如图1所示。从上游工序产生出的毛管很长 ，要经过切管机把毛管切成适当长度的子管，然 后继续在下游的机器上进行倒棱、接箍拧紧、通 径、涂漆等工序，最后形成成品套管。 引言 图：管加工厂流程 切管机 热处理 中间库 成品库 套管加工 引言 钢铁企业使用的都是大型设备，提高设备的利用 率是关键的指标，因此本文研究的调度问题以求 工件最大完成时间最小化作为目标函数。 引言 文中研究的工件是分解类型的，工件数目经过切 管机后发生变化，并且母件每产生出一个子件都 可以开始在下游的机器上加工，而不用等其所有 子件全部产生在开始在第二台机器上加工，因此 问题与传统的二机流水问题不同，不能直接由 Johnson规则得到最优解。 引言 在以往的文献中，有许多研究的是流水车间环境 下求最大完成时间最小问题，调度的类型都是工 件类型不变，在此对其进行简单的综述。Sung 和 Kim2研究的二机流水车间求最大完成时间问题 ，允许工件有动态的到达时间；Lin 和 Cheng3 研究的二机流水车间求最大完成时间是批调度问 题；Allahverdi4论文考虑的流水车间问题，目标 函数是最大完成时间与平均流水时间的加权求和 。 引言 还有一些文献研究流水车间装配类型的调度问题 ：Koulamas 和 Kyparisis5研究三机流水装配车间 问题,目标函数是最大完成时间,还有Yang6， Yakoyama和 masao7研究的也是装配工件的调度 问题。Lee8考虑具有装配类型特征的分解工件 调度问题，目标函数是多个费用和最小，给出问 题的启发式算法，并分析界。 协调问题 首先给出这一部分考虑的协调问题都要用到的一 条性质。 性质1：对于文中提出的问题，如果可以得到最小 值，总是可以通过使所有工件在两机器上的加工 顺序相同得到。 由性质1，文中研究的问题总是认为所有子件在二 台机器上加工顺序相同。 协调问题 引理：如果问题有最优解，总是可以通过使第一 个机器上没有闲置时间而得到。 证明：如果问题的最优解中，工件在机器一上的 加工有闲置，移动工件，使机器一上的加工没有 闲置，问题的目标函数值不会增大。 由引理，我们在下面的定理证明中认为工件在第 一个机器上没有闲置时间。即工件在第一台机器 上的加工是连续的。 母件分解子件个数相同 这一部分中，研究母件个数为 ，每个母件经过 切管机裂变出的子工件个数均为 。 首先考虑母件经过切管机同时裂变出所有的子工 件，这个问题总可以看作是一般意义上的二机流 水求最小完成时间问题，母件在第两台机器上的 处理时间为其所有子件的处理时间之和。按照求 解问题的Johnson规则求出问题的最优解。 母件分解子件个数相同 接下来考虑母件裂变子工件有确定处理时间，母 件在第一台机器上的加工不可中断问题。就一些 特殊的情况给出求解问题的最优算法。 性质2：当 ，对所有的 ， 都成立，要得最大完成时间最小，这 时只要把满足 的母件 安排在所有 母件的最后位置加工，同时其中的第 个子件安 排在其所有子件的最后位置加工即可。其他母件 、子件的顺序任意。 证明略。 母件分解子件个数相同 性质3：当 ,对所有的 ， 都成立。这时要得最大完成时间到最小 ，只要把满足 的母件 安排在所 有母件的第一个位置加工，同时其第 个子件安 排在其所有子件的第一个位置加工即可。其他母 件、子件的顺序任意。 证明略。 母件分解子件个数相同 下面考虑在切管机在还没有切出一个母件的所有 子件时，可以改切另一个母件，求最大完成时间 最小问题。这里切管机上母件的切换有一个常数 的切换时间。下面给出一个多项式时间动态规划 算法。 母件分解子件个数相同 设函数 为第二台机器加工了 个子工件的完 成时间，其中 表示第二台机器加工的最后一个 子工件是由第 个母件产生的。 ， 为切管机上切换一个母件的时间， 为已经产生 出至少一个子工件的母件集合， 为没有加工过 的母件集合， 为第一台机器上产生了 个子工 件的完成时间， 。 ，其中 表 示由第 个母件产生，并且已经加工完的子件集 合， 表示第 个母件还未裂变出的子件集合。 母件分解子件个数相同 初始值 递归函数 最优解 母件分解子件个数任意 首先考虑如果母件经过切管机同时产生出 所有的子工件，这个问题仍然可以看作是 一般意义上的 二机流水问题。这时按照求 解问题的Johnson规则求出问题的最优解。 母件分解子件个数任意 接下来考虑如果每个子件的产生都有一个确定的 时间，问题是一般意义NP难的，问题的证明是由 最小平方和问题归约得到的。 最小平方和问题： 有限集A,每个 的大小 ,正整数 和 J。问：A是否能划分成K个不相交的集合 ，使得 ？ 定理 1：对于母件每产生一个子工件都有一个确 定的时间，母件加工不可中断，母件产生子件个 数任意，求 最小的问题是一般意义NP难问题 。 母件分解子件个数任意 证明：构造调度的例子如下，母管的个数 为K，每个母管切出的子管个数分别为 ，第j个母管经过第一台 机器切出的所有子工件的处理时间分别为0 ， ，所有工件在第二台机器上的处 理时间只有第一个工件的处理时间为 ，其余工件的处理时间都为0， 调度的门槛值设为J。 母件分解子件个数任意 如果最小平方和问题有解，可见目标函数 值不超过J。 反过来如果门槛值不超过J，由于 ， 可知必有 。调度函数 值即为工件在第二台机器上处理时间之和 。必有 。问题得证。 母件分解子件个数任意 在切管机在还没有切出一个母件的所有子 件时，可以改切另一个母件，求 最小 问题。这里切管机上母件的切换有一个常 数的切换时间。母件个数为n个，设函数 为第二台机器加工了i个子工件的完 成时间， 、 和 的定义同上，N、t、 、 、 、 、 的定义同上， 为第k个工件裂 变出的工件数， ，定义 这里给出一个母件产生任意多个 子工件的拟多项式时间动态规划算法。 母件分解子件个数任意 初始值 递归函数 最优解 母件分解子件个数任意 定理：这个动态规划的时间复杂性为 。 证明：状态变量有Ln个，循环所用的时间最 大为第二项，不会超过 ，算法的时间 复杂性为 。 结束语 本文研究的是一种工件分解类型调度问题