时间相关的单机排序的最坏竞争比分析  

The Worst-case Performance Ratio with Time-dependent Single-scheduling Problems

作　　者：张新功[1] 

机构地区：[1]重庆师范大学数学学院,重庆401331

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

基　　金：国家自然科学基金天元专项(No.11226237);重庆市教委自然科学基金(No.KJ120624);重庆师范大学校级资助项目(No11XLB027;No.2011XLZ05)

摘　　要：本文研究了工件的加工时间具有开工时间和加工所在位置相关的单机排序问题。工件的加工时间是序列中加工所在的位置和开工时间的非增函数,目标函数为最小化的误工工件个数和最小化总误工。本文对于所研究的2个目标函数利用Moore-Hodgson算法和EDD规则分别提出的启发式算法,对于目标函数位误工工件个数情形给出了最坏竞争比近似于2,最小化总误工给出非常数的最坏竞争比。进一步如果工件的加工时间和工期具有一致关系,分别给出了2个多项式时间算法。This paper addresses two single-machine scheduling problems with time-and-position-dependent processing times. The processing time of a job is non-increasing function of its starting time and its position in the sequence. The objective is to minimize the number of the lardy jobs and the total tardiness. We present heuristic sequencing rules by Moore-Hodgson algorithm or EDD rule and analyze their worst-case bounds for performance ratios. We also show that these heuristic rules can be optimal under some agreeable conditions between the normal processing times and job due dates.

关 键 词：排序 时间相关排序 最坏竞争比 多项式时间算法 

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