IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v60y2009i2d10.1057_palgrave.jors.2602534.html
   My bibliography  Save this article

A hybrid evolutionary algorithm for the job shop scheduling problem

Author

Listed:
  • G I Zobolas

    (Athens University of Economics and Business)

  • C D Tarantilis

    (Athens University of Economics and Business)

  • G Ioannou

    (Athens University of Economics and Business)

Abstract

In this paper, a hybrid metaheuristic method for the job shop scheduling problem is proposed. The optimization criterion is the minimization of makespan and the solution method consists of three components: a Differential Evolution-based algorithm to generate a population of initial solutions, a Variable Neighbourhood Search method and a Genetic Algorithm to improve the population; the latter two are interconnected. Computational experiments on benchmark data sets demonstrate that the proposed hybrid metaheuristic reaches high quality solutions in short computational times using fixed parameter settings.

Suggested Citation

  • G I Zobolas & C D Tarantilis & G Ioannou, 2009. "A hybrid evolutionary algorithm for the job shop scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(2), pages 221-235, February.
    • Handle: RePEc:pal:jorsoc:v:60:y:2009:i:2:d:10.1057_palgrave.jors.2602534
    DOI: 10.1057/palgrave.jors.2602534
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/palgrave.jors.2602534
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/palgrave.jors.2602534?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. O Etiler & B Toklu & M Atak & J Wilson, 2004. "A genetic algorithm for flow shop scheduling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(8), pages 830-835, August.
    2. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    3. C Gagné & M Gravel & W L Price, 2005. "Using metaheuristic compromise programming for the solution of multiple-objective scheduling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(6), pages 687-698, June.
    4. J-F Cordeau & M Gendreau & G Laporte & J-Y Potvin & F Semet, 2002. "A guide to vehicle routing heuristics," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(5), pages 512-522, May.
    5. Goncalves, Jose Fernando & de Magalhaes Mendes, Jorge Jose & Resende, Mauricio G. C., 2005. "A hybrid genetic algorithm for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 167(1), pages 77-95, November.
    6. James C. Bean, 1994. "Genetic Algorithms and Random Keys for Sequencing and Optimization," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 154-160, May.
    7. Peter J. M. van Laarhoven & Emile H. L. Aarts & Jan Karel Lenstra, 1992. "Job Shop Scheduling by Simulated Annealing," Operations Research, INFORMS, vol. 40(1), pages 113-125, February.
    8. Robert H. Storer & S. David Wu & Renzo Vaccari, 1992. "New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling," Management Science, INFORMS, vol. 38(10), pages 1495-1509, October.
    9. Joseph Adams & Egon Balas & Daniel Zawack, 1988. "The Shifting Bottleneck Procedure for Job Shop Scheduling," Management Science, INFORMS, vol. 34(3), pages 391-401, March.
    10. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    11. David Applegate & William Cook, 1991. "A Computational Study of the Job-Shop Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 3(2), pages 149-156, May.
    12. Éric D. Taillard, 1994. "Parallel Taboo Search Techniques for the Job Shop Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 108-117, May.
    13. Eugeniusz Nowicki & Czeslaw Smutnicki, 1996. "A Fast Taboo Search Algorithm for the Job Shop Problem," Management Science, INFORMS, vol. 42(6), pages 797-813, June.
    14. K S Hindi & K Fleszar & C Charalambous, 2003. "An effective heuristic for the CLSP with set-up times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(5), pages 490-498, May.
    15. Onwubolu, Godfrey & Davendra, Donald, 2006. "Scheduling flow shops using differential evolution algorithm," European Journal of Operational Research, Elsevier, vol. 171(2), pages 674-692, June.
    16. P M E Shutler, 2003. "A priority list based heuristic for the job shop problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(6), pages 571-584, June.
    17. Tasgetiren, M. Fatih & Liang, Yun-Chia & Sevkli, Mehmet & Gencyilmaz, Gunes, 2007. "A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1930-1947, March.
    18. E. H. L. Aarts & P. J. M. van Laarhoven & J. K. Lenstra & N. L. J. Ulder, 1994. "A Computational Study of Local Search Algorithms for Job Shop Scheduling," INFORMS Journal on Computing, INFORMS, vol. 6(2), pages 118-125, May.
    19. Paul M E Shutler, 2004. "A priority list based heuristic for the job shop problem: part 2 tabu search," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(7), pages 780-784, July.
    20. Fleszar, Krzysztof & Hindi, Khalil S., 2004. "Solving the resource-constrained project scheduling problem by a variable neighbourhood search," European Journal of Operational Research, Elsevier, vol. 155(2), pages 402-413, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhang, Rui & Chang, Pei-Chann & Wu, Cheng, 2013. "A hybrid genetic algorithm for the job shop scheduling problem with practical considerations for manufacturing costs: Investigations motivated by vehicle production," International Journal of Production Economics, Elsevier, vol. 145(1), pages 38-52.
    2. Repoussis, Panagiotis P. & Paraskevopoulos, Dimitris C. & Vazacopoulos, Alkiviadis & Hupert, Nathaniel, 2016. "Optimizing emergency preparedness and resource utilization in mass-casualty incidents," European Journal of Operational Research, Elsevier, vol. 255(2), pages 531-544.
    3. Ławrynowicz Anna, 2011. "Genetic Algorithms for Solving Scheduling Problems in Manufacturing Systems," Foundations of Management, Sciendo, vol. 3(2), pages 7-26, January.
    4. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. F. Guerriero, 2008. "Hybrid Rollout Approaches for the Job Shop Scheduling Problem," Journal of Optimization Theory and Applications, Springer, vol. 139(2), pages 419-438, November.
    2. Da Col, Giacomo & Teppan, Erich C., 2022. "Industrial-size job shop scheduling with constraint programming," Operations Research Perspectives, Elsevier, vol. 9(C).
    3. Edzard Weber & Anselm Tiefenbacher & Norbert Gronau, 2019. "Need for Standardization and Systematization of Test Data for Job-Shop Scheduling," Data, MDPI, vol. 4(1), pages 1-21, February.
    4. T. C. E. Cheng & Bo Peng & Zhipeng Lü, 2016. "A hybrid evolutionary algorithm to solve the job shop scheduling problem," Annals of Operations Research, Springer, vol. 242(2), pages 223-237, July.
    5. P M E Shutler, 2003. "A priority list based heuristic for the job shop problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(6), pages 571-584, June.
    6. Susana Fernandes & Helena Ramalhinho-Lourenço, 2007. "A simple optimised search heuristic for the job-shop scheduling problem," Economics Working Papers 1050, Department of Economics and Business, Universitat Pompeu Fabra.
    7. Ramesh Bollapragada & Norman M. Sadeh, 2004. "Proactive release procedures for just‐in‐time job shop environments, subject to machine failures," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(7), pages 1018-1044, October.
    8. Sels, Veronique & Craeymeersch, Kjeld & Vanhoucke, Mario, 2011. "A hybrid single and dual population search procedure for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 215(3), pages 512-523, December.
    9. Jain, A. S. & Meeran, S., 1999. "Deterministic job-shop scheduling: Past, present and future," European Journal of Operational Research, Elsevier, vol. 113(2), pages 390-434, March.
    10. Pierre Hansen & Nenad Mladenović & José Moreno Pérez, 2010. "Variable neighbourhood search: methods and applications," Annals of Operations Research, Springer, vol. 175(1), pages 367-407, March.
    11. Demirkol, Ebru & Mehta, Sanjay & Uzsoy, Reha, 1998. "Benchmarks for shop scheduling problems," European Journal of Operational Research, Elsevier, vol. 109(1), pages 137-141, August.
    12. Reinhard Bürgy, 2017. "A neighborhood for complex job shop scheduling problems with regular objectives," Journal of Scheduling, Springer, vol. 20(4), pages 391-422, August.
    13. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    14. Diarmuid Grimes & Emmanuel Hebrard, 2015. "Solving Variants of the Job Shop Scheduling Problem Through Conflict-Directed Search," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 268-284, May.
    15. Paul M E Shutler, 2004. "A priority list based heuristic for the job shop problem: part 2 tabu search," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(7), pages 780-784, July.
    16. Z C Zhu & K M Ng & H L Ong, 2010. "A modified tabu search algorithm for cost-based job shop problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(4), pages 611-619, April.
    17. Jelke J. Hoorn, 2018. "The Current state of bounds on benchmark instances of the job-shop scheduling problem," Journal of Scheduling, Springer, vol. 21(1), pages 127-128, February.
    18. Murovec, Boštjan, 2015. "Job-shop local-search move evaluation without direct consideration of the criterion’s value," European Journal of Operational Research, Elsevier, vol. 241(2), pages 320-329.
    19. Goncalves, Jose Fernando & de Magalhaes Mendes, Jorge Jose & Resende, Mauricio G. C., 2005. "A hybrid genetic algorithm for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 167(1), pages 77-95, November.
    20. Bryan A. Norman & James C. Bean, 1999. "A genetic algorithm methodology for complex scheduling problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 46(2), pages 199-211, March.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:pal:jorsoc:v:60:y:2009:i:2:d:10.1057_palgrave.jors.2602534. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.palgrave-journals.com/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.