具有不同释放时间的单机重新排序问题的近似算法

代理获取

页面导航

目录
摘要
著录项
相似文献
相关主题

摘要

近年来，重新排序问题研究开始引起广泛的关注.本文以工厂机器加工工件(工件与任务表示相同的概念)作为实际背景，主要考虑有一批工件已经按照某种规则进行了排序并使得目标函数达到了最优，其中有一些工件由于各种各样的原因要推迟到某个时间点后才可以开始加工，此时，决策者需要对原来的排序进行调整，即在原来最优排序的基础上，在工件的时间错位不至于太大的限制下进行重新排序，并使得原来的目标函数达到最优的单机问题。
　　本文研究的问题的目标函数是经典的加权完工时间总和。对于这个问题Nicholas G.Hall和Chris N.Potts已经提供了一种复杂度是伪多项式时间的动态规划最优算法TWCOA,并给出了其时间复杂度的分析，随后给出了GAA近似算法，其最坏情况误差比为2。本文对该近似算法进行改善，得到了更好的SR近似算法并给出了其最坏情况误差比比GAA近似算法小的证明。同时对该问题进行了拓展，将条件中的重排工件共有的一个释放时间变成两个不同的释放时间，使问题变得更一般化，然后进行讨论从而得到该问题的一个近似算法SRT。

著录项

作者
朱婷婷;
展开▼
作者单位

兰州大学;

展开▼
授予单位兰州大学;
学科数学运筹学与控制论
授予学位硕士
导师姓名王海明;
年度 2016
页码
总页数
原文格式 PDF
正文语种中文
中图分类动态规划;统筹方法;
关键词
任务调度; 动态规划; 最优排序; SRT算法;

相似文献

中文文献
外文文献
专利

1. 具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案 [J] . 金苗苗 ,吴蒙洁 ,罗文昌 . 运筹与管理 . 2021,第008期
2. 工件有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法 [J] . 刘晓霞 ,余山杉 ,罗文昌 . 运筹学学报 . 2020,第001期
3. 具有恶化效应和释放时间约束的单机成组调度问题研究 [J] . 贺宁 ,伍乃骐 . 价值工程 . 2016,第016期
4. 工件延误和可拒绝下的单机重新排序问题的近似方案 [J] . 余山杉 ,金苗苗 ,罗文昌 . 运筹学学报 . 2021,第002期
5. 具有老化效应的单机共同工期安排和工件可拒绝排序问题 [J] . 刘春来 ,王建军 . 运筹与管理 . 2021,第007期
6. 有尺寸的单机分批排序问题的近似算法 [C] . 吴翠连 . 中国企业运筹学第六届学术年会 . 2011
7. 工件有大小的单机分批排序问题的近似算法 [A] . 武海龙 . 2011

具有不同释放时间的单机重新排序问题的近似算法

目录

摘要

著录项

相似文献

相关主题

期刊订阅