Skip to content
KPI Science News
ISSN 2617-5509 · e‑ISSN 2663-7472 Open Access · CC BY 4.0
Vol. · Issue 1 · 2021 May 28, 2021 article

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

VR
Vadim V. Romanuke Corresponding Polish Naval Academy, Poland Ukraine
PublishedMay 28, 2021
PDF (Ukrainian)
KPISN 1 VOL · 1
VOL · ISS 1 · 2021 View issue

Abstract

Background. In preemptive job scheduling, which is a part of the flow-shop sequencing tasks, one of the most crucial goals is to obtain a schedule whose total tardiness would be minimal. Total 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 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 tardiness is 25 % greater than the minimum or even worse. Therefore, this heuristic needs a corrective branch which would further try to minimize total tardiness under certain conditions. Objective. The goal is to ascertain what is to be corrected in the heuristic so that the total tardiness value could be obtained lesser. 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. In this scheduling problem, the inaccuracy of finding the minimal total tardiness has the strongest negative impact, so this is almost the worst case, which defines the accuracy limit of the heuristic and positively serves just as the principle of minimax guaranteeing decreasing losses in the worst conditions. Methods. The heuristic sorts maximal decisive ratios by release dates, where the scheduling preference is given to the earliest job. To achieve the said goal, three other sorting approaches are presented and a computational study is carried out with applying each of the four heuristic approaches to minimize total tardiness. For this, two series of 266000 and 1064000 scheduling problems are generated. Results. The earliest-job sorting ensures a heuristically minimal total tardiness value in more than 97.6 % of scheduling problems, but it fails to minimize total tardiness in no less than 2.2 % of the cases. Nevertheless, a sorting approach with minimizing remaining processing periods produces a heuristically minimal total tardiness for almost any scheduling problem. If an exception occurs, this sorting approach “loses” to the other sorting approaches very little. Moreover, the exceptions are quite rare as it has been registered just a one scheduling problem (out of 31914 cases followed by a sole “win” of a heuristic version) whose minimal total tardiness is achieved by the earliest-job sorting. Conclusions. The best heuristic version is that one which uses the sorting approach with minimizing remaining processing periods. This, however, is confirmed only for the case where jobs do not have any priorities. The case when jobs have their priority weights is to be yet analyzed.

Keywords

#preemptive 1-machine job scheduling #total tardiness #heuristic #sorting approach #remaining processing periods #remaining available periods

References

  1. 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
  2. M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer International Publishing, 2016, 670 p. doi: 10.1007/978-3-319-26580-3
  3. 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
  4. 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
  5. 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
  6. 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
  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
  8. 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
  9. 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 V.N. Karazin Kharkiv National University, ser. MIA, vol. 44, pp. 94–101, 2019. doi: 10.26565/2304-6201-2019-44-10
  10. V.V. Romanuke, “Job order input for efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions,” in Proc. Sci. Papers O. S. Popov Odesa National Academy of Telecommunications (ОNAT), Odesa, Ukraine, 2020, vol. 1, no. 1, pp. 19–36. doi: 10.33243/2518-7139-2020-1-1-19-36
  11. 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
  12. 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
  13. R.L. Graham et al., “Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey,” in Annals of Discrete Mathematics, vol. 5, P.L. Hammer et al., Eds. B.C., Canada: North-Holland,1979, pp. 287–326. doi: 10.1016/S0167-5060(08)70356-X
  14. 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
  15. W.-Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational analysis,” Comput. & Operat. Res, vol. 73, pp. 165–173, 2016. doi: 10.1016/j.cor.2016.04.006
  16. 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
  17. R. Kneusel, Random Numbers and Computers. Springer International Publishing, 2018, 260 p. doi: 10.1007/978-3-319-77697-2
§ 06 — Related

Similar articles in this journal

Related peer-reviewed studies published in this journal.
View all issues

MODIFICATION OF THE SEPARABLE PHYSICS-INFORMED NEURAL NETWORK METHOD FOR THE APPROXIMATE SOLUTION OF A MIXED PROBLEM FOR THE HEAT CONDUCTION EQUATION IN AN ELLIPTICAL DOMAIN

Valerii Los, Oleksandr Riakhin

Background. Parabolic differential equations are mathematical models in engineering designed to study wide range of applied models. This necessitates the development of…

#heat conduction equation #mixed parabolic problem #elliptical domain #physics-informed neural network
10.20535/kpisn.2026.3.367316

Most read articles by the same author(s)

Similar Articles

1-10 of 199

You may also start an advanced similarity search for this article.