基于一般时间相关和位置相关的单机排序问题研究
|
摘要
【目的】研究了工件加工时间、开工时间与所在位置相关的单机排序问题,以扩展这类问题的研究范围。【方法】工件加工时间是开工时间和所在位置的一般非增函数。工件开工时间越晚,加工位置越靠后,实际加工时间则越短。受相关论文的启发,对此问题用经典算法进行了讨论。【结果】目标函数为极小化最大完工时间和总完工时间的问题证明了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.
[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.
引文
[1]NG C T,CHENG T C E,BACHMAN A,et al.Three scheduling problems with deteriorating jobs to minimize the total completion time[J].Information Processing Letter,2002,81:327-333.
[2]WANG J B,XIA Z Q.Scheduling jobs under decreasing linear deterioration[J].Information Processing Letters,2005,94:63-69.
[3]YANG D L,KUO W H.Some scheduling problems with deteriorating jobs and learning effects[J].Computers and Industrial Engineering,2010,58:25-28.
[4]高洁,赵玉芳.加工时间可控的单机排序问题[J].沈阳师范大学学报(自然科学版),2014,32(4):476-481.GAO J,ZHAO Y F.Single-machine scheduling problem with controllable processing times[J].Journal of Shenyang Normal University(Natural Science),2014,32(4):476-481.
[5]胡晨晨,赵玉芳.同时带有安装时间和送出时间的单机排序问题[J].沈阳师范大学学报(自然科学版),2015,33(3):36-42.HU C C,ZHAO Y F.Single machine scheduling problem with setup time and time of delivery[J].Journal of Shenyang Normal University(Natural Science),2015,33(3):36-42.
[6]谢秋莲,张新功.带有线性位置恶化及维修区间的单机排序问题[J].重庆师范大学学报(自然科学版),2015,32(5):38-43.XIE Q L,ZHANG X G.Single machine scheduling with a linear position deterioration and rate-modifying maintenance[J].Journal of Chongqing Normal University(Natural Science),2015,32(5):38-43.
[7]ZHANG X G,YAN G L,HUANG W Z,et al.Single-machine scheduling problems with time and position dependent processing times[J].Annal of Operational Research,2011,186:345-356.
[8]张新功.时间相关的单机排序的最坏竞争比分析[J].重庆师范大学学报(自然科学版),2013,30(5):5-10.ZHANG X G.The worst-case performance ratio with time-dependent single-scheduling problems[J].Journal of Chongqing Normal University(Natural Science),2013,30(5):5-10.
[2]WANG J B,XIA Z Q.Scheduling jobs under decreasing linear deterioration[J].Information Processing Letters,2005,94:63-69.
[3]YANG D L,KUO W H.Some scheduling problems with deteriorating jobs and learning effects[J].Computers and Industrial Engineering,2010,58:25-28.
[4]高洁,赵玉芳.加工时间可控的单机排序问题[J].沈阳师范大学学报(自然科学版),2014,32(4):476-481.GAO J,ZHAO Y F.Single-machine scheduling problem with controllable processing times[J].Journal of Shenyang Normal University(Natural Science),2014,32(4):476-481.
[5]胡晨晨,赵玉芳.同时带有安装时间和送出时间的单机排序问题[J].沈阳师范大学学报(自然科学版),2015,33(3):36-42.HU C C,ZHAO Y F.Single machine scheduling problem with setup time and time of delivery[J].Journal of Shenyang Normal University(Natural Science),2015,33(3):36-42.
[6]谢秋莲,张新功.带有线性位置恶化及维修区间的单机排序问题[J].重庆师范大学学报(自然科学版),2015,32(5):38-43.XIE Q L,ZHANG X G.Single machine scheduling with a linear position deterioration and rate-modifying maintenance[J].Journal of Chongqing Normal University(Natural Science),2015,32(5):38-43.
[7]ZHANG X G,YAN G L,HUANG W Z,et al.Single-machine scheduling problems with time and position dependent processing times[J].Annal of Operational Research,2011,186:345-356.
[8]张新功.时间相关的单机排序的最坏竞争比分析[J].重庆师范大学学报(自然科学版),2013,30(5):5-10.ZHANG X G.The worst-case performance ratio with time-dependent single-scheduling problems[J].Journal of Chongqing Normal University(Natural Science),2013,30(5):5-10.