Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

This is an Open Access publication published under CSC-OpenAccess Policy.
Publications from CSC-OpenAccess Library are being accessed from over 74 countries worldwide.
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
Job Shop Scheduling Problem, Genetic Algorithms, Parallel Genetic Algorithms
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 
1 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.
2 J. Carlier and E. Pinson. “An algorithm for solving the job shop problem.” Management Science, vol. 35, no. 29, pp. 164-176, 1989.
3 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.
4 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.
5 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.
6 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.
7 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.
8 J. adams, E. Balas, and D. Zawack. “The shifting bottleneck procedure for job shop scheduling.” Management Science, vol. 34, pp. 391–401, 1988.
9 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.
10 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.
11 P. V. Laarhoven, E. Aarts, and J. K. Lenstra. “Job shop scheduling by simulated annealing.” Operations Research, vol. 40, pp. 113-125, 1992.
12 J. B. Chambers. “Classical and flexible job shop scheduling by tabu search,” Ph.D. dissertation, University of Texas at Austin, Austin, TX, 1996.
13 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.
14 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.
15 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.
16 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.
17 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.
18 L. Wang and D. Z. Zheng. “A Modified Genetic Algorithm for Job Shop Scheduling.” International journal of advanced manufacturing technology, pp. 72-76, 2002.
19 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.
20 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.
21 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.
22 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.
23 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.
24 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.
25 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.
26 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.
27 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.
28 B. M. Ombuki, and M. Ventresca. “Local search genetic algorithms for the job shop scheduling problem.” Applied Intelligence, vol. 21, pp. 99-109, 2004.
29 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.
30 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.
31 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.
32 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.
33 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.
34 D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. MA: Addison-Wesley, 1989.
35 D. E. Goldberg and R. Lingle. “Alleles, loci, and the TSP,” in Proceeding of 1st International Conference on Genetic Algorithms, 1985, pp. 154-159.
36 D. C. Mattfeld and R. J. M. Vaessens. “Job shop scheduling benchmarks.” Internet: www mscmga.ms.ic.ac.uk, [Jul. 10, 2008].
Miss Leila Asadzadeh
- Iran
Mr. Kamran Zamanifar
- Iran