TIGHT-TARDY PROGRESSIVE IDLING-FREE 1-MACHINE PREEMPTIVE SCHEDULING WITH JOB PRIORITY WEIGHTS BY HEURISTIC’S EFFICIENT JOB ORDER INPUT
DOI:
https://doi.org/10.20535/kpisn.2020.4.209129Keywords:
preemptive single machine job scheduling, total weighted tardiness, heuristic;, ascending job order, descending job order, computation time, efficient job orderAbstract
Background. In setting a problem of minimizing total weighted 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 ascertained that scheduling a few equal-length jobs is expectedly faster by ascending order, whereas scheduling 30 to 70 equal-length jobs is 1.5 % to 2.5 % faster by descending order. For the number of equal-length jobs between roughly 90 and 250, the ascending job order again results in shorter computation times. In the case when the jobs have different lengths, the significance of the job order input is much lower. On average, the descending job order input gives a tiny advantage in computation time. This advantage decreases as the number of jobs increases.
Objective. The goal is to ascertain whether the job order input is significant in scheduling by using the heuristic for the case when the jobs have different lengths with job priority weights. Job order efficiency will be studied on tight-tardy progressive idling-free 1-machine preemptive scheduling.
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. First, the computation time for the ascending job order input is estimated for a series of job scheduling problems. Then, in each instance of this series, job lengths, priority weights, release dates, and due dates are reversed making thus the respective instance for the descending job order input, for which computation time is estimated as well.
Results. The significance of the job order input is much lower than that for the case of jobs without priorities. With assigning the job priority weights, the job order input becomes further “dithered”, adding randomly scattered priority weights to randomly scattered job lengths and partially randomized due dates. On average, the descending job order input is believed to give a tiny advantage in computation time in scheduling up to 100 jobs. However, this advantage, if any (being tinier than that in the case of random job lengths without priorities), quickly vanishes as the number of jobs increases.
Conclusions. It is better to compose job scheduling problems which would be closer to the case with equal-length jobs without priorities, where the saved computational time can be counted in hours. Even if the job lengths and priority weights are scattered, it is recommended to artificially “flatten” them. When artificial manipulations over job processing periods and job priority weights are impossible, it is recommended to use the descending job order input in scheduling up to 100 jobs, and either job order input in scheduling more than 100 jobs, although substantial benefits are not expected in this case.
References
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.180877
R. Panneerselvam, “Simple heuristic to minimize total tardiness in a single machine scheduling problem”, Int. J. Adv. Manufact. Technol., vol. 30, no. 7–8, pp. 722–726, 2006. doi: 10.1007/s00170-005-0102-1
M. Batsyn et al., “Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time”, Optimiz. Method. & Software, vol. 29, no. 5, pp. 955–963, 2014. doi: 10.1080/10556788.2013.854360
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, “Tight-tardy progressive idling-free 1-machine preemptive scheduling by heuristic’s efficient job order in-put”, KPI Sci. News, no. 3, pp. 32–42, 2020. doi: 10.20535/kpi-sn.2020.3.199850
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, “Heuristic’s job order efficiency in tight-tardy progressive idling-free 1-machine preemptive scheduling of equal-length jobs”, KPI Sci. News, no. 2, pp. 64–73, 2020. doi: 10.20535/kpi-sn.2020.2.181869
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
V.V. Romanuke, “Job order input for efficient exact minimization of total tardiness in tight-tardy progressive single machine scheduling with idling-free preemptions”, Scientific Papers O. S. Popov Odesa Nat. Academy Telecommun., no. 1, pp. 19–36, 2020. doi: 10.33243/2518-7139-2020-1-1-19-36
V.V. Romanuke, “Total weighted tardiness exact minimization by efficiently inputting jobs to tight-tardy progressive single machine scheduling with idling-free preemptions”, Digital Technol., no. 27, pp. 41–55, 2020.
V.V. Romanuke, “Minimal total weighted tardiness in tight-tardy single machine preemptive idling-free scheduling”, Appl. Comp. Syst., vol. 24, no. 2, pp. 150–160, 2019. doi: 10.2478/acss-2019-0019
M. Tamannaei and M. Rasti-Barzoki, “Mathematical programming and solution approaches for minimizing tardiness and transportation costs in the supply chain scheduling problem”, Comp. Industr. Eng., vol. 127, pp. 643–656, 2019. doi: 10.1016/j.cie.2018.11.003
R.T. Kneusel, Random Numbers and Computers. Springer International Publishing, 2018, 260 p. doi: 10.1007/978-3-319-77697-2
S. Vigna, “On the probability of overlap of random subsequences of pseudorandom number generators”, Inform. Process. Lett., vol. 158, ID 105939, 2020. doi: 10.1016/j.ipl.2020.105939
M.H. Ardakani et al., “Sliding dynamic data window: Improving properties of the incremental learning methods”, Comput. Aided Chemical Eng., vol. 40, pp. 1663–1668, 2017. doi: 10.1016/B978-0-444-63965-3.50279-8
N. Gasmi et al., “Chapter 21 - Nonlinear filtering design for discrete-time systems using sliding window of delayed measurements”, in Stability, Control and Applications of Time-delay Systems. Butterworth-Heinemann, 2019, pp. 423–439. doi: 10.1016/B978-0-12-814928-7.00021-4
Downloads
Published
Issue
Section
License
Copyright (c) 2020 Vadim V. Romanuke
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
