MINUKHIN S.V., LENKO D.S.
ABSTRACT
The paper deals with the algorithms of minimizing the total lag of works on a single device on the basis of determining the shortest Hamilton path in the arbitrary graph using the rank approach and the dominance rules. The performance metrics of applying the dominance rules based on the evaluation of locally optimal solutions, obtained on different ranks and the values of relative reduction of total lag in relation to the basic algorithm are proposed. The results of computational experiments for the weighted and unweighted cases for the works with different duration and the types of due dates defined in the research are given. The conditions, under which, the proposed algorithms allow improving the schedule of works are defined and the most effective dominance rules are determined.
KEYWORDS
rank approach, Hamilton path, schedule, total lag, time complexity, directive term , single device, duration,, dominance rules.
REFERENCES
1. Ye Nong, Gel Esma S., Li Xueping, Farley Toni and Lai Ying-Cheng (2005), “Web Server QoS Models: Applying Scheduling Rules from Production Planning”, Computers & Operations Research, no. 32, pp. 1147-1164.
2. Zafril Rizal M Azmi, Kamalrulnizam Abu Bakar, Abdul Hanan Abdullah, Mohd Shahir Shamsir, Wan Nurulsafawati Wan Manan (2011), “Performance Comparison of Priority Rule Scheduling Algorithms Using Different Inter Arrival Time Jobs in Grid Environment”, Intern. J. of Grid and Distributed Computing, Vol. 4, no. 3, pp. 61-70.
3. Singh, H. and Dr. Kumar, S. (2011), “Dispatcher Based Dynamic Load Balancing on Web Server System”, Ibid., Vol. 4, no. 3, pp. 89-105.
4. Zafril Rizal M Azmi, Kamalrulnizam Abu Bakar , Mohd Shahir Shamsir, Wan Nurulsafawati Wan Manan, Abdul Hanan Abdullah (2011), “Scheduling Grid Jobs Using Priority Rule Algorithms and Gap Filling Techniques”, Intern. J. of Advanced Science and Technology, Vol. 37, pp. 61-76.
5. Klusacek, D. and Rudova, H. (2008), “Comparison of Multi-criteria Scheduling Techniques”, Ed. Gorlatch, S., Fragopoulou, P., and Priol, T., Springer US, pp. 173-184.
6. Klusacek, D. and Rudova, H. (2008), “Improving QoS in Computational Grids through Schedule-based Approach”, In Scheduling and Planning Applications Workshop at the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS 2008), Sydney, Australia.
7. Listrovoy, S.V. and Minukhin, S.V. (2012), “The model and approach to planning the allocation of resources in heterogeneous GRID systems”, Problemy upravleniya i informatiki. Mezhdunarodnyy nauchno-tekhnicheskiy zhurnal, no. 5, pp. 120-133.
8. Listrovoy, S.V. and Minukhin, S.V. (2012), “The method for solving a problems of minimal vertex covering in arbitrary graph and a problem minimal coverage”, Elektronnoe modelirovanie, Vol. 34, no. 1, pp. 29-43.
9. Koulamas, C. (1994), “The Total Tardiness Problem: Review and Extensions”, Operations Research, Vol. 42, pp. 1025-1041.
10. Koulamas, C. (2010), “The Single-machine Total Tardiness Scheduling Problem: Review and Extensions”, European J. of Operational Research, Vol. 202, no. 1, pp. 1-7.
11. Sena, T., Suleka, J.M. and Dileepan Parthasarati (2003), “Static Scheduling Research to Minimize Weighted and Unweighted Tardiness: A State-of-the-art Survey”, Intern. J. Production Economics, Vol. 83, no. 1, pp. 1-12.
12. Du, J. and Leung, J.Y.-T. (1990), “Minimizing Total Tardiness on One Machine is NP-hard”, Mathematics of Operations Research, no. 15, pp. 483-495.
13. Lawler, E.L. (1977), “A «Pseudo Polynomial» Algorithm for Sequencing Jobs to Minimize Total Tardiness”, Annals of Discrete Mathematics, no. 1, pp. 331-342.
14. Baker, K.R. and Shrage, L.E. (1978), “Finding an Optimal Sequence by Dynamic Programming an Extension to Precedence-related Tasks”, Operations Research Letters, no. 26, pp. 111-120.
15. Lawler, E.L. (1982), “A Fully Polynomial Approximation Scheme for the Total Tardiness Problem”, Ibid., no. 1, pp. 207-208.
16. Potts, C.N., Van Wassenhove, L.N. (1987), “Dynamic Programming and Decomposition Approaches for the Single Machine Total Tardiness Problem”, European J. of Operational, no. 32, pp. 405-414.
17. Kovalyov, M.Y. (1995), “Improving the Complexities of Approximation Algorithms for Optimization problems” Operations Research Letters, March, Vol. 17, pp. 85-87.
18. Koulamas, C. (2009), “A Faster Fully Polynomial Approximation Scheme for the Single Machine Total Tardiness Problem”, European J. of Operational Research, no. 193, pp. 637-638.
19. Pavlov, A.A. and Misyura, E.B. (2002), “A new approach to solving the problem "Minimizing total weighted tardiness in carrying out independent tasks with one device directive deadlines"”, Sistemnye issledovaniya i informatsionnye tekhnologii, no. 2, pp. 7-32.
20. Pavlov, O.A., Mysyura, E.B. and Shevchenko, K.Yu. (2012), “Construction of PDC-algorithm for solving the problem of minimizing of total weighted tardiness works on one device”, Visnyk NTUU “KPI”. Informatyka, upravlinnya ta obchyslyuvalna tekhnika. Zbirnyk naukovykh prats [Informatics, Management and Computer Science], Kiev, no. 56, pp. 58-70.
21. Minukhin, S.V. (2009), “Method to minimize the time tasks with legislative term of non-clustered resource of computing system”, Informatsiyno-keruyuchi systemy na zaliznychnomu transporti, no. 3, pp. 47-53.
22. Minukhin, S. (2012), “Efficient Method for Single Machine Total Tardiness Problem”, IV Intern. Conf. «Problems of Cybernetics and Informatics» (PCI'2012), September 12-14, 2012.
23. Minukhin, S.V. and Lenko, D.S. (2013), “Research of the methods to minimize the total time of delay works with legislative term on single computing resource”, Problemy i perspektyvy rozvytku IT-industriyi. Systemy obrobky informatsiyi, Iss. 3 (110), Vol. 2, pp. 30-35.
24. Shevchenko, K.Yu. (2012), “Branch and bound algorithm for statistical studies of the new PDS algorithm for solving the problem of minimizing total weighted tardiness works on one device”, Visnyk NTUU “KPI”. Informatyka, upravlinnya ta obchyslyuvalna tekhnika: Zbirnyk naukovykh prats [Informatics, Management and Computer Science], Kiev, no. 55, pp. 56-69.
25. Chu, Ñ. (1992), “Efficient Heuristics to Minimize Total Flow Time with Release Dates”, Operations Research Letters, no. 12, pp. 321-330.
26. Jouglet, A., Savourey, D.D., Carlier, J. and Baptiste, P. (2008), “Dominance-Based Heuristics for One-Machine Total Cost Problems”, European J. of Operational Research, Vol. 184 (3), pp. 879-899.
27. Jouglet, A. and Savourey, D. (2011), “Dominance Rules for the Parallel Machine Total Weighted Tardiness Scheduling Problem with Release Dates”, Computers & Operations research, Vol. 38, Issue 9, pp. 1259-1266.
28. Jackson, J.R. (1955), Scheduling a Production Line to Minimize Maximum Tardiness. Minimizing Total Tardiness for One Machine Research, Report 43, Management Science Research Project, UCLA,
29. Lai Tsung-Chyan and Kuo Yuh-Kwo (1996), “Minimizing Total Tardiness for Single Machine Sequencing”, J. of the Operations Research Society of Japan, Vol. 39, no. 3, pp. 316-321.
30. Scheduling Single Machine Scheduling.
31. OR-Library.
32. Zotkin, D. and Keleher, P.J. (1999), “Job-Length Estimation and Performance in Backlling Schedulers”, In Proc. 8th High Performance Distributed Computing Conf. IEEE.
33. Mohamadreza Kaviani, Majid Aminnayeri, Seyed Nima Rafienejad and Fariborz Jolai (2012), “An Appropriate Pattern to Solving a Parallel Machine Scheduling by a Combination of Meta-heuristic and Data Mining”, J. of American Science, no. 8 (1), pp. 160-167.
34. Chandra, P., Li, S. and Stan, M. (1993), “Jobs and Tool Sequencing in an Automated Manufacturing Environment”, Intern. J. of Production Research, Vol. 31, Issue 1, pp. 2911-2925.
35. Sekhar, C.V.S. and Devi, M.P. (2007), “Improvement of Performance in a Maintenance Job Shop”, Proc. of the 11th WSEAS Intern. Conf. on Applied Mathematics, Dallas, Texas, USA, March 22-24, 2007, pp. 29-34.