可及时下线的批处理在线排序研究

项目名称： 可及时下线的批处理在线排序研究

项目编号： No.11301528

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

立项/批准年度： 2014

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

项目作者： 田记

作者单位： 中国矿业大学

项目金额： 22万元

中文摘要： 在线算法是排序论中的热点研究课题。本项目研究一类新型的在线排序模型：可及时下线的批处理在线排序。在该模型中，在批容量允许的情况下，多个工件可以放在一批中进行加工。同一批的工件具有相同的开工时间，但每一工件的完工时间等于该工件所在批的开工时间与其自身的加工时间之和。所研究问题的目标函数包括：工件的最大流程、工件的最大送货完成时间、工件的加权完工时间和等。本项目的研究还将与分组工件和允许重启等排序模型相结合形成更为广泛的研究内容。通过探讨离线最优排序的结构特征并以全新的在线排序理论工具为基础，寻求性能良好的在线算法；对可及时下线的批处理在线排序建立基本的理论构架并取得一系列创新性的研究成果。

中文关键词： 在线排序；可及时下线；批处理机；在线算法；竞争比

英文摘要： Online algorithm is a hot topic in the scheduling research. In this project we will study a new online scheduling problem: online scheduling on drop-line batch machines. In this model, several jobs can be processed in a batch as many as the batch capacity is not exceeded. All jobs in a batch have the same starting time. The completion time of a job is equal to the starting time of a batch, which contains the job, plus the job's processing time. The objective functions of the problems under research include: the maximum flow time of the jobs, the maximum delivery completion time of the jobs, and the total weighted completion time of the jobs. The scheduling models with family jobs and restarts are combined into our research to form an extensive research content. By studying the structure feature of the off-line optimal schedules and based on totally new theoretical tools in online scheduling, we seek for the online algorithms with better performance properties. For the online scheduling on drop-line batch machines, we will establish fundamental theoretical framework and obtain a series of innovative research achievements.

英文关键词： online scheduling；drop-line；batch machine；online algorithm；competitive ratio