%0 Journal Article %T A Genetic Algorithm for Solving Scheduling Problem %A Nazif, Habibeh %J Journal of Mathematics and Computer Science %D 2012 %V 5 %N 2 %@ ISSN 2008-949X %F Nazif2012 %X This paper considers a single machine family scheduling problem where jobs are partitioned into families and setup is required between these families. The objective is to find an optimal schedule that minimizes the total weighted completion time of the given jobs in the presence of the sequence independent family setup times. This problem has been proven to be strongly NP-hard. We introduce a genetic algorithm that employs an innovative crossover operator that utilizes an undirected bipartite graph to find the best offspring solution among an exponentially large number of potential offspring. Computational results are presented. The proposed algorithm is shown to be superior when compared with other local search methods namely the dynamic length tabu search and randomized steepest descent method. %9 journal article %R 10.22436/jmcs.05.02.03 %U http://dx.doi.org/10.22436/jmcs.05.02.03 %P 91-96 %0 Journal Article %T Optimized crossover for the independent set problem %A C. C. Aggarwal %A J. B. Orlin %A R. P. Tai %J Operations Research %D 1997 %V 45 %F Aggarwal1997 %0 Journal Article %T Single facility multi-class job scheduling %A B. H. Ahn %A J. H. Hyun %J Computers & Operations Research %D 1990 %V 17 %F Ahn1990 %0 Journal Article %T A greedy genetic algorithm for the quadratic assignment problem %A R. K. Ahuja %A J. B. Orlin %A A. Tiwari %J Computers & Operations Research %D 2000 %V 27 %F Ahuja2000 %0 Journal Article %T A review of scheduling research involving setup considerations %A A. Allahverdi %A J. N. D. Gupta %A T. Aldowaisan %J OMEGA, International Journal of Management Science %D 1999 %V 27 %F Allahverdi1999 %0 Journal Article %T A survey of scheduling problems with setup times or costs %A A. Allahverdi %A C. T. Ng %A T. C. E. Cheng %A M. Y. Kovalyov %J European Journal of Operational Research %D 2008 %V 187 %F Allahverdi2008 %0 Journal Article %T Finding large cliques in arbitrary graphs by bipartite matching %A E. Balas %A W. Niehaus %J In: Clique, Coloring and Satisfiability: Second DIMACS Implementation Challenge, D.S., Johnson and M.A., Trick, Eds. %D 1996 %V %F Balas1996 %0 Journal Article %T Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems %A E. Balas %A W. Niehaus %J Journal of Heuristics %D 1998 %V 4 %F Balas1998 %0 Journal Article %T Complexity of task sequencing with deadlines, set-up times and changeover costs %A J. Bruno %A P. Downey %J SIAM Journal on Computing %D 1978 %V 7 %F Bruno1978 %0 Journal Article %T Local search heuristics for single machine scheduling with batch set-up times to minimize total weighted completion time %A H. A. J. Crauwels %A C. N. Potts %A L. N. Van Wassenhove %J Annals of Operations Research %D 1997 %V 70 %F Crauwels1997 %0 Journal Article %T Branch and bound algorithm for single machine scheduling with batch set-up times to minimize total weighted completion time %A H. A. J. Crauwels %A A. M. A. Hariri %A C. N. Potts %A L. N. Van Wassenhove %J Annals of Operations Research %D 1998 %V 83 %F Crauwels1998 %0 Journal Article %T Lower bounds and algorithms for flowtime minimization on a single machine with set-up times %A S. Dunstall %A A. Wirth %A K. Baker %J Journal of Scheduling %D 2000 %V 3 %F Dunstall2000 %0 Journal Article %T Optimization and approximation in deterministic sequencing and scheduling: a survey %A R. L. Graham %A E. L. Lawler %A J. K. Lenstra %A A. H. G. Rinnooy Kan %J Annals of Discrete Mathematics %D 1979 %V 5 %F Graham1979 %0 Journal Article %T Single facility scheduling with multiple job classes %A J. N. D. Gupta %J European Journal of Operational Research %D 1998 %V 33 %F Gupta1998 %0 Journal Article %T Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with One planned setup period %A I. Kacem %A C. Chu %J European Journal of Operational Research %D 2008 %V 187 %F Kacem2008 %0 Journal Article %T Single-machine scheduling problems with past-sequencedependent setup times %A C. Koulamas %A G. J. Kyparisis %J European Journal of Operational Research %D 2008 %V 187 %F Koulamas2008 %0 Book %T Handbook of scheduling: Algorithms, models, and performance analysis %A J. Y-T. Leung %D 2004 %I Chapman & Hall/CRC %C US %F Leung2004 %0 Journal Article %T A genetic algorithms for single machine family scheduling problem, Proceedings of 3rd IMT-GT 2007 Regional Conference on Mathematics %A L. S. Lee %A C. N. Potts %A J. A. Bennell %J Statistics and Applications %D 2007 %V %F Lee2007 %0 Book %T Genetic algorithms and scheduling problems %A A. J. Mason %D 1992 %I PhD Dissertation, University of Cambridge %C UK %F Mason1992 %0 Journal Article %T Minimizing flow time on a single machine with job classes and setup times %A A. J. Mason %A E. J. Anderson %J Naval Research Logistics %D 1991 %V 38 %F Mason1991 %0 Journal Article %T On the complexity of scheduling with batch setup time %A C. L. Monma %A C. N. Potts %J Operations Research %D 1989 %V 37 %F Monma1989 %0 Journal Article %T A genetic algorithm on single machine scheduling problem to minimise total weighted completion time %A H. Nazif %A L. S. Lee %J European Journal of Scientific Research %D 2009 %V 35 %F Nazif2009 %0 Journal Article %T Scheduling with batching: a review %A C. N. Potts %A M. Y. Kovalyov %J European Journal of Operational Research %D 2000 %V 120 %F Potts2000 %0 Journal Article %T Various optimizers for single-stage production %A W. E. Smith %J Naval Research Logistics Quarterly %D 1956 %V 3 %F Smith1956 %0 Journal Article %T Scheduling grouped jobs on single machine with genetic algorithm %A D. Wang %A M. Gen %A R. Cheng %J Computer and Industrial Engineering %D 1999 %V 36 %F Wang1999 %0 Journal Article %T A new heuristic for a single machine scheduling problem with set-up times %A D. Williams %A A. Wirth %J Journal of the Operational Research Society %D 1996 %V 47 %F Williams1996