Maximizing the profit in customer’s order acceptance and scheduling problem with weighted tardiness penalty

The customer’s order acceptance and scheduling problem in a single machine environment has long been an appealing research subject. In this paper, a situation where a pool of customers exists and each customer tends to place all his orders to a single company is addressed. Hence, the customer’s orders will be entirely either accepted or rejected. In this work, decisions on rejection or acceptance of customers and sequencing of the accepted orders are simultaneously considered. The goal is to maximize the total net profit obtained from accepted orders revenues contributed by tardiness penalty. In response to the computational complexity of the problem, a heuristic algorithm and two optimal branch and bound procedures with upper bound, lower bound, and dominance rules are developed. Computational results demonstrate that the proposed methods perform well in a timely manner.