时间错位和序列错位呈线性关系的重新排序

摘要：

讨论了时间错位和序列错位呈线性关系,即最大时间错位与最大序列错位之和、最大时间错位与总序列错位之和、总时间错位与最大序列错位之和、总时间错位与总序列错位之和限制下,以使总完工时间最小为目标的重新排序问题.重新排序就是原始工件已经按照某种规则使目标函数值达到了最优,但还没有开始加工,这时又有一批新工件到达,要求将新工件与原始工件一起重排使目标函数为最优的排序问题.根据经典排序理论,证明了原始工件与新工件按最短加工时间优先规则可以使目标函数达到最优.由动态规划原理,对每个问题设计并证明了不同的算法及其时间复杂性,最后结合实例作了进一步论证.

关键词：重新排序、错位、线性关系、总完工时间和

所属期刊栏目：30

分类号：O223(运筹学)

资助基金：河南省自然科学基金112300410078;河南省教育厅自然科学基金2011B110008;河南工业大学博士科研基金;河南工业大学研究生科技创新基金项目10XJS056

在线出版日期：2013-04-07（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：25-29