【摘要】 以现代服务业预定系统中的实际问题为背景,研究了一类具有预约到达时间和最迟完工时间的在线排序问题;论证了两台机器时该问题的在线算法竞争比下界为2;在传统在线排序算法的基础上提出了针对该问题的在线贪婪算法,并分析了该算法的竞争比.更多还原

【Abstract】 On-line scheduling of independent jobs with order arrival time and hard deadlines is an extension of traditional on-line scheduling problems.Based on real booking systems in modern service industry,on-line scheduling of independent jobs with arbitrary order arrival time,job release times and hard deadlines on two parallel identical machines is studied.The upper bound of competitive ratios of on-line algorithms for the two-machine case is analyzed.An on-line greedy algorithm with a competitive ratio of 3 is presented.更多还原