最大化接收工件总利益的在线排序研究

Online scheduling is one of the fastest developed research direction in modern scheduling. Online schedule to maximize total profit of the accepted jobs is a very important online scheduling problem, which can be widely applied to network service and information technology. This project mainly studies the scheduling problem of maximizing total profit of the accepted jobs in the environment of semi online or batch online scheduling, and we try to derive some innovative contributions from the following two aspects: On one hand, by exploring the new methods and new techniques to improve the two new results for the problem of online batching schedule to maximize total profit of the accepted jobs in the literature; On the other hand, by establishing the new semi online scheduling models to further study the schedule problem to maximize total profit of the accepted jobs, and plans to look for ideal lower bounds on this kind of problem, by applying adversary method and computer data analysis, then using the methods such as, delay method, multiple method, instance reduction method, and charging method, to design and analysis best possible online algorithms matching the established lower bounds.

在线排序是现代排序领域中发展最为迅速的研究方向之一。最大化接收工件总利益的在线排序是一类非常重要的在线排序问题，被广泛的应用于网络服务和信息技术领域之中。本项目主要研究半在线或批处理在线环境下的最大化接收工件总利益排序问题，并力求在以下两方面取得若干创新性成果：一、探索新方法和新技巧改进文献中关于最大化接收工件总利益批处理在线排序问题的两个最新研究结果；二、通过建立新的半在线排序模型，更深入的研究最大化接收工件总利益排序问题，并计划将计算机数据分析和对手法相结合来寻找此类问题的理想下界，然后利用延迟法、倍数法、实例归结法、Charging法等方法，设计和分析与下界相匹配的最好可能的在线算法。

在线排序是现代排序领域中发展最为迅速的研究方向之一。最大化接收工件总利益的在线排序是一类非常重要的在线排序问题，被广泛的应用于网络服务和信息技术领域之中。本项目对工件具有友好释放时间的半在线环境以及批处理在线环境下的最大化接收工件总利益排序问题和最小化传统指标排序问题进行了系统研究。 对最大化接收工件总权值的批处理在线排序问题设计出了一些新的在线算法并改进了文献中已有的若干研究结果；对本项目中建立的“工件具有友好释放时间”这一新的半在线排序模型，分别研究了最大化接收工件总利益排序问题和最小化传统指标排序问题，并得到一系列最好可能在线算法； 对最大化接收工件总利益的若干离线排序问题，进行了全面的复杂性分析。 受本项目资助共发表期刊学术论文11篇，其中SCI论文8篇。代表性成果如下：(1) 对工件可以被中断抢先的最大化接收工件总权值的单机Lookahead在线排序问题，设计出了新的在线算法并改进了文献中的已有研究结果；(2) 对最大化接收工件总权值的多台批处理机在线排序问题，推广了文献中的结果并设计出了新的在线算法改进了文献中的部分结果；(3) 对多组工件具有友好释放时间的单机批处理最小化Makespan半在线排序问题，设计出了最好可能的在线算法；(4) 对工件具有友好释放时间的批处理机最小化最大加权完工时间和的半在线排序问题，设计出了最优在线算法以及特殊情形下的最好可能的在线算法；(5) 对工件具有友好释放时间的最大化接收工件总权值单机半在线排序问题，根据工件长度不同设计出了若干性能良好的在线算法。