SORTING APPROACHES IN THE HEURISTIC BASED ON REMAINING AVAILABLE AND PROCESSING PERIODS TO MINIMIZE TOTAL WEIGHTED TARDINESS IN PROGRESSIVE IDLING-FREE 1-MACHINE PREEMPTIVE SCHEDULING
DOI:
https://doi.org/10.20535/kpisn.2021.2.227037Keywords:
preemptive 1-machine job scheduling, total weighted tardiness, heuristic, sorting approach, remaining processing periods, remaining available periodsAbstract
Background. In preemptive job scheduling, total weighted tardiness minimization is commonly reduced to solving a combinatorial problem, which becomes practically intractable as the number of jobs and the numbers of their processing periods increase. To cope with this challenge, heuristics are used. A heuristic, in which the decisive ratio is the weighted reciprocal of the maximum of a pair of the remaining processing period and remaining available period, is closely the best one. However, the heuristic may produce schedules of a few jobs whose total weighted tardiness is enormously huge compared to the real minimum. Therefore, this heuristic needs further improvements, one of which already exists for jobs without priority weights with a sorting approach where remaining processing periods are minimized. Three other sorting approaches still can outperform it, but such exceptions are quite rare.
Objective. The goal is to determine the influence of the four sorting approaches and try to select the best one in the case where jobs have their priority weights. The heuristic will be applied to tight-tardy progressive idling-free 1-machine preemptive scheduling, where the release dates are given in ascending order starting from 1 to the number of jobs, and the due dates are tightly set after the release dates.
Methods. To achieve the said goal, a computational study is carried out with applying each of the four heuristic approaches to minimize total weighted tardiness. For this, two series of 4151500 scheduling problems are generated. In the solution of a scheduling problem, a sorting approach can “win” solely or “win” in a group of approaches, producing the heuristically minimal total weighted tardiness. In each series, the distributions of sole-and-group “wins” are ascertained.
Results. The sole “wins” and non-whole-group “wins” are rare: the four sorting approaches produce schedules with the same total weighted tardiness in over 98.39 % of scheduling problems. Although the influence of these approaches is different, it is therefore not really significant. Each of the sorting approaches has heavy disadvantages leading sometimes to gigantic inaccuracies, although they occur rarely. When the inaccuracy occurs to be more than 30 %, this implies that 3 to 9 jobs are scheduled.
Conclusions. Unlike the case when jobs do not have their priority weights, it is impossible to select the best sorting approach for the case with job priority weights. Instead, a hyper-heuristic comprising the sorting approaches (i. e., the whole group, where each sorting is applied) may be constructed. If a parallelization can be used to process two or even four sorting routines simultaneously, the computation time will not be significantly affected.
References
M.L. Pinedo, Planning and Scheduling in Manufacturing and Services. New York: Springer-Verlag, 2009, 536 p. doi: 10.1007/978-1-4419-0910-7
V.V. Romanuke, “Accuracy of a heuristic for total weighted completion time minimization in preemptive single machine scheduling problem by no idle time intervals,” KPI Sci. News, no. 3, pp. 52–62, 2019. doi: 10.20535/kpi-sn.2019.3.164804
V.V. Romanuke, “Minimal total weighted tardiness in tight-tardy single machine preemptive idling-free scheduling,” Appl. Comput. Syst., vol. 24, no. 2, pp. 150–160, 2019. doi: 10.2478/acss-2019-0019
M. Batsyn et al., “Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time,” Optimiz. Method. Softw., vol. 29, no. 5, pp. 955–963, 2014. doi: 10.1080/10556788.2013.854360
V.V. Romanuke, “Infinity substitute in exactly minimizing total tardiness in tight-tardy progressive 1-machine scheduling by idling-free preemptions of equal-length jobs,” Bulletin of V. Karazin Kharkiv National Univ. Math. Modell. Inf. Technol. Autom. Control Syst., no. 44, pp. 94–101, 2019. doi: 10.26565/2304-6201-2019-44-10
V.V. Romanuke, “Efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions of equal-length jobs,” KPI Sci. News, no. 1, pp. 27–39, 2020. doi: 10.20535/kpi-sn.2020.1.180877
V.V. Romanuke, “Job order input for efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions,” Proc. O.S. Popov ОNAT, vol. 1, no. 1, pp. 19–36, 2020. doi: 10.33243/2518-7139-2020-1-1-19-36
V.V. Romanuke, “Tight-tardy progressive idling-free 1-machine preemptive scheduling by heuristic’s efficient job order input,” KPI Sci. News, no. 3, pp. 32–42, 2020. doi: 10.20535/kpi-sn.2020.3.199850
K.-C. Ying et al., “Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic,” Exp. Syst. Applicat., vol. 36, no. 3, pp. 7087–7092, 2009. doi: 10.1016/j.eswa.2008.08.033
Y.H. Lee et al., “A heuristic to minimize the total weighted tardiness with sequence-dependent setups”, IIE Trans., vol. 29, no. 1, pp. 45–52, 1997. doi: 10.1080/07408179708966311
F. Jaramillo and M. Erkoc, “Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling,” Comput. & Ind. Eng., vol. 107, pp. 109–119, 2017. doi: 10.1016/j.cie.2017.03.012
M. Tamannaei and M. Rasti-Barzoki, “Mathematical programming and solution approaches for minimizing tardiness and transportation costs in the supply chain scheduling problem,” Comput. & Ind. Eng., vol. 127, pp. 643–656, 2019. doi: 10.1016/j.cie.2018.11.003
V.V. Romanuke, “A sorting improvement in the heuristic based on remaining available and processing periods to minimize total tardiness in progressive idling-free 1-machine preemptive scheduling,” KPI Sci. News, no. 1, pp. 7–16, 2021.
M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer International Publishing, 2016, 670 p. doi: 10.1007/978-3-319-26580-3
R.L. Graham et al., “Optimization and approximation in deterministic sequencing and scheduling: A survey,” in Annals of Discrete Mathematics, vol. 5, 1979, pp. 287–326. doi: 10.1016/S0167-5060(08)70356-X
R. Panneerselvam, “Simple heuristic to minimize total tardiness in a single machine scheduling problem,” Int. J. Advanc. Manuf. Technol., vol. 30, no. 7-8, pp. 722–726, 2006. doi: 10.1007/s00170-005-0102-1
Z. Tian et al., “An algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness,” J. Schedul., vol. 9, no. 4, pp. 343–364, 2006. doi: 10.1007/s10951-006-7039-6
V.V. Romanuke, “Heuristic’s job order efficiency in tight-tardy progressive idling-free 1-machine preemptive scheduling of equal-length jobs,” KPI Sci. News, no. 2, pp. 64–73, 2020. doi: 10.20535/kpi-sn.2020.2.181869
R.T. Kneusel, Random Numbers and Computers, Springer International Publishing, 2018, 260 p. doi: 10.1007/978-3-319-77697-2
J.M.A. Trejo and C.S. Calude, “A new quantum random number generator certified by value indefiniteness,” Theoretical Comput. Sci., vol. 862, pp. 3–13, 2021. doi: 10.1016/j.tcs.2020.08.014
W.-Y. Ku and J.C. Beck, “Mixed integer programming models for job shop scheduling: A computational analysis,” Comput. & Operations Res., vol. 73, pp. 165–173, 2016. doi: 10.1016/j.cor.2016.04.006
D. Kress et al., “An exact solution approach for scheduling cooperative gantry cranes,” European J. Operational Res., vol. 273, no. 1, pp. 82–101, 2019. doi: 10.1016/j.ejor.2018.07.043
H. Chen et al., “A hyper-heuristic based ensemble genetic programming approach for stochastic resource constrained project scheduling problem,” Exp. Syst. Applicat., vol. 167, p. 114174, 2021. doi: 10.1016/j.eswa.2020.114174
H.-B. Song and J. Lin, “A genetic programming hyper-heuristic for the distributed assembly permutation flow-shop scheduling problem with sequence dependent setup times,” Swarm Evol. Comput., vol. 60, p. 100807, 2021. doi: 10.1016/j.swevo.2020.100807
Downloads
Published
Issue
Section
License
Copyright (c) 2021 Vadym V. Romanuke
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under CC BY 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work
