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

Hyper-heuristic approaches for the response time variability problem

Author

Listed:
  • García-Villoria, Alberto
  • Salhi, Said
  • Corominas, Albert
  • Pastor, Rafael

Abstract

We propose two classes for the implementation of hyper-heuristic algorithms. The first is based on constructive heuristics, whereas the second uses improvement methods. Within the latter class, a general framework is designed for the use of local search procedures and metaheuristics as low-level heuristics. A dynamic scheme to guide the use of these approaches is also devised. These ideas are tested on an NP-hard scheduling problem known as the response time variability problem (RTVP). An intensive computational experiment shows, especially in the second class where the new best results are found, the effectiveness of the proposed hyper-heuristics.

Suggested Citation

  • García-Villoria, Alberto & Salhi, Said & Corominas, Albert & Pastor, Rafael, 2011. "Hyper-heuristic approaches for the response time variability problem," European Journal of Operational Research, Elsevier, vol. 211(1), pages 160-169, May.
    • Handle: RePEc:eee:ejores:v:211:y:2011:i:1:p:160-169
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00841-6
    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. R Bai & E K Burke & G Kendall, 2008. "Heuristic, meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(10), pages 1387-1397, October.
    2. Corominas, Albert & Kubiak, Wieslaw & Pastor, Rafael, 2010. "Mathematical programming modeling of the Response Time Variability Problem," European Journal of Operational Research, Elsevier, vol. 200(2), pages 347-357, January.
    3. M J Brusco, 2008. "Scheduling advertising slots for television," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(10), pages 1363-1372, October.
    4. Ho, Nhu Binh & Tay, Joc Cing & Lai, Edmund M.-K., 2007. "An effective architecture for learning and evolving flexible job-shop schedules," European Journal of Operational Research, Elsevier, vol. 179(2), pages 316-333, June.
    5. Salhi, S. & Sari, M., 1997. "A multi-level composite heuristic for the multi-depot vehicle fleet mix problem," European Journal of Operational Research, Elsevier, vol. 103(1), pages 95-112, November.
    6. John Miltenburg, 1989. "Level Schedules for Mixed-Model Assembly Lines in Just-In-Time Production Systems," Management Science, INFORMS, vol. 35(2), pages 192-207, February.
    7. Belarmino Adenso-Díaz & Manuel Laguna, 2006. "Fine-Tuning of Algorithms Using Fractional Experimental Designs and Local Search," Operations Research, INFORMS, vol. 54(1), pages 99-114, February.
    8. Dowsland, Kathryn A. & Soubeiga, Eric & Burke, Edmund, 2007. "A simulated annealing based hyperheuristic for determining shipper sizes for storage and transportation," European Journal of Operational Research, Elsevier, vol. 179(3), pages 759-774, June.
    9. Qu, Rong & Burke, Edmund K. & McCollum, Barry, 2009. "Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problems," European Journal of Operational Research, Elsevier, vol. 198(2), pages 392-404, October.
    10. Srinivas Bollapragada & Michael R. Bussieck & Suman Mallik, 2004. "Scheduling Commercial Videotapes in Broadcast Television," Operations Research, INFORMS, vol. 52(5), pages 679-689, October.
    11. Kubiak, Wieslaw, 1993. "Minimizing variation of production rates in just-in-time systems: A survey," European Journal of Operational Research, Elsevier, vol. 66(3), pages 259-271, May.
    12. Alberto Garcia-Villoria & Albert Corominas & Rafael Pastor, 2010. "Solving the response time variability problem by means of the cross-entropy method," International Journal of Manufacturing Technology and Management, Inderscience Enterprises Ltd, vol. 20(1/2/3/4), pages 316-330.
    13. Burke, Edmund K. & McCollum, Barry & Meisels, Amnon & Petrovic, Sanja & Qu, Rong, 2007. "A graph-based hyper-heuristic for educational timetabling problems," European Journal of Operational Research, Elsevier, vol. 176(1), pages 177-192, January.
    14. García-Villoria, Alberto & Pastor, Rafael, 2010. "Solving the response time variability problem by means of a genetic algorithm," European Journal of Operational Research, Elsevier, vol. 202(2), pages 320-327, April.
    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. Kheiri, Ahmed & Özcan, Ender, 2016. "An iterated multi-stage selection hyper-heuristic," European Journal of Operational Research, Elsevier, vol. 250(1), pages 77-90.

    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. Albert Corominas & Alberto García-Villoria & Rafael Pastor, 2013. "Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(2), pages 296-312, July.
    2. García-Villoria, Alberto & Pastor, Rafael, 2010. "Solving the response time variability problem by means of a genetic algorithm," European Journal of Operational Research, Elsevier, vol. 202(2), pages 320-327, April.
    3. Corominas, Albert & Kubiak, Wieslaw & Pastor, Rafael, 2010. "Mathematical programming modeling of the Response Time Variability Problem," European Journal of Operational Research, Elsevier, vol. 200(2), pages 347-357, January.
    4. R Bai & E K Burke & G Kendall, 2008. "Heuristic, meta-heuristic and hyper-heuristic approaches for fresh produce inventory control and shelf space allocation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(10), pages 1387-1397, October.
    5. R Qu & E K Burke, 2009. "Hybridizations within a graph-based hyper-heuristic framework for university timetabling problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1273-1285, September.
    6. Ioanna Makarouni & John Psarras & Eleftherios Siskos, 2015. "Interactive bicriterion decision support for a large scale industrial scheduling system," Annals of Operations Research, Springer, vol. 227(1), pages 45-61, April.
    7. Giovanni Giallombardo & Houyuan Jiang & Giovanna Miglionico, 2016. "New Formulations for the Conflict Resolution Problem in the Scheduling of Television Commercials," Operations Research, INFORMS, vol. 64(4), pages 838-848, August.
    8. Mohammed Al-Betar & Ahamad Khader & Iyad Doush, 2014. "Memetic techniques for examination timetabling," Annals of Operations Research, Springer, vol. 218(1), pages 23-50, July.
    9. M J Brusco, 2008. "Scheduling advertising slots for television," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(10), pages 1363-1372, October.
    10. Steiner, George & Yeomans, Julian Scott, 1996. "Optimal level schedules in mixed-model, multi-level JIT assembly systems with pegging," European Journal of Operational Research, Elsevier, vol. 95(1), pages 38-52, November.
    11. Drexl, Andreas & Kimms, Alf, 1999. "Belastungsorientierte Just-in-Time Variantenfließfertigung," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 502, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    12. Caridi, Maria & Sianesi, Andrea, 2000. "Multi-agent systems in production planning and control: An application to the scheduling of mixed-model assembly lines," International Journal of Production Economics, Elsevier, vol. 68(1), pages 29-42, October.
    13. Boysen, Nils & Fliedner, Malte & Scholl, Armin, 2009. "Sequencing mixed-model assembly lines: Survey, classification and model critique," European Journal of Operational Research, Elsevier, vol. 192(2), pages 349-373, January.
    14. Boysen, Nils & Fliedner, Malte & Scholl, Armin, 2009. "The product rate variation problem and its relevance in real world mixed-model assembly lines," European Journal of Operational Research, Elsevier, vol. 197(2), pages 818-824, September.
    15. Shinjini Pandey & Goutam Dutta & Harit Joshi, 2017. "Survey on Revenue Management in Media and Broadcasting," Interfaces, INFORMS, vol. 47(3), pages 195-213, June.
    16. Giovanni Giallombardo & Giovanna Miglionico & Houyuan Jiang, 2015. "New Reformulations for the Conflict Resolution Problem in the Scheduling of Television Commercials," Working Papers 2015/03, Cambridge Judge Business School, University of Cambridge.
    17. Zhu, Jin & Ding, Fong-Yuen, 2000. "A transformed two-stage method for reducing the part-usage variation and a comparison of the product-level and part-level solutions in sequencing mixed-model assembly lines," European Journal of Operational Research, Elsevier, vol. 127(1), pages 203-216, November.
    18. Johannes Vass & Marie-Louise Lackner & Christoph Mrkvicka & Nysret Musliu & Felix Winter, 2022. "Exact and meta-heuristic approaches for the production leveling problem," Journal of Scheduling, Springer, vol. 25(3), pages 339-370, June.
    19. Ding, Fong-Yuen & Zhu, Jin & Sun, Hui, 2006. "Comparing two weighted approaches for sequencing mixed-model assembly lines with multiple objectives," International Journal of Production Economics, Elsevier, vol. 102(1), pages 108-131, July.
    20. José Antonio Carbajal & Wes Chaar, 2017. "Turner Optimizes the Allocation of Audience Deficiency Units," Interfaces, INFORMS, vol. 47(6), pages 518-536, December.

    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:211:y:2011:i:1:p:160-169. 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.