论文标题
关于在线最短处理时间（SRPT）计划的竞争力的结果
Results on Competitiveness of Online Shortest Remaining Processing Time(SRPT) Scheduling with Special Classes of Inputs
论文作者
论文摘要
最短的剩余处理时间（SRPT）是一种众所周知的单层处理器和多处理器系统的预先设定算法。 SRPT在新兴区域中查找应用程序，例如安排客户请求，这些请求已提交给Web服务器，以访问静态网页，管理多源数据库系统中对文件的访问请求，并根据数据通信中的带宽可用性来管理多个链接的数据包。事实证明，SRPT对于设置是最佳的，在此目标是最大程度地减少工作列表的平均响应时间。据我们所知，关于在线SRPT的研究对MakePan作为绩效标准的最小化的关注较少。在本文中，我们研究了SRPT算法在多处理器系统中以MakePAN最小化为目标的在线调度。根据实际的现实生活应用，我们为特殊类别的在线工作序列获得了算法SRPT的恒定竞争性结果。
Shortest Remaining Processing Time (SRPT) is a well known preemptive scheduling algorithm for uniprocessor and multiprocessor systems. SRPT finds applications in the emerging areas such as scheduling of client's requests that are submitted to a web server for accessing static web pages, managing the access requests to files in multiuser database systems and routing of packets across several links as per bandwidth availability in data communications. SRPT has been proved to be optimal for the settings, where the objective is to minimize the mean response time of a list of jobs. According to our knowledge, there is less attention on the study of online SRPT with respect to the minimization of makespan as a performance criterion. In this paper, we study the SRPT algorithm for online scheduling in multiprocessor systems with makespan minimization as an objective. We obtain improved constant competitiveness results for algorithm SRPT for special classes of online job sequences based on practical real life applications.
