Order acceptance and scheduling with earliness and tardiness penalties

Simon Thevenin (), Nicolas Zufferey () and Marino Widmer ()
Additional contact information
Simon Thevenin: University of Geneva
Nicolas Zufferey: University of Geneva
Marino Widmer: University of Fribourg

Journal of Heuristics, 2016, vol. 22, issue 6, No 3, 849-890

Abstract: Abstract This paper addresses a production scheduling problem in a single-machine environment, where a job can be either early, on time, late, or rejected. In order acceptance and scheduling contexts, it is assumed that the production capacity of a company is overloaded. The problem is therefore to decide which orders to accept and how to sequence their production. In contrast with the existing literature, the considered problem jointly takes into account the following features: earliness and tardiness penalties (which can be linear or quadratic), sequence-dependent setup times and costs, rejection penalties, and the possibility of having idle times. The practical relevance of this new NP-hard problem is discussed and various solution methods are proposed, ranging from a basic greedy algorithm to refined metaheuristics (e.g., tabu search, the adaptive memory algorithm, population-based approaches loosely inspired on ant algorithms). The methods are compared for instances with various structures containing up to 200 jobs. For small linear instances, the metaheuristics are favorably compared with an exact formulation using CPLEX 12.2. Managerial insights and recommendations are finally given.

Keywords: Scheduling; Earliness; Tardiness; Order acceptance; Metaheuristics (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-016-9321-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:22:y:2016:i:6:d:10.1007_s10732-016-9321-x

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-016-9321-x

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().