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

管加工中两机器协调调度问题第一页，共二十八页，2022年，8月28日基金项目国家杰出青年科学基金(70425003)；国家自然科学基金项目(70171030,60274049)；高等学校优秀青年教师教学科研奖励计划(教育司[2002]383).第二页，共二十八页，2022年，8月28日摘要

本文研究大型钢铁加工企业管加工厂生产作业中存在的一种工件分解类型的生产调度问题，其特点为一个工件（母件）经过切管机后被切成多个子件，母件和子件分别在两个工序对应的设备上（每个工序假设只有一个设备）进行加工，文中考虑的机器环境是二机流水车间，目标函数是所有工件最大完成时间最小。第三页，共二十八页，2022年，8月28日摘要传统生产调度都是工件装配类型或者工件类型不变，本文研究的调度问题与传统问题不同，属于分解类型的调度，不仅需要确定母件在切管机上的排序，同时要考虑母件在切管机上切出各个子管的先后顺序。第四页，共二十八页，2022年，8月28日摘要根据母件分解成子件的数目不同，把问题分成为两类：一类是所有母件分解成子件的数目相同；一类是母件分解成子件的数目任意。对于这两类问题又分别就下面的几种情况进行分析：子件同时产生；子件不同时产生、母件的加工不可中断；母件加工可中断、母件间的切换有一个常数时间。第五页，共二十八页，2022年，8月28日引言本文研究的问题描述如下：考虑工件分解型的调度问题，机器环境是二机流水车间，一个工件(母件)在经过第一台机器时裂变出多个工件(子件)，考虑的目标函数是所有工件的最大完成时间最小。调度需要确定每个工件(母件)在切管机上的加工顺序，以及母件的每个子件产生的顺序。第六页，共二十八页，2022年，8月28日引言本文研究的问题是以钢铁加工企业钢管厂为背景，研究套管加工流程中切管机和下游机器的协调调度，如图1所示。从上游工序产生出的毛管很长，要经过切管机把毛管切成适当长度的子管，然后继续在下游的机器上进行倒棱、接箍拧紧、通径、涂漆等工序，最后形成成品套管。第七页，共二十八页，2022年，8月28日引言图１：管加工厂流程切管机热处理中间库成品库套管加工第八页，共二十八页，2022年，8月28日引言钢铁企业使用的都是大型设备，提高设备的利用率是关键的指标，因此本文研究的调度问题以求工件最大完成时间最小化作为目标函数。第九页，共二十八页，2022年，8月28日引言文中研究的工件是分解类型的，工件数目经过切管机后发生变化，并且母件每产生出一个子件都可以开始在下游的机器上加工，而不用等其所有子件全部产生在开始在第二台机器上加工，因此问题与传统的二机流水问题不同，不能直接由Johnson规则得到最优解。第十页，共二十八页，2022年，8月28日引言在以往的文献中，有许多研究的是流水车间环境下求最大完成时间最小问题，调度的类型都是工件类型不变，在此对其进行简单的综述。Sung

和Kim[2]研究的二机流水车间求最大完成时间问题，允许工件有动态的到达时间；Lin

和Cheng[3]研究的二机流水车间求最大完成时间是批调度问题；Allahverdi[4]论文考虑的流水车间问题，目标函数是最大完成时间与平均流水时间的加权求和。

第十一页，共二十八页，2022年，8月28日引言还有一些文献研究流水车间装配类型的调度问题：Koulamas和Kyparisis[5]研究三机流水装配车间问题,目标函数是最大完成时间,还有Yang[6]，Yakoyama和masao[7]研究的也是装配工件的调度问题。Lee[8]考虑具有装配类型特征的分解工件调度问题，目标函数是多个费用和最小，给出问题的启发式算法，并分析界。第十二页，共二十八页，2022年，8月28日协调问题首先给出这一部分考虑的协调问题都要用到的一条性质。性质1：对于文中提出的问题，如果可以得到最小值，总是可以通过使所有工件在两机器上的加工顺序相同得到。由性质1，文中研究的问题总是认为所有子件在二台机器上加工顺序相同。第十三页，共二十八页，2022年，8月28日协调问题引理：如果问题有最优解，总是可以通过使第一个机器上没有闲置时间而得到。证明：如果问题的最优解中，工件在机器一上的加工有闲置，移动工件，使机器一上的加工没有闲置，问题的目标函数值不会增大。由引理，我们在下面的定理证明中认为工件在第一个机器上没有闲置时间。即工件在第一台机器上的加工是连续的。第十四页，共二十八页，2022年，8月28日母件分解子件个数相同

这一部分中，研究母件个数为，每个母件经过切管机裂变出的子工件个数均为。首先考虑母件经过切管机同时裂变出所有的子工件，这个问题总可以看作是一般意义上的二机流水求最小完成时间问题，母件在第两台机器上的处理时间为其所有子件的处理时间之和。按照求解问题的Johnson规则求出问题的最优解。第十五页，共二十八页，2022年，8月28日母件分解子件个数相同接下来考虑母件裂变子工件有确定处理时间，母件在第一台机器上的加工不可中断问题。就一些特殊的情况给出求解问题的最优算法。性质2：当，对所有的，都成立，要得最大完成时间最小，这时只要把满足的母件安排在所有母件的最后位置加工，同时其中的第个子件安排在其所有子件的最后位置加工即可。其他母件、子件的顺序任意。证明略。第十六页，共二十八页，2022年，8月28日母件分解子件个数相同性质3：当,对所有的，都成立。这时要得最大完成时间到最小，只要把满足的母件安排在所有母件的第一个位置加工，同时其第个子件安排在其所有子件的第一个位置加工即可。其他母件、子件的顺序任意。证明略。第十七页，共二十八页，2022年，8月28日母件分解子件个数相同下面考虑在切管机在还没有切出一个母件的所有子件时，可以改切另一个母件，求最大完成时间最小问题。这里切管机上母件的切换有一个常数的切换时间。下面给出一个多项式时间动态规划算法。第十八页，共二十八页，2022年，8月28日母件分解子件个数相同设函数为第二台机器加工了个子工件的完成时间，其中表示第二台机器加工的最后一个子工件是由第个母件产生的。，为切管机上切换一个母件的时间，为已经产生出至少一个子工件的母件集合，为没有加工过的母件集合，为第一台机器上产生了个子工件的完成时间，。，其中表示由第个母件产生，并且已经加工完的子件集合，表示第个母件还未裂变出的子件集合。第十九页，共二十八页，2022年，8月28日母件分解子件个数相同初始值递归函数最优解第二十页，共二十八页，2022年，8月28日母件分解子件个数任意首先考虑如果母件经过切管机同时产生出所有的子工件，这个问题仍然可以看作是一般意义上的二机流水问题。这时按照求解问题的Johnson规则求出问题的最优解。第二十一页，共二十八页，2022年，8月28日母件分解子件个数任意接下来考虑如果每个子件的产生都有一个确定的时间，问题是一般意义NP难的，问题的证明是由最小平方和问题归约得到的。最小平方和问题：有限集A,每个的大小,正整数和J。问：A是否能划分成K个不相交的集合，使得？定理1：对于母件每产生一个子工件都有一个确定的时间，母件加工不可中断，母件产生子件个数任意，求最小的问题是一般意义NP难问题。第二十二页，共二十八页，2022年，8月28日母件分解子件个数任意证明：构造调度的例子如下，母管的个数为K，每个母管切出的子管个数分别为，第j个母管经过第一台机器切出的所有子工件的处理时间分别为0，，所有工件在第二台机器上的处理时间只有第一个工件的处理时间为，其余工件的处理时间都为0，调度的门槛值设为J。第二十三页，共二十八页，2022年，8月28日母件分解子件个数任意如果最小平方和问题有解，可见目标函数值不超过J。反过来如果门槛值不超过J，由于，可知必有。调度函数值即为工件在第二台机器上处理时间之和。必有。问题得证。第二十四页，共二十八页，2022年，8月28日母件分解子件个数任意在切管机在还没有切出一个母件的所有子件时，可以改切另一个母件，求最小问题。这里切管机上母件的切换有一个常数的切换时间。母件个数为n个，设函数为第二台机器加工了i个子工件的完成时间，、和的定义同上，N、t、、、、、的定义同上，为第k个工件裂变出的工件数，，定义这里给出一个母件产生任意多个子工件的拟多项式时间动态规划算法。第二十五页，共二十八页，2022年，8月28日母件分解子件个数任意初始值递归函数最优解第二十六页，共二十八页，2022年，8月28日母件分解子件个数任意定理：这个动态规划的时间复杂性为。证明：状态变量有Ln个，循环所用的时间最大为第二项，不会超过，算法的时间复杂性为。第二十七页，共二十