ACCURACY OF A HEURISTIC FOR TOTAL WEIGHTED COMPLETION TIME MINIMIZATION IN PREEMPTIVE SINGLE MACHINE SCHEDULING PROBLEM BY NO IDLE TIME INTERVALS
DOI:
https://doi.org/10.20535/kpi-sn.2019.3.164804Keywords:
Job scheduling, Preemptive single machine scheduling, Exact model, Heuristic, Total weighted completion time, Heuristic’s accuracy, Heuristic’s rapidness advantageAbstract
Background. A special case of the job scheduling process is that when jobs are processed on a single machine, preemptions are allowed, and there are no idle time intervals. Despite the exact solution models are always much slower than the heuristics, laws of heuristic’s rapidness advantage and heuristic’s solution closeness to the exact solution are unknown. Such laws would be useful to estimate real benefits of solution approximation.
Objective. Issuing from the lack of knowledge in relationship between heuristics and exact solution models, the goal is to study statistical difference between them for the preemptive single machine scheduling problem by no idle time intervals.
Methods. The two well-known approaches are invoked – the rule of weighted shortest remaining processing period as a heuristic and the Boolean linear programming model as an exact model. The relative error of the heuristic is defined and then studied how it varies against increasing complexity of job scheduling problems. The heuristic’s rapidness gain is shown as well.
Results. The main issue with the heuristic’s accuracy can arise at a few jobs to be scheduled. Additionally to this, if a sequence of jobs is divided into the fewest parts, the heuristic’s accuracy becomes the lowest. The exception exists for the shortest sequences – when only two jobs are to be scheduled. As the number of jobs increases up off 6, the relative error expectedly decreases along with the dramatically growing heuristic’s rapidness advantage. Therefore, scheduling a long sequence of jobs is preferable. The top relative error of the heuristic can exceed 6 % for three to five jobs to be scheduled, when they are divided into the fewest parts.
Conclusions. Starting off six jobs, the heuristic’s accuracy averagely increases, by a fixed rate of randomness in processing periods, priority weights, and release dates, as the complexity of job scheduling problems increases. The rate of randomness influences inversely: if processing periods, priority weights, and release dates are more randomly scattered, the heuristic schedules more accurately. The exact approach is truly applicable for cases when three to five jobs are to be scheduled (in particular cases, when the number of job parts is constant and is 2, the upper number of jobs can be increased up to 10). For such cases, an approximate solution’s real loss (given by the heuristic) is the average relative error not exceeding 1.2 % for job scheduling problems with low rate of the randomness. If such a loss is not admissible, the exact approach will work instead.References
H. Belouadah et al., “Scheduling with release dates on a single machine to minimize total weighted completion time”, Discrete Appl. Math., vol. 36, iss. 3, pp. 213–231, 1992. doi: 10.1016/0166-218X(92)90255-9
M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer International Publishing, 2016, 670 p. doi: 10.1007/978-3-319-26580-3
M.L. Pinedo, Planning and Scheduling in Manufacturing and Services. Springer-Verlag New York, 2009, 536 p. doi: 10.1007/978-1-4419-0910-7
P. Brucker, Scheduling Algorithms. Springer-Verlag Berlin Heidelberg, 2007, 371 p. doi: 10.1007/978-3-540-69516-5
W. Tian and Y. Zhao, “Energy efficiency by minimizing total busy time of offline parallel scheduling in cloud computing”, in Optimized Cloud Resource Management and Scheduling, W. Tian and Y. Zhao, eds. Morgan Kaufmann, 2015, pp. 135–157. doi: 10.1016/B978-0-12-801476-9.00007-0
W.-Y. Ku and J. C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational analysis”, Computers & Operations Research, vol. 73, pp. 165–173, 2016. doi: 10.1016/j.cor.2016.04.006
A.C. Nearchou, “An efficient meta-heuristic for the single machine common due date scheduling problem”, in Intelligent Production Machines and Systems, D.T. Pham et al., eds. Elsevier Science Ltd, 2006, pp. 431–435. doi: 10.1016/B978-008045157-2/50077-8
L.P. Fávero and P. Belfiore, “Integer Programming”, in Data Science for Business and Decision Making, L.P. Fávero and P. Belfiore, eds. Academic Press, 2019, pp. 887–918. doi: 10.1016/B978-0-12-811216-8.00019-7
V.V. Romanuke, “Acyclic-and-asymmetric payoff triplet refinement of pure strategy efficient Nash equilibria in trimatrix games by maximinimin and superoptimality”, Naukovi Visti NTUU KPI, no. 4, pp. 38–53, 2018. doi: 10.20535/1810-0546.2018.4.131696
R.L. Bowman, “Evaluating pseudo-random number generators”, in Chaos and Fractals, C. Pickover, Ed. Elsevier Science, 1998, pp. 133–142. doi: 10.1016/B978-044450002-1/50023-0
V.V. Romanuke, “Optimal pixel-to-shift standard deviations ratio for training 2-layer perceptron on shifted images with pixel distortion in classifying shifting-distorted objects”, Appl. Comp. Syst., vol. 19, pp. 61–70, 2016. doi: 10.1515/acss-2016-0008
M. Mnich and R. van Bevern, “Parameterized complexity of machine scheduling: 15 open problems”, Computers & Operations Research, vol. 100, pp. 254–261, 2018. doi: 10.1016/j.cor.2018.07.020
Downloads
Published
Issue
Section
License
Copyright (c) 2019 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
