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

项目名称： 最大化接收工件总利益的在线排序研究

项目编号： No.11501279

项目类型： 青年科学基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 李文杰

作者单位： 洛阳师范学院

项目金额： 18万元

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

中文关键词： 在线排序；批处理机；接收工件总利益；在线算法；竞争比

英文摘要： 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.

英文关键词： Online scheduling;Batching machines;Total profit of the accepted jobs;Online algorithms;Competitive ratio