<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>A problem of minimizing the total weighted tardiness in the preemptive single machine scheduling for discrete manufacturing is considered. A hyper-heuristic is presented, which is composed of 24 various heuristics, to find an approximately optimal schedule whenever finding the exact solution is practically intractable. The three heuristics are based on the well-known rules, whereas the 21 heuristics are introduced first. Therefore, the hyper-heuristic selects the best heuristic schedule among 24 schedule versions, whose total weighted tardiness is minimal. Each of the 24 heuristics can solely produce a schedule which is the best one for a given scheduling problem. Despite the percentage of zero gap instances decreases as the greater number of jobs is scheduled, the average and maximal gaps decrease as well. In particular, the percentage is not less than 80 % when up to 10 jobs are scheduled. The average gap calculated over nonzero gaps does not exceed 4 % in the case of scheduling 7 jobs. When manufacturing consists of hundreds of jobs, the hyper-heuristic is made an online scheduling algorithm by applying it only to a starting part of the manufacturing process.</p>
</abstract>

A problem of minimizing the total weighted tardiness in the preemptive single machine scheduling for discrete manufacturing is considered. A hyper-heuristic is presented, which is composed of 24 various heuristics, to find an approximately optimal schedule whenever finding the exact solution is practically intractable. The three heuristics are based on the well-known rules, whereas the 21 heuristics are introduced first. Therefore, the hyper-heuristic selects the best heuristic schedule among 24 schedule versions, whose total weighted tardiness is minimal. Each of the 24 heuristics can solely produce a schedule which is the best one for a given scheduling problem. Despite the percentage of zero gap instances decreases as the greater number of jobs is scheduled, the average and maximal gaps decrease as well. In particular, the percentage is not less than 80 % when up to 10 jobs are scheduled. The average gap calculated over nonzero gaps does not exceed 4 % in the case of scheduling 7 jobs. When manufacturing consists of hundreds of jobs, the hyper-heuristic is made an online scheduling algorithm by applying it only to a starting part of the manufacturing process.

A Hyper-Heuristic for the Preemptive Single Machine Scheduling Problem to Minimize the Total Weighted Tardiness

Applied Computer Systems

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

A problem of minimizing the total weighted tardiness in the preemptive single machine scheduling for discrete manufacturing is considered. A hyper-heuristic is...

A Hyper-Heuristic for the Preemptive Single Machine Scheduling Problem to Minimize the Total Weighted Tardiness

Published Online: Aug 23, 2022

Page range: 1 - 12

DOI: https://doi.org/10.2478/acss-2022-0001

Keywords
Gap, heuristics, hyper-heuristic, job scheduling, total weighted tardiness

© 2022 Vadim Romanuke, published by Sciendo

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

A Hyper-Heuristic for the Preemptive Single Machine Scheduling Problem to Minimize the Total Weighted Tardiness

Published Online: Aug 23, 2022

Page range: 1 - 12

DOI: https://doi.org/10.2478/acss-2022-0001

KeywordsGap, heuristics, hyper-heuristic, job scheduling, total weighted tardiness

© 2022 Vadim Romanuke, published by Sciendo

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

Keywords
Gap, heuristics, hyper-heuristic, job scheduling, total weighted tardiness