Open AccessInfinity substitute in exactly minimizing total tardiness in tight-tardy progressive 1-machine scheduling by idling-free preemptions of equal-length jobs
Author(s) -
Vadim Romanuke,
Oleksandr Popov
Publication year - 2019
Publication title -
vìsnik harkìvsʹkogo nacìonalʹnogo unìversitetu ìmenì v.n. karazìna. serìâ matematične modelûvannâ, ìnformacìjnì tehnologìï, avtomatizovanì sistemi upravlìnnâ
Language(s) - English
Resource type - Journals
eISSN - 2524-2601
pISSN - 2304-6201
DOI - 10.26565/2304-6201-2019-44-10
Subject(s) - tardiness , infinity , computation , scheduling (production processes) , integer programming , mathematics , mathematical optimization , job shop scheduling , schedule , upper and lower bounds , linear programming , integer (computer science) , computer science , algorithm , mathematical analysis , programming language , operating system
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.