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

管加工中两机器协调调度问题 第一页，共二十八页，2022年，8月28日 基金项目 国家杰出青年科学基金； 国家自然科学基金项目 ； 高等学校优秀青年教师教学科研奖励计划 (教育司[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日 协调问题 引理：如果问题有最优解，总是可以通过使第一个机器上没有闲置时间而得到。 证明：如果问题的最优解中，工件在机器一上的加工有闲置，移动工件，使机器一上的加工没有闲置，问题的目标函数值不会增大。 由引理，我们在下面的定理证明中认为工件在第一个机器上没有闲置时间。即工件在第一台机器上的加工是连续的。 第十