TOTAL WEIGHTED TARDINESS MINIMIZATION FOR TASKS WITH A COMMON DUE DATE ON PARALLEL MACHINES IN CASE OF AGREEABLE WEIGHTS AND PROCESSING TIMES
DOI:
https://doi.org/10.20998/2079-0023.2019.01.04Keywords:
scheduling theory, parallel machines, total weighted tardiness, common due date, agreeable weights, PSC-algorithmAbstract
We consider tasks scheduling problem on identical parallel machines by the criterion of minimizing the total weighted tardiness of tasks. All tasks arrive for processing at the same time. Weights and processing times are agreeable, that is, a greater weight of a task corresponds to a shorter processing time. In addition, we have arbitrary start times of machines for tasks processing. The times may be less or greater than the due date or to coincide with it. The problem in this formulation is addressed for the first time. It can be used to provide planning and decision making in systems with a network representation of technological processes and limited resources. We give efficient PSC-algorithm with complexity that includes the polynomial component and the approximation algorithm based on permutations of tasks. The polynomial component contains sufficient signs of optimality of the obtained solutions and allows to obtain an exact solution by polynomial subalgorithm. In the case when the sufficient signs of optimality do not fulfill, we obtain approximate solution with an estimate of deviation from the optimum for each individual problem instance of any practical dimension. We show that a schedule obtained as a result of the problem solving can be split into two schedules: the schedule on machines which start time is less than or equal to the due date, and the schedule on machines which start after the due date. Optimization is only done in the first schedule. The second schedule is optimal by construction. Statistical studies of the PSC-algorithm showed its high efficiency. We solved problems with dimensions up to 40,000 tasks and up to 30 machines. The average time to solve the problem by the algorithm using the most efficient types of permutations was 27.3 ms for this dimension. The average frequency of an optimal solution obtaining amounted to 90.3 %. The average deviation from an optimum was no more than 0.000251.References
Yalaoui F. Minimizing total tardiness in parallel-machine scheduling with release dates. Applied evolutionary computation. 2012, vol. 3, iss. 1, pp. 21–46. doi: 10.4018/jaec.2012010102
Zgurovsky M. Z., Pavlov A. A. Combinatorial optimization problems in planning and decision making: theory and applications. Cham, Springer Publ., 2019. 526 p. doi: 10.1007/978-3-319-98977-8
Garey M. R., Johnson D. S. Computers and intractability: a guide to the theory of NP-completeness. San Francisco, W. H. Freeman and Co. Publ., 1979. 348 p.
Lawler E. L. A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics. 1977, vol. 1, pp. 331–342. doi: 10.1016/S0167-5060(08)70742-8
Pinedo M. L. Scheduling: theory, algorithms, and systems. 5 th ed. Cham, Springer Publ., 2016. 690 p. doi: 10.1007/978-3-319-26580-3
Kramer A., Subramanian A. A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems. Available at: https://arxiv.org/abs/1509.02384 (accessed 05.05.2019).
Tanaev V. S., Shkurba V. V.: Vvedenie v teoriyu raspisaniy [Introduction to scheduling theory]. Moscow, Nauka Publ., 1975. 256 p.
Kovalyov M. Y., Werner F. Approximation schemes for scheduling jobs with common due date on parallel machines to minimize total tardiness. Journal of Heuristics. 2002, vol. 8, iss. 4, pp. 415–428. doi: 10.1023/A:1015487829051
Zgurovsky M. Z., Pavlov A. A. Trudnoreshaemye zadachi kombinatornoy optimizatsii v planirovanii i prinyatii resheniy: monografiya [Intractable problems of combinatorial optimization in planning and decision-making: monograph]. Kiev, Naukova dumka Publ., 2016. 716 p.
Pavlov A. A., Misura E. B., Melnikov O. V., Mukha I. P., Lishchuk K. I. Approximation algorithm for parallel machines total tardiness minimization problem for planning processes automation. The Second International Conference on Computer Science, Engineering and Education Applications ICCSEEA 2019 (26–27 January 2019, Kiev). Cham, Springer Publ., 2020, pp. 459–467. doi: 10.1007/978-3-030-16621-2_43
Lawler E. L., Moore J. M. A functional equation and its application to resource allocation and sequencing problems. Management Science. 1969, vol. 16, no. 1, pp. 77–84. doi: 10.1287/mnsc.16.1.77
Yuan J. The NP-hardness of the single machine common due date weighted tardiness problem. Journal of Systems Science and Complexity. 1992, vol. 5, no. 4, pp. 328–333.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2019 Bulletin of the National Technical University "KhPI". Series: System analysis, control and information technologyAuthors 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 a Creative Commons Attribution License 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 (See The Effect of Open Access).
