随机与重新排序问题研究

作     者：郝赟 

作者单位：河南工业大学 

学位级别：硕士

导师姓名：慕运动

授予年度：2012年

学科分类：07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：重新排序 随机排序 指数分布 错位 期望完工时间 截止日期 延误 

摘      要：本文研究的重新排序问题包括确定性的重新排序和随机的重新排序问题.对于随机重新排序问题,我们考虑了如下两个方面的问题：（1）工件的加工时间服从任意分布,在错位限制下的随机重新排序问题,目标是使期望总完工时间最小;（2）在错位限制下的含有退化工件的随机重新排序问题,工件的加工时间是服从指数分布的,对于退化工件,我们把工件的实际期望加工时间看作是工件开始期望加工时间的线性函数,目标是极小化期望总完工时间.具体的模型如下： 对于确定的重新排序问题,我们考虑了以下两个方面的问题：（1）时间错位和序列错位呈线性关系的重新排序问题,目标是使总完工时间最小;（2）在错位限制下的含有退化工件的重新排序问题,我们把工件的实际加工时间看作是工件开工时间的线性函数,目标函数是使得总延误时间最小.具体的模型如下： 根据理论分析的方法研究了工件的最优解的性质,给出了相应的多项式时间算法或拟多项式时间算法,并证明了这些算法的可行性和最优性.