TOTAL WEIGHTED TARDINESS EXACT MINIMIZATION BY EFFICIENTLY INPUTTING JOBS TO TIGHT-TARDY PROGRESSIVE SINGLE MACHINE SCHEDULING WITH IDLING-FREE PREEMPTIONS

Abstract

A schedule ensuring the exactly minimal total weighted 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. 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 jobs can have both different lengths and different priority weights. The Boolean linear programming model provided for finding schedules with the minimal total weighted tardiness is used. 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. Then the relative difference between the computation times is to be estimated and treated. The job order influences the speed of computing the exact solution but it is hardly possible to predict it. The matter is that the jobs can have both different lengths and different priority weights, that additionally “dithers” the respective job order input leaving only release dates which are always given in that order. It has been revealed that scheduling 3 or 4 jobs is executed on average faster by the descending job order input. However, the expected acceleration by the descending job order input cannot be estimated with a great confidence factor. This result disproves a possibility to manipulate the job order for obtaining schedules more efficiently in a single job scheduling problem or in a few such problems. Only if the job scheduling problems by 3 or 4 jobs resemble the descending job order input, and there are thousands of such problems, then it is recommended to use that job order input. Inputting jobs efficiently by the descending job order style is still possible when different job lengths and different priority weights are both scattered not much, that would be closer to the case of total tardiness by equal job lengths and equal priority weights. This case is the most promising one, where the descending job order computation time can be shorter up to 10 % and more in scheduling 2 to 6 jobs divided into two to four or even five parts each.