Fulltext

Metaheuristics for a scheduling problem with rejection and tardiness penalties

Thevenin, Simon ; Zufferey, Nicolas ; Widmer, Marino

In: Journal of Scheduling, 2015, vol. 18, no. 1, p. 89-105

Zum persönliche Liste hinzufügen
    Titel
    • Metaheuristics for a scheduling problem with rejection and tardiness penalties
    Autor
    • Thevenin, Simon. Geneva School of Economics and Management (GSEM), University of Geneva, Geneva, Switzerland
    • Zufferey, Nicolas. Geneva School of Economics and Management (GSEM), University of Geneva, Geneva, Switzerland
    • Widmer, Marino. DIUF Decision Support & Operations Research, University of Fribourg, Fribourg, Switzerland
    Dokumententyp
    • Postprint
    Sprache
    • Englisch
    Veröffentlicht in
    • Journal of Scheduling, 2015, vol. 18, no. 1, p. 89-105. Springer US; http://www.springer-ny.com
    Andere elektronische Ausgabe
    OAI-PMH-ID
    • oai:doc.rero.ch:332684
    Summary
    In this paper, we consider a single-machine scheduling problem (P) inspired from manufacturing instances. A release date, a deadline, and a regular (i.e., non-decreasing) cost function are associated with each job. The problem takes into account sequence-dependent setup times and setup costs between jobs of different families. Moreover, the company has the possibility to reject some jobs/orders, in which case a penalty (abandon cost) is incurred. Therefore, the problem at hand can be viewed as an order acceptance and scheduling problem. Order acceptance problems have gained interest among the research community over the last decades, particularly in a make-to-order environment. We propose and compare a constructive heuristic, local search methods, and population-based algorithms. Tests are performed on realistic instances and show that the developed metaheuristics significantly outperform the currently available resolution methods for the same problem.