A joint order acceptance and scheduling problem with earliness and tardiness penalties considering overtime
- PDF / 779,638 Bytes
- 20 Pages / 595.276 x 790.866 pts Page_size
- 44 Downloads / 181 Views
A joint order acceptance and scheduling problem with earliness and tardiness penalties considering overtime Xin Li1 · José A. Ventura1
· Kevin A. Bunn1
Accepted: 24 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper considers a joint order acceptance and scheduling problem under a general scenario. A manufacturer receives multiple orders with a given revenue, processing time, release date, due date, deadline, and earliness and tardiness penalties. The manufacturer can be seen as a single-machine system. Due to limited capacity, the manufacturer cannot process every order and needs to determine the optimal set of accepted orders and corresponding production schedule such that the total profit is maximized. The manufacturer can extend its capacity with overtime by paying an additional cost. A time-indexed formulation is presented to model the problem. Two exact algorithms are proposed. The first algorithm, denoted by DPIA-GR, is a dynamic programming (DP)-based algorithm that starts by solving a relaxed version of the original model and successively recovers the relaxed constraint until an optimal solution to the original problem is achieved. The second algorithm, denoted by DPIA-LRGR, improves DPIA-GR by incorporating Lagrangian relaxation (LR). The subgradient method is employed to find the optimal Lagrangian multipliers. The relaxed model in DPIA-GR and the LR model in DPIA-LRGR can be represented using a weighted di-graph. Both algorithms are equivalent to finding the longest path in the graph and applying a graph reduction strategy to prevent unnecessary computational time and memory usage. A genetic algorithm (GA) is also proposed to solve large-scale versions of the problem. Numerical experiments show that both DPIA-GR and DPIA-LRGR solve the problem efficiently and outperform CPLEX and GA, but DPIA-LRGR offers better performance. Keywords Order acceptance · Single-machine scheduling · Earliness and tardiness penalties · Overtime · Dynamic programming · Lagrangian relaxation · Genetic algorithm
1 Introduction Make-to-order (MTO) as a pull-type production strategy has gained considerable popularity in the past decades, which stems from the increasing demand for product variety and customization in today’s market. On the one hand, manufacturers employing MTO benefit from high flexibility and thus can handle a wide variety of product specifications and avoid unnecessary inventory. On the other hand, MTO manufacturers risk insufficient capacity, especially when a spike in demand occurs. This can lead to delays in order delivery time or even order rejections which can result in a decline in customer satisfaction. In such a situation, an MTO manufac-
B 1
José A. Ventura [email protected] Harold and Inge Marcus Department of Industrial and Manufacturing Engineering, The Pennsylvania State University, University Park, PA 16802, USA
turer needs to determine which orders to accept to achieve a high overall revenue; process the orders by following a good schedule, so
Data Loading...
