skip to main content
10.1145/1143997.1144101acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
Article

Combining simplex with niche-based evolutionary computation for job-shop scheduling

Published: 08 July 2006 Publication History

Abstract

We propose a hybrid algorithm (called ALPINE) between Genetic Algorithm and Dantzig's Simplex method to approximate optimal solutions for the Flexible Job-Shop Problem. Locally, Simplex is extended for the JSP linear program to reduce the number of infeasible solutions while solution quality is improved with an operation order search. Globally, a niche-based evolutionary strategy is employed to gain parallelization while solution diversity is maintained in two ways; composite dispatching rule-based population initialization and memory-based machine assignment. Performance results on benchmark problems show that ALPINE outperforms existing hybrid techniques with a new global optima found for the 10x7 Flexible Job Shop Problem.

References

[1]
Branke, J., "Memory enhanced evolutionary algorithms for changing optimization problems," Proc. IEEE Congress on Evolutionary Computation, pp. 1875--1882, 1999.
[2]
Chelouah, R. and Siarry, P., "Genetic and Nelder-Mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions," European Journal of Operational Research, vol. 148, pp. 335--348, 2003.
[3]
Foo, Y. S. and Takefuji, T., "Integer linear programming neural networks for job-shop scheduling," IEEE International Conference on Neural Networks, vol. 2, pp 341--348, 1988.
[4]
Gonçalves, J. F., Mendes, J. J. M., Resende, M. G. C., "A hybrid genetic algorithm for the job shop scheduling problem," European Journal of Operational Research, vol. 167(1), pp. 77--95, 2005.
[5]
Ho, N. B. and Tay, J. C., "GENACE: An Efficient Cultural Algorithm for solving the Flexible Job-Shop Problem," Proc. IEEE Congress on Evolutionary Computation, pp. 1759--1766, 2004.
[6]
Jain, A. S. and Meeran, S., "Job Shop Scheduling using Neural Networks," International Journal of Production Research, vol. 36(5), pp 1249--1272, 1998.
[7]
Kacem, I., Hammadi, S., Borne, P., "Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems," IEEE Transactions on Systems, Man and Cybernetics, vol. 32(1), pp. 1--13, 2002.
[8]
Kacem, I., Hammadi, S., Borne, P., "Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic" Mathematics and Computers in Simulation, vol. 60, pp. 245--276, 2002.
[9]
Kacem, I., "Genetic algorithm for the flexible job-shop scheduling problem," Proc. IEEE International Conference on Systems, Man and Cybernetics, vol. 4, pp. 3464--3469, 2003.
[10]
Mathias, K. E., Whitley, L. D., Stork, C., Kusuma, T., "Staged hybrid genetic search for seismic data imaging," Proc. The First IEEE Conference on Evolutionary Computation, vol.1, pp. 356--361, 1994.
[11]
Mesghouni, K., Hammadi, S., Borne, P., "Evolution programs for job-shop scheduling," Proc. IEEE International Conference on Computational Cybernetics and Simulation, vol. 1, pp. 720--725, 1997.
[12]
Panek, S., Stursberg, O., Engell, S., "Optimization of timed automata models using mixed integer programming," Formal Modeling And Analysis of Timed Systems: First International Workshop, vol. 2791, pp. 73--87, 2004.
[13]
Tay, J. C. and Wibowo, D., "An Effective Chromosome Representation for Evolving Flexible Job Shop Schedules," Genetic and Evolutionary Computation Conference, vol. 2, pp 210--221, 2004.
[14]
Wei, L. and Zhao, M., "A niche hybrid genetic algorithm for global optimization of continuous multimodal functions," Applied Mathematics and Computation, vol. 160, pp. 649--661, 2005.
[15]
Xia, W. and Wu, Z., "An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems" Computers & Industrial Engineering, vol. 48(2), pp. 409--425, 2005.
[16]
Yen, J., Liao, J. C., Bogju, L., Randolph, D., "A hybrid approach to modeling metabolic systems using a genetic algorithm and simplex method," IEEE Transactions on Systems, Man and Cybernetics, vol. 28, pp. 173--191, 1998.

Cited By

View all
  • (2010)Specialized Evolutionary Algorithm for Production Scheduling in Complex Correlated Manufacturing SystemApplied Mechanics and Materials10.4028/www.scientific.net/AMM.20-23.22620-23(226-231)Online publication date: Jan-2010

Index Terms

  1. Combining simplex with niche-based evolutionary computation for job-shop scheduling

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation
    July 2006
    2004 pages
    ISBN:1595931864
    DOI:10.1145/1143997
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 08 July 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. flexible job-shop scheduling
    2. hybrid evolutionary computation
    3. linear programming
    4. niche-based strategy

    Qualifiers

    • Article

    Conference

    GECCO06
    Sponsor:
    GECCO06: Genetic and Evolutionary Computation Conference
    July 8 - 12, 2006
    Washington, Seattle, USA

    Acceptance Rates

    GECCO '06 Paper Acceptance Rate 205 of 446 submissions, 46%;
    Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)4
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 22 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2010)Specialized Evolutionary Algorithm for Production Scheduling in Complex Correlated Manufacturing SystemApplied Mechanics and Materials10.4028/www.scientific.net/AMM.20-23.22620-23(226-231)Online publication date: Jan-2010

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media