KPI Science News (Mar 2020)
HEURISTIC’S JOB ORDER EFFICIENCY IN TIGHT-TARDY PROGRESSIVE IDLING-FREE 1-MACHINE PREEMPTIVE SCHEDULING OF EQUAL-LENGTH JOBS
Abstract
Background. In setting a problem of minimizing total tardiness by the heuristic based on remaining available and processing periods, there are two opposite ways to input the data: the job release dates are given in either ascending or descending order. It was recently proved that an efficient job order can save significant computation time by using the Boolean linear programming model provided for finding schedules with the exactly minimal total tardiness. Objective. The goal is to ascertain whether the job order input is significant in scheduling by using the heuristic. Job order efficiency will be studied on tight-tardy progressive idling-free 1-machine preemptive scheduling of equal-length jobs. 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 heuristic, are excluded. Results. Scheduling a few jobs is expectedly faster by ascending order, but this part is full of computational artifacts. Scheduling 30 to 70 jobs is 1.5 % to 2.5 % faster by descending order. However, scheduling up to 90 jobs is expectedly still faster by descending order, although a risk of losing this advantage exists. For the number of jobs between roughly 90 and 250, the ascending job order again results in shorter computation times. Since the point of about 250 jobs, the advantage trend (of either ascending or descending order) appears more stable. Conclusions. In scheduling by using the heuristic, the job order input is indeed significant. The average relative difference does not exceed 1.5 % for 2 to 1000 jobs consisting up to 17 processing periods. For obtaining a statistically reliable computation speed advantage, it is better to consider no less than 250 jobs. As either the number of jobs or the number of job parts increases, the computation speed advantage may become unstable and eventually vanish. Nevertheless, the ascending job order can save a lot of computational time in the case of scheduling at least a few thousand jobs having just a few processing periods each. After solving thousands of such cases the saved time may be counted in hours.
Keywords
