Indian Journal of Science and Technology

Open Access Open Access  Restricted Access Subscription Access

Solving Flexible Job-shop Scheduling Problem Using Clonal Selection Algorithm


Affiliations
1 Department of Industrial Engineering, Islamic Azad University Ramsar Branch , P.O. Box 46819-66856, Ramsar, Iran, Islamic Republic of
2 Young Researchers Club, Neyshabur Branch, Islamic Azad University, Neyshabur, Iran, Islamic Republic of
3 Department of Managment, Islamic Azad University Ramsar Branch , P.O. Box 46819-66856, Ramsar, Iran, Islamic Republic of
 

In this paper we present a clonal selection algorithm (CSA) to solve the Flexible Job-shop Scheduling Problem (FJSP). The scheduling objective minimizes the maximal completion time of all the operations, which is denoted by Makespan. The performance of CSA is evaluated in comparison with Lingo 8 software. Experimental results prove that the CSA can be used to solve FJSP effectively.

Keywords

Flexible Job-shop Scheduling Problem, Clonal Selection Algorithm, Makespan
User

  • Barnes JW and Chambers JB (1996) Flexible job shop scheduling by tabu search. In: Graduate program in operations research and industrial engineering, The University of Texas at Austin, Technical report series. ORP. pp: 96-09.

  • Bean J (1994) Genetic algorithms and random keys for sequencing and optimization. Operations Res. Soc. Am. J.Computing (ORSA). 6, 154–160.

  • Chen H, Ihlow J and Lehmann C (1999) A genetic algorithm for flexible job-shop scheduling. In: Proc. of the Intl. Conf. Robotics & Automation. NY. IEEE. pp. 1120-1125.

  • Defersha FM and Chen M (2009) A coarse-grain parallel genetic algorithm for flexible job-shop scheduling with lot streaming. Proc. Intl. Conf. Compu. Sci. & Engg. 1, 201–208.

  • Gao J, Sun L and Gen M (2008) A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Compu. & Operations Res. 35, 2892–2907.

  • Garey MR, Johnson DS and Sethi R (1976) The complexity of flowshop and jobshop scheduling. Maths. Operations Res. 1, 117–129.

  • Gonçalves JF, Mendes JJM and Resende MGC (2005) A hybrid genetic algorithm for the job shop scheduling problem. Europ. J. Operational Res. 167(1), 77–95.

  • Jain AS and Meeran S (1999) Deterministic job-shop scheduling: Past, present and future. Europ. J. Operational Res. 113, 390–434.

  • Kacem I, Hammadi S and Borne P (2002) Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man and Cybernetics Part C. Appl. & Rev. 32(1), 1-13.

  • Kobayashi S, Ono I and Yamamura M (1995) An efficient genetic algorithm for job shop scheduling problems. In LJ. Eshelman (Ed.). Proce. 6th Intl. conf. on genetic algorithms. San Francisco, CA:Morgan Kaufman Publ. pp: 506–511.

  • Kumar V, Prakash MK Tiwari and Felix T S Chan (2008) Stochastic make-to-stock inventory deployment problem: an endosymbiotic psychoclonal algorithm based approach. Intl. J. Production Res. 44(11), 2245–2263.

  • Lourenço HR (1995) Local optimization and the jobshop scheduling problem. Eur. J. Operational Res. 83, 347–364.

  • Mastrolilli M and Gambardella LM (2000) Effective neighborhood functions for the flexible job shop problem. J. Scheduling. 3(1), 3–20.

  • Najid M, Stephane DP and Zaidat A (2002) A modified simulated annealing method for flexible job shop scheduling problem. Proce. 2002 Intl. Conf. Sys. Man & Cybernetics. NY. IEEE. pp: 89-94.

  • Nowicki E and Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Managt. Sci. 42(6), 797–813.

  • Pezzella F and Merelli E (2000) A tabu search method guided by shifting bottleneck for the job shop scheduling problem. Eur. J. Operational Res. 120(2), 297–310.

  • Pezzella F, Morganti G and Ciaschetti G (2008) A genetic algorithm for the flexible job-shop scheduling problem. Compu. & Operations Res. 35, 3202–3212.

  • Sun D, Batta R and Lin L (1995) Effective job shop scheduling through active chain manipulation. Compu. & Operations Res. 22(2), 159–172.

  • Wang L and Zheng DZ (2001) An effective hybrid optimization strategy for jobshop scheduling problems. Compu. & Operations Res. 28, 585–596.

  • Xia W and Wu Z (2005) An effective hybrid optimization approach for multiobjective flexible jobshop scheduling problems. Compu. & Indust. Engg. 48, 409–425.

  • Yazdani M, Amiri M and Zandieh M (2010) Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Sys. with Appli. Intl. J. 37(1), 678–687.


Abstract Views: 433

PDF Views: 220




  • Solving Flexible Job-shop Scheduling Problem Using Clonal Selection Algorithm

Abstract Views: 433  |  PDF Views: 220

Authors

Mohammad Akhshabi
Department of Industrial Engineering, Islamic Azad University Ramsar Branch , P.O. Box 46819-66856, Ramsar, Iran, Islamic Republic of
Mostafa Akhshabi
Young Researchers Club, Neyshabur Branch, Islamic Azad University, Neyshabur, Iran, Islamic Republic of
Javad Khalatbari
Department of Managment, Islamic Azad University Ramsar Branch , P.O. Box 46819-66856, Ramsar, Iran, Islamic Republic of

Abstract


In this paper we present a clonal selection algorithm (CSA) to solve the Flexible Job-shop Scheduling Problem (FJSP). The scheduling objective minimizes the maximal completion time of all the operations, which is denoted by Makespan. The performance of CSA is evaluated in comparison with Lingo 8 software. Experimental results prove that the CSA can be used to solve FJSP effectively.

Keywords


Flexible Job-shop Scheduling Problem, Clonal Selection Algorithm, Makespan

References





DOI: https://doi.org/10.17485/ijst%2F2011%2Fv4i10%2F30166