A Genetic Algorithm for Solving Scheduling Problem
- Department of Mathematics, Payame Noor University, IRAN.
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.
Share and Cite
Habibeh Nazif, A Genetic Algorithm for Solving Scheduling Problem, Journal of Mathematics and Computer Science, 5 (2012), no. 2, 91-96
Nazif Habibeh, A Genetic Algorithm for Solving Scheduling Problem. J Math Comput SCI-JM. (2012); 5(2):91-96
Nazif, Habibeh. "A Genetic Algorithm for Solving Scheduling Problem." Journal of Mathematics and Computer Science, 5, no. 2 (2012): 91-96
- genetic algorithm
- single machine scheduling
- completion time.
C. C. Aggarwal, J. B. Orlin, R. P. Tai, Optimized crossover for the independent set problem, Operations Research, 45 (1997), 226-234.
B. H. Ahn, J. H. Hyun, Single facility multi-class job scheduling, Computers & Operations Research, 17 (1990), 265-272.
R. K. Ahuja, J. B. Orlin, A. Tiwari , A greedy genetic algorithm for the quadratic assignment problem, Computers & Operations Research, 27 (2000), 917-934.
A. Allahverdi, J. N. D. Gupta, T. Aldowaisan, A review of scheduling research involving setup considerations, OMEGA, International Journal of Management Science, 27 (1999), 219-239.
A. Allahverdi, C. T. Ng, T. C. E. Cheng, M. Y. Kovalyov, A survey of scheduling problems with setup times or costs, European Journal of Operational Research, 187 (2008), 985-1032.
E. Balas, W. Niehaus, Finding large cliques in arbitrary graphs by bipartite matching, In: Clique, Coloring and Satisfiability: Second DIMACS Implementation Challenge, D.S., Johnson and M.A., Trick, Eds., (1996), 29-53.
E. Balas, W. Niehaus, Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems, Journal of Heuristics, 4 (1998), 107-122.
J. Bruno, P. Downey, Complexity of task sequencing with deadlines, set-up times and changeover costs, SIAM Journal on Computing, 7 (1978), 393-404.
H. A. J. Crauwels, C. N. Potts, L. N. Van Wassenhove, Local search heuristics for single machine scheduling with batch set-up times to minimize total weighted completion time, Annals of Operations Research, 70 (1997), 261-279.
H. A. J. Crauwels, A. M. A. Hariri, C. N. Potts, L. N. Van Wassenhove, Branch and bound algorithm for single machine scheduling with batch set-up times to minimize total weighted completion time, Annals of Operations Research, 83 (1998), 59-76.
S. Dunstall, A. Wirth, K. Baker, Lower bounds and algorithms for flowtime minimization on a single machine with set-up times , Journal of Scheduling, 3 (2000), 51-69.
R. L. Graham, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5 (1979), 287-326.
J. N. D. Gupta, Single facility scheduling with multiple job classes, European Journal of Operational Research, 33 (1998), 42-45.
I. Kacem, C. Chu, Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with One planned setup period, European Journal of Operational Research, 187 (2008), 1080-1089.
C. Koulamas, G. J. Kyparisis, Single-machine scheduling problems with past-sequencedependent setup times, European Journal of Operational Research, 187 (2008), 1045-1049.
J. Y-T. Leung, Handbook of scheduling: Algorithms, models, and performance analysis, Chapman & Hall/CRC, US (2004)
L. S. Lee, C. N. Potts, J. A. Bennell , A genetic algorithms for single machine family scheduling problem, Proceedings of 3rd IMT-GT 2007 Regional Conference on Mathematics , Statistics and Applications, (2007), 488-493.
A. J. Mason, Genetic algorithms and scheduling problems, PhD Dissertation, University of Cambridge, UK (1992)
A. J. Mason, E. J. Anderson, Minimizing flow time on a single machine with job classes and setup times, Naval Research Logistics, 38 (1991), 333-350.
C. L. Monma, C. N. Potts, On the complexity of scheduling with batch setup time, Operations Research, 37 (1989), 798-804.
H. Nazif, L. S. Lee, A genetic algorithm on single machine scheduling problem to minimise total weighted completion time, European Journal of Scientific Research, 35 (2009), 444-452.
C. N. Potts, M. Y. Kovalyov, Scheduling with batching: a review, European Journal of Operational Research, 120 (2000), 228-249.
W. E. Smith, Various optimizers for single-stage production, Naval Research Logistics Quarterly, 3 (1956), 59-66.
D. Wang, M. Gen, R. Cheng, Scheduling grouped jobs on single machine with genetic algorithm, Computer and Industrial Engineering, 36 (1999), 309-324.
D. Williams, A. Wirth, A new heuristic for a single machine scheduling problem with set-up times, Journal of the Operational Research Society, 47 (1996), 175-180.