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

The Rescheduling Problems with Linear Relationship for Sequence Disruption and Time Disruption

作　　者：卢宁丹 许小艳[1] 郝赟[1] 慕运动[1] 

机构地区：[1]河南工业大学理学院,郑州450001

出　　处：《重庆师范大学学报（自然科学版）》2013年第1期25-29,共5页Journal of Chongqing Normal University:Natural Science

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

摘　　要：讨论了时间错位和序列错位呈线性关系,即最大时间错位与最大序列错位之和、最大时间错位与总序列错位之和、总时间错位与最大序列错位之和、总时间错位与总序列错位之和限制下,以使总完工时间最小为目标的重新排序问题。重新排序就是原始工件已经按照某种规则使目标函数值达到了最优,但还没有开始加工,这时又有一批新工件到达,要求将新工件与原始工件一起重排使目标函数为最优的排序问题。根据经典排序理论,证明了原始工件与新工件按最短加工时间优先规则可以使目标函数达到最优。由动态规划原理,对每个问题设计并证明了不同的算法及其时间复杂性,最后结合实例作了进一步论证。In this paper, we consider the rescheduling problems which sequence disruption and time disruption is a linear relation- ship, that is maximum sequence disruption and maximum time disruption, maximum sequence disruption and total time disrup- tion, total sequence disruption and maximum time disruption, total sequence disruption and total time disruption, the objective is to minimize the total completion time. Rescheduling problem is a set of original jobs that have been scheduled on a single machine according to some orders. There is another set of new jobs that arrive over time. Preemption is not permitted, so that no interrup- tion in the processing of a job is allowed. The goal is to find a schedule of original jobs set and new jobs set that minimize some ob- jective subject to some disruption constraints. According to classical scheduling theory, we show that shortest processing time first rule is to minimize objective functions, and design some algorithms by dynamic programming, given examples and time complexity of algorithms.

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

分 类 号：O223[理学—运筹学与控制论]