DOI: https://doi.org/10.20535/kpi-sn.2020.1.180877

EFFICIENT EXACT MINIMIZATION OF TOTAL TARDINESS IN TIGHT-TARDY PROGRESSIVE SINGLE MACHINE SCHEDULING WITH IDLING-FREE PREEMPTIONS OF EQUAL-LENGTH JOBS

Vadim V. Romanuke

Abstract


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.

Keywords


Job scheduling; Preemptive single machine scheduling; Exact model; Total tardiness; Computation time; Ascending job order; Descending job order

Full Text:

PDF

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


GOST Style Citations




Refbacks

  • There are currently no refbacks.




Copyright (c) 2020 The Author(s)

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