带容量限制的平行机排序问题

《带容量限制的平行机排序问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、绪论定义1．2：RA兰inf{r≥1：RA(I)≤nV，]．而其最坏情况渐进性能比【6】定义为：定义1．3：R霄兰inf{r≥1：3N>0，OPT(I)≥N，RA(I)≤nV，)为简便起见，我们也常常将A(I)和oPT(i)记为A和OPT．这里，我们不得不提及计算复杂性，即哪些问题是简单的，又有哪些问题是困难的．很显然，计算复杂性是近似算法领域的基石．而为了解决一个实际问题，我们或者试图去寻找关于该问题的一个多项式时间算法去求解其最优值，或者尝试去证明该问题的Ⅳ尸一困难性，在此基础上去寻找一个有效的近似算法．我们称问题P为在线

2、问题，如果它的输入以在线方式到达同时其输出也以在线方式产生，这意味着在线输入所产生的输出会影响到最终解的值．由此产生一个自然的想法，也就是将优化问题分类为在线问题与离线问题．许多优化问题内在地属于离线情况，例如大部分的线性规划都假设它们的输入是离线给出的．但是也存在许多优化问题，考虑它们的在线与离线情况都具有重要的实际应用背景，例如装箱问题(binpacking)与平行机排序问题(scheduling)．此外，还有许多优化问题属于在线问题，但是即使对于这样的问题，我们仍然可以假设存在一个绝对聪明的对手使其所给予的算法达到离线情

3、况的最优值⋯．1．2排序问题简介我们先引入最基本的排序问题(ParallelMachineScheduling)：假设有m台机器坛(i=1，2⋯．，m)以及n个相互独立的_T-件Jj(J=1，2⋯．，n)．现需将每个工件安排到任一台机器上不中断地加工一次，记每个工件的加工时间为Pj≥O(j=l，2⋯．，扎)，且每个工件在零时刻到达．假设已给定一个排序，我们称G为工件乃的完工时间，记％n。=III&Xa．我们的目标是找到一个安排这些工件的加工方案，使得所有工件在最短时间内完工，即min％nz．该问题称为使时间跨度(makespa

4、n)最小的平行机排序问题．自从1966年R．Graham[4】提出关于上述问题的第一个近似算法以来，迄今人们已广泛地从不同的背景和观点研究排序问题．特别地，受到理论计算机科学发展所绪论需，排序问题持续地成为组合优化领域中极具活力的包含有大量有趣结论的一个研究方向．对于排序问题，我们现实中常常需要对其进行在线情况分析，即工件的信息并非在零时刻完全释放，我们需要根据现有的局部信息对工件进行安排．排序问题可根据工件，机器或目标值的特征分为各种不同的类型，关于它们的详细介绍请参见J．Sgall所撰写的综述性文章[71．我们将在本节简单

5、介绍一下排序问题的基本类型：1．2．1关于工件的相关标记设工件以包含礼；个操作步骤0m⋯，0加每个步骤0tf需要的加工时间为P泓若工件以只包含一个步骤(吼=1)，则记它的加工时间为Pi．更进一步地，将工件以第一个步骤可执行的时刻称为它的释放时间n．与0；f相应的加工机器记为％冬{尬，⋯，‰)．一般情况下，l／ij所属的集合或者是单台机，或者是所有机器的集合．第一种情况意味着相应工件必须由特定的机器加工，后一种情况下我们则称这些机器为平行机．本文主要研究的是平行机排序问题．此外，当每个工件以加工完成时，对应产生一个成本函数值^(

6、￡)，这里针对不同的目标成本函数，我们可以选择完工时间也或权重龇来定义五．一般情况下，我们假设排序问题中的所有数据Pi,P巧，n，d{，∽都是整数，并称一个排序是可行的如果任意两个工件加工区间在同一台机器上没有重叠，任意工件的单个步骤没有在两台机器上同时加工，以及符合与排序问题各种类型相关的其它特定限制．我们称一个排序是最优排序，如果它对于相应的目标优化准则取得最小值．有时我们也将工件以简单地记为指标值i，这将在本文的论述和证明中加以使用．更进一步地，人们倾向于使用约定俗成的“三参数表示法”(three．fieldrepres

7、enta—tion)将各种不同类型的排序问题表示为Q蚓7的形式．这里Ot表示机器环境，p表示工件特征，1表示优化目标准则[31．1．2．2机器环境机器环境由两个参数组成的字符串Q=Q1乜2表示．我们在研究过程中常常遇到的关于参数＆。的取值可能性主要有。，P，Q，R，G，0，ZF等．下面主要介绍一下。，P，Q，R的含义，其它记号请参考文献【31．绪论若Q1=o，920表示每个工件必须被安排到某一特定的机器上进行加工，这时相应的Q表示为a=＆2．若Q1∈{P，Q，R)，则表明这些机器是平行机．更进一步地，若OL。=P，则表示机器为

8、同型平行机(identicalparallelmachines)，也就是说若工件五被安排到机器尬上时，其对应的加工时间为P巧=Pt，则当其被安排到其它机器时上述加工时间维持不变．若Q1=Q，则表示机器为同类平行机(uniformparallelmachines)，即Pij=P