JOB ORDER INPUT FOR EFFICIENT EXACT MINIMIZATION OF TOTAL TARDINESS IN TIGHT-TARDY PROGRESSIVE SINGLE MACHINE SCHEDULING WITH IDLING-FREE PREEMPTIONS

Abstract

Abstract. 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 into the model in reverse order. The goal is to
ascertain whether the job order in tight-tardy progressive single machine scheduling with idling-free
preemptions influences the speed of computing the exact solution. The Boolean linear programming
model provided for finding schedules with the minimal total tardiness is used. To achieve the said goal, a
computational study is carried out with the purpose of estimating 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. As in
the case of equal-length jobs, it has been ascertained that the job order really influences the speed of
computing schedules whose total tardiness is minimal. Scheduling two to five jobs is executed on
average faster by the descending job order input, where 1 to 3 % speed-up is expected. Further
increment of the number of jobs to be scheduled cannot guarantee any speed-up even on average. This
result is similar to that in the case of equal-length jobs, but there is no regularity in such an efficient job
order input. Without any assurance for a single job scheduling problem, the efficient exact minimization of
total tardiness by the descending job order input must be treated as on average only.