Random Articles
Reseach Article
Solving Single Machine Total Weighted Tardiness Problem using Variable Structure Learning Automata
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 56 - Number 1 |
| Year of Publication: 2012 |
| Authors: Saeed Sabamoniri, Kayvan Asghari, Mohammad Javad Hosseini |
10.5120/8858-2816
|
Saeed Sabamoniri, Kayvan Asghari, Mohammad Javad Hosseini . Solving Single Machine Total Weighted Tardiness Problem using Variable Structure Learning Automata. International Journal of Computer Applications. 56, 1 ( October 2012), 37-42. DOI=10.5120/8858-2816
Abstract
In this paper intelligent search technique of variable structure learning automata (VSLA) has been used to solve single machine total weighted tardiness job scheduling problem. The goal is investigating reduction in delays result in late execution of the jobs after specified deadline as well as reducing the time required to find the best execution order of the jobs. For this reason, fixed structure learning automata and genetic algorithm approaches has been studied and then a new scheduling approach called VSLA-Scheduler has been proposed by employing variable structure learning automata technique. In order to identify strengths and weaknesses of the proposed method, its performance is compared with other intelligent techniques. In this regard, for performance evaluation of the proposed method and comparing it with other methods, computer simulations have been used. Finally, the results produced by the proposed and previous algorithms have been compared with the best solutions in OR library. Experimental results show that the proposed algorithm's performance (VSLA-Scheduler) is more acceptable than other methods.
References
- Lenstra, J. K. Kinnooy Kan, A. H. G. and Brucker, P. 1977. Complexity of machine scheduling problems. Annals of Discrete Mathematics. 1. 343–362.
- Madureira, A. Ramos, C. and Silva, S. 2001. A GA based scheduling system for dynamic single machine problem. In Proceedings of the 4th IEEE International Symposium on Assembly and Task Planning Soft Research Park. 262–267.
- Morton, T. E. David, P. W. 1993 Heuristic Scheduling Systems. John Wiley & Sons.
- Baker, K. R. 1974 Introduction to Sequencing and Scheduling. Wiley. New York.
- Lawer, E. L. 1977. A pseudopolinomial algorithm for Sequencing Jobs to Minimize Total Tardiness. Annals of Discrete Mathematics. 331–342.
- Abdul-Razaq, T. S. Potts, C. N. and Van Wassenhove, L. N. 1990. A survey for the Single-Machine Scheduling Total WT Scheduling Problem. Discrete Applied Mathematics. 26. 235–253.
- Potts, N. Van Wassenhove, L. N. 1991. Single Machine Tardiness Sequencing Heuristics. IIE Transactions. 23. no. 4. 346–354.
- Shwimer, J. 1972. On the n-job, one-machine, sequence independent scheduling problem with tardiness penalties: a branch-bound solution. Management Science. 18. no. 6. 301–313.
- Rinnooy Kan, H. G. Lageweg, B. J. and Lenstra, J. K. 1975. Minimizing total costs in one-machine scheduling. Operations research. 23. no. 5. 908–927.
- Potts, C. N. Wassenhove, L. N. V. 1985. A branch and bound algorithm for the total weighted tardiness problems. Operations Research. 33. no. 2. 363–377.
- Schrage, L. Baker, K. R. 1978. Dynamic programming solution of sequencing problem with precedence constraints. Operations research. 26. 444–449.
- Huegler, P. A. Vasko, F. J. 1997. A performance comparison of heuristics for the total weighted tardiness problem. Computers & Industrial Engineering. 32. no. 4 753–767.
- Crauwels, H. A. J. Potts C. N. and Wassenhove, L. N. V. 1998. Local search heuristics for the single machine total weighted tardiness scheduling problem. INFORMS Journal on Computing. 10. no. 3. 341–350.
- Ferrolho, A. Crisóstomo, M. 2007. Single Machine Total Weighted Tardiness Problem with Genetic Algorithms. In Proceedings of the 3rd International Conference on Computer Systems and Applications. Amman. 1–8.
- Asghari, K. and Meybodi, M. R. 2009. Solving Single Machine Total Weighted Tardiness Scheduling Problem using Learning Automata and Combination of it with Genetic Algorithm. In Proceedings of the 3rd Iran Data Mining Conference. Tehran University of Science and Technology. Iran.
- Narendra, K. S. Thathachar, M. A. L. 1989. Learning Automata: An Introduction. Prentice-hall. Englewood cliffs.
- Najim, K. Poznyak, A. S. 1994. Learning Automata: Theory and Application. Tarrytown. Elsevier.
- Oommen J. and Ma, D. C. Y. 1998. Deterministic Learning Automata Solutions to the equipartitioning problem. IEEE Transactions on Computers. 37. 2-13.
- Morton, T. E. Rachamadugu, R. M. and Vepsalainen, A. 1984. Accurate myopic heuristics for tardiness scheduling. GSIA Working Paper. no. 36. Carnegie-Mellon University. PA. 83-84.
- Beasley, JE. 1990. O. R. library. http://people. brunel. ac. uk /~mastjjb/jeb/orlib/wtinfo. html
- Congram, R. K. Potts, C. N. Van de Velde, S. 2002. An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS Journal on Computing. 14. 52–67.
Index Terms
Keywords