New Formulation for the Single Machine Order Acceptance and Scheduling Problem with Sequence-Dependent Setup Times

In make-to-order production environments, firms may not be able to meet all demands within a given period due to limited capacity. Accepting all orders may cause overloads, delays in order completions and customer dissatisfaction. Therefore, firms try to manage order fulfillment process efficiently. Order acceptance and scheduling problem refers to simultaneously deciding which orders to be selected and how to schedule these selected orders. An extension of this problem including sequence-dependent setup times and release dates was introduced by Oğuz et al. in 2010 and a mathematical formulation was presented. In this paper, we consider the case where there are no release dates for all jobs.We develop a new mathematical formulation with O(n2) binary variables and O(n2) constraints and conduct a detailed computational analysis with CPLEX 12.4 by solving benchmark instances proposed by Cesaret et al. (2012). Reduced formulation of Oğuz et al. (2010) can solve the test problems optimally up to 10 jobs within given time limit. Our proposed formulation can solve all problems optimally up to 100 jobs within the same time limit. We observe that our formulation is extremely faster than the existing one and can solve small and moderate size real-life problems to optimality