Order acceptance with weighted tardiness

Over the past decade the strategic importance of order acceptance has been widely recognized in practice as well as academic research. This paper examines order acceptance decisions when capacity is limited, customers receive a discount for late delivery, but early delivery is neither penalized nor rewarded. We model a manufacturing facility that considers a pool of orders, and chooses for processing the subset that results in the highest profit. We present several solution methods, beginning with a straightforward application of an approach which separates sequencing and job acceptance. We then develop an optimal branch-and-bound procedure that uses a linear (integer) relaxation for bounding and performs the sequencing and job acceptance decisions jointly. We develop a variety of fast and high-quality heuristics based on this approach. For small problems, beam search runs almost 20 times faster than the benchmark, with a high degree of accuracy, and a branch-and-bound heuristic using Vogel's method for bounding is over 100 times faster with very high accuracy. For larger problems, a myopic heuristic based on the relaxation runs 2000 times faster than the beam-search benchmark, with comparable accuracy.