加工时间依赖于机器自由作业排序问题.pdf

《加工时间依赖于机器自由作业排序问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、年月运筹学学报第卷第期,加工时间依赖于机器的自由作业排序问题项思明安徽建筑工业学院,安徽,唐国春上海第二工业大学,上海,摘要年提出工件的加工时间依赖于机器的排序问题,并研究以最大完工时间和以总的完工时间为优化目标的两种这类排序问题然而,对以总的完工时间为优化“”是错误的本文用算例表明他提出的算法不是最优的,目标提出的最优算法并在机器连续加工,把这个排序问题转化成指派问题,的条件下从而可以用匈牙利算法得到最优解最后,我们提出几个尚未解决的问题,以期引起国内外同行进一步研究关健词自由作业,排序,指派问题,最优化算法问题的提出设有。个工件几二,,⋯,要在台机器城,,⋯,。上加工每“,而

2、每个工件都要在这台机器上各加工一次一个工件在这台机器上加工的加工顺序是可以任意选择的这种加工方式通常称为是自由作业叩叩加工方式自由作业排序,尤其是以和式为优化目标,包括以总的完工时间为优化目标的成果非常少’几,经典排序中通常用来表示工件毛在机器上的加工时间年提出研究工件的加工时间依赖于机器的排序问题这时,每个工件在一台机器从上的加工时’只与此机,、,器有关因而可以把工件在机器从上的加工时间记成在同篇论文中研究两台机器自由作业以最大完工时间和以总的完工时间为优化目标的两种这类排序问题采用三参数分类法’,这两种排序问题可以分别表示为队二‘和队、艺,其中表示工件几的完工时间,表示“最大

3、的工件完工时间遗憾的是给出的以总的完工时间为优化目标的最”,优算法是错误的据我们所知国内外还没有论文指出他的错误本文第节介“”,绍提出的最优算法并用算例说明这个算法得到的解不是最优的在第节中,在机器连续加工的情况下,我们把这个问题转化为指派问题收稿日期年月日国家自然科学基金和安徽省教委科研基金资助项目项思明,唐国春卷,从而可以用匈牙利算法得到最优解最后一节提出进一步研究的几点思考··的错误,对问题几艺在工件的加工时间和满足条件的情况时,提出以下算法加工,算法从把工件分配给机器和把工件儿分配给机器姚开始每当机器把分配给它的工件加工完成时,在尚未在此机器加工过的工件中挑选工件下标最小

4、的工件分配给此机器加,直到每工件都分别在这两机器上加工过一次工为止按上述算法,对算例尹、‘,尹,,艺得到图所示的加工方案,其二目标值,,。图按算法得到的加工方案然而,按图所示的加工方案,在第二台机器人上把工件。和工件对调,为“”,“”“”了避免加工发生冲突第二台机器几了在加工工件前要等待或空闲一个单位时间这样加工的目标值艺图机器有空闲的加工方案如果按照后面第节我们提出的方法,得到机器加工没有空闲连续地加工的方案,如图所示,目标值是又,、。、,,,图按第节化成指派问题得到的加工方案这表明提出的算法无论在机器不允许空闲或允许空闲时都不是最优的机器连续加工情况下的最优解设在问题几,,个

5、工件,儿,,人在机器艺中⋯和峨上的加工时间分别都是,,和记是在机器加工不空闲连续加工的情况下期加工时间依赖于机器的自由作业排序问题这个问题的一个加工方案这里和分别表示工件在机器和几九上一个紧接着一个加工的加工顺序由,于对换任意两个工件的加工次序不会影响总的完工时间,因此,可以把工件重新编号,使工件在机器上的加工顺序是自然顺序,,⋯,这表示在机器上工件是按顺序,几,⋯,人一个紧接着一个进行加工记,,,这里,,,。是,,,凡⋯⋯⋯,,,,的一个排列置换表示在机器场上工件是按顺序⋯同一个紧接着一个进行加工所,,‘以原问题队艺成为选择在第二台机器场上工件的加工顺序,使总的完工时间艺为最小

6、在第,一台机器上工件是按自然顺序加工所以工件再在第一台机器上是第个加工,加工的结束时间是知如果工件丙在第二台机器场上是第￡个加工,那么加工结束时间就是咖由于一个工件至多只能在一台机器上进行,,“”,加工也就是讲不能使一个工件加工发生冲突不能使一个工件同时在两台,“”“”机器上进行加工为此对于加工发生冲突的工件的完工时间赋以很大的,,“”,,数例如就可以避免这种冲突发生这样工件丙的完工时间或者更具体地讲,工件丙在第,一台机器上是第个加工在第二台机器场上是第葱个加工的完工时间弓为、了”,三一‘”,,华时勺一呵一’,钾‘三竺一严吧,二、·,一‘,‘,一习气升且”,,,‘从而问题队艺几在

7、机器加工没有空闲情况下的最优加工方案是在机器上,几,,人工件的加工顺序是自然顺序⋯二在机器峨上工件的加工顺序是由下列一个指派问题的最优解乙来决定这里少、了、,人如果工件内在第二台机器从上是第葱个加工几」一如果工件几在第二台机器从上不是第乞个加工指派问题的整数规划形式为‘、艺艺弓份艺肠闺,‘,,,一‘,一‘艺“一云可以用匈牙利算法来求解这个指派问题,从而也就得到原问题在机器连续加工情况下的最优解下面对第节中的算例化成指派问题来计算一下按和式得到这个算例相应的指派问题的系数矩阵如下所