UNIGE document Scientific Article
previous document  unige:91048  next document
add to browser collection

Order acceptance and scheduling with earliness and tardiness penalties

Widmer, Marino
Published in Journal of Heuristics. 2016, vol. 22, no. 6, p. 849–890
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 (OAS) 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 SchedulingEarlinessTardinessOrder acceptanceMetaheuristic
Full text
Article (Author postprint) (349 Kb) - document accessible for UNIGE members only Limited access to UNIGE
(ISO format)
THEVENIN, Simon, ZUFFEREY, Nicolas, WIDMER, Marino. Order acceptance and scheduling with earliness and tardiness penalties. In: Journal of Heuristics, 2016, vol. 22, n° 6, p. 849–890. https://archive-ouverte.unige.ch/unige:91048

137 hits

0 download


Deposited on : 2017-01-13

Export document
Format :
Citation style :