Minimal Total Weighted Tardiness in Tight-Tardy Single Machine Preemptive Idling-Free Scheduling

2019
Vadim Romanuke

Two possibilities of obtaining the minimal total weighted tardiness in tight-tardy single machine preemptive idling-free scheduling are studied. The Boolean linear programming model, which allows obtaining the exactly minimal tardiness, becomes too time-consuming as either the number of jobs or numbers of job parts increase. Therefore, a heuristic based on remaining available and processing periods is used instead. The heuristic schedules 2 jobs always with the minimal tardiness. In scheduling 3 to 7 jobs, the risk of missing the minimal tardiness is just 1.5 % to 3.2 %. It is expected that scheduling 12 and more jobs has at the most the same risk or even lower. In scheduling 10 jobs without a timeout, the heuristic is almost 1 million times faster than the exact model. The exact model is still applicable for scheduling 3 to 5 jobs, where the averaged computation time varies from 0.1 s to 1.02 s. However, the maximal computation time for 6 jobs is close to 1 minute. Further increment of jobs may delay obtaining the minimal tardiness at least for a few minutes, but 7 jobs still can be scheduled at worst for 7 minutes. When scheduling 8 jobs and more, the exact model should be substituted with the heuristic.

Keywords
Boolean linear programming model, heuristic, job scheduling, job preemptions, relative gap, remaining available period, remaining processing period, single machine scheduling, total weighted tardiness.
DOI
10.2478/acss-2019-0019
Hyperlink
https://doi.org/10.2478/acss-2019-0019

Romanuke, V. Minimal Total Weighted Tardiness in Tight-Tardy Single Machine Preemptive Idling-Free Scheduling. Applied Computer Systems, 2019, Vol. 24, No. 2, pp. 150-160. ISSN 2255-8683. e-ISSN 2255-8691. Available from: doi:10.2478/acss-2019-0019

Publication language
English (en)