ACCURATE TOTAL WEIGHTED TARDINESS MINIMIZATION IN TIGHT-TARDY PROGRESSIVE SINGLE MACHINE SCHEDULING WITH PREEMPTIONS BY NO IDLE PERIODS

Background. The problem of minimization of total weighted tardiness can be solved either exactly by the corresponding models or heuristically. As of October 2019, nearly the best heuristic is one based on using remaining available and processing periods. The heuristic is extremely rapid compared to the exact solution models, but its accuracy can be both 100 % and intolerably low. Objective. Issuing from the lack of knowledge in relationship between the heuristic and Boolean linear programming model provided for exact solutions, the goal is to study statistical difference between them for the preemptive single machine scheduling problem by no idle periods, in which processing periods are equal by progressively running release and due dates set tightly. Methods. The relative gap of the heuristic is defined and then studied how it varies against increasing complexity of job scheduling problems. The complexity implies the number of jobs and the number of job processing periods. The computation times of the heuristic and the exact model are registered as well. Results. The heuristic has successfully replaced the exact model no less than in 72 % of non-timeout instances, where it schedules with the same minimal total weighted tardiness (100 % accuracy). This rate is about 90 % to 97 % on average, although huge gaps may appear in the rest of cases. In the practice of fast-refreshable schedules, the Boolean linear programming model is indeed hardly tractable in scheduling no less than 14 two-parted jobs and no less than 10 three-parted jobs. Scheduling jobs divided into a greater number of parts each will have a significantly lower worst gap than scheduling jobs divided into a lesser number of parts. If a job is divisible, it is strongly recommended to divide the job into as great number of its parts as possible. If scheduling only 2 jobs is impossible, it is strongly recommended to artificially increase the number of jobs to be scheduled. Conclusions. Total weighted tardiness minimization in tight-tardy progressive single machine scheduling with preemp­tions by no idle periods can be sufficiently accurate by the heuristic if no less than 7 jobs divided into no less than five parts each are scheduled (the “7/5” pattern). An exception from this rule is that the heuristic schedules just 2 jobs always at the 100 % accuracy, not depending on in how many parts the job is divided (the “2/any” exception). An intermediate between the “7/5” pattern and the “2/any” exception is that scheduling 3 jobs divided into either four or five parts is sufficiently accurate as well, where the inaccuracy does not exceed 0.7 %. In other cases the heuristic is either inapplicable or there is a high risk of obtaining intolerable gaps. The inapplicability does not directly imply a bad inaccuracy, but it implies an unpredictable accuracy drop. For example, 974 of 1000 instances of 3 two-parted jobs have been scheduled with the 100 % accuracy, but 26 instances have been scheduled with an average gap in 13.31 %, which is quite intolerable and thus inapplicable.