Percentile Optimization Based On Classical Scheduling Model

Scheduling is a common decision-making process.It refers to the process of making decisions on task assignment and processing order with the goal of optimizing functions such as completion time and utilization when resource constraints and machine task states are given.Usually,all tasks in a scheduling process need to be decided,and the optimization target value is closely related to the state after all tasks are completed.But in practice,in order to balance the contradiction between cost and performance,many scenarios no longer require all tasks to be processed.For example,in the tail delay optimization of a data center cluster,we usually only consider a certain percentage of tasks to achieve the expected response delay instead of all tasks;In some security application scenarios,there are similar problems.Such problems that only optimize part of the task to complete as percentile optimization problems.At present,there is still a lack of research on percentile optimization problems in academia and industry.In this paper,the percentile optimization problem in the common multi-parallel computer environment is deeply studied.We mainly consider the optimization objectives related to the completion time,and give theoretical results and analysis for the percentile optimization problem under various scheduling models.Specifically,the main contributions of this paper include the following two points:1.Propose solutions based on the Reduction algorithm:When the algorithm is combined with the LPT(Longest Processing Time First)algorithm and the Kawaguchi[1]algorithm,can achieve a constant approximation ratio for the percentile scheduling problem of weighted completion time and completion time;When combined with SPT(Shortest Processing Time First)and linear programming,we can get the optimal solution to the percentile scheduling problem that optimizes the total completion time and the completion time in the preemptive case.2.Propose solutions based on CONVERT algorithm and SRPT algorithm:For the percentile optimization problem of the total completion time in the case of preemption,we propose an online algorithm SRPT(Shortest Remaining Processing Time First).Algorithm SRPT can achieve the performance guarantee of the approximate ratio of 2 under the model when release time exist;when the task has no release time,we can get the optimal solution.CONVERT algorithm can remove the preemption restriction and adapt the scheduling algorithm originally suitable for the preemptive model to the non-preemptive scheduling model.For the percentile scheduling model of the total completion time that cannot be preempted and has release time,the combination of this algorithm and the SRPT algorithm can achieve a performance guarantee of 6 approximate ratio.