Back
 AJIBM  Vol.6 No.6 , June 2016
A Study of Crossover Operators for Genetic Algorithm and Proposal of a New Crossover Operator to Solve Open Shop Scheduling Problem
Abstract: Open Shop Scheduling Problem (OSSP) is a combinatorial optimization problem for more than two machines and n jobs. Open Shop Scheduling Problem is another kind of scheduling problem along with flow shop and job shop scheduling problems. The open shop scheduling problem involves scheduling of jobs, where the sequence of the operations of each job can be arbitrarily chosen and need not be same. This means that the operations of the jobs can be performed in any sequence. In the absence of sequences for the jobs, for a given set of jobs, finding different parameters like maximum completion time Cmax becomes highly difficult and complex. One can use complete enumeration method or branch and bound method to solve this problem optimally for small and medium size problems. The large size problems of open shop problem with more than two machines and with n jobs can be solved by either a heuristic or meta-heuristics such as genetic algorithm, simulated annealing algorithm, etc. to obtain very near optimal solution. The performance of the genetic algorithm is affected by crossover operator performed between two parent chromosomes. Hence, this paper explores various crossover operators used, while using evolutionary based genetic algorithm to solve open shop scheduling problems. It further attempts to propose a new crossover operator using three chromosomes.
Cite this paper: Anand, E. and Panneerselvam, R. (2016) A Study of Crossover Operators for Genetic Algorithm and Proposal of a New Crossover Operator to Solve Open Shop Scheduling Problem. American Journal of Industrial and Business Management, 6, 774-789. doi: 10.4236/ajibm.2016.66071.
References

[1]   Panneerselvam, R. (2012) Production and Operations Management. Third Edition, PHI Learning, New Delhi.

[2]   Panneerselvam, R. (2006) Operations Research. Second Edition, PHI Learning, New Delhi.

[3]   Panneerselvam, R. (1999) Heuristic for Moderated Job Shop Scheduling Problem to Minimize Makespan. Industrial Engineering Journal, 28, 26-29.

[4]   Panneerselvam, R. (2016) Design and Analysis of Algorithms. Second Edition, PHI Learning, New Delhi.

[5]   Anand, E. and Panneerselvam, R. (2015) Literature Review of Open Shop Scheduling Problem. Intelligent Information Management, 7, 33-52.
http://dx.doi.org/10.4236/iim.2015.71004

[6]   Senthilkumar, P. and Shahabudeen, P. (2006) GA Based Heuristic for the Open Job Shop Scheduling Problem. International Journal of Advanced Manufacturing Technology, 30, 297-301.
http://dx.doi.org/10.1007/s00170-005-0057-2

[7]   Louis, S.J. and Xu, Z.J. (1996) Genetic Algorithms for Open Shop Scheduling and Re-Scheduling. ISCA 11th International Conference on Computers and Their Applications, San Francisco, 7-9 March 1996, 99-102.

[8]   Zobolas, G.I., Tarantilis, C.D. and Ioannou, G. (2009) Solving the Open Shop Scheduling Problem via a Hybrid Genetic-Variable Neighborhood Search Algorithm. Cybernetics and Systems: An International Journal, 40, 259-285.
http://dx.doi.org/10.1080/01969720902830322

[9]   Taillard, E. (1993) Benchmarks for Basic Scheduling Problems. European Journal of Operational Research, 64, 278-285.
http://dx.doi.org/10.1016/0377-2217(93)90182-M

[10]   Brucker, P., Hurink, J., Jurisch, B. and Wostmann, B. (1997) A Branch and Bound Algorithm for the Open Shop Problem. Discrete Applied Mathematics, 76, 43-59.
http://dx.doi.org/10.1016/S0166-218X(96)00116-3

[11]   Gueret, C. and Prins, C. (1999) A New Lower Bound for the Open Shop Problems. Annals of Operations Research, 92, 165-183.
http://dx.doi.org/10.1023/A:1018930613891

[12]   Kokosinski, Z. and Studzienny, L. (2007) Hybrid Genetic Algorithms for the Open Shop Scheduling Problem. International Journal of Computer Science and Network Security, 7, 136-145.

[13]   Liaw, C.F. (2000) A Hybrid Genetic Algorithm for the Open Shop Scheduling Problem. European Journal of Operational Research, 124, 28-42.
http://dx.doi.org/10.1016/S0377-2217(99)00168-X

[14]   Andresen, M., Brasel, H., Marc, M., Tusch, J., Werner, F. and Willenius, P. (2008) Simulated Annealing and Genetic Algorithms for Minimizing Mean Flow Time in an Open Shop. Mathematical and Computer Modelling, 48, 1279-1293.
http://dx.doi.org/10.1016/j.mcm.2008.01.002

[15]   Matta, M.E. (2009) A Genetic Algorithm for the Proportionate Multiprocessor Open Shop. Computers & Operations Research, 36, 2601-2618.
http://dx.doi.org/10.1016/j.cor.2008.11.009

[16]   Panneerselvam, R. (2012) Research Methodology. Second Edition, PHI Learning, New Delhi.

 
 
Top