EFFICIENT EXACT MINIMIZATION OF TOTAL TARDINESS IN TIGHT-TARDY PROGRESSIVE SINGLE MACHINE SCHEDULING WITH IDLING-FREE PREEMPTIONS OF EQUAL-LENGTH JOBS
DOI:
https://doi.org/10.20535/kpi-sn.2020.1.180877Keywords:
Job scheduling, Preemptive single machine scheduling, Exact model, Total tardiness, Computation time, Ascending job order, Descending job orderAbstract
Background. A schedule ensuring the exactly minimal total tardiness can be found with the respective integer linear programming problem. An open question is whether the exact schedule computation time changes if the job release dates are input to the model in reverse order.
Objective. The goal is to ascertain whether the job order in tight-tardy progressive single machine scheduling with idling-free preemptions of equal-length jobs influences the speed of computing the exact solution. The Boolean linear programming model provided for finding schedules with the minimal total tardiness is used.
Methods. To achieve the said goal, a computational study is carried out with a purpose to estimate the averaged computation time for both ascending and descending orders of job release dates. Instances of the job scheduling problem are generated so, that schedules which can be obtained trivially, without the exact model, are excluded.
Results. Based on the three-dimensional barred plot of the relative difference between the averaged computation times, it has been shown that a possibility exists to find schedules more efficiently by manipulating the job order. For instance, schedules of 5 jobs consisting of two processing periods each are found on average by 14.67 % faster for the descending job order. In another example of 7 three-parted jobs, an optimal schedule is found on average in 69.51 seconds by the ascending job order, whereas the descending job order takes just 36.52 seconds to find it, saving thus 32.99 seconds.
Conclusions. Scheduling a fewer jobs divided into a fewer job parts is executed on average faster by the descending job order. As the number of jobs increases along with increasing the number of their processing periods, the ascending job order becomes more efficient. However, the computation time efficiency by both job orders tends to be irregular.References
P. Brucker, Scheduling Algorithms. Berlin, Heidelberg, Germany: Springer-Verlag, 2007, 371 p. doi: 10.1007/978-3-540-69516-5
M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer International Publishing, 2016, 670 p. doi: 10.1007/978-3-319-26580-3
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, “Accurate total weighted tardiness minimization in tight-tardy progressive single machine scheduling with preemptions by no idle periods”, KPI Sci. News, no. 5-6, pp. 26–42, 2019. doi: 10.20535/kpi-sn.2019.5-6.178016
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
W.-Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational ana-lysis”, Comp. Oper. Res., vol. 73, pp. 165–173, 2016. doi: 10.1016/j.cor.2016.04.006
Z.J. Tian et al., “An O(n2) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness”, J. Scheduling, vol. 9, iss. 4, pp. 343–364, 2006. doi: 10.1007/s10951-006-7039-6
V.V. Romanuke, “The exact minimization of total weighted completion time in the preemptive scheduling problem by subsequent length-equal job importance growth”, Bulletin of V. Karazin Kharkiv National University. Series “Mathematical Modelling. Information Technology. Automated Control Systems”, iss. 40, pp. 60–66, 2018. doi: 10.26565/2304-6201-2018-40-07
R. Kneusel, Random Numbers and Computers. Springer International Publishing, 2018, 260 p. doi: 10.1007/978-3-319-77697-2
Downloads
Published
Issue
Section
License
Copyright (c) 2020 The Author(s)
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
