一致平行机上在线排序

《一致平行机上在线排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、硕士学位论文题，但由于整数规划的求解同样也是困难的，而组合优化又涵盖甚广，因此人们致力于研究各个问题的组合结构，试图找到一些好的性质和有针对性的求解方法．常见的组合优化问题有划分问题(PartitionPrdblem)，排序问题(schedul．ingProblem)，装箱问题(BinpackingProblem)，背包问题(KnapsackProblem)，指派问题(AssigIlmentProblem)，旅行售货商问题(naveuingproblem)，斯坦纳最小树问题(steinerMiIlim

2、alneeProblem)等．网络中的组合优化问题还包括最短路问题(shortestPathProbl锄)，最小生成树问题(Minimalspan血gneeProblem)，最大流问题(M躲floWProbl锄)，最小费用流问题(Min-costFlowProblem)等．组合优化全貌参见【1，2】．在此，只对本文研究的排序问题作一下介绍．1．2排序问题排序问题是组合优化中一类有着重要理论意义和广泛实际背景的问题．其实就是寻找需要完成任务的合理安排以得到某种意义下的最优结果【3，41．它在理论计算机科

3、学和离散组合数学也存在着密切的联系．近几十年来，排序问题得到了运筹学，工程学，管理学，和计算机科学的极大关注，并且随着对经典问题研究的日趋深入，大量具有实际背景的新问题不断涌现，使排序问题极具有生命力和研究价值．可以这样说，对排序问题的研究正进入成熟期．按照学术界多年来形成的惯例，我们把需要完成的任务称为工件Oob)，把完成任务需要的资源称为机器(machine)，我们希望找到一个可行的排序(schedule)，使得某个给定的目标函数达到最大(小)．这里了性一般指在同一时刻，一台机器至多加工一个工件，

4、一个工件排序也只在一台机器上加2一致平行机上在线排序工，并且该排序满足问题的约束条件．排序问题按照静态(static)和动态(dynaIIlic)，确定性(deterministic)和非确定性(non—deter耐nistic)可以分为四类．对于静态的确定性排序问题，我们习惯上用三参数法来表示。1967年Con锄yf5

5、等首先提出用四个参数来表示排序问题，1979年Grah啪[6】等提出改用三参数即用Q俐7来表示一个排序问题．其中Q，p，，y分别代表特定的机器环境，工作特征和最优准则．机器环境用来描

6、述机器的数量，不同机器之间的关系等与机器有关的性质．机器可以分为两大类：通用平行机(paraLllel)和专用串联机(dedi．cated)．对于不许中断加工的情况来讲，一个工件在矾台平行机器上加工只需要在仇台机器中的任何一台机器上加工一次即可；一个工件在m台串联机上的加工则需要在这m台机器中的每一台机器上都加工一次．常见的平行机类型有：同型平行机(identicalpauraJlelmachin骼)，即所有机器的加工速度一样，通常用P表示．若写成Pm，则表示系统中共有m台同型平行机且m为固定常数；一

7、致平行机(uniformparaJlelmachin稍)，即机器有各自不同的速度，但任意工件在不同机器上的加工时间有相同的比例关系，通常用Q表示．非一致平行机(unrelatedparallelmachines)，即机器的加工速度不同，且工件在不同机器上的加工时间没有比例关系，通常用R表示．串联机也可以分为三类：每个工件以特定的相同的机器次序在机器上加工的流水作业(aowshop)，工件依次在机器上加工的次序可以任意的自由作业(叩enshop)和每一个工件以各自特定的机器次序进行加工的异序作业00bs

8、hop)．工件特征一般是指工件的各种加工信息，包括工件的加工时间，工件3硕士学位论文的到达时间，工件之间加工顺序以及工件和其开工时间的依赖关系，工件加工时间是否允许中断以及中断恢复后再加工时是否要接受惩罚等等．根据排序者对工件信息的了解程度，又可以将排序问题分为离线(omine)，在线(online)和半在线(semi-online)三类．在离线问题中，全部工件的所有信息都已知，排序者可以充分利用上述信息对工件进行安排，而对在线问题，其基本假设有两条：(1)工件的信息是逐个释放的，即工件pJ+。信息只

9、有在排序者对工件pt，仇⋯，功作出安排后才会被排序者所知道；(2)工件加工不可以改变，即一旦排序者将工件安排给某台机器加工，在其后的任何阶段不能以任何方式加以改变．1996年出现了一种新的排序概念．半在线排序问题．在实际问题中，出现离线和在线的情况并不多，大量存在的问题是排序者一方面不可能知道工件的所有信息，另一面可能掌握着笔经典在线模型更多的信息或有着更大的排序自由度，因此使问题变得比离线相对困难些，但比在线相对容易些．在1996后，各种不同的半在线模