KPI Science News (Mar 2020)
EFFICIENT EXACT MINIMIZATION OF TOTAL TARDINESS IN TIGHT-TARDY PROGRESSIVE SINGLE MACHINE SCHEDULING WITH IDLING-FREE PREEMPTIONS OF EQUAL-LENGTH JOBS
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
