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
DOI: https://doi.org/10.19139/soic-2310-5070-1256
Keywords: Job scheduling, Preemptive 1-machine scheduling, Total weighted tardiness, Exact model, Infinity substitute, Computation time

Abstract

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.

References

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.

Published
2021-08-01
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. https://doi.org/10.19139/soic-2310-5070-1256
Issue
Vol 9 No 4 (2021)
Section
Research Articles
Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).