A property-based hybrid genetic algorithm and tabu search for solving order acceptance and scheduling problem with trapezoidal penalty membership function

To improve the profitability and customer satisfaction, in make-to-order environment, manufacturers need to simultaneously consider which orders should be accepted and how to arrange these accepted orders for production, i.e., order acceptance and scheduling (OAS) problem. In practice, orders are often expected to be completed in a certain time interval, but the existing OAS-related studies mainly focus on the hard due date. Therefore, this study is dedicated to solving a single-machine OAS problem that considers the earliness/tardiness penalty under the common due window to maximize the total net profit (TNP), and the main innovative works are described as follows: (1) a trapezoidal earliness/tardiness penalty membership function under the common due window is designed, and a mathematical model is established to characterize the concerned problem; (2) six problem-specific properties are derived for determining which orders to be accepted or rejected, arranging the processing sequence and deciding the start processing time for these accepted orders; and (3) an effective property-based hybrid algorithm (GATS-SSRIR) is designed to deal with the concerned problem, which hybridizes the genetic algorithm, tabu search and six problem-specific properties. In numerical experiments, Taguchi method is first employed to optimize the parameter setting of GATS-SSRIR under different initialization methods. Second, the effectiveness of the proposed problem-specific properties is verified by comparing with other strategies, and the average improvement is 45.3%. Next, the superiority of the proposed GATS-SSRIR algorithm is demonstrated by algorithm comparison, and the average improvement is 67.3%. Finally, a sensitivity analysis on the common due window is performed. To sum up, the proposed problem properties and GATS-SSRIR algorithm are efficient and benefit, and the length of due window has a significant impact on the TNP.

Automated summary

To maximize profitability and customer satisfaction, this study focuses on the order acceptance and scheduling (OAS) problem in a make-to-order environment. A mathematical model is established to consider earliness/tardiness penalty under a common due window and maximize total net profit (TNP). Problem-specific properties are derived to determine which orders to accept and the processing sequence and start processing time for accepted orders. An efficient hybrid algorithm (GATS-SSRIR) is designed, combining genetic algorithm, tabu search, and problem-specific properties. Numerical experiments validate the effectiveness of the proposed properties and the superiority of the GATS-SSRIR algorithm, with average improvements of 45.3% and 67.3% respectively. Sensitivity analysis reveals the significant impact of the due window on TNP.