文档介绍：第卷第期经济数学
年月
复合并行机’,
排序问题的归并算法研究‘
吕绪华,李寿贵
武汉科技大学理学院,湖北武汉,
摘要在文蔽中,已经证明了排序问题厂妻,是完全问题,没有好算法本文提出了
复合并行机厂,,。排序问题的一个启发式算法—归并算法,并证明了该算法在最坏情况下
,,,,,,,,, , 、。从一‘,、一、,广。,、‘,
的性能比‘是兰篇一,且优于文献“」中算法·
关键词排序,装配式流水作业,完全问题,启发式算法,性能比
。前言
根据年出版的运筹学
和管理科学手册》第四卷第章,, 和
等的论文“”的观点,经典排
序有四个基本假设川
资源的类型机器是加工工件所需要的一种资源我们假设,一台机器在任何时刻最
多只能加工一个工件,同时还假设,一个工件在任何时刻至多在一台机器上加工
确定性我们假设,决定排序问题的一个实例的所有输人参数都是事先知道的和完
全确定的
可运算性我们是在可以运算、可以计算的程度上研究排序问题,而不去顾及诸如如何
确定工件的交货期,如何购置机器和配备设备等技术上可能发生的问题
单目标和正则性我们假设排序的目的是使衡量排法好坏的一个一维目标函数的函数
值为最小,而且这个目标函数是工件完工时间的非降函数
但假设限制了排序理论的发展,在机器制造系统中,一个部件由多个零件组成,每个零
件由多台机器同时并行加工在大型并行机计算系统中,有多于两台计算机同时计算某一个问
题的多个子问题这些都是由多台机器同时加工一个零件的新型加工模型亦即年波芝
兰大学计算机学院教授首先提出一个新排序问题“一
”—“复合并行机排序”问题其中两台机器并行加工的排序问题已证明是一
完全问题因此,绝大多数复合并行机排序问题是一完全问题,没有多项式时间算法
湖北省教育厅科研基金课题资助
收稿日期一一
经济数学第卷
为了文章的完整性,我们把文献川中的装配式排序问题的定义重新叙述如下
设有个工件集合,,⋯,,和十台机器集合王,,,⋯⋯,对阴,从,每个
工件必须在十台机器上加工,,在机器,,,,··一,,,风上的加工时间依次分别
记为尸,尸,尸,⋯⋯,尸,,尸。,,⋯,工件必须按以下方式加工‘先在前台
机器上同时加工,或分别加工,必须在前台机器上加工完成以后,方可在第台
机器上进行加工假设一旦工件在某一机器上开始加工,则不允许间断,还假定在第一道工序
完工后,有足够的空间容量贮存等待加工的工件和半成品,优化指标是排序长度
,目的是构造一个排序,使。达到最小依照,和等人
提出的三区域表示法,且与文〕中的排序问题的表示相区别,我们把该问题记为厂】,
、
在文献中,已经证明了排序问题厂妻,是完全问题,没有好算法·
在这篇论文中,我们将提出求解问题的一个启发式算法—归并算法,并证明该算法在
一
最坏情况下的性能比是优于文献叫中算法
玲
’,的启发式算法
算法
步骤给定厂,二的某一实例,设口去艺、,二,,⋯,,且设
与加工时间丸。相应的虚拟机器为从·
步骤虚设个新的零件洲其中,,⋯,,洲在和从的加工时间为。和丸。
其中二,,⋯,,构成一个两台机器个零件的,优化目标为排序长度的流水作业排序问
题、
步骤在。,丸,其中,,⋯,中找最小