基于一般时间相关和位置相关的单机排序问题研究  

Study on Single Machine Scheduling Problem Based on General Time-and-position Dependent Jobs Processing Time

作　　者：王申重[1] 

机构地区：[1]郑州大学西亚斯国际学院文理学院,河南新郑451150

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

基　　金：河南省高等学校重点科研项目(No.15A510015)

摘　　要：【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,对此问题用经典算法进行了讨论。【结果】目标函数为极小化最大完工时间和总完工时间的问题证明了SPT算法仍是最优算法。对极小化加权总完工时间问题分析了最坏竞争比;在正常加工时间和权重或工期存在特殊关系时对加权总完工时间和最大延迟问题证明了经典算法是最优的。【结论】对所研究的单机排序问题给出了若干结果。[Purposes]It addresses single-machine scheduling problems with time and position dependent job processing times.[Methods]The processing time of a job is non-increasing function of its starting time and its position in the sequence.Inspired by the related papers,it discusses the classical algorithm.[Findings]It proves that the classical SPT（Shortest processing time）rule remains optimal to minimize the makespan or the total completion time.For problem of minimizing the total weighted completion time,it presents heuristic sequencing rules and analyzes the worst case bound for performance ratios.It also presents that these classical rules can be optimal under some special conditions between the normal processing times and job weights or due dates.[Conclusions]Some results on the single machine scheduling problem are given.

关 键 词：排序 时间相关排序 位置相关排序 多项式时间算法 

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