A Heuristic’s Job Order Gain in Pyramidal Preemptive Job Scheduling Problems for Total Weighted Completion Time Minimization

2019
Vadim Romanuke

A possibility of speeding up the job scheduling by a heuristic based on the shortest processing period approach is studied in the paper. The scheduling problem is such that the job volume and job priority weight are increasing as the job release date increases. Job preemptions are allowed. Within this model, the input for the heuristic is formed by either ascending or descending job order. Therefore, an estimator of relative difference in duration of finding an approximate schedule by these job orders is designed. It is ascertained that the job order results in different time of computations when scheduling at least a few hundred jobs. The ascending-order solving becomes on average by 1 % to 2.5 % faster when job volumes increase steeply. As the steepness of job volumes decreases, this gain vanishes and, eventually, the descending-order solving becomes on average faster by up to 4 %. The gain trends of both job orders slowly increase as the number of jobs increases.

Keywords
Heuristic; job order; job parts; job scheduling; preemption; total weighted completion time minimization
DOI
10.7250/itms-2019-0001
Hyperlink
https://doi.org/10.7250/itms-2019-0001

Romanuke, V. A Heuristic’s Job Order Gain in Pyramidal Preemptive Job Scheduling Problems for Total Weighted Completion Time Minimization. Information Technology and Management Science, 2019, Vol. 22, pp. 1-8. ISSN 2255-9086. e-ISSN 2255-9094. Available from: doi:10.7250/itms-2019-0001

Publication language
English (en)