Exact algorithms for a joint order acceptance and scheduling problem

Xin Li and Jose A. Ventura

International Journal of Production Economics, 2020, vol. 223, issue C

Abstract: This paper considers the scenario where a manufacturer receives multiple orders that are characterized by the revenue, processing time, due date, and tardiness penalty per time unit. The manufacturer can be seen as a single-machine system that adopts a make-to-order strategy. Due to the capacity limitation and tardiness penalty, the manufacturer cannot accept all orders. It needs to determine the optimal set of accepted orders and the corresponding production schedule that maximizes the total revenue minus tardiness penalty. Three different mathematical formulations are presented to model the problem: sequential relation-based formulation (SBF), assignment formulation (ASF), and time-index formulation (TIF). The first two models use both continuous and binary variables while (TIF) only uses binary variables but requires order processing times to be integer. Three exact algorithms are proposed to solve the problem. The first algorithm, denoted by DPA, follows a pure dynamic programming (DP) approach. The second algorithm, denoted by DPIA-SR, solves the problem in multiple stages. In the first stage, it solves a relaxed version of (TIF) using DP; then, in the following stages, the relaxed constraint is gradually recovered, and the resulting models are solved using DP until an optimal solution to the original model is found. The results of one stage are used to eliminate unnecessary states in the DP algorithm for the next stage. The third algorithm, denoted by DPIA-LRSR, improves DPIA-SR by incorporating Lagrangian relaxation to achieve higher computational efficiency. The numerical experiment shows that, when using CPLEX to solve the models, (ASF) and (TIF) take much less CPU time than (SBF); the last two algorithms and their variations significantly outperform CPLEX regarding computational time; and DPIA-LRSR shows the highest efficiency.

Keywords: Order acceptance; Single machine scheduling; Tardiness penalty; Exact algorithms; Dynamic programming; Lagrangian relaxation (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0925527319303378
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:proeco:v:223:y:2020:i:c:s0925527319303378

DOI: 10.1016/j.ijpe.2019.107516

Access Statistics for this article

International Journal of Production Economics is currently edited by Stefan Minner

More articles in International Journal of Production Economics from Elsevier
Bibliographic data for series maintained by Catherine Liu ().