HEURISTIC’S JOB ORDER EFFICIENCY IN TIGHT-TARDY PROGRESSIVE IDLING-FREE 1-MACHINE PREEMPTIVE SCHEDULING OF EQUAL-LENGTH JOBS
DOI:
https://doi.org/10.20535/kpi-sn.2020.2.181869Keywords:
Preemptive single machine job scheduling, Equal-length jobs, Total tardiness, Heuristic, Ascending job order, Descending job order, Computation time, Efficient job orderAbstract
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.References
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
Downloads
Published
Issue
Section
License
Copyright (c) 2020 The Author(s)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under CC BY 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work
