单机分批排序和平行机在线排序问题

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

1、曲阜师范大学硕士学位论文单机分批排序和平行机在线排序问题姓名：王琳申请学位级别：硕士专业：运筹学与控制论指导教师：张玉忠2003.3.12曲阜师范大学硕士学位毕业论文单机分批排序和平行机在线排序问题摘要排序问题有深刻的实际背景．无论在工农业生产，还是在国防、科研、交通运输以及各种服务行业，每天都会遇到它．排序问题是运筹学的一个较年轻的分支，而其中的分批排序以及在线排序问题，因其明显的实际意义，更是吸引了国内外许多学者．本文主要研究了这两类排序问题．论文共分三章．第一章(绪言)主要介绍了排序的产生背景、发展及其一些相关的基本知识．第二章

2、研究了目标函数为∑：lqU的批处理问题．模型为：一台批处理机要加工n个工件，已知每个工件的加工时间pj，权重％以及交货期d，，问怎样分批，怎样排序，使得目标函数∑警l屿U达到最小．我们把此问题记为1IBI∑警1札。K．若给定一个排序，我们可以很容易地得出每个工件以b=1，2，⋯，竹)的完工时间Q及其迟后工程yj=min{Tj，Pj}，这里Tj=max{Cj～dj，0)。迟后工程巧是工件如在其交货期嘭之后加工的部分．若K=0，说明工件以是提前完工的；若o

3、才开始加工的．Ports等【31j证明了1lI∑警1屿yj即使wj三1时也是NP一完备的，由此我们知道lIB

4、形下，表面上看似所有工件一批就可加工，事实上由于工件的性能不同可能造成目标值加大．本文我们则是证明在这种情况下问题的NP完备性．定理2．1问题llrj=0，B≥nI∑羔1wiv,是NP一完备的．为证明该问题是NP一完备的，我们将证明著名的二划分问题可多项式变换到该问题．给定二划分问题的一个实例如下：已知一个m个正整数组成的集合G={n·，a2⋯，n。)，问是否存在G的一个子集x，使得∑aj=A=；∑。，jex“J=l我们构造一个排序模型，可多项式变化到二划分问题，从而证明了问题lh=0，B≥扎I∑n，：1％U的NP完备性．第三章首次提

5、出并研究了带机器准备时间的平行机在线(Oil—line)排序问题，这里工件是可打断的(preemptive)．具体模型为：m台平行机^4H一，M。需加工佗个工件^，⋯，厶，每个工件是在线到达(onebyone)且可打断的，机器舰的准备时间为口i，怎样安排加工顺序，使工件的最大完工时间(makespan)尽可能地小，称此问题为带机器准备时间的平行机在线排序问题。它是带机器准备时间的平行机排序和平行机在线排序问题的综合和推广，具有广泛的应用背景．这里工件在线到达(onebyone)指的是工件的情况并不是提前知道的，只有将工件西一·安排完以

6、后我们才能知道工件以的一些情况(如工件的加工时间鳓等)．工件是可打断的，也就是说，工件在加工过程中可以被中途打断，然后过一段时间或立即可以在同一台机器或另外一台机器上继续加工，并且总的加工时间不变。但任一工件不能被两台机器同时加工．曲阜师范大学硕士学位毕业论文首先我们先给出一些记号：设r=F砭知，t时刻：排完第t个工件后的时刻，L：：t时刻机器尬要加工完已排好的工件所需的时间，Q：=L：+ai，OPT‘：对工件集{^，⋯，^)在off-line下所得的最优解，LB。为其对应的下界，S‘=∑名1聊十∑仁rnlai．对于加工时间分别为Pl

7、，P2，⋯，P。的n个工件，若它们零时刻到达且可打断，机器有各自的速度8i与准备时间ai≥0，则机器的完工时间有三个显然的下界：maxl_

8、lsiQis躺'--ii-∥．算法：现假设已排完前t个工件^，⋯，五，步骤1对于新到的工件五+1，先由(3．2．1)计算LBt+X，步骤2然后再来看各机器上可安排五+-的时间段，对机器尬，这个时间段为％=[Q‰，rLB蚌