`Name:`

HRRN(Highest Response Ratio Next) `Domain:`

Algorithm`Functionality:`

Deciding which process should be allocated CPU time when there are more than one process waiting and competing the resources. `Input:`

$I(P_{s_{1}},P_{s_{1}},\cdots,P_{s_n})$:where n is the number of the scheduled processes and $P_{s_i}=P_i(arrived-time_i,service-time_i)(1 \le i \le n)$ presents the information of the $i^{th}$ process which is waiting to be scheduled.(Type:Set) In order to simplify our illustration, we would use the previous sample input I as their common source test case $I_s$, that is, $I_s= [P_{1}(43,39), P_{2}(1,37), P_{3}(35,48), P_{4}(43,49), P_{5}(0,11), P_{6}(0,20), P_{7}(7,27), P_{8}(36,24), P_{9}(49,21), P_{10}(19,29)]$.

`Output:`

$O(P'_{s_{1}},P'_{s_{2}},\cdots,P'_{s_n},)$:where $P'_{s_j}(1 \le j \le n)$ is the name of the $j^{th}$ scheduled process, and we use $P_{jc}$ to denote the corresponding process of $P'_j$ in I.(Type: Set)

`Source input:`

$I_s$ ;
`Source output:`

$O_s$ `Follow-up input:`

$I_f$ ;
`Follow-up output:`

$O_f$ `Input relation:`

$I_f=Permutating elements of I_s$ `Output relation:`

$O_f=O_s$ `Source input:`

$I_s$ ;
`Source output:`

$O_s$ `Follow-up input:`

$I_f$ ;
`Follow-up output:`

$O_f$ `Input relation:`

$I_f$=Delaying the arrival time or increasing the service time of the last scheduled process of $O_s$ in $I_s$ `Output relation:`

$O_f=O_s$ `Source input:`

$I_s$ ;
`Source output:`

$O_s$ `Follow-up input:`

$I_f$ ;
`Follow-up output:`

$O_f$ `Input relation:`

$I_f$ is constructed based on $I_s$ but with the following changes: randomly choose $P'_{s_j}$ and $P'_{s_k} (1 \le k \le j \le n)$ from $O_s$ find their corresponding process $P_{s_{jc}}$ and $P_{s_{kc}}$ reset the parameters of $P_{s_{jc}}$ such that $P_{s_{jc}.arrival_time=P_{s_{kc}.arrival_time-1$, $P_{s_{jc}.service_time=P_{s_{kc}.service_time-1$. `Output relation:`

$P_{s_{jc}}$ will be scheduled earlier than$P_{s_{kc}}$ in $O_f$, while it is opposite in $O_s$. `Source input:`

$I_s$ ;
`Source output:`

$O_s$ `Follow-up input:`

$I_f$ ;
`Follow-up output:`

$O_f$ `Input relation:`

$I_f$ is constructed based on $I_s$ but with the following changes: randomly choose any two process $P'_{s_j}$ and $P'_{s_{j+1}} (1 \le j \le n)$ from $O_s$ find their corresponding process $P_{s_{jc}}$ and $P_{s_{(j+1)c}}$ in $I_s$ apply following operations: If $P_{s_{jc}}.arrival-time < P_{s_{(j+1)c}}.arrival -time$, Then (if $P_{s_{jc}}.service-time \ge P_{s_{(j+1)c}}.service-time$) then swap the arrival time of $P_{s_{jc}}$ and $P_{s_{(j+1)c}}$, else set $P_{s_{(j+1)c}}.arrival -time=P_{s_{jc}}.arrival-time-1$ $P_{s_{(j+1)c}}.service-time=P_{s_{jc}}.service-time-1$ else swap the service time of $P_{s_{jc}}$ and $P_{s_{(j+1)c}}$. `Output relation:`

The order between$P_{s_{jc}}$ and $P_{s_{(j+1)c}}$ in $O_f$ is opposite to .that of $O_s$. `Source input:`

$I_s$ ;
`Source output:`

$O_s$ `Follow-up input:`

$I_f$ ;
`Follow-up output:`

$O_f$ `Input relation:`

$I_f$ is constructed by adding a new process P which arrives at the same time as a selected process $P_{s_i} (1 \le i \le n)$ while its service time is longer than $P_{s_i}$ or adding a process P whose service time is the same as the selected process $P_{s_i} (1 \le i \le n)$ while it arrives later than $P_{s_i} $. `Output relation:`

P will be scheduled later than $P_{s_i} $. `Source input:`

$I_s$ ;
`Source output:`

$O_s$ `Follow-up input:`

$I_f$ ;
`Follow-up output:`

$O_f$ `Input relation:`

$I_f$ = Deleting one process from $I_s$ `Output relation:`

The execution sequences before the deleted process of $O_s$ will remain the same as those in $O_f$.