带恶化和学习效应的排序模型

作     者：董坤厚 

作者单位：兰州大学 

学位级别：硕士

导师姓名：王海明

授予年度：2010年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

主      题：排序 学习效应 恶化效应 多项式算法 成组技术 

摘      要：本文主要讨论了带恶化效应和学习效应的单机排序和单机成组排序问题。对于这两个问题分别给出了两个模型,并对这些模型给出了相应的多项式算法。 第二章的第一、二节分别研究单机排序模型1│pi,[r]=(pi=α(t))rβ│f(C)和1│pr[r]=(pirβ+α(t))│f(C),对目标函数分别为时间表长、总完工时间以及总完工时间平方和,证明了多项式可解性;对目标函数为极小化最大延误,在满足p(?)≤pk当且仅当d(?)≤dk(i=1,2..n)的情况下,同样证明了多项式可解性。 第三章的第一、二节分别对单机成组排序问题的两个模型进行了研究。对于模型1|(?)和模型1│pi,j[r]=αi,j(a+bt)rβi,si=δi(a+bt),GT│f(C),当目标函数分别为时间表长和总完工时间时,我们给出了多项式算法;当目标函数为加权总完工时间,在且满足α(?)≥α(?)当且仅当wi,u≤wi,v(i=1,2..m)时,我们也给出了多项式算法。