Infinity Substitute in Finding Exact Minimum of Total Weighted Tardiness in Tight-Tardy Progressive 1-machine Scheduling by Idling-free Preemptions

  • Vadim Romanuke Polish Naval Academy
Keywords: Job scheduling, Preemptive 1-machine scheduling, Total weighted tardiness, Exact model, Infinity substitute, Computation time


A job schedule ensuring the exact minimum of total weighted tardiness can be found with the respective integer linear programming problem model, in which the infinity showing that the respective states are either forbidden or impossible is substituted with a sufficiently great positive integer. An open question is whether the substitute can be selected so that the computation time would be decreased. Thus, it is ascertained that, whichever job lengths and its priority weights are, substituting the infinity with just “a sufficiently great positive integer” is never recommended. To decrease the computation time on average, it is strongly recommended to select the infinity substitute as multiple maximum over finite decision variable weights in the exact model. It is sufficient to take 2 to 5 such maxima as the infinity substitute. However, the shortened computation time is not guaranteed for solving a single or few scheduling problems. It is only an expected benefit, which builds up as a few hundred scheduling problems are solved at least.


M. Batsyn, B. Goldengorin, P. Pardalos, and P. Sukhov, Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time, Optimization Methods & Software, vol. 29, iss. 5, pp. 955–963, 2014.

J. O. Berger, Statistical Decision Theory and Bayesian Analysis, Springer, New York, NY, 1985.

P. Brucker, Scheduling Algorithms, Springer-Verlag Berlin Heidelberg, 2007.

R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, no. 5, pp. 287–326, 1979.

F. Jaramillo, B. Keles, and M. Erkoc, Modeling single machine preemptive scheduling problems for computational efficiency, Annals of Operations Research, no. 285, pp. 197–222, 2020.

M. L. Pinedo, Planning and Scheduling in Manufacturing and Services, Springer-Verlag New York, 2009.

M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer Inter. Publishing, 2016.

V. V. Romanuke, Decision making criteria hybridization for finding optimal decisions’ subset regarding changes of the decision function, Journal of Uncertain Systems, vol. 12, no. 4, pp. 279–291, 2018.

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.

V. V. Romanuke, Infinity substitute in exactly minimizing total tardiness in tight-tardy progressive 1-machine scheduling by idlingfree preemptions of equal-length jobs, Bulletin of V. Karazin Kharkiv National University. Mathematical Modelling. Information Technology. Automated Control Systems, iss. 44, pp. 94–101, 2019.

V. V. Romanuke, Minimal total weighted tardiness in tight-tardy single machine preemptive idling-free scheduling, Applied Computer Systems, vol. 24, no. 2, pp. 150–160, 2019.

V. V. Romanuke, Efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions of equal-length jobs, KPI Science News, no. 1, pp. 27–39, 2020.

A. S. Uyar, E. Ozcan, and N. Urquhart, Automated Scheduling and Planning: From Theory to Practice, Springer-Verlag Berlin Heidelberg, 2013.

How to Cite
Vadim Romanuke. (2021). Infinity Substitute in Finding Exact Minimum of Total Weighted Tardiness in Tight-Tardy Progressive 1-machine Scheduling by Idling-free Preemptions. Statistics, Optimization & Information Computing, 9(4), 820-837.
Research Articles