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