IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v194y2009i3p650-662.html
   My bibliography  Save this article

A filter-and-fan approach to the job shop scheduling problem

Author

Listed:
  • Rego, César
  • Duarte, Renato

Abstract

The job shop scheduling problem (JSSP) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new heuristic algorithm for the JSSP that effectively combines the classical shifting bottleneck procedure (SBP) with a dynamic and adaptive neighborhood search procedure. Our new search method, based on a filter-and-fan (F&F) procedure, uses the SBP as a subroutine to generate a starting solution and to enhance the best schedules produced. The F&F approach is a local search procedure that generates compound moves by a strategically abbreviated form of tree search. Computational results carried out on a standard set of 43 benchmark problems show that our F&F algorithm performs more robustly and effectively than a number of leading metaheuristic algorithms and rivals the best of these algorithms.

Suggested Citation

  • Rego, César & Duarte, Renato, 2009. "A filter-and-fan approach to the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 194(3), pages 650-662, May.
    • Handle: RePEc:eee:ejores:v:194:y:2009:i:3:p:650-662
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00002-7
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. F Della Croce & V T'kindt, 2002. "A Recovering Beam Search algorithm for the one-machine dynamic total completion time scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(11), pages 1275-1280, November.
    2. 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.
    3. J. Carlier & E. Pinson, 1989. "An Algorithm for Solving the Job-Shop Problem," Management Science, INFORMS, vol. 35(2), pages 164-176, February.
    4. Sabuncuoglu, I. & Bayiz, M., 1999. "Job shop scheduling with beam search," European Journal of Operational Research, Elsevier, vol. 118(2), pages 390-412, October.
    5. Mutsunori Yagiura & Toshihide Ibaraki & Fred Glover, 2004. "An Ejection Chain Approach for the Generalized Assignment Problem," INFORMS Journal on Computing, INFORMS, vol. 16(2), pages 133-151, May.
    6. 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.
    7. Nuijten, W. P. M. & Aarts, E. H. L., 1996. "A computational study of constraint satisfaction for multiple capacitated job shop scheduling," European Journal of Operational Research, Elsevier, vol. 90(2), pages 269-284, April.
    8. R. J. M. Vaessens & E. H. L. Aarts & J. K. Lenstra, 1996. "Job Shop Scheduling by Local Search," INFORMS Journal on Computing, INFORMS, vol. 8(3), pages 302-317, August.
    9. Egon Balas, 1969. "Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm," Operations Research, INFORMS, vol. 17(6), pages 941-957, December.
    10. Ivens, Philip & Lambrecht, Marc, 1996. "Extending the shifting bottleneck procedure to real-life applications," European Journal of Operational Research, Elsevier, vol. 90(2), pages 252-268, April.
    11. Rego, Cesar, 1998. "Relaxed tours and path ejections for the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 522-538, April.
    12. L Cavique & C Rego & I Themido, 1999. "Subgraph ejection chains and tabu search for the crew scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(6), pages 608-616, June.
    13. Egon Balas & Alkis Vazacopoulos, 1998. "Guided Local Search with Shifting Bottleneck for Job Shop Scheduling," Management Science, INFORMS, vol. 44(2), pages 262-275, February.
    14. 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.
    15. César Rego, 1998. "A Subpath Ejection Method for the Vehicle Routing Problem," Management Science, INFORMS, vol. 44(10), pages 1447-1459, October.
    16. S. Lin & B. W. Kernighan, 1973. "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, INFORMS, vol. 21(2), pages 498-516, April.
    17. 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.
    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 & Song, Shiji & Wu, Cheng, 2013. "A hybrid artificial bee colony algorithm for the job shop scheduling problem," International Journal of Production Economics, Elsevier, vol. 141(1), pages 167-178.
    2. Gromicho, J.A.S. & Hoorn, J.J. van & Timmer, G.T., 2009. "Exponentially better than brute force: solving the jobshop scheduling problem optimally by dynamic programming," Serie Research Memoranda 0056, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
    3. Lixin Tang & Ying Meng & Zhi-Long Chen & Jiyin Liu, 2016. "Coil Batching to Improve Productivity and Energy Utilization in Steel Production," Manufacturing & Service Operations Management, INFORMS, vol. 18(2), pages 262-279, May.
    4. Shahed Mahmud & Ripon K. Chakrabortty & Alireza Abbasi & Michael J. Ryan, 2022. "Switching strategy-based hybrid evolutionary algorithms for job shop scheduling problems," Journal of Intelligent Manufacturing, Springer, vol. 33(7), pages 1939-1966, October.
    5. César Rego & Fred Glover, 2010. "Ejection chain and filter-and-fan methods in combinatorial optimization," Annals of Operations Research, Springer, vol. 175(1), pages 77-105, March.
    6. Jens Heger & Jürgen Branke & Torsten Hildebrandt & Bernd Scholz-Reiter, 2016. "Dynamic adjustment of dispatching rule parameters in flow shops with sequence-dependent set-up times," International Journal of Production Research, Taylor & Francis Journals, vol. 54(22), pages 6812-6824, November.

    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. César Rego & Fred Glover, 2010. "Ejection chain and filter-and-fan methods in combinatorial optimization," Annals of Operations Research, Springer, vol. 175(1), pages 77-105, March.
    2. 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.
    3. 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.
    4. Pezzella, Ferdinando & Merelli, Emanuela, 2000. "A tabu search method guided by shifting bottleneck for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 120(2), pages 297-310, January.
    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. 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.
    7. Bürgy, Reinhard & Bülbül, Kerem, 2018. "The job shop scheduling problem with convex costs," European Journal of Operational Research, Elsevier, vol. 268(1), pages 82-100.
    8. Blazewicz, Jacek & Domschke, Wolfgang & Pesch, Erwin, 1996. "The job shop scheduling problem: Conventional and new solution techniques," European Journal of Operational Research, Elsevier, vol. 93(1), pages 1-33, August.
    9. Da Col, Giacomo & Teppan, Erich C., 2022. "Industrial-size job shop scheduling with constraint programming," Operations Research Perspectives, Elsevier, vol. 9(C).
    10. Mascis, Alessandro & Pacciarelli, Dario, 2002. "Job-shop scheduling with blocking and no-wait constraints," European Journal of Operational Research, Elsevier, vol. 143(3), pages 498-517, December.
    11. Hamed Piroozfard & Kuan Yew Wong & Adnan Hassan, 2016. "A Hybrid Genetic Algorithm with a Knowledge-Based Operator for Solving the Job Shop Scheduling Problems," Journal of Optimization, Hindawi, vol. 2016, pages 1-13, April.
    12. Chen, Haoxun & Luh, Peter B., 2003. "An alternative framework to Lagrangian relaxation approach for job shop scheduling," European Journal of Operational Research, Elsevier, vol. 149(3), pages 499-512, September.
    13. El-Bouri, A. & Azizi, N. & Zolfaghari, S., 2007. "A comparative study of a new heuristic based on adaptive memory programming and simulated annealing: The case of job shop scheduling," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1894-1910, March.
    14. Tarantilis, C. D. & Kiranoudis, C. T., 2002. "A list-based threshold accepting method for job shop scheduling problems," International Journal of Production Economics, Elsevier, vol. 77(2), pages 159-171, May.
    15. Hosseini, Amir & Otto, Alena & Pesch, Erwin, 2024. "Scheduling in manufacturing with transportation: Classification and solution techniques," European Journal of Operational Research, Elsevier, vol. 315(3), pages 821-843.
    16. 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.
    17. Dauzère-Pérès, Stéphane & Ding, Junwen & Shen, Liji & Tamssaouet, Karim, 2024. "The flexible job shop scheduling problem: A review," European Journal of Operational Research, Elsevier, vol. 314(2), pages 409-432.
    18. Steinhofel, K. & Albrecht, A. & Wong, C. K., 1999. "Two simulated annealing-based heuristics for the job shop scheduling problem," European Journal of Operational Research, Elsevier, vol. 118(3), pages 524-548, November.
    19. 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.
    20. 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.

    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:eee:ejores:v:194:y:2009:i:3:p:650-662. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.