A Heuristic’s Job Order Gain in Pyramidal Preemptive Job Scheduling Problems for Total Weighted Completion Time Minimization
Abstract
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
|
Full Text: |
References
M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer International Publishing, 2016. https://doi.org/10.1007/978-3-319-26580-3
P. Brucker, Scheduling Algorithms. Springer-Verlag Berlin Heidelberg, 2007. https://doi.org/10.1007/978-3-540-69516-5
M. L. Pinedo, Planning and Scheduling in Manufacturing and Services. Springer-Verlag New York, 2009. https://doi.org/10.1007/978-1-4419-0910-7
V. V. Romanuke, “The exact minimization of total weighted completion time in the preemptive scheduling problem by subsequent length-equal job importance growth,” Bulletin of V. Karazin Kharkiv National University. Mathematical Modelling. Information Technology. Automated Control Systems, iss. 40, pp. 60–66, 2018.
V. V. Romanuke, “A faster way to approximately schedule equally divided jobs with preemptions on a single machine by subsequent job importance growth,” Bulletin of V. Karazin Kharkiv National University. Mathematical Modelling. Information Technology. Automated Control Systems, iss. 41, pp. 80–87, 2019.
W.-Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational analysis,” Computers & Operations Research, vol. 73, pp. 165–173, 2016. https://doi.org/10.1016/j.cor.2016.04.006
V. V. Romanuke, “Accuracy of a heuristic for total weighted completion time minimization in preemptive single machine scheduling problem by no idle time intervals,” KPI Science News, no. 3, pp. 52–62, 2019. https://doi.org/10.20535/kpi-sn.2019.3.164804
H. Belouadah, M. E. Posner, and C. N. Potts, “Scheduling with release dates on a single machine to minimize total weighted completion time,” Discrete Applied Mathematics, vol. 36, no. 3, pp. 213–231, 1992. https://doi.org/10.1016/0166-218X(92)90255-9
S. Ul Sabha, “A novel and efficient round robin algorithm with intelligent time slice and shortest remaining time first,” Materials Today: Proceedings, vol. 5, no. 5, part 2, pp. 12009–12015, 2018. https://doi.org/10.1016/j.matpr.2018.02.175
H. Wei and J. Yuan, “Two-machine flow-shop scheduling with equal processing time on the second machine for minimizing total weighted completion time,” Operations Research Letters, vol. 47, no. 1, pp. 41–46, 2019. https://doi.org/10.1016/j.orl.2018.12.002
B. Wang, Y. Song, J. Cao, X. Cui, and L. Zhang, “Improving task scheduling with parallelism awareness in heterogeneous computational environments,” Future Generation Computer Systems, vol. 94, pp. 419–429, 2019. https://doi.org/10.1016/j.future.2018.11.012
M. Nattaf, S. Dauzère-Pérès, C. Yugma, and C.-H. Wu, “Parallel machine scheduling with time constraints on machine qualifications,” Computers & Operations Research, vol. 107, pp. 61–76, 2019. https://doi.org/10.1016/j.cor.2019.03.004
DOI: 10.7250/itms-2019-0001
Refbacks
- There are currently no refbacks.
Copyright (c) 2019 Vadim Romanuke
This work is licensed under a Creative Commons Attribution 4.0 International License.