Home   >   CSC-OpenAccess Library   >    Manuscript Information
Design and Implementation of a Multi-Agent System for the Job Shop Scheduling Problem
Leila Asadzadeh, Kamran Zamanifar
Pages - 287 - 297     |    Revised - 01-05-2011     |    Published - 31-05-2011
Volume - 5   Issue - 2    |    Publication Date - May / June 2011  Table of Contents
MORE INFORMATION
KEYWORDS
Job Shop Scheduling Problem, Genetic Algorithms, Parallel Genetic Algorithms
ABSTRACT
Job shop scheduling is one of the strongly NP-complete combinatorial optimization problems. Developing effective search methods is always an important and valuable work. Meta-heuristic methods such as genetic algorithms are widely applied to find optimal or near-optimal solutions for the job shop scheduling problem. Parallelizing genetic algorithms is one of the best approaches that can be used to enhance the performance of these algorithms. In this paper, we propose an agent-based parallel genetic algorithm for job shop scheduling problem. In our approach, initial population is created in an agent-based parallel way then an agent-based method is used to parallelize genetic algorithm. Experimental results showed that the proposed approach enhances the performance.
CITED BY (2)  
1 Bharathi, K., & Vijaylakshmi, C. Optimization for Flexible Job Shop Scheduling by Evolutionary Representation.
2 Krishnan, M., Karthikeyan, T., Chinnusamy, T. R., & Murugesan, A. (2013). Dynamic Scheduling of Flexible Manufacturing System Using Scatter Search Algorithm. International Journal of Emerging Technology and Advanced Engineering, 3(10), 329-341.
1 Google Scholar 
2 CiteSeerX 
3 refSeek 
4 iSEEK 
5 Libsearch 
6 Bielefeld Academic Search Engine (BASE) 
7 Scribd 
8 SlideShare 
9 PdfSR 
A. S. Jain and S. Meeran. “Deterministic job-shop scheduling: past, present and future,” Department of Applied Physics and Electronic and Mechanical Engineering, University of Dundee, Dundee, Scotland, UK, 1998.
B. J. Lageweg, J. K. Lenstra, and A. H. G. Rinnooy Kan. “Job shop scheduling by implicit enumeration.” Management Science, vol. 24, pp. 441-450, 1977.
B. M. Ombuki, and M. Ventresca. “Local search genetic algorithms for the job shop scheduling problem.” Applied Intelligence, vol. 21, pp. 99-109, 2004.
D. C. Mattfeld and R. J. M. Vaessens. “Job shop scheduling benchmarks.” Internet: www mscmga.ms.ic.ac.uk, [Jul. 10, 2008].
D. E. Goldberg and R. Lingle. “Alleles, loci, and the TSP,” in Proceeding of 1st International Conference on Genetic Algorithms, 1985, pp. 154-159.
D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. MA: Addison-Wesley, 1989.
E. Nowicki and C. Smutnicki. “A fast taboo search algorithm for the job-shop problem.” Management Science, vol. 42, no. 6, pp. 797-813, June 1996.
F. Bellifemine, A. Poggi, and G. Rimassa. “Developing multi-agent systems with a FIPAcompliant agent framework.” Software: Practice and Experience, vol. 31, pp. 103-128, 2001.
F. D. Croce, R. Tadei, and G. Volta. “A genetic algorithm for the job shop problem.” Computers and Operations Research, vol. 22, pp. 15-24, 1995.
J. adams, E. Balas, and D. Zawack. “The shifting bottleneck procedure for job shop scheduling.” Management Science, vol. 34, pp. 391–401, 1988.
J. B. Chambers. “Classical and flexible job shop scheduling by tabu search,” Ph.D. dissertation, University of Texas at Austin, Austin, TX, 1996.
J. Carlier and E. Pinson. “An algorithm for solving the job shop problem.” Management Science, vol. 35, no. 29, pp. 164-176, 1989.
J. F. Goncalves, J. J. d. M. Mendes, and M. G. C. Resende. “A hybrid genetic algorithm for the job shop scheduling problem.” European Journal of Operational Research, vol. 167, pp. 77-95, 2005.
J. Montgomery, C. Fayad, and S. Petrovic. “Solution representation for job shop scheduling problems in ant colony optimization,” Faculty of Information & Communication Technologies, Swinburne University of Technology, 2006.
J. Zhang, X. Hu, X. Tan, J. H. Zhong, and Q. Huang. “Implementation of an Ant Colony Optimization technique for job shop scheduling problem.” Transactions of the Institute of Measurement and Control, vol. 28, pp. 93-108, 2006.
K. L. Huang and C. J. Liao. “Ant colony optimization combined with taboo search for the job shop scheduling problem.” Computers & Operations Research, vol. 35, pp. 1030- 1046, 2008.
L. Asadzadeh, K. Zamanifar. “An Agent-based Parallel Approach for the Job Shop Scheduling Problem with Genetic Algorithms.” Mathematical and Computer Modeling, Vol. 52, pp. 1957-1965, 2010.
L. Wang and D. Z. Zheng. “A Modified Genetic Algorithm for Job Shop Scheduling.” International journal of advanced manufacturing technology, pp. 72-76, 2002.
L. Wang and D. Z. Zheng. “An effective hybrid optimization strategy for job-shop scheduling problems.” Computers & Operations Research, vol. 28, pp. 585-596, 2001.
M. E. Aydin and T. C. Fogarty. “Simulated annealing with evolutionary processes in job shop scheduling,” in Evolutionary Methods for Design, Optimization and Control, (Proceeding Of EUROGEN 2001), Barcelona, 2002.
M. Kolonko. “Some new results on simulated annealing applied to job shop scheduling problem.” European Journal of Operational Research, vol. 113, pp. 123-136, 1999.
M. Ventresca and B. Ombuki. “Ant Colony Optimization for Job Shop Scheduling Problem,” in Proceedings of 8th IASTED International Conference On Artificial Intelligence and Soft Computing, 2004, pp. 451-152.
P. Brucker, B. Jurisch, and B. Sievers. “A branch and bound algorithm for job-shop scheduling problem.” Discrete Applied Mathematics, vol. 49, pp. 105-127, 1994.
P. V. Laarhoven, E. Aarts, and J. K. Lenstra. “Job shop scheduling by simulated annealing.” Operations Research, vol. 40, pp. 113-125, 1992.
R. Cheng, M. Gen, and Y. Tsujimura. “A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: Hybrid genetic search strategies.” Computers & Industrial Engineering, vol. 36, pp. 343–364, 1999.
R. T. Mogaddam, F. Jolai, F. Vaziri, P. K. Ahmed, and A. Azaron. “A hybrid method for solving stochastic job shop scheduling problems.” Applied Mathematics and Computation, vol. 170, pp. 185-206, 2005.
R. Vancheeswaran and M. A. Townsend. “A two-stage heuristic procedure for scheduling job shops.” Journal of Manufacturing Systems, vol. 12, pp. 315-325, 1993.
S. C. Lin, E. D. Goodman, and W. F. Punch. “Investigating parallel genetic algorithms on job shop scheduling problems,” Genetic algorithm research and applications group, State university of Michigan, Michigan, 1995.
S. G. Ponnambalam, P. Aravindan, and S. V. Rajesh. “A tabu search algorithm for job shop scheduling.” International Journal of Advanced Manufacturing Technology, vol. 16, pp. 765-771, 2000.
S. Petrovic, and C. Fayad. “A genetic algorithm for job shop scheduling with load balancing,” School of Computer Science and Information Technology, University of Nottingham, Nottingham, 2005.
S. Rajakumar, V. P. Arunachalam, and V. Selladurai. “Workflow balancing in parallel machine scheduling with precedence constraints using genetic algorithm.” Journal of Manufacturing Technology Management, vol. 17, pp. 239-254, 2006.
S. Y. Foo, Y. Takefuji, and H. Szu. “Scaling properties of neural networks for job shop scheduling.” Neurocomputing, vol. 8, no.1, pp. 79-91, 1995.
T. Satake, K. Morikawa, K. Takahashi, and N. Nakamura. “Simulated annealing approach for minimizing the makespan of the general job-shop.” International Journal of Production Economics, vol. 60-61, pp. 515-522, 1999.
V. R. Kannan and S. Ghosh. “Evaluation of the interaction between dispatching rules and truncation procedures in job-shop scheduling.” International journal of production research, vol. 31, pp. 1637-1654, 1993.
Y. Chen, Z. Z. Li, and Z. W. Wang. “Multi-agent-based genetic algorithm for JSSP,” in Proceedings of the third international conference on Machine Learning and Cybernetics, 2004, pp. 267-270.
Z. He, T. Yang, and D. E. Deal. “Multiple-pass heuristic rule for job scheduling with due dates.” International journal of production research, vol. 31, pp. 2677-2692, 1993.
Miss Leila Asadzadeh
- Iran
leila_asadzadeh_cs@yahoo.com
Mr. Kamran Zamanifar
- Iran


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS