TY - JOUR
AU - Vadim Romanuke
PY - 2021/08/01
Y2 - 2022/05/21
TI - Infinity Substitute in Finding Exact Minimum of Total Weighted Tardiness in Tight-Tardy Progressive 1-machine Scheduling by Idling-free Preemptions
JF - Statistics, Optimization & Information Computing
JA - Stat., optim. inf. comput.
VL - 9
IS - 4
SE - Research Articles
DO - 10.19139/soic-2310-5070-1256
UR - http://iapress.org/index.php/soic/article/view/1256
AB - 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.
ER -