Abstract
The n-job, m-machine job shop scheduling (JSS) problem is one of the general production scheduling problems. Many existing heuristics give solutions for small size problems with near optimal solutions. This paper deals with the criterion of makespan minimization for the job shop scheduling of different size problems. The proposed computational method of artificial immune system algorithm (AIS) is used for finding optimal makespan values of different size problems. The artificial immune system algorithm is tested with 130 benchmark problems [10 (ORB1-ORB5 & ARZ5-ARZ9), 40 (LA01-LA40) and 80 (TA01-TA80)]. The results show that the AIS algorithm is an efficient and effective algorithm which gives better results than the Tabu search shifting bottleneck procedure (TSSB) as well as the best solution of shifting bottleneck procedure ( SB-GLS1 ) of Balas and Vazacopoulos.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Abbreviations
- AIS:
-
Best solution of AIS algorithm
- m:
-
Number of machines
- MRE:
-
Mean relative error in percent for a set of problems
- n:
-
Number of jobs
- Opt (LB UB):
-
The optimal value of known best lower and Upper bound, from OR-Library
- RESB-GLS1 :
-
Percent relative error by SB-GLS1
- RETSSB :
-
Percent relative error by TSSB
- REAIS :
-
Percent relative error by AIS
- RE:
-
Relative error in percent
- SB-GLS1:
-
Best solution of SB-GLS1 procedure of Balas and Vazacopoulos
- TSSB:
-
Best solution of TSSB
- Tav:
-
Average computing time in seconds
References
Bruker P (1995) Scheduling algorithms 2nd edn. Springer, Berlin Heidelberg New York
Garey M, et al (1976) The complexity of flow shop and job shop scheduling. Math Oper Res 1:117–129
Erschler JF, Roubellat JP, Vernhes (1976) Finding some essential characteristics of the feasible solutions for a scheduling problem. Oper Res 24:774–783
French S (1982) Sequencing and scheduling: An introduction to the mathematics of the job shop. Wiley, New York
Carlier J, Pison E (1989) An algorithm for solving the job shop problem. Manage Sci 35:164–176
Bruker P et al (1994) A branch and bound algorithm for job shop problem. Discrete Appl Math 49:107–127
Blazewickz J (1996) The job shop scheduling problem: Conventional and new solutions techniques. Eur J Oper Res pp 931–30
Pezzella F, Merelli E (2000) A tabu search method guided by shifting bottleneck for the job shop scheduling problem. Eur J Oper Res 120:297–310
Balas E, Vazacopoulos A (1994) Guided local search with shifting bottleneck for job shop scheduling. Tech Rep Management Science Research Report MSRR-609, GSIA Carnegie Mellon University, Pittsburgh
Forrest S, Perelson A, Allen L, Cherukuri R (1994) Self-nonself discrimination in a computer. Proc IEEE Symposium on Research in Security and Privacy, IEEE Computer Society Press, Los Alamitos, CA, pp 202–212
Forrest S, Hoffmeyr SA (2000) Engineering an immune system. Graft 4(5):5–9
Dasgupta D, Forrest S (1996) Novelty detection in time series data using ideas from immunology. Proc ISCA’96, Reno, Nevada, June 1996, pp 19–21
Dasgupta D, Forrest S (1999) Artificial immune systems in industrial applications. Proc Second International Conference on Intelligent Processing and Manufacturing Materials (IPMM), Honolulu, July 1999, pp10–15
De Castro LN, Von Zuben FJ (2000) The clonal selection algorithm with engineering applications. Proc Workshop on GECCO 2000, Las Vegas, 8-12 July 2000, pp 36–37
Trojanowski K, Wierzchon ST (2002) Searching for memory in artificial immune system. Proc 11th International Symposium on Intelligent Information Systems, June 2002, pp 3–6
Nasaroui O, Dasgupta D, Gonzales F (2002) The promise and challenges of artificial immune system based web-usage mining: preliminary results. Proc Workshop on Web Analytics at Second SIAM International Conference on Data Mining (SDM), Arlington, VA, April 2002, pp 11–13
Timmis J, Neal MJ (2000) A resource limited artificial immune system for data analysis. Research and Development in Intelligent Systems XVII, Proceedings of the ES2000, Cambridge, UK, pp 19–32
Yang S, Wang D (2001) A new adaptive neural network and heuristics hybrid approach for job shop scheduling. Comput Oper Res 28:955–971
Engin O, Doyen A (2004) A new approach to solve hybrid flow shop scheduling problems by artificial immune system. Future Generation Comput Syst 20:1083–1095
Costa AM, Vargas PA, Von Zuben FJ, França PM (2002) Makespan minimization on parallel processors: an immune based approach. Proc Special Sessions on Artificial Immune Systems, IEEE World Congress on Computational Intelligence, Honolulu, HI, pp 115–123
Zheng H, Zhang J, Nahavandi S (2004) Learning to detect texture objects by artificial immune approaches. Future Generation Comput Systems 20:1197–1208
Huang S (1999) Enhancement of thermal unit commitment using immune algorithms based optimization approaches. Electr Power Energy Syst 21:245–252
Zheng H, Zhang J, Nahavandi S (2004) Learning to detect texture objects by artificial immune approaches. Future Generation Comput Syst 20:1197–1208
Attux RRF, et al (2003) A paradigm for blind IIR equalization using the constant modules criterion and an artificial immune network. IEEE XIII Workshop on Neural Networks for Signal Processing, pp 839–849
May P, Mander K, Timmis J (2003) Mutation Testing: An Artificial Immune System Approach. Computing Laboratory, University of Kent, Canterbury, Kent, CT2 7NF
De Castro LN, Von Zuben FJ (1999) Artificial immune systems, Part 1, basic theory and applications. Technical Report, TR-DCA 01/99
Applegate D, Cook W (1991) A computational study of the job shop scheduling problem. ORSA J Comput 3:149–156
Adams J, Balas E, Zawack D (1988) The shifting bottleneck procedure for job shop scheduling. Manage Sci 34:391–401
Lawrence S (1984) Supplement to resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques. Tech Rep, GSIA, Carnegie Mellon Univ
Taillard E (1993) Benchmarks for basic scheduling problems. Eur J Oper Res 64:278–285
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chandrasekaran, M., Asokan, P., Kumanan, S. et al. Solving job shop scheduling problems using artificial immune system. Int J Adv Manuf Technol 31, 580–593 (2006). https://doi.org/10.1007/s00170-005-0226-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-005-0226-3