<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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.</p></abstract>

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.

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

Applied Computer Systems

This work is licensed under the Creative Commons Attribution 4.0 Public License.

Two possibilities of obtaining the minimal total weighted tardiness in tight-tardy single machine preemptive idling-free scheduling are studied. The Boolean...

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

Publié en ligne: 20 févr. 2020

Pages: 150 - 160

DOI: https://doi.org/10.2478/acss-2019-0019

Mots clés
Boolean linear programming model, heuristic, job scheduling, job preemptions, relative gap, remaining available period, remaining processing period, single machine scheduling, total weighted tardiness

© 2019 Vadim Romanuke, published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 Public License.

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

Publié en ligne: 20 févr. 2020

Pages: 150 - 160

DOI: https://doi.org/10.2478/acss-2019-0019

Mots clésBoolean linear programming model, heuristic, job scheduling, job preemptions, relative gap, remaining available period, remaining processing period, single machine scheduling, total weighted tardiness

© 2019 Vadim Romanuke, published by Sciendo

This work is licensed under the Creative Commons Attribution 4.0 Public License.

Mots clés
Boolean linear programming model, heuristic, job scheduling, job preemptions, relative gap, remaining available period, remaining processing period, single machine scheduling, total weighted tardiness