Order acceptance and scheduling decisions in make-to-order systems

We examine simultaneous order acceptance and scheduling decisions where the orders are defined by their release dates, due dates, deadlines, processing times, sequence dependent setup times and revenues in a single machine environment. The objective is to maximize total revenue, where the revenue from an order is a function of its tardiness and deadline. We give an MILP formulation which can be solved to optimality up to 15 orders. We develop three heuristic algorithms to solve large sized problems. Computational tests indicate that the proposed algorithms are both computationally efficient and effective even for instances up to 300 orders.