Preemptive single machine job scheduling, Equal-length jobs, Total tardiness, Heuristic, Ascending job order, Descending job order, Computation time, Efficient job order


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.

Author Biography

Vadim V. Romanuke, Polish Naval Academy

Вадим Васильевич Романюк


J.C. Price and J.S. Forrest, Practical Airport Operations, Safety, and Emergency Management. Butterworth-Heinemann, 2016, 630 p. doi: 10.1016/C2013-0-15991-0

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

H. Alhussian et al., “An unfair semi-greedy real-time multiprocessor scheduling algorithm”, Computers & Electrical Engineering, vol. 50, pp. 143–165, 2016. doi: 10.1016/j.compeleceng.2015.07.003

D. Rupanetti and H. Salamy, “Task allocation, migration and scheduling for energy-efficient real-time multiprocessor architectures”, J. Syst. Architec., vol. 98, pp. 17–26, 2019. doi: 10.1016/j.sysarc.2019.06.003

V.V. Romanuke, “Efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions of equal-length jobs”, KPI Sci. News, no. 1, pp. 27–39, 2020. doi: 10.20535/kpi-sn.2020.1.164804

W.-Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational analysis”, Comp. Operat. Res., vol. 73, pp. 165–173, 2016. doi: 10.1016/j.cor.2016.04.006

F. Jaramillo and M. Erkoc, “Minimizing total weighted tardiness and overtime costs for single machine preemptive scheduling”, Comp. Industr. Eng., vol. 107, pp. 109–119, 2017. doi: 10.1016/j.cie.2017.03.012

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