The minimization of exact total weighted completion time in the preemptive scheduling problem by subsequent length-equal job importance growth
Abstract
For the preemptive scheduling problem in case of subsequent job importance growth, it is studied whether the optimal schedule might be found faster within an exact model. It is ascertained that when the number of jobs up to six (except for the case of four jobs) and there is no randomness in problem forming, a little advantage of weight-descending job order exists only on average. As the number of jobs increases, the advantage of either weight-descending or weight-ascending job order becomes more certain. When priority weights are formed randomly, weight-descending job order is expected to be faster than weight-ascending.
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.
L. P. Fávero and P. Belfiore, “Integer Programming”, in: Data Science for Business and Decision Making, Fávero L. P., Belfiore P. (eds.). Academic Press, pp. 887 – 918, 2019.
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.
Fávero L. P., Belfiore P. Integer Programming, in: Data Science for Business and Decision Making / Fávero L. P., Belfiore P. (eds.). Academic Press. 2019. P. 887 – 918.
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.
