A Genetic Algorithm for Solving Scheduling Problem

Volume 5, Issue 2, pp 91-96 http://dx.doi.org/10.22436/jmcs.05.02.03

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 2583 Downloads
• 3324 Views

Authors

Habibeh Nazif - Department of Mathematics, Payame Noor University, IRAN.

Abstract

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

Keywords

• genetic algorithm
• single machine scheduling
• completion time.

MSC

•  90B35
•  90C59

References

• [1] C. C. Aggarwal, J. B. Orlin, R. P. Tai, Optimized crossover for the independent set problem, Operations Research, 45 (1997), 226-234.


• [2] B. H. Ahn, J. H. Hyun, Single facility multi-class job scheduling, Computers & Operations Research, 17 (1990), 265-272.


• [3] R. K. Ahuja, J. B. Orlin, A. Tiwari , A greedy genetic algorithm for the quadratic assignment problem, Computers & Operations Research, 27 (2000), 917-934.


• [4] 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.


• [5] 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.


• [6] 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.


• [7] 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.


• [8] J. Bruno, P. Downey, Complexity of task sequencing with deadlines, set-up times and changeover costs, SIAM Journal on Computing, 7 (1978), 393-404.


• [9] 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.


• [10] 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.


• [11] 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.


• [12] 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.


• [13] J. N. D. Gupta, Single facility scheduling with multiple job classes, European Journal of Operational Research, 33 (1998), 42-45.


• [14] 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.


• [15] C. Koulamas, G. J. Kyparisis, Single-machine scheduling problems with past-sequencedependent setup times, European Journal of Operational Research, 187 (2008), 1045-1049.


• [16] J. Y-T. Leung, Handbook of scheduling: Algorithms, models, and performance analysis, Chapman & Hall/CRC, US (2004)


• [17] 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.


• [18] A. J. Mason, Genetic algorithms and scheduling problems, PhD Dissertation, University of Cambridge, UK (1992)


• [19] 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.


• [20] C. L. Monma, C. N. Potts, On the complexity of scheduling with batch setup time, Operations Research, 37 (1989), 798-804.


• [21] 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.


• [22] C. N. Potts, M. Y. Kovalyov, Scheduling with batching: a review, European Journal of Operational Research, 120 (2000), 228-249.


• [23] W. E. Smith, Various optimizers for single-stage production, Naval Research Logistics Quarterly, 3 (1956), 59-66.


• [24] D. Wang, M. Gen, R. Cheng, Scheduling grouped jobs on single machine with genetic algorithm, Computer and Industrial Engineering, 36 (1999), 309-324.


• [25] 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.