Open AccessInfinity Substitute in Finding Exact Minimum of Total Weighted Tardiness in Tight-Tardy Progressive 1-machine Scheduling by Idling-free Preemptions
Author(s) -
Vadim Romanuke
Publication year - 2021
Publication title -
statistics, optimization and information computing
Language(s) - English
Resource type - Journals
eISSN - 2311-004X
pISSN - 2310-5070
DOI - 10.19139/soic-2310-5070-1256
Subject(s) - tardiness , computation , scheduling (production processes) , infinity , integer programming , mathematical optimization , mathematics , integer (computer science) , job shop scheduling , schedule , linear programming , computer science , algorithm , mathematical analysis , programming language , operating system
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.