ACCURATE TOTAL WEIGHTED TARDINESS MINIMIZATION IN TIGHT-TARDY PROGRESSIVE SINGLE MACHINE SCHEDULING WITH PREEMPTIONS BY NO IDLE PERIODS
DOI:
https://doi.org/10.20535/kpi-sn.2019.5-6.178016Keywords:
Job scheduling, Preemptive single machine scheduling, Exact model, Heuristic, Total weighted tardiness, Heuristic’s accuracy, Relative gap, Top worst maximal relative gapAbstract
Background. The problem of minimization of total weighted tardiness can be solved either exactly by the corresponding models or heuristically. As of October 2019, nearly the best heuristic is one based on using remaining available and processing periods. The heuristic is extremely rapid compared to the exact solution models, but its accuracy can be both 100 % and intolerably low.
Objective. Issuing from the lack of knowledge in relationship between the heuristic and Boolean linear programming model provided for exact solutions, the goal is to study statistical difference between them for the preemptive single machine scheduling problem by no idle periods, in which processing periods are equal by progressively running release and due dates set tightly.
Methods. The relative gap of the heuristic is defined and then studied how it varies against increasing complexity of job scheduling problems. The complexity implies the number of jobs and the number of job processing periods. The computation times of the heuristic and the exact model are registered as well.
Results. The heuristic has successfully replaced the exact model no less than in 72 % of non-timeout instances, where it schedules with the same minimal total weighted tardiness (100 % accuracy). This rate is about 90 % to 97 % on average, although huge gaps may appear in the rest of cases. In the practice of fast-refreshable schedules, the Boolean linear programming model is indeed hardly tractable in scheduling no less than 14 two-parted jobs and no less than 10 three-parted jobs. Scheduling jobs divided into a greater number of parts each will have a significantly lower worst gap than scheduling jobs divided into a lesser number of parts. If a job is divisible, it is strongly recommended to divide the job into as great number of its parts as possible. If scheduling only 2 jobs is impossible, it is strongly recommended to artificially increase the number of jobs to be scheduled.
Conclusions. Total weighted tardiness minimization in tight-tardy progressive single machine scheduling with preemptions by no idle periods can be sufficiently accurate by the heuristic if no less than 7 jobs divided into no less than five parts each are scheduled (the “7/5” pattern). An exception from this rule is that the heuristic schedules just 2 jobs always at the 100 % accuracy, not depending on in how many parts the job is divided (the “2/any” exception). An intermediate between the “7/5” pattern and the “2/any” exception is that scheduling 3 jobs divided into either four or five parts is sufficiently accurate as well, where the inaccuracy does not exceed 0.7 %. In other cases the heuristic is either inapplicable or there is a high risk of obtaining intolerable gaps. The inapplicability does not directly imply a bad inaccuracy, but it implies an unpredictable accuracy drop. For example, 974 of 1000 instances of 3 two-parted jobs have been scheduled with the 100 % accuracy, but 26 instances have been scheduled with an average gap in 13.31 %, which is quite intolerable and thus inapplicable.References
P. Brucker, Scheduling Algorithms. Springer-Verlag Berlin Heidelberg, 2007, 371 p. doi: 10.1007/978-3-540-69516-5
M.L. Pinedo, Scheduling: Theory, Algorithms, and Systems. Springer International Publishing, 2016, 670 p. doi: 10.1007/978-3-319-26580-3
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, Planning and Scheduling in Manufacturing and Services. Springer-Verlag New York, 2009, 536 p. doi: 10.1007/978-1-4419-0910-7
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
R. L. Graham et al., “Optimization and approximation in deterministic sequencing and scheduling: A survey”, Ann. Discrete Math., vol. 5, pp. 287–326, 1979. doi: 10.1016/S0167-5060(08)70356-X
Z. J. Tian et al., “An O(n2) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness”, J. Scheduling, vol. 9, iss. 4, pp. 343–364, 2006. doi: 10.1007/s10951-006-7039-6
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
V.V. Romanuke, “The exact minimization of total weighted completion time in the preemptive scheduling problem by subsequent length-equal job importance growth”, Bulletin of V. Karazin Kharkiv National University. Series “Mathematical Modelling. Information Technology. Automated Control Systems”, iss. 40, pp. 60–66, 2018.
W.-Y. Ku and J.C. Beck, “Mixed Integer Programming models for job shop scheduling: A computational analysis”, Comp. Oper. Res., vol. 73, pp. 165–173, 2016. doi: 10.1016/j.cor.2016.04.006
R. Panneerselvam, “Simple heuristic to minimize total tardiness in a single machine scheduling problem”, Int. J. Adv. Manuf. Technol., vol. 30, iss. 7-8, pp. 722–726, 2006. doi: 10.1007/s00170-005-0102-1
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
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
