A faster way to approximately schedule equally divided jobs with preemptions on a single machine by subsequent job importance growth
Abstract
The goal of this work is to study whether the input order of the job release dates results in different time of computations in finding an approximate schedule for equally divided jobs with preemptions on a single machine by subsequent job importance growth,. It has been ascertained that the descending job order has a 1 % relative advantage when scheduling more than 200 jobs. With increasing the number of jobs off 1000, the advantage tends to increase. The advantage can grow up to 22%. A maximally possible gain in computation time is obtained in scheduling longer series of bigger-sized job scheduling problems.
Downloads
References
/References
M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer Int. Publ., 2016.
P. Brucker, Scheduling Algorithms. Springer-Verlag Berlin Heidelberg, 2007.
H. Belouadah et al., “Scheduling with release dates on a single machine to minimize total weighted completion time”, Discrete Applied Mathematics, vol. 36, iss. 3, pp. 213 — 231, 1992.
M. L. Pinedo, Planning and Scheduling in Manufacturing and Services. Springer, 2009.
I. A. Mandzyuk and V. V. Romanuke, “Rheometric research of polypropylene Licocene PP2602 melts”, Archives of Materials Science and Engineering, vol. 50, iss. 1, pp. 31 — 35, 2011.
V. V. Romanuke, “Appropriate number and allocation of ReLUs in convolutional neural networks”, Research Bulletin of NTUU “Kyiv Polytechnic Institute”, no. 1, pp. 69 — 78, 2017.
V. V. Romanuke, “Acyclic-and-asymmetric payoff triplet refinement of pure strategy efficient Nash equilibria in trimatrix games by maximinimin and superoptimality”, KPI Science News, no. 4, pp. 38 — 53, 2018.
Pinedo M. L. Scheduling: Theory, Algorithms, and Systems. — Springer Int. Publ., 2016. — 670 p.
Brucker P. Scheduling Algorithms. — Springer-Verlag Berlin Heidelberg, 2007. — 371 p.
Belouadah H., Posner M. E., Potts C. N. Scheduling with release dates on a single machine to minimize total weighted completion time // Discrete Applied Mathematics. — 1992. — Vol. 36, Iss. 3. — P. 213 — 231.
Pinedo M. L. Planning and Scheduling in Manufacturing and Services. — Springer, 2009. — 536 p.
Mandzyuk I. A., Romanuke V. V. Rheometric research of polypropylene Licocene PP2602 melts // Archives of Materials Science and Engineering. — 2011. — Vol. 50, Iss. 1. — P. 31 — 35.
Romanuke V. V. Appropriate number and allocation of ReLUs in convolutional neural networks // Research Bulletin of NTUU “Kyiv Polytechnic Institute”. — 2017. — No. 1. — P. 69 — 78.
Romanuke V. V. Acyclic-and-asymmetric payoff triplet refinement of pure strategy efficient Nash equilibria in trimatrix games by maximinimin and superoptimality // KPI Science News. — 2018. — No. 4. — P. 38 — 53.
