ITEM METADATA RECORD
Title: Order acceptance and scheduling in a single-machine environment: exact and heuristic algorithms
Authors: Talla Nobibon, Fabrice
Herbots, Jada
Leus, Roel
Issue Date: Feb-2009
Publisher: K.U.Leuven - Faculty of Business and Economics
Series Title: FBE Research Report KBI_0904 pages:1-28
Abstract: In this paper, we develop exact and heuristic algorithms for the order acceptance and scheduling problem in a single-machine environment. We consider the case where a
pool consisting of firm planned orders as well as potential orders is available from which an over-demanded company can select. The capacity available for processing the accepted orders is limited and orders are characterized by known processing times, delivery dates, revenues and the weight representing a penalty per unit-time delay beyond the delivery date promised to the customer. We prove the non-approximability of the problem and give two linear formulations that we solve with CPLEX. We devise two exact branch-and-bound procedures able to solve problem instances of practical dimensions. For the solution of large instances, we propose six heuristics. We provide a comparison and comments on the efficiency and quality of the results obtained using both the exact and heuristic algorithms, including the solution of the linear formulations using CPLEX.
Publication status: published
KU Leuven publication type: IR
Appears in Collections:Research Center for Operations Research and Business Statistics (ORSTAT), Leuven
Research Center for Operations Management, Leuven

Files in This Item:
File Description Status SizeFormat
KBI_0904.pdfOrder acceptance and scheduling in a single-machine environment: exact and heuristic algorithms Published 431KbAdobe PDFView/Open

 


All items in Lirias are protected by copyright, with all rights reserved.