Infinity substitute in exactly minimizing total tardiness in tight-tardy progressive 1-machine scheduling by idling-free preemptions of equal-length jobs

Abstract

A schedule ensuring the exactly minimal total tardiness can be found by the respective integer linear programming problem with infinities. In real computations, the infinity which shows 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. The goal is to ascertain how the increment of the infinity substitute in the respective model influences the computation time of exact schedules. If the influence appears to be significant, then a recommendation on selecting the infinity substitute is to be stated in order to decrease the computation time. A pattern of generating instances of the job scheduling problem is provided. The instances of the job scheduling problem are generated so that schedules which can be obtained trivially, without the exact model, are excluded. Nine versions of the infinity substitute have been proposed. The increment of the infinity substitute in the model of total tardiness exact minimization rendered to solving an integer linear programming problem involving the branch-and-bound approach may have bad influence on the computation time of exact schedules. At least, the greater value of the infinity substitute cannot produce an optimal schedule faster in tight-tardy progressive 1-machine scheduling by idling-free preemptions of equal-length jobs. Roughly the best value of the infinity substitute is the maximal value taken over all the finite triple-indexed weights in the model and increased then by 1. The influence of the “max” infinity substitution is extremely significant. Compared to the case when the infinity is substituted with a sufficiently great integer, the “max” infinity substitution saves up to 50 % of the computation time. This saves hours and even days or months when up to 8 jobs of a few equal processing periods are scheduled for a few thousands of cycles or longer. Therefore, it is strongly recommended always to select the infinity substitute as less as possible in order to decrease the computation time.