文档介绍：⑧两类新型排序问题:算法设计与分析论文作者签名:指导教师签名:论文评阅人评阅人答辩委员会主席:委员胡旭东研究员鲁习文教授谢金星教授邢文训教授陈秋双教授姚恩瑜教授陈光亭教授杨启帆教授张国川淌谈之奕教授答辩日期:二零一一年六月
工嚣,蕾●叫
⑧’:’
浙江大学研究生学位论文独创性声明学位论文版权使用授权书写过的研究成果,也不包含为获得浙江大学或其他教育机构的学位或证书而使本学位论文作者完全了解浙江大学有关保留、使用学位论文的规定,有权保本人授权浙江大学可以将学位论文的全部或部分内容编入有关数据库进行检索本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名:签字日期:年留并向国家有关部门或机构送交本论文的复印件和磁盘,允许论文被查阅和借阅。和传播,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。C艿难宦畚脑诮饷芎笫视帽臼谌ㄊ签字期:月日导师签名:
致谢很幸运来到浙江大学跟随我的导师张国川教授攻读博士学位,是他把我引入了“组合优化”这一研究领域,没有他的指导,鼓励,支持,帮助及对我思维能力的训练,,,扎实的学问,务实创新的研究理念,严谨的治学风格,对名利的淡薄值得我终身学习,,杨启帆教授,谈之奕教授,,,程郁琨,梅丽丽,万龙,武海龙,申华,杨双全,徐海峰,余炜,张安等同学在生活和学上给予的帮助,与他们一起上讨论班,讨论问题,爬山,打牌,逛西湖,吃斋饭,散步聊天给我带来了很多生活和学习上的快乐,,、
非了扑惴ê以/￡,,,出现了多客户排序问题,每个客户拥有自己的工件,,,,本文主要讨论下面几个新型排序模型:维护时间可变的单机排序问题,浮动维护下的线性退化工件单机排序问题和两个客户下的两台机流水第一章为绪论,,,最大延迟和工件的完工时间和时,,,,即维护的时长是维护开始时刻的非降凹函数时,我们分别给出最后,我们讨论了维护的时长是维护开始时刻的任意函数的情形,证明了对极小化橙完工时间和的目标函数,不存在近似比为常数的多项式时间算法,,,,
,;二是以一个客户的目标为约束,,,然后设计了一个简单的近似算法,,,:排序,计算复杂性,近似算法浙江大学博士学位论文